modifizierter Gauß-Algorithmus

Verfahren der vollständigen Elimination, manchmal auch nur Gaußscher Algorithmus oder Gauss-Algorithmus.
I. Charakterisierung: Variante des Gauß-Algorithmus, die jedes lineare Gleichungssystem (ursprüngliches System) systematisch mit Hilfe lösungsneutraler Umformungen in ein äquivalentes kanonisches lineares Gleichungssystem überführt, aus dem dann die Lösungsmenge des ursprünglichen Systems abgelesen werden kann bzw. das ggf. anzeigt, daß das ursprüngliche System überhaupt keine Lösung besitzt. - Grundgedanke: Der m. G. A. besteht aus maximal n Schritten, wobei in jedem Schritt eine Noch-nicht-Basisvariable xq zur Basisvariablen bestimmt, eine Gleichung Gp, in der diese neue Basisvariable stehen soll, festgelegt und die entsprechende kanonische Form für xq erzeugt wird. Letzteres geschieht durch Normieren der Gleichung Gp (d. h. Ersetzen der Gleichung Gp durch ein 1/apq-faches (apq 0) von ihr) und anschließendes Eliminieren der Variablen xq aus jeder anderen Gleichung i (i p) (d. h. Ersetzen der Gleichung (i p) durch die Summe dieser Gleichung und des -aiq-fachen der ungeformten Gleichung Gp). Sollte das ursprüngliche Gleichungssystem keine Lösung besitzen, so tritt mindestens eine Widerspruchsgleichung auf.
II. Bezeichnungsweisen: Das Bündel von lösungsneutralen Umformungen, das erforderlich ist, um eine Gleichung Gp nach der ausgewählten Variablen xq zu normieren und diese Variable aus allen übrigen Gleichungen zu eliminieren, nennt man Pivotschritt, xq heißt in diesem Zusammenhang Pivotvariable, die Gleichung Gp Pivotgleichung. Das Indexpaar (p,q) bezeichnet man als Pivot, den Koeffizienten apq als Pivotelement.
III. Algorithmus: Anwendungsvoraussetzungen: Gegeben ist ein lineares Gleichungssystem der allgemeinen Form:
Anfangsschritt:
(0.1) Setze r: = m!
Schritt 1 (Unlösbarkeit):
(1.1) Gibt es eine Gleichung Gp in GS, in der alle Koeffizienten gleich Null sind und die rechte Seite ungleich Null ist?
JA: —> (6.1)! NEIN: —> (2.1)!
Schritt 2 (Nullgleichung):
(2.1) Gibt es eine Gleichung Gp in GS, in der alle Koeffizienten und die rechte Seite gleich Null sind?
JA: —> (2.2)! NEIN: —> (3.1)!
(2.2) Streiche die Gleichung Gp!
(2.3) Numeriere die Gleichungen in GS neu durch!
(2.4) Setze r:=r – 1! —> (2.1)!
Schritt 3 (kanonische Form):
(3.1) Ist die Anzahl der bereits markierten Basisvariablen in GS gleich r?
JA: —> (6.2)! NEIN: —> (4.1)!
Schritt 4 (Auswahl des Pivotelements):
(4.1) Wähle eine Gleichung Gp, die noch nicht markiert ist!
(4.2) Wähle eine Variable xq, die noch nicht als Basisvariable markiert ist, mit apq0!
Schritt 5 (Pivotschritt):
(5.1) Setze:
(5.2) Markiere xq als Basisvariable!
(5.3) Markiere die Gleichung Gp
Endschritt:
(6.1) "Das Gleichungssystem besitzt keine Lösung" —> (6.3)!
(6.2) "Das Gleichungssystem liegt in kanonischer Form vor."
(6.3) STOP!

<< vorheriger Begriff

nächster Begriff>>

modifizierte Zielgleichung

modifizierter Zielkoeffizient