Thomas algorithm

It is one of the application of Gaussian Elimination in Tridiagonal System of Equations

1. Thomas Algorithm LU Decomposition for Tri-Diagonal Systems S.K.PARIDHI

2. Banded matrix A band matrix is a sparse matrix whose non-zero entries are confined to a diagonal band , comprising the main diagonal and zero or more diagonals on either side.    

3. The matrix can be symmetric, having the same number of sub- and super-diagonals . If a matrix has only one sub- and one super-diagonal , we have a tridiagonal matrix etc. The number of super-diagonals is called the upper bandwidth (two in the example), and the number of sub-diagonals is the lower bandwidth (three in the example). The total number of diagonals, six in the example, is the bandwidth. Banded matrix

4. What is a TriDiagonal Matrix…?? A tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal , the first diagonal below this , and the first diagonal above the main diagonal . Considering a 4 X 4 Matrix    

5. Tridiagonal Matrix Algorithm Thomas’ algorithm , also called TriDiagonal Matrix Algorithm (TDMA) is essentially the result of applying Gaussian elimination to the tridiagonal system of equations. A system of simultaneous algebraic equations with nonzero coefficients only on the main diagonal , the lower diagonal , and the upper diagonal is called a tridiagonal system of equations .

6. Generalizing Tridiagonal Matrix Consider a tridiagonal system of N equations with N unknowns, as given below:  

7. Generalizing Tridiagonal Matrix The Matrix can be written as Looking at the system of equations, we see that unknown can be expressed as a function of unknown. That is    

8. Lets solve a problem for clear understanding..!! Let us consider the system of equations Matrix form is  

9. STAGE I : Converting Mx = r into Ux =   Row 1 Divide the Equation by in this case = 3 Assuming the coefficient of as and the remaining constants as Now the equations converts to,  

10. After Changing Row 1  

11. Converting Mx = r into Ux =   Row 2 Multiplying (-1) in Row 1 and eliminating Row 2   Row 2 x Row 1 Subtracting Row 2 Subtracting Divide by , Equation becomes  

12. After Changing Row 2  

13. Converting Mx = r into Ux =   Row 3 Multiplying (-1) in Row 1 and eliminating Row 3   Row 3 x Row 2 Subtracting Row 3 Subtracting  

14. After Changing Row 3  

15. STAGE II -> Backward Substitution   Row 2:   Substituting    

16. STAGE II -> Backward Substitution   Row 1:   Substituting    

17. SOLUTION  

18. Why Thomas Algorithm is used ? This type of computation is quick. Tridiagonal system of equations are most common. Even most of them convert the general system of equations to tridiagonal system of equations. It’s importance is clearly visible with a large number of unknowns.

19. Limitations of Thomas Algorithm Algorithm is unstable when = 0 This occurs if the tridiagonal matrix is singular and in some cases non-singular also.   Singular Matrix (Determinant is Zero) (*Square Matrix) (It doesn’t have a Inverse) Non-Singular Matrix (Determinant is Non-Zero) (*Square Matrix) (It has a Inverse)

20. Condition for algorithm to be stable for every i .   What can be done when the algorithm is numerically unstable..?? Pivoting of matrix