Direkt zum Inhalt

Lexikon der Mathematik: Gaußscher Algorithmus

Gauß-Verfahren, das prominenteste Verfahren zur Berechnung der eindeutig existierenden Lösung x = (x1, …, xn)t des linearen Gleichungssystems Ax = b mit einer regulären (n × n)-Matrix A = (aij) über \({\mathbb{K}}\) und einem Vektor \(b\space =\space {({b}_{1},\ldots,{b}_{n})}^{t}\space \in \space {{\mathbb{K}}}^{n}\).

Der Gaußsche Algorithmus ist ein direktes Verfahren zur Lösung eines linearen Gleichungssystems und wird im gleichnamigen Übersichtsartikel im Zusammenhang geschildert. Hier wird nochmal eine kompakte Formulierung gegeben.

Mit A|b sei die (n × n + 1)-Matrix bezeichnet, die durch Hinzufügen des Vektors b als (n + 1)-tem Spaltenvektor an die Matrix A aus dieser hervorgeht. A|b kann durch elementare Zeilenumformungen auf folgende Gestalt (1) gebracht werden, bei der alle \({a}_{ii}^{^{\prime} }\) von Null verschieden sind und unterhalb der Diagonalen \(({a}_{11}^{^{\prime} },\ldots,\space {a}_{nn}^{^{\prime} })\) lauter Nullen stehen: \begin{eqnarray}\begin{array}{cc}A^{\prime} |b^{\prime} =\left(\begin{array}{ccccc}{a}_{11}^{^{\prime} } & & & & {b}_{1}^{^{\prime} }\\ & {a}_{22}^{^{\prime} } & & & {b}_{2}^{^{\prime} }\\ & & \ddots & & \vdots \\ & & & {a}_{nn}^{^{\prime} } & {b}_{n}^{^{\prime} }\end{array}\right ).\end{array}\end{eqnarray}

Vorgehensweise: Zuerst wird (falls notwendig) durch eine Zeilenvertauschung erreicht, daß an der Stelle (1, 1) der Matrix ein von Null verschiedenes Element steht; durch Addition geeigneter Vielfacher der (evtl. neuen) ersten Zeile zu den Zeilen 2 bis n werden dann an den Stellen (2,1) bis (n, 1) lauter Nullen erzeugt. Jetzt wird (falls notwendig) ohne Verwendung der ersten Zeile durch eine Zeilenvertauschung erreicht, daß an der Stelle (2, 2) der Matrix ein von Null verschiedenes Element steht mit dessen Hilfe an den Stellen (3, 2) bis (n, 2) Nullen erzeugt werden. Analog verfährt man mit den Spalten 3 bis n der Matrix.

Die Lösung des durch A′|b′ dargestellten Gleichungssystems Ax = b′ läßt sich durch „Rückwärtseinsetzen“ direkt ablesen; diese Lösung stimmt mit der Lösung von Ax = b überein.

Allgemeiner bezeichnet man auch die Reduktion einer beliebigen (m × n)-Matrix über \({\mathbb{K}}\) mittels elementarer Zeilenumformungen auf Zeilenstufenform als Gaußschen Algorithmus, Gauß-Eliminationsverfahren oder Zeilenreduktion. Es gilt der folgende Satz, der auch als Gauß-Eliminationsverfahren oder als Zeilenreduktion bezeichnet wird:

Sei Ax = b ein lineares Gleichungssystem mit einer (m × n)-Matrix A über \({\mathbb{K}}\)vom Rang r < m und einem Lösungsvektor \(b\space \in \space {{\mathbb{K}}}^{m}\). Sei Ax = bdas hierzu äquivalente lineare Gleichungssystem in Zeilenstufenform.

Ax = b besitzt genau dann eine Lösung, wenn die Komponenten \({b}_{i}^{\text{'}}\)des Vektors bfür i > r alle Null sind.

Der Gaußsche Algorithmus ist das gängige Verfahren, um die Inverse einer regulären Matrix zu berechnen, sowie den Rang einer Matrix und die Lösungsmenge eines beliebigen linearen Gleichungssystems zu bestimmen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos