Thomas Algorithm or Tri-diagonal Matrix Algorithm (TDMA)

Definition

The Thomas Algorithm is used to solve a linear Tridiagonal matrix

We have the system of linear equations

a_{1} x_{1} + c_{1} x_{2} b_{2} x_{1} + a_{2} x_{2} + c_{2} x_{3} b_{n - 1} x_{n - 2} + a_{n - 1} x_{n - 1} + c_{n - 1} x_{n} b_{n} x_{n - 1} + a_{n} x_{n} = b_{1} = b_{2} ⋮ = b_{n - 1} = b_{n}

In Matrix form

a_{1} b_{2} c_{1} a_{2} ⋱ c_{2} ⋱ ⋱ ⋱ ⋱ b_{n} c_{n - 1} a_{n} x_{1} x_{2} x_{3} ⋮ x_{n} = b_{1} b_{2} b_{3} ⋮ b_{n}

If $A$ is the TDM, $x$ is the vector containing the unknowns and $b$ is the vector containing constants, we have

A x = b

We consider the factorization

A = LU

where $L, U \to$ Lower and Upper Triangular Matrix respectively.

L = 1 ℓ_{2} 1 ⋱ ⋱ ⋱ ⋱ ℓ_{n} 1, U = r_{1} s_{1} r_{2} s_{2} ⋱ ⋱ ⋱ s_{n - 1} r_{n}

Then, we need to determine $ℓ_{2}, \dots, ℓ_{n}, r_{1}, \dots, r_{n}$ and $s_{1}, \dots, s_{n - 1}$ .

Given that $r_{i} \neq = 0$ , $i = 1, \dots n - 1$

s_{i} = c_{i} r_{1} = a_{1}

- ℓ_{i} - r_{i} = \frac{b _{i}}{r _{i - 1}} = a_{i} - ℓ_{i} s_{i - 1}