Solving a tridiagonal matrix using the Thomas Algorithm

This post is part of a series of articles on the Finite Difference Method, with other posts in this series covering:

• Approximation of derivatives using the finite difference method
• Solving explicit diffusion equations
• Default Crank-Nicolson method
• Solving a tridiagonal matrix system using Thomas's algorithm

In the previous article, a set of linear equations was arranged in the form of a tridiagonal matrix equation. Solving this equation allows for the calculation of values at the interior grid points. The system of equations must be solved at every time step, which clearly requires more resources than the explicit method at each time step. However, the implicit method can use much larger time steps, giving it a long-term advantage.

The method used to solve this matrix equation is Llewellyn Thomas's algorithm, also known as the Tridiagonal Matrix Algorithm (TDMA), which is essentially the application of Gaussian Elimination to a matrix with a banded structure.

The form of the system of equations

The initial equation can be written in the form:

ai​ui−1n+1​+bi​uin+1​+ci​ui+1n+1​=di​

For i=1,2,...,N−2

Setting new coefficients

The algorithm starts by creating new coefficients ci′ and di′ to replace ai, bi, ci, and di as follows:

For i=1:

c1′​=b1​c1​​,d1′​=b1​d1​​

For i=2,3,...,N−2:

ci′​=bi​−ai​ci−1′​ci​​

di′​=bi​−ai​ci−1′​di​−ai​di−1′​​

Replacing the system of equations

With these new coefficients The system of equations can be rewritten in the form:

uin+1​=ci′​ui+1n+1​+di′​, for i=1,2,...,N−2

Back Substitution algorithm

When the values of ci′ and di′ have been fully calculated, the value of uin+1 can be found by back-substituting from i=N−2 down to i=1 as follows:

Starting point:

uN−2n+1​=dN−2′​

Backtrack:

uin+1​=ci′​ui+1n+1​+di′​, for i=N−3,...,1

At this stage, the algorithm for finding the values at each grid point at each time step has been fully described. The final step in practical implementation is to write a program to process according to the algorithm, which will be the topic of the next article.

Reference: Tridiagonal Matrix Solver via Thomas Algorithm

From https://www.quantstart.com/articles/Tridiagonal-Matrix-Solver-via-Thomas-Algorithm/