Tridiagonale-matrix-algoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het tridiagonale-matrix-algoritme, kortweg TDMA genoemd, en ook bekend als het Thomas-algoritme, is een numerieke methode om een vierkant stelsel van lineaire vergelijkingen op te lossen dat wordt beschreven door een tridiagonale matrix. Dit is een matrix waarbij de elementen buiten de diagonaal en de twee nevendiagonalen alle gelijk aan nul zijn, zoals in onderstaande matrix. De methode is niets anders dan een toepassing van de Gauss-eliminatiemethode, met als doel de elementen onder de hoofddiagonaal nul te maken, waardoor het stelsel een geschikte vorm krijgt om te worden opgelost door achterwaartse substitutie.

Methode[bewerken]

Een tridiagonaal stelsel van n vergelijkingen en n onbekenden heeft als vorm:

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

waarbij  a_1  = 0\, en  c_n = 0\, . In matrixvorm wordt dit:


\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}
.

De elementen b_i vormen hierbij samen de hoofdiagonaal of kortweg diagonaal. De elementen a_i en c_i bevinden zich op de zogenaamde nevendiagonalen, meer bepaald respectievelijk op de onderdiagonaal en de bovendiagonaal. De oplossing van dergelijke stelsels kan worden uitgevoerd in O(n) bewerkingen in plaats van de normale O(n^3) bewerkingen van de Gauss-methode. In een eerste stap worden de coëfficiënten a_i weggewerkt, waarna via achterwaartse substitutie de oplossing wordt gevonden. Dit soort stelsels komt bijvoorbeeld voor bij de numerieke oplossing van de diffusievergelijking en bij het berekenen van natuurlijke splines.

In de eerste stap worden de coëfficiënten van het stelsel omgevormd, opdat alle elementen van de coëfficiëntenmatrix op de onderdiagonaal nul worden. De nieuwe coëfficiënten worden in onderstaande vergelijkingen met een accent aangeduid:

