# Tridiagonal matrix algorithm - TDMA (Thomas algorithm)

(Difference between revisions)
 Revision as of 20:43, 15 December 2005 (view source)Tsaad (Talk | contribs) (towards a uniform notation for linear systems : A*Phi = B)← Older edit Revision as of 23:01, 18 December 2005 (view source)Jasond (Talk | contribs) m (→Introduction)Newer edit → Line 1: Line 1: == Introduction == == Introduction == - 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 Gaussian 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 discretization of 1D problems. + instead of $O(n^3)$. Example of such matrices are matrices arising from discretization of 1D problems. We can write the tri-diagonal system in the form:
We can write the tri-diagonal system in the form:
:$:[itex] - a_i \phi_{i - 1} + b_i \phi_i + c_i \phi_{i + 1} = d_i + a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i$
[/itex]
Where $a_1 = 0$ and $c_n = 0$
Where $a_1 = 0$ and $c_n = 0$

## Introduction

The Thomas Algorithm is a special form of Gaussian 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(n^3)$. Example of such matrices are matrices arising from discretization 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
$\phi_n = {{d_n^' } \over {b_n }}$
for k := n-1 stepdown until 1 do
$\phi_k = {{d_k^' - c_k \phi_{k + 1} } \over {b_k }}$
end loop (k)

## References

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