Tridiagonal Matrix Algorithm

In numerical linear algebra, the tridiagonal matrix algorithm, also known as the Thomas algorithm (named after Llewellyn Thomas), is a simplified form of Gaussian elimination that can be used to solve tridiagonal systems of equations. A tridiagonal system for n unknowns may be written as

$a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i, \,\!$

where and .

$\begin{bmatrix} {b_1} & {c_1} & { } & { } & { 0 } \\ {a_2} & {b_2} & {c_2} & { } & { } \\ { } & {a_3} & {b_3} & \ddots & { } \\ { } & { } & \ddots & \ddots & {c_{n-1}}\\ { 0 } & { } & { } & {a_n} & {b_n}\\ \end{bmatrix} \begin{bmatrix} {x_1 } \\ {x_2 } \\ {x_3 } \\ \vdots \\ {x_n } \\ \end{bmatrix} = \begin{bmatrix} {d_1 } \\ {d_2 } \\ {d_3 } \\ \vdots \\ {d_n } \\ \end{bmatrix} .$

For such systems, the solution can be obtained in operations instead of required by Gaussian elimination. A first sweep eliminates the 's, and then an (abbreviated) backward substitution produces the solution. Examples of such matrices commonly arise from the discretization of 1D Poisson equation (e.g., the 1D diffusion problem) and natural cubic spline interpolation.

Read more about Tridiagonal Matrix Algorithm: Method, Derivation, Variants

Famous quotes containing the word matrix:

“As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.”
—Margaret Atwood (b. 1939)