Appendix: Tridiagonal Matrix Algorithm

Summary

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. Consider a tridiagonal system of N equations with N unknowns, u1, u2, u3,… u_N as follows:

A standard method for solving a system of linear, algebraic equations is Gaussian elimination. Thomas’ algorithm, also called the tridiagonal matrix algorithm (TDMA) is essentially a shortened variant of the Gaussian elimination method to solve the tridiagonal system of equations.

The i^th equation in the system may be written as

where a₁ = 0 and b_N = 0. Looking at the system of equations, we see that the i^th unknown can be expressed in terms of (i+1)^th unknowns. That is,

where P_i and Q_i are constants. Note that if all the equations in the system are expressed in this fashion, the coefficient matrix of the system would transform to upper triangular matrix.

To determine the constants P_i and Q_i, we plug Equation (A.4) in (A.2) to yield

These are the recurring relations for the constants P and Q. It shows that P_i can be calculated if P_i-1 is known. To start the computation, we use the fact that a₁ = 0. Now, P₁ and Q₁ can be easily calculated because terms involving P₀ and Q₀ vanish. Therefore,

Once the values of P₁ and Q₁ are known, we can use the recurring expressions for P_i and Q_i for all values of i.

To start the back substitution, we use the fact that b_N = 0. As a consequence, from Equation (A.6), we have P_N = 0. Therefore,

Once the value of uN is known, we use Equation (A.3) to obtain u_N-1, u_N-2,…u1.