Zum Inhalt springen

Gauß-Jordan-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Der Gauß-Jordan-Algorithmus ist ein Algorithmus aus den mathematischen Teilgebieten der linearen Algebra und Numerik. Mit dem Verfahren lässt sich die Lösung eines linearen Gleichungssystems berechnen. Es ist eine Erweiterung des gaußschen Eliminationsverfahrens, bei dem in einem zusätzlichen Schritt das Gleichungssystem bzw. dessen erweiterte Koeffizientenmatrix auf die reduzierte Stufenform gebracht wird. Daraus lässt sich dann die Lösung direkt ablesen. Außerdem kann der Gauß-Jordan-Algorithmus zur Berechnung der Inversen einer Matrix verwendet werden.

Namensgeber neben Carl Friedrich Gauß ist nicht, wie gelegentlich angenommen wird,<ref>Rainer Ansorge, Hans Joachim Oberle: Mathematik für Ingenieure, Band 1. Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim 2000, S. 110.</ref> der ebenfalls in der Linearen Algebra herausragende französische Mathematiker Camille Jordan, sondern der deutsche Geodät Wilhelm Jordan. Dieser ist aber mit großer Wahrscheinlichkeit nicht der „Erfinder“ des zusätzlichen Algorithmusschrittes, sondern nur derjenige, der es seinem Leser- und Hörerkreis nähergebracht hat.<ref>Steven C. Althoen, Renate McLaughlin: <templatestyles src="Webarchiv/styles.css" />{{#if:20160123200448 

      | {{#ifeq: 20160123200448 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Gauss-Jordan Reduction: A Brief History | {{#invoke:WLink|getEscapedTitle|Gauss-Jordan Reduction: A Brief History}} | {{#invoke:Webarchiv|getdomain|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20160123200448}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Gauss-Jordan Reduction: A Brief History | {{#invoke:WLink|getEscapedTitle|Gauss-Jordan Reduction: A Brief History}} | {{#invoke:Webarchiv|getdomain|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20160123200448}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Gauss-Jordan Reduction: A Brief History | {{#invoke:WLink|getEscapedTitle|Gauss-Jordan Reduction: A Brief History}} | {{#invoke:Webarchiv|getdomain|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Gauss-Jordan Reduction: A Brief History | {{#invoke:WLink|getEscapedTitle|Gauss-Jordan Reduction: A Brief History}} | {{#invoke:Webarchiv|getdomain|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Gauss-Jordan Reduction: A Brief History | {{#invoke:WLink|getEscapedTitle|Gauss-Jordan Reduction: A Brief History}} | {{#invoke:Webarchiv|getdomain|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Gauss-Jordan Reduction: A Brief History | {{#invoke:WLink|getEscapedTitle|Gauss-Jordan Reduction: A Brief History}} | {{#invoke:Webarchiv|getdomain|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20160123200448|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf}}
    || {{#if:  || }}
  }}{{#if: Gauss-Jordan Reduction: A Brief History
    | {{#if: {{#invoke:WLink|isBracketedLink|Gauss-Jordan Reduction: A Brief History}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://macs.citadel.edu/chenm/240.dir/12fal.dir/history4.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} (englisch; PDF, 370 kB). In: American Mathematical Monthly, Bd. 94, 1987, S. 130–142.</ref>

Umformungsschritte

  1. Man wählt die erste Spalte von links, in der mindestens ein von Null verschiedener Wert steht.
  2. Ist die oberste Zahl der gewählten Spalte eine Null, so vertauscht man die erste Zeile mit einer anderen Zeile, in der in dieser Spalte keine Null steht.
  3. Man dividiert die erste Zeile durch das nun oberste Element der gewählten Spalte.
  4. Man subtrahiert entsprechende Vielfache der ersten Zeile von den darunterliegenden Zeilen mit dem Ziel, dass das erste Element jeder Zeile (außer der ersten) Null wird.
  5. Durch Streichen der ersten Zeile und Spalte erhält man eine Restmatrix, auf die man diese Schritte wieder anwendet. Das führt man solange durch, bis die Matrix in Zeilenstufenform ist.
  6. Man zieht danach von den darüberliegenden Zeilen entsprechende Vielfache der jeweils passenden darunterliegenden Zeile ab, sodass über jeder führenden 1 nur noch Nullen stehen.

Beispiel

Gegeben ist das folgende lineare Gleichungssystem:

<math>

\begin{align} a &+ \ \ b + c = 0\\ 4a &+ 2b+ c = 1\\ 9a &+ 3b+ c = 3 \end{align} </math>

Nun wird die erweiterte Koeffizientenmatrix des Gleichungssystems gebildet. In der ersten Spalte stehen die Faktoren der Variablen <math>a</math>, in der zweiten die der Variablen <math>b</math>, in der dritten die der Variablen <math>c</math> und in der vierten die rechte Seite des Gleichungssystems. Von den einzelnen Zeilen dieser Matrix sollen solche Vielfache der übrigen Zeilen subtrahiert werden, dass schließlich auf der linken Seite die Einheitsmatrix steht:

<math>
 \left(\begin{array}{ccc|c}
   1 & 1 & 1 & 0 \\
   4 & 2 & 1 & 1 \\
   9 & 3 & 1 & 3
 \end{array}\right)

</math>

Nun werden folgende Zeilentransformationen vorgenommen:

  • Von Zeile 2 wird subtrahiert: 4 × Zeile 1.
  • Von Zeile 3 wird subtrahiert: 9 × Zeile 1.

Damit ergibt sich:

<math>
 \left(\begin{array}{ccc|c}
   1 &\  1 &\  1 & 0 \\
   0 & -2 & -3 & 1 \\
   0 & -6 & -8 & 3
 \end{array}\right)

</math>

  • Von Zeile 3 wird subtrahiert: 3 × Zeile 2.
  • Zeile 2 wird dividiert durch −2.
<math>
 \left(\begin{array}{ccc|c}
   1 &  1 &  1 &\ 0 \\
   0 & 1 & {3 \over 2} & -{1 \over 2} \\
   0 & 0 & 1 &\ 0
 \end{array}\right)

</math>

  • Von Zeile 1 wird subtrahiert: 1 × Zeile 3.
  • Von Zeile 2 wird subtrahiert: 3/2 × Zeile 3.
<math>
 \left(\begin{array}{ccc|c}
   1 & 1 & 0 &\ 0 \\
   0 & 1 & 0 &-{1 \over 2} \\
   0 & 0 & 1 &\ 0
 \end{array}\right)

</math>

  • Von Zeile 1 wird subtrahiert: 1 × Zeile 2.
<math>
 \left(\begin{array}{ccc|c}
   1 & 0 & 0 &\ {1 \over 2} \\
   0 & 1 & 0 & -{1 \over 2} \\
   0 & 0 & 1 &\ 0
 \end{array}\right)

</math>

Diese Matrix wird nun wieder in ein Gleichungssystem übertragen. Da in jeder Zeile aber nur eine Variable steht, erhält man sofort

<math>a = \frac{1}{2}, \ b = -\frac{1}{2}, \ c = 0</math>.

Literatur

  • Howard Anton: Lineare Algebra. Spektrum Akademischer Verlag GmbH Heidelberg, Berlin, ISBN 3-8274-0324-3.

Weblinks

Einzelnachweise

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Gauß-Jordan-Algorithmus&oldid=202240“