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:

““The matrix is God?”
“In a manner of speaking, although it would be more accurate ... to say that the matrix has a God, since this being’s omniscience and omnipotence are assumed to be limited to the matrix.”
“If it has limits, it isn’t omnipotent.”
“Exactly.... Cyberspace exists, insofar as it can be said to exist, by virtue of human agency.””
—William Gibson (b. 1948)