Thomas-Algorithmus

Geert Bülow Juli 26, 2016 T 8 0
FONT SIZE:
fontsize_dec
fontsize_inc

In numerischen linearen Algebra, die Thomas-Algorithmus, der auch als Thomas-Algorithmus bekannt, ist eine vereinfachte Form der Gauß-Elimination, die verwendet werden können, um tridiagonal Gleichungssysteme zu lösen. A tridiagonal System für n Unbekannten geschrieben werden als

wo und.

Für solche Systeme kann die Lösung in Betrieb, anstatt erhalten durch Gauß-Elimination erforderlich. Ein erster Durchlauf beseitigt die 's, und dann eine Rückwärtssubstitution erzeugt die Lösung. Beispiele für solche Matrizen ergeben sich häufig aus der Diskretisierung der Poisson-Gleichung 1D und natürliche kubische Spline-Interpolation; ähnliche Systeme von Matrizen ergeben sich feste Bindung der Physik oder der nächste Nachbar Effects-Modelle.

Verfahren

Die Vorwärtspfeilung besteht aus Veränderung der Koeffizienten wie folgt, bezeichnet die neuen modifizierten Koeffizienten mit Primzahlen:

und

Die Lösung wird dann durch Rücksubstitution erhalten:

Abstammung

Die Ableitung des Thomas-Algorithmus beinhaltet das manuelle Durchführung einiger spezialisierter Gauß-Elimination in einer generischen Art und Weise.

Annehmen, dass die Unbekannten sind, und dass die zu lösenden Gleichungen sind:

Sehen Modifizieren der zweiten Gleichung mit dem ersten Gleichung wie folgt:

was geben würde:

und der Effekt ist, dass aus der zweiten Gleichung eliminiert. Verwendung eines ähnlichen Taktik mit dem modifizierten zweiten Gleichung auf die dritte Gleichung ergibt:

Diese Zeit wurde eliminiert. Wenn diese Prozedur wird wiederholt, bis die Reihe; Die Gleichung wird nur eine Unbekannte ,. beinhalten Dies kann gelöst werden, und dann verwendet, um die Gleichung zu lösen, und so weiter, bis alle der Unbekannten zu lösen.

Offensichtlich sind die Koeffizienten der modifizierten Gleichungen mehr und mehr kompliziert, wenn dies ausdrücklich angegeben ist. Durch Untersuchung der Verfahren können die modifizierten Koeffizienten anstelle rekursiv definiert werden:

Um weiter zu beschleunigen den Lösungsprozess, kann unterteilt werden, die neueren modifizierten Koeffizienten mit einem Strich notiert werden:

Das gibt das folgende System mit denselben Unbekannten und Koeffizienten in Bezug auf die ursprünglichen vorstehend definiert ist:

Die letzte Gleichung beinhaltet nur eine Unbekannte. Lösen sie wiederum die nächsten letzte Gleichung auf eine unbekannte, so dass diese Rückwärtssubstitution kann verwendet werden, um alle der Unbekannten zu finden:

Varianten

In einigen Situationen, insbesondere solche mit periodischen Randbedingungen, muss eine etwas gestörte Form tridiagonalen System gelöst werden:

In diesem Fall können wir den Einsatz des Sherman-Morrison Formel zu machen, um die zusätzlichen Operationen der Gauß-Elimination zu vermeiden und immer noch die Thomas-Algorithmus. Das Verfahren erfordert die Lösung einer modifizierten nichtcyclischen Version des Systems sowohl für die Eingabe und einen lichten Korrekturvektor und dann Kombinieren der Lösungen. Dies kann effizienter erfolgen, wenn beide Lösungen auf einmal berechnet werden, da der vordere Teil des reinen Thomas-Algorithmus kann gemeinsam genutzt werden.

In anderen Situationen kann das Gleichungssystem Block tridiagonal, wobei kleinere Untermatrizen als die einzelnen Elemente in der obigen Matrixsystem angeordnet sind. Vereinfachte Formen der Gauß-Elimination haben für diese Situationen entwickelt.

Das Lehrbuch Numerische Mathematik durch Quarteroni, Sacco und Saleri, listet eine modifizierte Version des Algorithmus, der einige der Divisionen vermeidet, was sich positiv auf einigen Computer-Architekturen ist.

  Like 0   Dislike 0
Bemerkungen (0)
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha