Tridiagonal matrix algorithm

The Thomas algorithm (after Llewellyn Thomas ) or tri-diagonal matrix algorithm ( TDMA) is a simplified form of Gaussian elimination which is used for quick release systems of linear equations with a tridiagonal matrix.

A tridiagonal system in n unknowns can be written as

Which should apply: and.

In matrix form, the system is written as:

Examples of these matrices are usually formed from the discretization of the one-dimensional Poisson equation (e.g., one-dimensional diffusion problems ) and from a natural cubic spline interpolation.

For such systems, the solution can be found with the Thomas algorithm after surgery: a first pass eliminates the s, then the solution is obtained using a reverse - insertion method.

Method

The first step is to modify the coefficients recursively (the "new" modified coefficients are denoted by a dash ):

This is the forward flow. The solution is then obtained by a reverse - insertion process:

Variants

In some situations, especially in those with periodic boundary conditions, it may be that a slightly modified form of the tridiagonal system to solve:

In matrix form:

In this case, the Sherman - Woodbury - Morrison formula can be used to take advantage of the Thomas algorithm, and to avoid the additional operations of Gaussian elimination.

In other cases may be block tridiagonal system of equations, i.e., the elements of the above equation system is smaller sub-arrays (e.g., at the two-dimensional Poisson's equation). Also simplified variants of Gaussian elimination have been developed for these cases.

Another variation of the algorithm is the Thomas - Hu - Gallash algorithm that uses a forward insertion process instead of the reverse - insertion method.

Derivation

The unknowns are. The equations to be solved are:

The second equation ( ) is now modified as follows with the first equation:

This results in:

Thereby has been eliminated from the second equation. A procedure analogous to results from the modified second and third equation:

It has now been eliminated. If this procedure is repeated up to the -th row, the modified -th equation contains only one unknown. This equation is then solved and the result used to dissolve the -th equation. This continues until all unknowns are known.

Understandably, the coefficients are complicated with each step when they are explicitly shown. However, the coefficients can be represented recursively:

To further accelerate the solution process is divided out (if ). The new coefficients are:

This results in:

The last equation contains only one unknown. If we determine it, you reduce the number of unknowns in the penultimate equation to one, so that this reverse loading method can be used to determine all unknowns.