CG -- The Method of Steepest Descent


![Pasted image 20221225215518.png](/img/user/attachment/Pasted image 20221225215518.png)
Whenever you read "residual", think "direction of steepest descent"


  1. Starting from an initial point x0
  2. compute r0=bAx0, which is the direction
  3. Select next point x1=x0=αr0

How to decide r0

Choose the vector which has the minimized increase of f, where the projection on the direction line (r0) is 0

Final procedure

![Pasted image 20221225220257.png](/img/user/attachment/Pasted image 20221225220257.png)


CG -- Eigenvalues (Eigenvectors) and convergency

Several Special cases

We are using the Final procedure.

Special Case 1

If e_(i) is an eigenvector with eigenvalue λ_e
![Pasted image 20221228163248.png](/img/user/attachment/Pasted image 20221228163248.png)


r_(i)=Ae_(i)=λee_(i) from Definitions

It takes only one step to converge to the exact solution

General Formula

If e_(i) is a linear combination of eigenvectors, and if A is symmetric, there exists a set of n orthogonal eigenvectors of A. We have the following:


Special case 2

If e(i) has only one eigenvector component, then convergency is also achieved in one step by choosing α(i)=λe1.

Special case 3

All the eigenvectors have a common eigenvalue λ

General Convergency

We have the formula General Formula


We define energy norm to help


Recall for an arbitrary point p, and the solution point x=A1b, we have


(From Conjugate Gradient >

That is


Thus, minimizing ||e(i)||A is equivalent to minimizing f(x(i))

![500](/img/user/attachment/Pasted image 20221228165621.png)


Recall ξ and λ in General Formula

Express ω as condition number slop (we defined)

Here we only consider n=2
We define

  • the spectral condition number as κ=λ1/λ2>1,
  • The slop of e(i) as μ=ξ2/ξ1

![Pasted image 20221228170942.png](/img/user/attachment/Pasted image 20221228170942.png)

Plotting w.r.t. κ and μ

![Pasted image 20221228171025.png](/img/user/attachment/Pasted image 20221228171025.png)

The worst case is when μ=±κ
That is, the larger its condition numberκ), the slower the convergence of in Steepest Descent.