Lab: Steepest Descent Method to Solve System of Equations
by Wei Dai (Oct. 8, 2011)
Objective:
- Provide test case of solving system of equations with steepest descent method, with or without preconditioning.
- 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:
- Read these 3 files and understand the algorithm.
Figure 1. Convergence path of the steeepest descent method.
- Execute test_sd.m and produce above figure.
Figure 2. Convergence path of the preconditioned steeepest descent method.
- Execute test_pre.m and produce above figure.
Figure 3. Convergence path of the steeepest descent method with 2D line search.
- Execute test_2D.m and produce above figure.
Questions:
- Examine the number of iterations required for the steepest descent method and preconditioned steepest descent method, and explain the difference.
- 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.
- 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.)