Stamp tridiagonale

In Mathematical, in Linear algebra, a matrix tridiagonale is a matrix such as the coefficients which are not on the diagonal, on the diagonal just below or on the diagonal just above are all null.

For example, the following matrix is tridiagonale:

\begin{pmatrix}

1 & 4 & 0 & 0 \ \ 3 & 4 & 1 & 0 \ \ 0 & 2 & 3 & 4 \ \ 0 & 0 & 1 & 3 \ \ \end{pmatrix}

Definition

A matrix

M \ in \ mathcal {M} _n \ left (\ mathbb {K} \ right)

, which one notes the coefficients

m_ {I, J}

, is known as tridiagonale if and only if:

m_ {I, J} = 0 \,

for all ( I , J ) such as

|i-j| > 1 \,

Properties

A matrix tridiagonale is a Matrice of Hessenberg.

If a real matrix tridiagonale has checks has _{K , K +1} × has _{K +1, K} > 0 for K = 1,2,…, N - i.e. the signs of these coefficients are symmetrical, then it is similar to a square Matrice and thus all its eigenvalues is real. This property is preserved if one considers the condition by rather has _{K , K +1} × has _{K +1, K} ≥ 0.

The whole of all the matrices tridiagonales N × N is a vector Space of Dimension 3n-2 .

Use

Algorithms

Many algorithms of linear algebra require much less operations when one carries out them on diagonal matrices. It is current that this profit is propagated with the matrices tridiagonales.

For example, the Déterminant of a matrix tridiagonale has N × N can be calculated by the following recursive formula:

\ det has = a_ {N, N} \ det \, _ {\ {1, \ ldots, n-1 \}} - a_ {N, n-1} a_ {n-1, N} \ det \, _ {\ {1, \ ldots, N2 \}} \, \,

where one noted

\ det _ {\ {1, \ ldots, K \}}

the K - ième minor, i.e. the determinant of the matrix obtained by keeping only the K first lines and columns of has . The calculation of determinant by this method is linear in N for the matrices tridiagonales, whereas it is in N ³ in the general case.

A transformation which reduces an unspecified matrix to a matrix of Hessenberg will reduce a square matrix to a matrix tridiagonale. Thus, of many calculation algorithms of the eigenvalues use a stage of reduction in the shape of a matrix tridiagonale if they work on square matrices.

Memory

A matrix tridiagonale can be stored in an optimized way by using a particular representation. For example, the bookstore LAPACK records a not-symmetrical matrix in the shape of three unidimensional tables, one containing the diagonal coefficients and the two others the elements respectively above and below the diagonal.

Mathematics

The matrices tridiagonales are current in the study of the cubic Spline S. They are also often solutions with the problem of Sturm-Liouville.

In addition, a linear system implicant a matrix tridiagonale, form:

A \ cdot X = B \ in \ reals^n

can be solved through specific algorithms, which require O (N) operations (Golub and Van Loan).

See too

Matrix bidiagonale;
triangular Matrix;
diagonal Matrix;
Matrix of Hessenberg.

Refer

Random links: