Tridiagonal matrix algorithm - TDMA (Thomas algorithm)

(Difference between revisions)
 Revision as of 08:24, 27 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Revision as of 06:22, 3 October 2005 (view source)Zxaar (Talk | contribs) Newer edit → Line 26: Line 26: #{{reference-book|author=Conte, S.D., and deBoor, C.|year=1972|title=Elementary Numerical Analysis|rest= McGraw-Hill, New York.}} #{{reference-book|author=Conte, S.D., and deBoor, C.|year=1972|title=Elementary Numerical Analysis|rest= McGraw-Hill, New York.}} + + + ---- + Return to [[Numerical methods | Numerical Methods]]

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 descretisation of 1D problems.

We can write the tri-diagonal system in the form:

$a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i$

Where $a_1 = 0$ and $c_n = 0$

Algorithm

for k:= 2 step until n do
$m = {{a_k } \over {b_{k - 1} }}$
$b_k^' = b_k - mc_{k - 1}$
$d_k^' = d_k - md_{k - 1}$
end loop (k)
then
$x_n = {{d_n^' } \over {b_n }}$
for k := n-1 stepdown until 1 do
$x_k = {{d_k^' - c_k x_{k + 1} } \over {b_k }}$
end loop (k)

References

1. Conte, S.D., and deBoor, C. (1972), Elementary Numerical Analysis, McGraw-Hill, New York..