Numerical Linear Algebra, Conjugate Gradient Method

[hgd7833]

The question is number (38.2) in page 302 in Numerical Linear Algebra (Trefethen & Bau) We have a real symmetric matrix with eigenvalues: 1, 1.01, 1.02,..., 8.98, 8.99, 9.00 and 10, 12, 16, 24.

 

How many steps of the conjugate gradient iteration must you take to reduce the initial error by a factor of 10^6 ??

 

---------------------------------------------------------------------------

 

The answer is easy: The condition number of the matrix is

 

k = lamda max / lamda min = 24/1 = 24.

 

So, 1/10^6 = ||e_n|| / || e_0|| < = 2(sqrt(k)-1/sqrt(k)+1)^n .

 

Solving the equation: We get n>= 35.03 . So, we need at least 36 steps of the CG iteration.

 

 

-------------

 

BUT

another question arises:

 

How does the distribution of the eigenvalues affect the rate

of convergence ??

 

 

In other words, what if the eigenvalues were: 1,2,3,...,24 for example. what does that afect the convergence ?

 

The whole calculations are based on the fact that the condition number k = lamda max / lamda min.

 

It seems to me that the only thing that would affect that are only the maximum and the minimum eigenvalues, NOT all eigenvalues ?

 

which implies that the rate of convergence will not change if we have a different kind of distribution of the eigenvalues.

 

Is this right ? Any ideas ??

 

Thank you

 

 

 

 

 

 

 

 

 

 

 

[imatfaal]

!

Moderator Note

Moved to Homework Help