The Mathematical Garden

Convergence Analysis

Given a square matrix G, we observe that

(In - G)( k å i=0  Gi) = (In-G) (In +G +G2 + ¼+ Gk) = In - Gk+1.

Thus if

lim k ® ¥  Gk = 0

then

lim k ® ¥  k å i=0  Gi = (In -G)-1.

Recall our iterative scheme

x(k+1) = S-1 b - S-1 (A-S) x(k).

Let

G=S-1(S-A)     and     r=S-1b

then we have

x(k+1) = Gk+1x(0) + ( k å i=0  Gi)r.

Hence if

lim k® ¥  Gk+1=0

then

lim k ® ¥  xk+1 = (In-G)-1r = A-1b.

Theorem 4: If

lim k ® ¥  (In- S-1A))k = 0

then the iterative scheme

x(k+1) = S-1b - S-1 (A-S) x(k)

converges to the solution of Ax=b independent of x⁽⁰⁾.

Special Case Analysis

In the following, we give a convergence proof for the Jacobi method for solving the tridiagonal linear system. We need the following interesting result.

Theorem 5: The eigenvalues of the matrix

H = é ê ê ê ê ê ê ê ê ê ë a b 0 c a b ··· ··· ··· c a b 0 c a ù ú ú ú ú ú ú ú ú ú û

is given by

l = a + Ö   bc   cos(  jp n+1 )     for    j=1,2,¼,n.

The proof is as follows.

Let l be an eigenvalue and v=(v₁,v₂,¼,v_n) be its eigenvector. Then from Hv=lv we have n equations as follows:

(a-l)v1 + b v2 = 0 cv1 + (a-l)v2 + bv3 = 0 : : : cvn-1 + (a-l)vn = 0.

This can be summarized as a difference equation:

cvj-1 + (a-l)vj +bvj+1 = 0     for    j=1,2,¼,n

with v₀=v_n+1=0.

By using standard solution for a second order linear difference equation, the solution is given by

vj = am1j + bm2j

where m_i are the distinct roots of the quadratic equation

c+ (a-l)m + bm2 = 0.

We have

0 = a+ b    and     0=am1n+1 + bm2n+1.

Hence we have

(  m1 m2 )n+1 = 1 = ei2jp     and     m1m2=  c b .

Therefore we can solve

m1=   æ Ö  c b   e[(ijp)/(n+1)]     and    m2=   æ Ö  c b   e[(-ijp)/(n+1)].

Since

m1 + m2 =  l-a b

we get

l = a + Ö   bc   ( e[(ijp)/(n+1)] +e[(-ijp)/(n+1)]) = a + 2 Ö   bc   cos(  jp n+1 ).

Hence the result.

For the Jacobi method, we have

G = é ê ê ê ê ê ê ê ê ê ë 0 1/2 0 1/2 0 1/2 ··· ··· ··· 1/2 0 1/2 0 1/2 0 ù ú ú ú ú ú ú ú ú ú û .

From Theorem 5 the eigenvalues of G are given by

lj = cos(  jp n+1 )=1 -2sin2(  jp 2(n+1) ),     j=1,2,¼,n.

We note that |l_j| < 1, so all the eigenvalues of lim_{k ® ¥} G^k are zero. Since G^k are all symmetric, we have

lim k ® ¥  Gk = 0.

Hence the Jacobi matrix is convergent for solving the tridiagonal linear system.