Computational Physics - Department of Physics

190 6 Linear Algebra

If the matrixAˆis positive definite or diagonally dominant, one can show that this method
will always converge to the exact solution.
We can demonstrate Jacobi’s method by a 4 × 4 matrix problem. We assume a guess for the
initial vector elements, labeledx(i^0 ). This guess represents our first iteration. The new values
are obtained by substitution

x( 11 )= (b 1 −a 12 x( 20 )−a 13 x( 30 )−a 14 x( 40 ))/a 11

x( 21 )= (b 2 −a 21 x( 10 )−a 23 x( 30 )−a 24 x( 40 ))/a 22

x( 31 )= (b 3 −a 31 x( 10 )−a 32 x( 20 )−a 34 x( 40 ))/a 33

x( 41 )= (b 4 −a 41 x( 10 )−a 42 x( 20 )−a 43 x( 30 ))/a 44 ,

which afterk+ 1 iterations result in

x( 1 k+^1 )= (b 1 −a 12 x( 2 k)−a 13 x( 3 k)−a 14 x( 4 k))/a 11

x( 2 k+^1 )= (b 2 −a 21 x( 1 k)−a 23 x( 3 k)−a 24 x( 4 k))/a 22

x( 3 k+^1 )= (b 3 −a 31 x( 1 k)−a 32 x( 2 k)−a 34 x( 4 k))/a 33

x( 4 k+^1 )= (b 4 −a 41 x( 1 k)−a 42 x( 2 k)−a 43 x( 3 k))/a 44 ,

We can generalize the above equations to

xi(k+^1 )= (bi−

n

∑

j= 1 ,j 6 =i

ai jx(jk))/aii

or in an even more compact form as

x(k+^1 )=Dˆ−^1 (b−(Lˆ+Uˆ)x(k)),

withAˆ=Dˆ+Uˆ+LˆandDˆbeing a diagonal matrix,Uˆan upper triangular matrix andLˆa lower
triangular matrix.

6.6.2 Gauss-Seidel.

Our 4 × 4 matrix problem

x( 1 k+^1 )= (b 1 −a 12 x( 2 k)−a 13 x( 3 k)−a 14 x( 4 k))/a 11

x( 2 k+^1 )= (b 2 −a 21 x( 1 k)−a 23 x( 3 k)−a 24 x( 4 k))/a 22

x( 3 k+^1 )= (b 3 −a 31 x( 1 k)−a 32 x( 2 k)−a 34 x( 4 k))/a 33

x( 4 k+^1 )= (b 4 −a 41 x( 1 k)−a 42 x( 2 k)−a 43 x( 3 k))/a 44 ,

can be rewritten as

x( 1 k+^1 )= (b 1 −a 12 x( 2 k)−a 13 x( 3 k)−a 14 x( 4 k))/a 11

x( 2 k+^1 )= (b 2 −a 21 x( 1 k+^1 )−a 23 x( 3 k)−a 24 x( 4 k))/a 22

x( 3 k+^1 )= (b 3 −a 31 x( 1 k+^1 )−a 32 x( 2 k+^1 )−a 34 x( 4 k))/a 33

x( 4 k+^1 )= (b 4 −a 41 x( 1 k+^1 )−a 42 x( 2 k+^1 )−a 43 x( 3 k+^1 ))/a 44 ,