c'_i =
\begin{cases}
\begin{array}{lcl}
  \cfrac{c_1}{b_1}                  & ; & i = 1 \\
  \cfrac{c_i}{b_i - c'_{i - 1} a_i} & ; & i = 2, 3, \dots, n-1 \\
\end{array}
\end{cases}
\,

en:

d'_i =
\begin{cases}
\begin{array}{lcl}
  \cfrac{d_1}{b_1}                  & ; & i = 1 \\
  \cfrac{d_i - d'_{i - 1} a_i}{b_i - c'_{i - 1} a_i} & ; & i = 2, 3, \dots, n. \\
\end{array}
\end{cases}
\,

Na deze voorwaartse stap volgt als tweede stap een achterwaartse substitutie die de oplossing levert:

x_n = d'_n\,
x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1.

Concrete implementaties[bewerken]

Het Engelstalige artikel over dit onderwerp bevat voorbeelden van implementaties in de programmeertalen C, Matlab en Fortran. Bij het programmeren dient men ermee rekening te houden dat de nummering van de elementen van een vector of een matrix in sommige programmeertalen loopt van 1 tot n, en in andere van 0 tot n-1. In het laatste geval dienen de uitdrukkingen in dit artikel aangepast te worden.

Afleiding[bewerken]

De afleiding van het tridiagonaal-matrix-algoritme is gebaseerd op Gauss-eliminatie, waarbij de elementen van de onderdiagonaal nul worden gemaakt door het uitvoeren van elementaire rijoperaties. Stel dat de onbekenden van het stelsel x_1,\ldots, x_n zijn en de vergelijkingen:

\begin{align}
b_1 x_1 + c_1 x_2 & = d_1;& i & = 1 \\
a_i x_{i - 1} + b_i x_i  + c_i x_{i + 1} & = d_i;& i & = 2, \ldots, n - 1 \\
a_n x_{n - 1} + b_n x_n & = d_n;& i & = n.
\end{align}

Dan wordt de tweede vergelijking door middel van de eerste als volgt gewijzigd:


(\mbox{vergelijking 2}) \cdot b_1 - (\mbox{vergelijking 1}) \cdot a_2

Het resultaat van deze elementaire rijoperatie is:


(a_2 x_1 + b_2 x_2  + c_2 x_3) b_1 - (b_1 x_1  + c_1 x_2) a_2 = d_2 b_1 - d_1 a_2
\,

(b_2 b_1 - c_1 a_2) x_2  + c_2 b_1 x_3 = d_2 b_1 - d_1 a_2
\,

Op deze manier is x_1 verwijderd uit de tweede vergelijking. Met behulp van de tweede vergelijking wordt dan de derde op analoge manier behandeld, zodat:


(a_3 x_2 + b_3 x_3 + c_3 x_4) (b_2 b_1 - c_1 a_2) -
((b_2 b_1 - c_1 a_2) x_2 + c_2 b_1 x_3) a_3
= d_3 (b_2 b_1 - c_1 a_2) - (d_2 b_1 - d_1 a_2) a_3
\,

(b_3 (b_2 b_1 - c_1 a_2) - c_2 b_1 a_3 )x_3 + c_3 (b_2 b_1 - c_1 a_2) x_4
= d_3 (b_2 b_1 - c_1 a_2) - (d_2 b_1 - d_1 a_2) a_3.
\,

Dit systeem van rijoperaties wordt nu verder toegepast doorheen de matrix, waardoor alle elementen op de onderdiagonaal nul worden. Als gevolg hiervan bevat de n-de rij slechts één onbekende, namelijk x_n, die dus direct kan gevonden worden. Vervolgens worden de andere onbekenden in volgorde van onder naar boven bepaald. Bij elke stap bevat de te behandelen vergelijking immers nog slechts één onbekende. De laatste onbekende die wordt bepaald is dus x_1.

Indien de coëfficiënten van de gewijzigde vergelijkingen expliciet worden opgeschreven worden ze steeds ingewikkelder. Het is daarom beter de gewijzigde coëfficiënten, hieronder aangeduid met een tilde, recursief te definiëren.

\tilde a_i = 0\,
\tilde b_1 = b_1\,
\tilde b_i = b_i \tilde b_{i - 1} - \tilde c_{i - 1} a_i\,
\tilde c_1 = c_1\,
\tilde c_i = c_i \tilde b_{i - 1}\,
\tilde d_1 = d_1\,
\tilde d_i = d_i \tilde b_{i - 1} - \tilde d_{i - 1} a_i.\,

Om de oplossing nog vlotter te laten verlopen kan men ook nog \tilde b_i wegdelen (indien niet deze niet nul zijn). De aldus gewijzigde coëfficiënten, aangeduid met een asterisk, zijn:

a'_i = 0\,
b'_i = 1\,
c'_1 = \frac{c_1}{b_1}\,
c'_i = \frac{c_i}{b_i - c'_{i - 1} a_i}\,
d'_1 = \frac{d_1}{b_1}\,
d'_i = \frac{d_i - d'_{i - 1} a_i}{b_i - c'_{i - 1} a_i}.\,

Dit geeft het volgende stelsel, nog steeds in de oorspronkelijke onbekenden:

\begin{array}{lcl}
x_i + c'_i x_{i + 1} = d'_i \qquad &;& \ i = 1, \ldots, n - 1 \\
x_n = d'_n/b'_n \qquad &;& \ i = n. \\
\end{array}
\,

De oplossingen zijn, startend vanaf x_n en zo door achterwaartse substitutie naar x_1:

x_n = d'_n/b'_n\,
x_i = (d'_i - c'_i x_{i + 1})/b'_i \qquad ; \ i = n - 1, n - 2, \ldots, 1.

Varianten[bewerken]

In bepaalde situaties, zoals in het geval van periodieke randvoorwaarden, komt een lichtjes andere vorm van een tridiagonaal stelsel voor:


\begin{align}
a_1 x_{n}  + b_1 x_1  + c_1 x_2  & = d_1, \\
a_i x_{i - 1}  + b_i x_i  + c_i x_{i + 1}  & = d_i,\quad\quad i = 2,\ldots,n-1 \\
a_n x_{n-1}  + b_n x_n  + c_n x_1  & = d_n.
\end{align}

In dat geval kan de formule van Sherlan-Morrison gebruikt worden om bijkomende bewerkingen tijdens de elementaire rijoperaties te vermijden. In andere gevallen komt een stelsel voor dat in matrixvorm een blokmatrix geeft. Ook in dit geval bestaan er aangepaste methoden van de Gauss-eliminatiemethode.

Referenties[bewerken]

  • Conte, S.D., and de Boor, C., Elementary Numerical Analysis: an algorithmic approach, McGraw-Hill, New York, ISBN 0-07-066228-2, 1981

Externe links[bewerken]

Bronnen[bewerken]