Scribd
Upload
2K views4 pages

Methods For Solving Tridiagonal System

The document describes methods for solving tridiagonal systems of equations, which frequently arise when solving partial differential equations numerically. It presents Thomas algorithm, a efficient method that takes advantage of the tridiagonal structure. The key steps of Thomas algorithm are outlined, which involve first solving for intermediate vectors u and y, then back-substituting to find the solution vector x. An example 4x4 system is also given and solved using both Thomas algorithm and Gauss-Seidel iteration to compare the approaches.

Uploaded by

Shivam Sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2K views4 pages

Methods For Solving Tridiagonal System

The document describes methods for solving tridiagonal systems of equations, which frequently arise when solving partial differential equations numerically. It presents Thomas algorithm, a efficient method that takes advantage of the tridiagonal structure. The key steps of Thomas algorithm are outlined, which involve first solving for intermediate vectors u and y, then back-substituting to find the solution vector x. An example 4x4 system is also given and solved using both Thomas algorithm and Gauss-Seidel iteration to compare the approaches.

Uploaded by

Shivam Sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Methods for Solving tridiagonal System 

This lecture consists of solution of an important problem arising in many process,


whether we are solving Parabolic or Elliptic PDE . While applying implicit techniques in any
of the method, we usually come across with the coefficient matrix which have many zeros. If
the equations are properly analyzed then usually the coefficient matrix is Tridiagonal. One
can thus reduce the computational efforts by using the specific tridiagonal solvers.

Let a tridiagonal system be given as

 b1 c1 0   0   x1   r1 
a b2 c2   0   x2  r2 
 2
             (6.1)
    
           
 0    an bn   xn  rn 

The total elements of n  n matrix are to be saved where as in this specific algorithm only
(3n-2) locations to be saved. Thus sufficient amount of memory is saved. This saves not
only computational time but also increases computational efficiency. The solution is obtained
in the following steps:

i  u1  b1 , ui  bi 
ai ci 1
, i  2,  , n
ui 1

ii  y1  r1 , yi  ri 
ai yi1
, i  2,  , n
ui1
y c x
iii  xn  yn
, xi  i i i1 , i  n  1,  ,1
un ui

This algorithm is known as Thomos Algorithm and is very efficient for large system of
equations.

1.98  1.01 0 0   x1  0.985


0.98  1.98 1.02
 0   x2   0.01 
Example: 
 0 0.97  1.98 1.03   x3  0.016
    
 0 0 0.96  1.98  x4  1.540 

Solve the above system using Thomos Algorithm & Gauss-Seidel Method and compare the
result.
Solution:
The given problem is of form: AX = B

Now matrix A is Tridiagonal hence applying Thomos Algorithm, we have:

b1  1.98 ; b2  b3  b4  1.98
c1  1.01 ; c2  1.02 ; c3  1.03
a2  0.98 ; a3  0.97 ; a4  0.96
ai ci1
Now, u1  b1 ; ui  bi  , i  2,3,4
ui 1
Hence, u1  1.98 ; u 2  1.4801
; u3  1.3115
; u 4  1.2261
ai yi 1
Now, y1  r1 ; yi  ri  , i  2,3,4
ui 1
Hence, y1  0.985 ; y 2  0.4775
; y 3  0.2980
; y 4  1.3220
y4 yi  ui xi  1
Now, x4  ; xi  , i  3,2,1
u4 ui
Hence, x4  1.0782 ; x3  0.6200
; x2  0.1016
; x1  0.4456

By Gauss-Seidel Method:

The given problem is of form: AX = B

Here A is already diagonally dominant.

1.98 0 0 0 
0.98 - 1.98 0 0 
D+L 
 0 0.97 - 1.98 0 
 
 0 0 0.96 - 1.98

0  1.01 0 0 
0 0 1.02 0 
U 
0 0 0 1.03
 
0 0 0 0 
Gauss-Seidel Iterative Scheme is:

X k 1  HX k  C (6.2)
where, H  D  L  U and C  D  L  B
1 1

 0.5051 0 0 0 
0.2500 - .5051 0 0 
D  L 1   00
0.1225 - .2474 - .5051 0 
 
0.0594 - .1200 - .2449 - .5051 

0 0.5051 0 0 
0 0.2525 0.5152 0 
H 
0 0.1237 0.2524 0.5202
 
0 0.06 0.1224 0.2522

 0.4975 
 0.2412 
C  D  L  B   
1

 0.1106 
 
 .7242 

0 
0 
Let initial vector X 0   
0 
 
0 

Now, by equation 6.2 , we have :


 0.4975   0.6205 
 0.2412   0.3590 
X1    ; X2  
 0.1106   0.2084
   
 0.7242   0.8788

 0.6808   0.6120 
 0.2245   0.1151 
X 
3  ; X 
4 
 0.3548   0.4453
   
 0.9498  0.9937 
 0.4932   0.4766 
 0.0410  0.0625
X 
7  ;X  
8 
  0.5693  0.5864
   
  1.0538    1.0621
 0.4656   0.4585 
 0.0767  0.0861
X9    ; X 10   
 0.5977  0.6051
   
  1.0675    1.0711

Hence,
x1  0.4585
x2  0.0861
x3  0.6051
x4  1.0711

It may be observed from the results that for large systems the Thomos algo. is very efficient.

You might also like