Tridiagonal matrix algorithm - TDMA (Thomas algorithm)
From CFD-Wiki
(Difference between revisions)
m (Thomas algorithm moved to Tridiagonal matrix algorithm - TDMA (Thomas algorithm)) |
(towards a uniform notation for linear systems : A*Phi = B) |
||
| Line 2: | Line 2: | ||
The Thomas Algorithm is a special form of Gauss elimination that can be used to solve tridiagonal | The Thomas Algorithm is a special form of Gauss elimination that can be used to solve tridiagonal | ||
systems of equations. When the matrix is tridiagonal, the solution can be obtained in O(n) operations, | systems of equations. When the matrix is tridiagonal, the solution can be obtained in O(n) operations, | ||
| - | instead of O(n3/3). Example of such matrices are matrices arising from | + | instead of O(n3/3). Example of such matrices are matrices arising from discretization of 1D problems. |
We can write the tri-diagonal system in the form: <br> | We can write the tri-diagonal system in the form: <br> | ||
:<math> | :<math> | ||
| - | a_i | + | a_i \phi_{i - 1} + b_i \phi_i + c_i \phi_{i + 1} = d_i |
</math> <br> | </math> <br> | ||
Where <math> a_1 = 0 </math> and <math> c_n = 0 </math> <br> | Where <math> a_1 = 0 </math> and <math> c_n = 0 </math> <br> | ||
| Line 17: | Line 17: | ||
: end loop (k) | : end loop (k) | ||
: then <br> | : then <br> | ||
| - | :: <math> | + | :: <math> \phi_n = {{d_n^' } \over {b_n }} </math> <br> |
: for k := n-1 stepdown until 1 do <br> | : for k := n-1 stepdown until 1 do <br> | ||
| - | :: <math> | + | :: <math> \phi_k = {{d_k^' - c_k \phi_{k + 1} } \over {b_k }} </math> <br> |
: end loop (k) | : end loop (k) | ||
---- | ---- | ||
Revision as of 20:43, 15 December 2005
Introduction
The Thomas Algorithm is a special form of Gauss elimination that can be used to solve tridiagonal systems of equations. When the matrix is tridiagonal, the solution can be obtained in O(n) operations, instead of O(n3/3). Example of such matrices are matrices arising from discretization of 1D problems.
We can write the tri-diagonal system in the form:
Where 
and 
Algorithm
- for k:= 2 step until n do
-
- end loop (k)
- then
-
- for k := n-1 stepdown until 1 do
-
- end loop (k)
References
- Conte, S.D., and deBoor, C. (1972), Elementary Numerical Analysis, McGraw-Hill, New York..
Return to Numerical Methods
