\documentclass[a4paper,12pt]{scrartcl}
\usepackage{ngerman}
\usepackage{amssymb} % Paket für R-, N-, Q-Symbole
\usepackage[latin1]{inputenc}
\usepackage{pst-pdf,pstricks,pst-plot,pst-node,pst-circ}
\usepackage{color}
\usepackage{ifpdf}    % "workaround" um Fehler in hyperref mit pstricks
\ifpdf                %
\usepackage{hyperref} %
\hypersetup{colorlinks=true,urlcolor=cyan,linkcolor=blue}
\fi                   %
\setlength{\fboxrule}{1pt} % Breite der Umrandung
%\usepackage{graphicx}
%\usepackage{wrapfig} % Paket für Umfließen der Grafik
%\usepackage{caption}
%\captionsetup{labelformat=empty}
%\pagestyle{empty}    % ohne Seitennummerierung
\widowpenalty=10000
\clubpenalty=10000
\setlength{\parindent}{0pt} % kein Einrücken nach Abschnitt
\begin{document}

\title{Das Gauß-Jordan-Verfahren zur Lösung von Lineargleichungssystemen}
\author{Wolfgang Kippels}
\maketitle
\tableofcontents
\newpage

\section{Vorwort}
Diese und ähnliche Anleitungen zu erstellen erfordert sehr viel Zeit und Mühe.
Trotzdem stelle ich alles kostenfrei der Allgemeinheit zur Verfügung. Wenn Sie
diese Datei hilfreich finden, dann bitte ich Sie um Erfüllung des nachfolgend
beschriebenen "`Generationenvertrages"':
\begin{quote}
\emph{Wenn Sie später einmal Ihre Ausbildungsphase beendet haben und im Beruf stehen
(oder auch noch danach), geben Sie bitte Ihr Wissen in geeigneter Form an die
nachfolgende Generation weiter}.
\end{quote}

Wenn Sie mir eine Freude machen wollen, dann schreiben Sie mir bitte eine
kleine Email an die folgende Adresse:
\includegraphics[width=25mm]{Adresse.jpg}\\

Vielen Dank!
\newpage

\section{Das Prinzip des Verfahrens von Gauß}
Carl Friedrich Gauss hat das
Additions-/Subtraktionsverfahren\footnote{Einzelheiten siehe auch hier:
\ifpdf \url{https://dk4ek.de/lib/exe/fetch.php/add.pdf} \fi}
systematisiert und weiterentwickelt. Das von ihm vorgestellte und nach ihm
benannte Gaußsche Eliminationsverfahren eignet sich dadurch besonders gut zum
schematischen Lösen, wie es Rechner durchführen können. Später wurde das
Verfahren durch Wilhelm Jordan noch etwas verfeinert. Auch diese Verbesserung
möchte ich mit vorstellen.\\

Wir gehen von einem Lineargleichungssystem $n$-ter Ordnung aus, das in
\textbf{Normalform} angegeben ist. Das bedeutet, wir haben $n$ Gleichungen und
ebensoviele Variablen. Die Variablen sollen \mbox{$x_1, x_2, \ldots , x_n$}
heißen. Damit sieht das Gleichungssystem folgendermaßen aus:
\[\begin{array}{cccccc}
a_{11}x_1& +a_{12}x_2& + \ldots & + a_{1n}x_n&=&b_1 \\
a_{21}x_1& +a_{22}x_2& + \ldots & + a_{1n}x_n&=&b_2 \\
 \vdots  & \vdots    &          & \vdots     &=& \vdots \\
a_{n1}x_1& +a_{n2}x_2& + \ldots & + a_{nn}x_n&=&b_n \\
\end{array}\]
Hierbei kommen \textbf{Doppelindizes} vor, beispielsweise
$a_{21}$\footnote{Gesprochen wird das als "`a Zwei Eins"', nicht als "`a
Einundzwanzig"'.}. Dabei bedeutet die erste Zahl die \textbf{Zeile}, in der der
Koeffizient steht und der zweite die \textbf{Spalte}. Der Koeffizient $a_{21}$
steht also in der zweiten Zeile in der ersten Spalte, der Koeffizient $a_{1n}$
in der 1. Zeile in der $n$-ten Spalte.\\

Wir schauen uns dazu ein Beispiel an. Gegeben sei dieses Gleichungssystem:
\[\begin{array}{|rrrrrcl|}
\hline
(1)&&  3x&-2y&+2z&=&10 \\
(2)&&  4x&+2y&-3z&=&1 \\
(3)&&  2x&-3y&+2z&=&7 \\
\hline
\end{array}\]
In diesem Beispiel wäre \mbox{$x=x_1$}, \mbox{$y=x_2$} und \mbox{$z=x_3$}.
Entsprechend ist \mbox{$a_{11}=3$}, \mbox{$a_{12}=-2$}, \mbox{$a_{13}=2$},
\mbox{$b_1=10$}, usw.\\

Zur Vereinfachung der Schreibarbeit schreibt man das Gleichungssystem in Form
einer \textbf{Matrix} auf. Das sieht dann so aus:
\[ \left( \begin{array}{ccccc}
a_{11}& a_{12}& \ldots & a_{1n}&b_1 \\
a_{21}& a_{22}& \ldots & a_{1n}&b_2 \\
\vdots& \vdots&        & \vdots& \vdots \\
a_{n1}& a_{n2}& \ldots & a_{nn}&b_n \\
\end{array}\right) \]
Es werden also nur die Koeffizienten (einschließlich Vorzeichen) aufgeschrieben,
nicht aber die Variablen und die Gleichheitszeichen.\\
\textbf{Anmerkung:} Die beiden großen Klammern links und rechts gehören
zwingend zur mathematisch korrekten Schreibweise einer Matrix dazu.\\

Für unser Beispiel sieht die Matrix damit folgendermaßen aus:
\[ \left( \begin{array}{rrrr}
3 & -2 & 2 & 10 \\
4 &  2 & -3& 1 \\
2 & -3 & 2 & 7 \\
\end{array}\right) \]
Das Ziel beim Gauß-Jordan-Verfahren besteht darin, die Matrix in folgende Form
zu bringen.
\[ \left( \begin{array}{ccccc}
1 & 0 &\ldots& 0 & k_1 \\
0 & 1 &\ldots& 0 & k_2 \\
\vdots&\vdots&\ddots&\vdots&\vdots \\
0 & 0 &\ldots& 1 & k_n \\
\end{array}\right) \]
Wenn es gelingt, die Matrix so umzuformen, dass vorn in der Matrix nur Nullen
mit Einsen in der Diagonalen stehen, dann stellen die Parameter
\mbox{$k_1 \ldots k_n$} die Lösungen für \mbox{$x_1 \ldots x_n$} dar, denn dazu
würde das Gleichungssystem in dieser Form passen:
\[\begin{array}{cccccc}
1 \cdot x_1 & +0 \cdot x_2 &\ldots& +0 \cdot x_n &=& k_1 \\
0 \cdot x_1 & +1 \cdot x_2 &\ldots& +0 \cdot x_n &=& k_2 \\
\vdots&\vdots&\ddots&\vdots&=&\vdots \\
0 \cdot x_1 & +0 \cdot x_2 &\ldots& +1 \cdot x_n &=& k_n \\
\end{array}\]
Noch deutlicher wird das, wenn das Gleichungssystem zusammengefasst wird:
\[\begin{array}{cccccc}
x_1 & +0   &\ldots& +0     &=& k_1 \\
0   & +x_2 &\ldots& +0     &=& k_2 \\
\vdots&\vdots&\ddots&\vdots&=&\vdots \\
0   & +0   &\ldots& +x_n &=& k_n \\
\end{array}\]
Die $k$-Werte sind dann direkt die Lösungen für die $x$-Werte.
Das Ziel ist also klar, aber wie kommen wir dahin?\\

Zunächst muss oben links in der Matrix eine 1 entstehen. Dazu dividiert man die
erste Zeile durch $a_{11}$. Dem entspricht eine Division der ersten Gleichung
durch $a_{11}$.\\

Es kann nun sein, dass $a_{11}=0$ ist. In diesem Fall müsste man durch Null
dividieren, was ja bekanntermaßen nicht geht. Dann ist es aber möglich, die
erste Zeile (Gleichung) mit einer anderen Zeile (Gleichung) zu tauschen, bei
der der erste Parameter ungleich Null ist. Mindestens in einer Zeile
\textbf{muss} der erste Parameter
ungleich Null sein, anderenfalls ist das Gleichungssystem unterbestimmt und
somit nicht eindeutig lösbar.\\

\newpage  %------------------------------------
Wir führen das nun an unserem Beispiel durch.
\[ \left( \begin{array}{rrrr}
3 & -2 & 2 & 10 \\
4 &  2 & -3& 1 \\
2 & -3 & 2 & 7 \\
\end{array}\right) \]
Da $a_{11}=3$ ist, muss die erste Zeile durch 3 dividiert werden.
\[ \left( \begin{array}{rrrr}
1 & -\frac{2}{3} & \frac{2}{3} & \frac{10}{3} \\
4 &  2 & -3& 1 \\
2 & -3 & 2 & 7 \\
\end{array}\right) \]

Als nächstes müssen unter der 1 in der ersten Spalte Nullen erzeugt werden. Das
geschieht dadurch, dass zu jeder der nachfolgenden Zeilen (Gleichungen) ein
passendes Vielfaches der ersten Zeile (Gleichung) addiert wird, so dass jeweils
vorn die Null entsteht. Was heißt das konkret?\\

Die zweite Zeile muss dazu mit dem $-a_{21}$-fachen der ersten Zeile
multipliziert werden, die dritte mit dem $-a_{31}$-fachen, usw. Das führen
wir nun an dem Beispiel durch.\\

Die zweite Zeile entsteht, indem die erste mit $-4$ multipliziert und
elementweise zur zweiten hinzuaddiert wird.
\[ \left( \begin{array}{rrrr}
1 & -\frac{2}{3} & \frac{2}{3} & \frac{10}{3} \\
0 &  \frac{14}{3}& -\frac{17}{3}& -\frac{37}{3} \\
2 & -3 & 2 & 7 \\
\end{array}\right) \]

Die dritte Zeile entsteht, indem die erste mit $-2$ multipliziert und
elementweise zur dritten hinzuaddiert wird.
\[ \left( \begin{array}{rrrr}
1 &-\frac{2}{3} & \frac{2}{3} & \frac{10}{3} \\
0 & \frac{14}{3}&-\frac{17}{3}&-\frac{37}{3} \\
0 &-\frac{5}{3} & \frac{2}{3} & \frac{1}{3} \\
\end{array}\right) \]

Damit ist der erste Schritt abgeschlossen. Man betrachtet nun die
"`Restmatrix"', die sich ergibt, wenn man die erste Zeile und die erste Spalte
in Gedanken herausstreicht. Das erste Element dieser "`Restmatrix"' ist nun
$a_{22}$. Um dieses zu 1 zu machen und darunter Nullen geht man genau so vor,
wie bei der ersten Zeile beschrieben. Für die dritte und ggf. alle weiteren
Zeilen geht man ebenso vor.\\

Wir wenden das jetzt wieder auf unser Beispiel an. Die zweite Zeile muss durch
$\frac{14}{3}$ dividiert werden. Da man bekanntlich durch einen Bruch
dividiert, indem man mit seinem Kehrwert multipliziert, können wir die zweite
Zeile auch mit $\frac{3}{14}$ multiplizieren. Die Null in der ersten Spalte
wird dadurch nicht beeinflusst.
\[ \left( \begin{array}{rrrr}
1 &-\frac{2}{3} & \frac{2}{3}  & \frac{10}{3} \\
0 & 1           &-\frac{17}{14}&-\frac{37}{14} \\
0 &-\frac{5}{3} & \frac{2}{3}  & \frac{1}{3} \\
\end{array}\right) \]

Nun muss $a_{32}=0$ gemacht werden. Dazu wird das $\frac{5}{3}$-fache der
zweiten Zeile zur dritten hinzuaddiert.
\[ \left( \begin{array}{rrrr}
1 &-\frac{2}{3} & \frac{2}{3}  & \frac{10}{3} \\
0 & 1           &-\frac{17}{14}&-\frac{37}{14} \\
0 & 0           &-\frac{57}{42}&-\frac{171}{42} \\
\end{array}\right) \]
Zum Schluss wird noch die letzte Zeile durch $-\frac{57}{42}$ geteilt, damit
die letzte fehlende 1 in die Diagonale kommt.
\[ \left( \begin{array}{rrrr}
1 &-\frac{2}{3} & \frac{2}{3}  & \frac{10}{3} \\
0 & 1           &-\frac{17}{14}&-\frac{37}{14} \\
0 & 0           & 1            & 3 \\
\end{array}\right) \]

\section{Die Ergänzung des Verfahrens von Jordan}
Im Prinzip könnte man hier schon aufhören, denn aus der dritten Zeile geht
sofort der Wert für \mbox{$x_3=z$} hervor. In eine Gleichung "`übersetzt"'
steht da nämlich \mbox{$1 \cdot x_3=3$}. Das Ergebnis könnte man in die
vorletzte Zeile (Gleichung) einsetzen, um damit sofort die vorletzte Variable
zu berechnen, usw. An dieser Stelle hat Wilhelm Jordan angesetzt und das
Verfahren ergänzt. Man erhält damit die Nullen oberhalb der aus Einsen
bestehenden Diagonale, wie oben beschrieben.\\

Das Verfahren zur Erzeugung dieser Nullen läuft ähnlich dem Verfahren ab, das
wir bis hierher benutzt haben; man fängt nur nicht oben links, sondern unten
rechts an. Genauer: zur ersten Zeile wird das $-a_{1n}$-fache der letzten
($n$-ten) Zeile hinzuaddiert. Dadurch entsteht senkrecht über der untersten 1
in der ersten Zeile eine 0. Alle Elemente davor bleiben erhalten. Das führt man
Zeile für Zeile bis zur $(n-1)$-ten (vorletzten) Zeile durch.\\

Anschließend denkt man sich die letzte Zeile weg und macht entsprechendes mit
den davor liegenden Zeilen, bis überall die gewünschten Nullen stehen. Wir
sehen uns das an unserem Beispiel an.
\[ \left( \begin{array}{rrrr}
1 &-\frac{2}{3} & \frac{2}{3}  & \frac{10}{3} \\
0 & 1           &-\frac{17}{14}&-\frac{37}{14} \\
0 & 0           & 1            & 3 \\
\end{array}\right) \]
Die letzte Zeile muss mit $-\frac{2}{3}$ multipliziert und zur ersten Zeile
addiert werden. Wir erhalten diese Matrix:

\[ \left( \begin{array}{rrrr}
1 &-\frac{2}{3} & 0            & \frac{4}{3} \\
0 & 1           &-\frac{17}{14}&-\frac{37}{14} \\
0 & 0           & 1            & 3 \\
\end{array}\right) \]
Jetzt muss das $\frac{17}{14}$-fache der letzten Zeile zur zweiten addiert
werden.
\[ \left( \begin{array}{rrrr}
1 &-\frac{2}{3} & 0 & \frac{4}{3} \\
0 & 1           & 0 & 1 \\
0 & 0           & 1 & 3 \\
\end{array}\right) \]

Damit ist die hintere "`Nullenspalte"' fertig. Nebenbei bemerkt kann man jetzt
auch schon ablesen, dass \mbox{$x_2=y=1$} ist.\\

Nun kommt die zweite Spalte dran. Über der mittleren 1 muss eine Null
entstehen. Dazu wird zur ersten Zeile das $\frac{2}{3}$-fache der zweiten Zeile
addiert. Wir erhalten dann dieses Ergebnis:
\[ \left( \begin{array}{rrrr}
1 & 0 & 0 & 2 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 3 \\
\end{array}\right) \]

Damit haben wir es geschafft. Die Ergebnisse für die gesuchten Variablen stehen
in der letzten Spalte: \mbox{$x=2$}, \mbox{$y=1$} und \mbox{$z=3$}, oder als
Lösungsmenge: \mbox{$L=\{(2|1|3)\}$}\\

\paragraph{Anmerkung:}
Es gibt eine schöne interaktive Webseite, auf der man sich die Lösung eines
beliebigen Lineargleichungssystems mit allen Zwischenschritten anzeigen lassen
kann:
\begin{center}\ifpdf
\url{https://matrixcalc.org/de/slu.html} \fi \end{center}

\newpage
\section{Das Gauß-Jordan-Verfahren in der Anwendung für Rechenprogramme}
Wir haben gesehen, dass das Verfahren sehr systematisch abläuft. Weiterhin
haben wir gesehen, dass zwischendurch ungünstig handhabbare Zahlenwerte
entstehen, auch wenn es ganzzahlige Ergebnisse gibt. Aus diesen beiden Gründen
eignet sich das Verfahren weniger für die Ausrechnung "`zu Fuß"', sondern eher,
um damit ein Rechnenprogramm für den Computer zu schreiben. Aus diesem Grund
möchte ich die notwendigen Schritte "`computergerecht"' aufschreiben,
allerdings ohne dabei direkt eine bestimmte Programmiersprache zu verwenden.
Der Algorithmus lässt sich in jeder Sprache umsetzen, sei es C,
Assembler oder welche Sprache auch immer.\\

\subsection{Festlegung von Variablen}
Wir gehen davon aus, dass folgende Variablen als \textbf{Integer-Variablen}
definiert sind:
\begin{description}
\item[n:] Die Anzahl der Variablen und Gleichungen
\item[k:] Hilfsvariable für Teilmatritzen
\item[i:] Hilfsvariable für Zeilennummern
\item[j:] Hilfsvariable für Spaltennummern
\end{description}

Weiterhin sei \textbf{a} als ein zweidimensionales Feld mit der Größe
\mbox{\textbf{n}$\mathbf{\times}$\textbf{n+1}}
(n Zeilen, n+1 Spalten) bestehend aus Fließkommavariablen in dieser Form
definiert:
\[ \textnormal{\textbf{a}}= \left( \begin{array}{ccccc}
a_{11}& a_{12}& \ldots & a_{1n}&b_1 \\
a_{21}& a_{22}& \ldots & a_{1n}&b_2 \\
\vdots& \vdots&        & \vdots& \vdots \\
a_{n1}& a_{n2}& \ldots & a_{nn}&b_n \\
\end{array}\right) \]
Auch die \textbf{b}-Werte (die Werte auf der rechten Seite in den zugrunde
liegenden Gleichungen) werden damit als \textbf{a}-Werte -- nämlich als
\textbf{a}$_{i,n+1}$ -- angesprochen. In einem Gleichungssystem 3. Grades
(\textbf{n}=3) beispielsweise wäre dann
\mbox{\textbf{b}$\mathbf{_1}$=\textbf{a}$\mathbf{_{14}}$},
\mbox{\textbf{b}$\mathbf{_2}$=\textbf{a}$\mathbf{_{24}}$} und
\mbox{\textbf{b}$\mathbf{_3}$=\textbf{a}$\mathbf{_{34}}$}. Das erleichtert die
Berechnungen, die ja immer in einer \textbf{kompletten Zeile} stattfinden.\\

\subsection{Die eigentliche Programmieranleitung}
Die Beschreibung des Algorithmus beginnt, nachdem alle Werte in die Matrix
eingetragen sind und auch \textbf{n} die Zahl der Variablen enthält. Der
Algorithmus besteht in zwei aufeinanderfolgenden Teilen. Im ersten wird die
Diagonale mit Einsen und das Dreieck unten links mit Nullen gefüllt, im zweiten
Teil kommen die Nullen oben rechts dazu.\\

\paragraph*{Schritt 1:} Einserdiagonale und Nullen unten links.
\begin{itemize}
\item Führe nachfolgende Befehle für $\mathbf{k=1}$ bis $\mathbf{k=n}$ aus:
  \begin{itemize}
  \item Ist $\mathbf{a_{kk}=0}$? Wenn ja, führe nachfolgende Befehle aus.
    \begin{itemize}
    \item Setze \textbf{i}=\textbf{k+1}
    \item Ist $\mathbf{i>n}$? Wenn ja, brich ab mit der
      Fehlermeldung:"`Das Gleichungssystem ist unterbestimmt!"'
    \item Ist $\mathbf{a_{ik}=0}$? Wenn ja, erhöhe \textbf{i} um eins und prüfe
      erneut. Wenn dabei \mbox{$\mathbf{i>n}$} wird, brich mit der oben
      genannten Fehlermeldung ab. Diese Erhöhungen werden so lange fortgesetzt,
      bis entweder $\mathbf{a_{ik}\not=0}$ ist, oder mit der Fehlermeldung
      abgebrochen wurde.
    \item Tausche die Werte aus Zeile \textbf{i} mit den Werten aus Zeile
      \textbf{k}.
    \end{itemize}
    \item Berechne von $\mathbf{j=n+1}$ rückwärts bis
      \textbf{j=k}:  $\mathbf{a_{kj}=\frac{a_{kj}}{a_{kk}}}$
    \item Falls $\mathbf{k<n}$ ist, führe nachfolgenden Befehl für
      $\mathbf{i=k+1}$ bis $\mathbf{i=n}$ aus.
      \begin{itemize}
      \item Berechne für $\mathbf{j=n+1}$ rückwärts bis $\mathbf{j=k}$:
        $\mathbf{a_{ij}=a_{ij}-a_{kj} \cdot a_{ik}}$
      \end{itemize}
  \end{itemize}
\end{itemize}
Wenn wir hier angekommen sind, ist der erste Teil abgeschlossen; die
Einserdiagonale mit den Nullen darunter ist erzeugt.

\paragraph*{Schritt 2:} Die Nullen oben rechts.
\begin{itemize}
\item Führe folgende Schritte für $\mathbf{k=n}$ rückwärts bis $\mathbf{k=2}$
  durch.
  \begin{itemize}
  \item Führe folgende Schritte für $\mathbf{i=1}$ bis $\mathbf{i=k-1}$ durch.
    \begin{itemize}
    \item Berechne für $\mathbf{j=n+1}$ rückwärts bis $\mathbf{j=k}$:
      $\mathbf{a_{ij}=a_{ij}-a_{kj} \cdot a_{ik}}$
    \end{itemize}
  \end{itemize}
\end{itemize}
Danach stehen alle Lösungen in der letzten Spalte der Matrix.

\end{document}
%\begin{wrapfigure}{r}{9cm}
%\includegraphics[width=\linewidth]{Bilddatei}
%\caption{Bildunterschrift}
%\end{wrapfigure}
%\pagecolor{yellow}    % setzt Hintergrundfarbe für die Seite
%\color{red}           % Schreibt ab hier mit Farbe
%\color[rgb]{0,0.5,0}  % Farbe aus Anteilen zusammensetzen; Anteile: 0..1
%\textcolor{red}{text} % Schreibt vorübergehend mit Farbe
%\fcolorbox{red}{yellow}{Text} % Umrandet Text auf gelb mit rot
%\htmladdnormallink{text}{URL}
%\rput{Winkel}(Drehpunkt){Objekt} % Drehen eines Objektes
