Lab: Steepest Descent Method to Solve System of Equations

by Wei Dai (Oct. 8, 2011)


Objective:

  1. Provide test case of solving system of equations with steepest descent method, with or without preconditioning.
  2. Test 2D line search method.

Introduction:

  • In order to solve a system of equations defining by L=[4 6;2 5;0 3;1 4] and t=[10 7 3 5], a misfit functional is defined as f(x)=0.5*||Lx-t||^2.
  • The solution is found by minimizing the misfit functional. (A solution that minimizes the least-squares errors.)
  • The misfit functional is quadratic, so this is a linear problem.

    Platform:

    Matlab.

    Download:

    Please download these 3 files:test_sd.m,test_pre.m, and test_2D.m.

    Exercises:

    1. Read these 3 files and understand the algorithm.




      Figure 1. Convergence path of the steeepest descent method.
    2. Execute test_sd.m and produce above figure.




      Figure 2. Convergence path of the preconditioned steeepest descent method.
    3. Execute test_pre.m and produce above figure.




      Figure 3. Convergence path of the steeepest descent method with 2D line search.

    4. Execute test_2D.m and produce above figure.

    Questions:

    1. Examine the number of iterations required for the steepest descent method and preconditioned steepest descent method, and explain the difference.
    2. Examine the number of iterations required for the steepest descent method with 2D line search and explain why it only takes one iteration to converge.
    3. Change the code to apply these 3 methods to minimize the Rosenbrock function and produce similar figures. (Note: Minimizing Rosenbrock function is a non-linear problem.)