imported>Meinichselbst: Parameter fix

2025-10-03T18:18:37Z

Parameter fix

Neue Seite

Der '''Thomas-Algorithmus''' (nach [[Llewellyn Thomas]]) oder auch '''Tridiagonalmatrix-Algorithmus (TDMA)''' ist eine vereinfachte Form des [[Gaußsches Eliminationsverfahren|Gaußschen Eliminationsverfahrens]], der zum schnellen Lösen von [[lineares Gleichungssystem|linearen Gleichungssystemen]] mit einer [[Tridiagonalmatrix]] benutzt wird.

== Verfahren ==
Ein tridiagonales System mit ''n'' Unbekannten <math> x_{i} \,\!</math> kann geschrieben werden als
:<math>
a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i , \,\!</math>

wobei gelten soll: <math> a_1 = 0\, </math> und <math> c_n = 0\, </math>.

In [[Matrix (Mathematik)|Matrizen]]<nowiki/>form wird das System geschrieben als:
<math>
\left[
\begin{matrix}
{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{matrix}
\right]
\left[
\begin{matrix}
{x_1 } \\
{x_2 } \\
{x_3 } \\
\vdots \\
{x_n } \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
{d_1 } \\
{d_2 } \\
{d_3 } \\
\vdots \\
{d_n } \\
\end{matrix}
\right].
</math>

Beispiele für diese Matrizen entstehen üblicherweise aus der [[Diskretisierung]] der eindimensionalen [[Poisson-Gleichung]] (z. B. eindimensionale [[Wärmeleitungsgleichung|Diffusionsprobleme]]) und aus der natürlichen kubischen [[Spline-Interpolation]].

Für solche Systeme kann die Lösung mit dem Thomas-Algorithmus nach [[Landau-Notation|<math> \mathcal{O}(n) </math>]] Operationen gefunden werden: Ein erster Durchlauf eliminiert die <math>a_i</math>s, anschließend erhält man die Lösung mit Hilfe eines [[gaußsches Eliminationsverfahren#Rückwärtseinsetzen|Rückwärts-Einsetzverfahrens]].

Der erste Schritt ist es, die [[Koeffizient]]en folgendermaßen [[rekursiv]] zu modifizieren (die „neuen“ modifizierten Koeffizienten sind mit einem Strich gekennzeichnet):

:<math>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}
\,</math>

:<math>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}
\,</math>

Dies ist der vorwärts gerichtete Durchlauf. Die Lösung ergibt sich dann durch ein Rückwärts-Einsetzverfahren:

:<math>x_n = d'_n\,</math>

:<math>x_i = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1</math>

== Varianten ==
In manchen Situationen, insbesondere in solchen mit [[Periodizität (Mathematik)|periodischen]] [[Randbedingung]]en, kann es sein, dass eine leicht veränderte Form des tridiagonalen Systems zu lösen ist:

:<math>
\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}
</math>

In Matrizenform:
<math>
\left[
\begin{matrix}
{b_1} & {c_1} & { } & { } & { a_1 } \\
{a_2} & {b_2} & {c_2} & { } & { } \\
{ } & {a_3} & {b_3} & \ddots & { } \\
{ } & { } & \ddots & \ddots & {c_{n-1}}\\
{ c_n } & { } & { } & {a_n} & {b_n}\\
\end{matrix}
\right]
\left[
\begin{matrix}
{x_1 } \\
{x_2 } \\
{x_3 } \\
\vdots \\
{x_n } \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
{d_1 } \\
{d_2 } \\
{d_3 } \\
\vdots \\
{d_n } \\
\end{matrix}
\right].
</math>

In diesem Fall kann die [[Sherman-Morrison-Woodbury-Formel]] benutzt werden, um den Thomas-Algorithmus zu nutzen und die zusätzlichen Operationen des Gaußschen Eliminationsverfahrens zu vermeiden.

In anderen Fällen kann das Gleichungssystem ''block''-tridiagonal sein, d. h. die Elemente des obigen Gleichungssystems sind kleinere [[Blockmatrix#Blocktridiagonalmatrix|Blockmatrizen]] (z. B. bei der zweidimensionalen [[Poisson-Gleichung]]). Für diese Fälle wurden ebenfalls vereinfachte Varianten der Gauß-Elimination entwickelt.

Eine weitere Variante des Thomas-Algorithmus ist der Hu-Gallash-Algorithmus, der statt des Rückwärts-Einsetzverfahrens ein Vorwärts-Einsetzverfahren nutzt.

== Herleitung ==

Die Unbekannten seien <math>x_1,\ldots, x_n</math>. Die zu lösenden Gleichungen seien:

:<math>
\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}
</math>

Die zweite Gleichung (<math>i = 2</math>) wird nun wie folgt mit der ersten Gleichung modifiziert:

:<math>
(\mbox{Gleichung 2}) \cdot b_1 - (\mbox{Gleichung 1}) \cdot a_2
</math>

Dies ergibt:

:<math>\begin{align}
(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
\,\end{align}</math>

Dadurch wurde <math>x_1</math> aus der zweiten Gleichung eliminiert. Mit einer analogen Vorgehensweise ergibt sich aus der modifizierten zweiten und der dritten Gleichung:

:<math>\begin{align}
(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
\,\end{align}</math>

Jetzt wurde <math>x_2</math> eliminiert. Wird diese Vorgehensweise bis zur <math>n</math>-ten Zeile wiederholt, enthält die modifizierte <math>n</math>-te Gleichung nur eine Unbekannte. Diese Gleichung wird nun gelöst und das Ergebnis genutzt, um die <math>(n - 1)</math>-te Gleichung zu lösen. Dies wird so lange fortgeführt, bis alle Unbekannten bekannt sind.

Verständlicherweise werden die Koeffizienten mit jedem Schritt komplizierter, wenn sie explizit dargestellt werden. Die Koeffizienten können jedoch auch rekursiv dargestellt werden:

:<math>\begin{align}
\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
\,\end{align}</math>

Um den Lösungsprozess weiter zu beschleunigen, wird <math>\tilde b_i</math> herausdividiert (wenn <math>\tilde b_i \ne 0</math>). Die neuen Koeffizienten lauten:

:<math>\begin{align}
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}
\,\end{align}</math>

Dies ergibt:

:<math>\begin{array}{llcl}
x_i + c'_i x_{i + 1} & = d'_i \qquad &;& \ i = 1, \ldots, n - 1 \\
x_n & = d'_n \qquad &;& \ i = n \\
\end{array}
\,</math>

Die letzte Gleichung enthält nur eine Unbekannte. Bestimmt man sie, reduziert man die Anzahl der Unbekannten in der vorletzten Gleichung auf eins, so dass dieses Rückwärts-Einsetzverfahren genutzt werden kann, um alle Unbekannten zu bestimmen.

:<math>\begin{align}
x_n & = d'_n \\
x_i & = d'_i - c'_i x_{i + 1} \qquad ; \ i = n - 1, n - 2, \ldots, 1
\end{align}</math>

== Einzelnachweise ==
*{{cite book|author=Conte, S.D., and deBoor, C.|year=1972|title=Elementary Numerical Analysis|publisher= McGraw-Hill, New York |language=en}}

[[Kategorie:Numerische lineare Algebra]]

Thomas-Algorithmus - Versionsgeschichte

imported>Meinichselbst: Parameter fix