Tridiagonal matris

Från Wikipedia
Hoppa till: navigering, sök

En tridiagonal matris är inom matematiken en matris som är "nästan" diagonal, mer specifikt har den nollskilda element endast i huvuddiagonalen samt diagonalerna precis under och över huvuddiagonalen.

En tridiagonal matris kan alltså skrivas:

\begin{pmatrix}
b_1 & c_1 &  &  & 0 \\
a_2 & b_2 & c_2 &   \\
 & a_2 & b_2 & \ddots \\
 & & \ddots & \ddots & c_{n-1} \\
0 & & & a_n & b_n
\end{pmatrix}

Egenskaper[redigera | redigera wikitext]

Tridiagonala matriser är ett specialfall av Hessenbergmatriser.

Om elementen i en tridiagonal matris  A är symmetriska med avseende på tecknet, dvs  a_{k,k+1} a_{k+1,k} > 0 , så kan den via basbyte omvandlas till en hermitesk matris.

Många algoritmer inom linjär algebra är betydligt snabbare när de appliceras på diagonala matriser, något som ofta även gäller för tridiagonala matriser.

Lösning av tridiagonala system[redigera | redigera wikitext]

Ett system av ekvationer Ax = d, där A är tridiagonal kan lösas i O(n) tid. Om matrisen A ser ut som ovan och vektorerna x och d har elementen xi respektive di kan en lösning fås genom att införa nya variabler:

c_i' = \begin{cases} \frac{c_1}{b_1} & i = 1 \\ \frac{c_1}{b_i - c_{i-1}'a_i} & i = 2, 3, \dots, n-1 \end{cases}
d_i' = \begin{cases} \frac{d_1}{b_1} & i = 1 \\ \frac{d_i - d_{i-1}'a_i}{b_i - c_{i-1}'a_i} & i = 2, 3, \dots, n \end{cases}

Då en lösning sedan fås genom bakåtsubstitution:

x_n = d_n'\,
x_i = d_i' - c_i' x_{i+1}\,