Department of Electrical and Electronic Engineering

Bangladesh University of Engineering and Technology

EEE 424: Numerical Methods Laboratory

Experiment 4# LU Decomposition for Tri-diagonal Matrices
Introduction:
A banded matrix is a square matrix that has all elements equal to zero, other than a band
centered on the main diagonal. Banded systems are frequently encountered in engineering
and scientific practice, e.g. solution of differential equations, cubic splines, etc. Special type
of algorithms can be employed in such cases to take advantage of large number of useless
zeros. Thomas algorithm is used for a special type of banded system – a tridiagonal matrix.
Instead of storing the entire square matrix, only the diagonals are to be stored in a 3-column
matrix. As number of elements in each row is only three, this algorithm will significantly
reduce the number of operations and in turn enhance processing speed.

𝑓1 𝑔1 𝑥1 𝑏1
𝑒2 𝑓2 𝑔2 𝑥2 𝑏2
𝑒3 𝑓3 𝑔3 𝑥3 𝑏3
⋮ = ⋮
⋮ ⋮
𝑒𝑛−1 𝑓𝑛−1 𝑔𝑛−1 𝑥𝑛−1 𝑏𝑛−1
𝑒𝑛 𝑓𝑛
𝑥𝑛 𝑏𝑛

Theory:

To solve a system of equations given by 𝐴𝒙 = 𝒃, first the coefficient matrix is to be

factorized into L and U matrices. Rewriting the equation using 𝐴 = 𝐿𝑈 yields 𝐿𝑈𝒙 = 𝒃.

Using the notation 𝑈𝒙 = 𝒚, the system becomes 𝐿𝒚 = 𝒃, which can be solved for 𝒚 using
forward substitution. Then 𝒙 can be found from 𝑈𝒙 = 𝒚 using backward substitution.

So solving a system using this kind of approach require three steps.

 LU Factorization
 Forward Substitution
 Backward Substitution

The L and U matrices can be stored in a single matrix to reduce the memory storage further.
In Thomas algorithm, the main diagonal with ‘1’s and the lower diagonal constitute the
lower triangular matrix, L and the upper two diagonals form the upper triangular matrix, U.

Let us consider a 3-by-3 square system with non-zero elements on the three diagonal
positions only.

Page 1 of 3
LU Factorization:

𝑓1 𝑔1 1 𝑓1 ′ 𝑔1 ′
𝑒2 𝑓2 𝑔2 = 𝑒2′ 1 𝑓2 ′ 𝑔2 ′
𝑒3 𝑓3 𝑒3 ′ 1 𝑓3 ′

𝑓1 = 𝑓1′ 𝑓1′ = 𝑓1

𝑔1 = 𝑔1′ 𝑔1′ = 𝑔1
In general,
𝑒2 = 𝑒2′ 𝑓1′ 𝑒2
𝑒2′ = ′ 𝑒𝑘
𝑓1
𝑒𝑘 =
𝑓2 = 𝑒2′ 𝑔1′ + 𝑓2 ′ 𝑓𝑘−1
𝑓2′ = 𝑓2 − 𝑒2′ 𝑔1′
𝑔2 = 𝑔2′ 𝑓𝑘 = 𝑓𝑘 − 𝑒𝑘 𝑔𝑘−1
𝑔2′ = 𝑔2
𝑒3 = 𝑒3′ 𝑓2′
𝑒3
𝑒3′ =
𝑓3 = 𝑒3′ 𝑔2′ + 𝑓3 ′ 𝑓2′

𝑓3′ = 𝑓3 − 𝑒3′ 𝑔2′

Forward Substitution:

1 𝑦1 𝑏1
𝑒2 ′ 1 𝑦2 = 𝑏2
𝑒3 ′ 1 𝑦3 𝑏3

𝑦1 = 𝑏1 𝑦1 = 𝑏1 In general,
𝑒2′ 𝑦1 + 𝑦2 = 𝑏2 𝑦2 = 𝑏2 − 𝑒2′ 𝑦1
𝑏𝑘 = 𝑏𝑘 − 𝑒𝑘 𝑏𝑘−1
𝑒3′ 𝑦2 + 𝑦3 = 𝑏3 𝑦3 = 𝑏3 − 𝑒3′ 𝑦2

Backward Substitution:

𝑓1 ′ 𝑔1 ′ 𝑥1 𝑦1
𝑓2 ′ 𝑔2 ′ 𝑥2 = 𝑦2
𝑓3 ′ 𝑥3 𝑦3

𝑦3 In general,
𝑥3 =
𝑓3′
𝑓3′ 𝑥3 = 𝑦3 𝑦𝑘 − 𝑔𝑘 𝑥𝑘+1
𝑥𝑘 =
𝑦2 − 𝑔2′ 𝑥3 𝑓𝑘
𝑓2′ 𝑥2 + 𝑔2′ 𝑥3 = 𝑦2 𝑥2 =
𝑓2′
or
𝑓1′ 𝑥1 + 𝑔1′ 𝑥2 = 𝑦1
𝑦1 − 𝑔1′ 𝑥2
𝑥1 = 𝑏𝑘 − 𝑔𝑘 𝑥𝑘+1
𝑓1′ 𝑏𝑘 =
𝑓𝑘

Page 2 of 3
Pseudocode:
(a) Decomposition
DO FOR k = 2, n
ek = ek/fk-1
fk = fk - ek gk-1
END DO
(b) Forward substitution
DO FOR k = 2, n
bk = bk – ek bk-1
END DO
(c) Back substitution
xn = bn/fn
DO FOR k = n - 1, 1, -1
xk = (bk - gk xk+1)/fk
END DO

Exercise:
Solve the following tridiagonal system with the Thomas algorithm.

2.04 −1 𝑥1 40.8
−1 2.04 −1 𝑥2 0.8
−1 2.04 −1 𝑥3 = 0.8
−1 2.04 𝑥4 200.8

Remarks:
Conventional LU decomposition can be employed to solve banded equations as well. But
they are inefficient for this type of systems, because if pivoting is unnecessary none of the
elements outside the band would change from their original values of zero. Thus,
unnecessary space and time would be expended on the storage and manipulation of these
useless zeros. If it is known beforehand that pivoting is unnecessary, very efficient
algorithms can be developed that do not involve the zero elements outside the band.

Thomas algorithm requires less computer memory compared to other LU decomposition

techniques. The n x n coefficient matrix can be stored in an n x 3 matrix. After the
operations are done, the coefficient matrix gets converted to the [L\U] matrix and the right-
side column vector becomes the solution vector.

References:
1. Numerical Methods for Engineers (6th Edition) – Steven C. Chapra & Raymond P. Canale
2. Applied Numerical Analysis (7th Edition) – Curtis F. Gerald & Patrick O. Wheatly

Page 3 of 3