Chapter 7 9/18/2013 Prof. R.-T.

Wang

Chapter 7 Iterative methods


x  {x1.....xn }T

  n
l2 norm of x is defined as x2 x
i 1
2
i

 
l norm of x is defined as x 
 max xi
1 i  n

     
x  y 2  ( x  y )T ( x  y )

  n
Natural matrix norm A  max
 Ax , Ax  { aij x j }
x 1
j 1
n
l2 norm of matrix A is A   max  aij
1i  n
j 1


l norm of A is A 2  max
 Ax 2
x 2 1

If {x ( k ) }k 1  x or lim xi( k )  xi or lim x ( k )  x   0

k  k 

then {x ( k ) }k 1 is convergent to x  .

The eigenvalue  and its corresponding eigenvector x of the matrix A

is Ax   x .

The spectral radius  ( A) of a matrix A is defined by

 ( A)  max  .

Properties:

1. A 2  [  ( AT A)]1/ 2

2.  ( A) for any natural norm


A is a convergent matrix iff lim An  0 , or  ( A)  1 or lim An x  0
n  n 


The problem Ax  b can be expressed as x  Tx  c

If  (T )  1 , then the iteration x ( k 1)  Tx ( k )  c converges.

1
Chapter 7 9/18/2013 Prof. R.-T. Wang

     
x ( k 1)  T (Tx ( k 1)  c )  c  T 2 x ( k 1)  (T  I )c
 
 T k x (0)  (T k 1  ....  T 0 )c

lim T k  O , S k  T k 1  ....  T 0 , TSk  T k  ....  T ,

k 

S k  TSk  ( I  T ) S k  I  T k , S k  ( I  T ) 1  ( I  T ) 1T k

 
lim S k  ( I  T ) 1 , lim x ( k 1)  ( I  T ) 1 c .
k  k 

Jacobi iteration

Express A  D  L  U , then Dx  ( L  U ) x  b or
    
x   D 1 ( L  U ) x  D 1b  Tx  c
n aij bi
xi( k 1)   x (jk 1) 
j i aii aii

Gauss-Seidel method
       
( D  L) x  Ux  b or x  ( D  L) 1Ux  ( D  L) 1 b  Tg x  c

SOR (successive over-relaxation) method

        
Dx   ( D  L  U ) x  Dx  b , Dx   ( D  L) x  Dx  Ux  b

  
( D   L) x  [(1   ) D  U ]x  b
    
x  ( D   L) 1[(1   ) D  U ]x   ( D   L) 1 b  T x  c

Iterative Refinement
 (0)  (0) 
Suppose x to be an approximate solution of Ax  b .
 (1)   (0)  (1)
The error b  b  Ax . Let x be an approximate solution of
 (1)  (1)     (0)  (1)
Ax  b . Then the solution of Ax  b is x  x  x .

§ The conjugate gradient method


The solution x of Ax  b is the optimal solution of

2
Chapter 7 9/18/2013 Prof. R.-T. Wang

 1 T  T 
min
 g ( x )  min(
 x Ax  x b ) , A  AT .
x x 2

Define h(t )  g ( x  tv )

How to find t and v such that g ( x  tv )  g ( x )

1       
h(t )  ( x  tv )T A( x  tv )  ( x  tv )T b
2
1       1  
 ( x T Ax  x T b )  tv T ( Ax  b )  t 2 v T Av
2 2
    1  
 g ( x )  tv T ( Ax  b )  t 2 v T Av
2
   ˆT 
0  h(tˆ)  v T ( Ax  b )  tv Av or

        
tˆ  v T ( Ax  b ) / v T Av  (v , b  Ax ) /(v , Av )
   2
 1 ( v , Ax  b ) 
h(tˆ)  g ( x )     g ( x)
2 (v , Av )
Given x (1)
     
v ( k )  b  Ax ( k ) , tk  (v ( k ) , v ( k ) ) /(v ( k ) , Av ( k ) ) ,

  
x ( k 1)  x ( k )  tk v ( k ) .

    1  
 g ( x )  tv T ( Ax  b )  t 2 v T Av
2
   ˆT 
0  h(tˆ)  v T ( Ax  b )  tv Av or

        
tˆ  v T ( Ax  b ) / v T Av  (v , b  Ax ) /(v , Av )

Given x (1) and v (1)

        
tk  (v ( k ) , b  Ax ( k ) ) /(v ( k ) , Av ( k ) ) , x ( k )  x ( k 1)  tk v ( k ) , v ( k 1)  b  Ax ( k )


Ex. The vector x  {2 1}T is the root of
  2 1  5 
Ax  b , A   , b 
1 2  4 
 (0)  (1) 5   2 1  1 2   (1)T  (1)  (1) 
Try x  {1 1}T , v        , v v 5, v Av  14
4  1 2  1 1 

3
Chapter 7 9/18/2013 Prof. R.-T. Wang

T   10 
v v 5  (1)  (0)  (1) 1 5 2  114 
t1  T   , x  x  t1 v         
v Av 14 1 14 1  1 1 
 14 
   (1) 17    (0)
x x  1 x  x
14
HW7
Solve the problem
4 x1  x2  x4  0
 x1  4 x2  x3  x5  1
 x2  4 x3  x5  x6  9
 x1  4 x4  x5  x6  4
 x2  x4  4 x5  x6  8
 x3  x5  4 x6  6
by (a) Jacobi method, (b) Gauss-Seidel method, (c) SOR method, and (d) the
conjugate gradient method.