Rückwärtssubstitution

Rückwärtssubstitution ist ein Verfahren zur Lösung von linearen Gleichungssystemen der Form Ux = b, wobei U eine obere Dreiecksmatrix ist. Sie tritt typischerweise nach einer Gaußschen Eliminierung oder im Rahmen von LU-Zerlegungen auf, wenn das System in eine Form gebracht wurde, in der die Unbekannten von der letzten nach vorne gelöst werden können.

Vorgehen: Ist U = [u_ij], x = (x1,...,xn)^T, b = (b1,...,bn)^T. Man setzt x_n = b_n / u_nn. Danach für k von n-1 bis 1: x_k = (b_k − ∑_{j=k+1}^n u_kj x_j) / u_kk. Voraussetzung ist u_kk ≠ 0. Falls u_kk = 0 oder nahe Null, wird Pivotisierung oder Umordnung benötigt.

Komplexität: Das Verfahren benötigt etwa n^2 Fließkomma-Operationen und speichert U sowie den Vektor b. Es ist damit O(n^2) Zeit und O(n^2) Speicher.

Verwendung: Nach Gaußscher Eliminierung oder bei der Lösung von Gleichungssystemen mit einer LU- oder PLU-Zerlegung wird Rückwärtssubstitution verwendet, um die endgültigen Unbekannten zu bestimmen. Bei Cholesky-Zerlegung wird sie im zweiten Schritt verwendet (L y = b, dann L^T x = y).

Stabilität und Pivotierung: Die numerische Stabilität hängt von der Bedingung des Problems und der Diagonalstruktur von U ab. In Fällen mit kleineren Diagonal-Elementen oder Null-Diagonal-Einträgen ist Pivotierung oder eine Umordnung der Gleichungen üblich.

Varianten: Für Block- oder gestaffelte Matrizen gibt es Block-Rückwärtssubstitution; bei spärlichen Matrizen können spezielle Strukturen genutzt werden, um Rechenaufwand zu reduzieren.