Mathematik: Lineare Algebra mit dem Austauschverfahren
Released by matroid on Do. 04. Juni 2020 17:16:25 [Statistics]
Written by lewis - 658 x read [Outline] Printable version Printer-friendly version -  Choose language   
Lineare Algebra

\(\begingroup\) Das Austauschverfahren ist ein allgemeines — inzwischen leider vernachlässigtes — Werkzeug der Linearen Algebra. Mit entsprechenden Anpassungen kann man damit
  • einen Basiswechsel durchführen,
  • den Rang einer Matrix ablesen,
  • Matrizen invertieren,
  • lineare Gleichungssysteme und Matrizengleichungen lösen,
  • Determinanten berechnen,
  • und Eigenvektoren finden.


Der Algorithmus

Das Austauschverfahren beinhaltet folgende (Rechen-)Regeln:
  1. Notiere die Matrix bzw. das erweitere Gleichungssystem in einer Tabelle der Dimension $n\times m$ und bezeichne die Spalten mit $x_1, x_2, ,..., x_m$ und die Zeilen mit $y_1, y_2,...,y_n$.
  2. Wähle in der Iteration $\ell$ in der Zeile $i$ und der Spalte $k$ das Pivotelement $p= a_{i,k} \not = 0$ und markiere dieses in der Tabelle. (Ab der zweiten Iteration muss man darauf achten, dass die Spalte des Pivotelements noch mit $x_k$ und die Zeile mit $y_i$ gekennzeichnet ist.)
  3. Notiere in der Kellerzeile der Pivotspalte $k$ den Kehrwert $1/p$.
  4. Dividiere in den Spalten $s= 1,2,...,m$ mit $s\not = k$ die anderen Elemente der Pivotzeile $a_{i,s}$ durch das negative Pivotelement, und schreibe das Ergebnis $a_{i,s}/(-p)$ in die Kellerzeile.
  5. Notiere für die Iteration $(\ell+1)$ eine neue Tabelle und tausche die Bezeichnungen der Pivotspalte $x_k$ und Pivotzeile $y_i$ aus.
  6. Schreibe in die Pivotzeile $i$ der vorherigen Iteration $\ell$ die Einträge der Kellerzeile.
  7. Ergänze in den Zeilen $z= 1,2,...,n$ mit $z\not = i$ die noch fehlenden Elemente der Pivotspalte $k$ durch den Quotienten $a_{z,k}/p$.
  8. Berechne die fehlenden Elemente $a_{z,s}^{\textrm{neu}} $ durch die Addition der bisherigen Werte $a_{z,s}$ und dem Produkt aus Kellerzeile und Pivotzeile: $a_{z,s}^{\textrm{neu}} =a_{z,s}^{\textrm{alt}}-\frac{a_{i,s}}{p} a_{z,k}$.
  9. Wiederhole die Schritte 2 bis 8 solange ein zulässiges Pivotelement $p\not = 0$ vorhanden ist.
  10. Sortiere falls nötig das Ergebnis.
Als Beispiel soll eine Iteration für eine $3\times 3$ Matrix mit der Pivotzeile $i=3$ und der Pivotspalte $k=2$ genügen: \[ \begin{array}{c|ccc} & x_1 & x_2& x_3\\ \hline y_1 & a_{1,1} & a_{1,2} & a_{1,3} \\ y_2& a_{2,1}& a_{2,2} & a_{2,3} \\ y_3& a_{3,1} & a_{3,2} & a_{3,3} \\ \end{array} \overset{\textrm{Schritt:} 2,3,4}{\leadsto} \begin{array}{c|ccc} & x_1 & x_2& x_3\\ \hline y_1 & a_{1,1} & a_{1,2} & a_{1,3} \\ y_2& a_{2,1}& a_{2,2} & a_{2,3} \\ y_3& a_{3,1} & \fbox{p} & a_{3,3} \\ \hline & -\frac{ a_{3,1}}{p} & \frac{1}{p} & -\frac{ a_{3,3}}{p} \end{array} \overset{\textrm{Schritt:}5,6,7,8}{\leadsto} \begin{array}{c|ccc} & x_1 & y_3& x_3\\ \hline y_1 & a_{1,1}-\frac{ a_{3,1}}{p}a_{1,2} & \frac{a_{1,2}}{p} & a_{1,3} -\frac{ a_{3,3}}{p}a_{1,2} \\ y_2& a_{2,1}-\frac{ a_{3,1}}{p}a_{2,2}& \frac{a_{2,2}}{p} & a_{2,3} -\frac{ a_{3,3}}{p}a_{2,2} \\ x_2& -\frac{ a_{3,1}}{p} & \frac{1}{p} & -\frac{ a_{3,3}}{p} \\ \hline \end{array} \] Im Vergleich zum Gauß-Algorithmen fallen einige Punkte auf:
  • Pivotzeile und Pivotspalte werden jeweils anders behandelt als der Rest der Tabelle.
  • Man arbeitet ausschließlich und systematisch mit Spaltenoperationen.
  • Die Wahl des Pivotelements ist relativ frei, weshalb das Ergebnis eventuell noch umsortiert werden muss.
Eine 'beliebte' Fehlerquelle ist die spezielle Behandlung der Pivotspalte (Regeln 3 & 7). Daher werden hier nur die Berechnungen von Determinanten und Eigenvektoren präsentiert, welche ohne diese Regeln auskommen.

Determinante einer Matrix

Für die Determinante einer quadratischen Matrix $\textbf{A}\in \mathbb{R}^{n\times n}$ entfallen alle Schritte bezüglich der Pivotzeile und Pivotspalte in der neuen Tabelle, so dass die Berechnung und die Notation sehr effektiv ist. Die Determinante erhält man nach $L ≤ n $ Iterationen — abgesehen vom Vorzeichen — aus dem Produkt aller Pivotelemente $p^{[\ell]}$ mit den sukzessiven Tabellen $\ell = 1,2,...,L$. Für das Vorzeichen notiert man die Wahl der Pivotelemente als Permutationsmatrix und zählt die Anzahl $o$ der Tauschoperationen, um diese in eine Einheitsmatrix zu transformieren. Für die Determiante gilt: \[ \det \textbf{A} = (-1)^o \prod_{\ell =1}^{L} p^{[\ell]} \] Kann für eine Matrix $\textbf{A}\in \mathbb{R}^{n\times n}$ ein Austausch in der Iteration $L < n$ nicht mehr durchgeführt werden, so gilt $\det \textbf{A} = 0$.

Beispiel 1

Als Beispiel soll die Matrix \[ \textbf{A}_1=\begin{pmatrix} 2& -3& 4& 3\\ 2& 3& -2& 1\\ 3& 3& 3& 6\\ 2& 4& -3 & 1 \end{pmatrix} \] untersucht werden: \[ \begin{array}{c|cccc} & x_1 & x_2 & x_3 & x_4\\ \hline y_1 & 2& -3& 4& 3\\ y_2 & 2& 3& -2& 1\\ y_3 & \fbox{ 3}& 3& 3& 6\\ y_4 & 2& 4& -3 & 1\\ \hline & 1/3 & -1 & -1 & -2 \end{array}\leadsto \begin{array}{c|ccc} & x_2 & x_3 & x_4\\ \hline y_1 & -5 & 2 & \fbox{ -1}\\ y_2 & 1 & -4 & -3\\ y_4 & 2 & -5 & -3\\ \hline & -5 & 2 & -1 \end{array}\leadsto \begin{array}{c|cc} & x_2 & x_3 \\ \hline y_2 & 16 &\fbox{-10}\\ y_4 & 17 & -11 \\ \hline & 1.6 & -1/10 \end{array}\leadsto \begin{array}{c|c} & x_2 \\ \hline y_4 &\fbox{-0.6}\\ \end{array} \] In der ersten Iteration $\ell = 1$ wird das Pivotelement $a^{[1]}_{3,1}$ gewählt, in der zweiten Iteration $\ell = 2 $ das Pivotelement $a^{[2]}_{4,1}$, etc. Damit ergib sich die Permutationsmatrix \[ \textbf{P}_1 = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 \\ 0 & 1& 0 & 0 \end{pmatrix}. \] Somit sind $o=3$ Spaltenoperationen nötig und es folgt für die Determinante \[ \det \textbf{A}_1 = (-1)^3 \Big( (3)(-1)(-10)(-0.6)\Big) = 18. \]

Eigenvektoren

Für die Eigenvektoren einer quadratischen Matrix $\textbf{A}\in \mathbb{R}^{n\times n}$ bestimmt man durch andere Verfahren alle Eigenwerte $\lambda$ und setzt in Tabelle jeweils die neue Matrix $( \textbf{A}-\lambda \textbf{E})$ ein. Bei der Berechnung entfallen die Schritte bezüglich der Pivotspalte in der nächsten Tabelle. Mindestens ein Austauch ist nicht möglich, da notwendigerweise eine Nullzeile entsteht. Man sortiert die Einträge in die korrekte Reihenfolge und ergänzt für das nicht-getauschte Element eine Eins.

Beispiel 2

Die Matrix \[ \textbf{A}_2 = \begin{pmatrix} 10& 10 &14 & -2\\ -6& -16 & -48& 36\\ 2& 11 &35 &-27\\ 2 & 7 &17 & -9\\ \end{pmatrix} \] hat einen Eigenwert $\lambda=2$. Den zugehörigen Eigenvektor erhält man mit dem Austauschverfahren: \[ \begin{array}{c|cccc} & x_1 & x_2 & x_3 & x_4\\ \hline y_1 &8& 10 &14 & \fbox{-2}\\ y_2 & -6& -18 & -48& 36\\ y_3& 2& 11 &33 &-27\\ y_4 & 2 & 7 &17 & -11\\ \hline & 4 & 5& 7&-1/2 \end{array}\leadsto \begin{array}{c|ccc} & x_1 & x_2 & x_3 \\ \hline x_4 & 4 & 5 & 7 \\ y_2 &138 & 162 & 204 \\ y_3 &-106& -124& -156 \\ y_4& -42& -48 & \fbox{-60} \\ \hline & -7/10 & -4/5 & -1/60 \end{array}\leadsto \begin{array}{c|cc} & x_1 & x_2 \\ \hline x_4 & -0.9 & -0.6 \\ y_2 &-4.8 & \fbox{-1.2} \\ y_3 &3.2& 0.8 \\ x_3& -0.7& -0.8 \\ \hline & -4 & 5/6 \end{array}\leadsto \begin{array}{c|c} & x_1 \\ \hline x_4 & 1.5 \\ x_2 &-4 \\ y_3 &0 \\ x_3& 2.5 \\ \hline & - \end{array} \] Aus der letzten Spalte liest man — nach dem Umsortieren — den Eigenvektor \[ \mathbb{E}(2) = \mathbb{R}\begin{pmatrix} 1, & -4 , & 2.5, & 1.5 \end{pmatrix}^\top \] ab, wobei die nicht-tauschbare $x_1$-Komponente mit Eins belegt wird.

Lösung linearer Gleichungssysteme

Für die Lösung linearer Gleichungssysteme $\textbf{A} \textbf{x} = \textbf{b}$ notiert man die erweiterte Koeffizientenmatrix analog zum Gauß-Algorithmus. Der Vektor $\textbf{b}$ erhält dabei das Label (-1). Sind insgesamt $L$ Iterationen möglich, so kann man durch Umbennen der Unbekannten diese Tabelle erhalten: \[ \begin{array}{c|cccc|cccc|c} &y_1&y_2&...&y_L&x_{L+1}&x_{L+2}&...&x_m& -1\\ \hline x_1 &&&&&&&&&\\ x_2 &&&&&&&&&\\ \vdots &&\textbf{B}&&&&\textbf{C}&&&\textbf{d}\\ x_L &&&&&&&&&\\ \hline y_{L+1} &&&&&&&&&\\ y_{L+2} &&&&&&&&&\\ \vdots &&\textbf{F}&&&&\textbf{0}&&&\textbf{h}\\ y_n &&&&&&&&&\\ \end{array} \] Dabei bezeichnen $\textbf{B}$, $\textbf{F}$, $\textbf{C}$ die berechneten Matrizen und $\textbf{0}$ eine Nullmatrix in den entsprechenden Dimensionen. Die letzte Spalte enthält als Ergebnis der Umformungen von $\textbf{b}$ die beiden (Teil-)Vektoren $\textbf{d}$ und $\textbf{h}$.
  • Falls $\textbf{h} \not = \textbf{0}$ ist, hat das System $\textbf{A} \textbf{x} = \textbf{b}$ keine Lösung.
  • Falls $\textbf{h} = \textbf{0}$ ist, existiert eine Lösung der Form \[ \begin{pmatrix} x_1\\ \vdots\\ x_L \end{pmatrix} = \textbf{C}\begin{pmatrix} x_{L+1}\\ \vdots\\ x_n \end{pmatrix}-\textbf{d} \] mit (n-L) freien Parametern. Für n=L erhält man einen eindeutigen Lösungsvektor $\textbf{x} =- \textbf{d}$. Da man die beiden Matrizen $\textbf{B}$ und $\textbf{F}$ für die Lösung nicht benötigt, kann man auch hier auf die genutzten Pivotspalten verzichten.

Beispiel 3

Um alle Möglichkeiten eines Gleichungssystems an einem Beispiel zu demonstrieren, werden 2 Parameter $\mu,\nu \in \mathbb{R}$ in die Aufgabenstellung einführt. Es soll das Gleichungsystem \[ \textbf{A}_3\textbf{x} = \textbf{b} \qquad \Leftrightarrow \qquad \begin{pmatrix} 0& 0 & 1 & 1\\ 1 & 2 & 0 & -1\\ 0 & -1 & 2 & 1 \\ 0 & 1 & 0 & \mu \end{pmatrix}\textbf{x} = \begin{pmatrix} 3\\ 2\\ 1\\ \nu \end{pmatrix} \] untersucht werden. Das Austauschverfahren liefert: \[ \begin{array}{c|cccc|c} &x_1 &x_2&x_3& x_4 & -1\\ \hline y_1 & 0 & 0 & \fbox{1} & 1 & 3 \\ y_2 & 1 & 2 & 0 & -1 & 2 \\ y_3 & 0 & -1 & 2 & 1 & 1\\ y_4 & 0 & 1 & 0 & \mu & \nu\\ \hline & 0&0&1&-1&-3 \end{array}\leadsto \begin{array}{c|ccc|c} &x_1 &x_2& x_4 & -1\\ \hline x_3 & 0 & 0 & -1 & -3 \\ y_2 & 1 & 2 & -1 & 2 \\ y_3 & 0 & \fbox{-1} & -1 & -5\\ y_4 & 0 & 1 & \mu & \nu\\ \hline & 0&-1&-1&-5 \end{array}\leadsto \begin{array}{c|cc|c} &x_1 & x_4 & -1\\ \hline x_3 & 0 & -1 & -3 \\ y_2 & \fbox{1} & -3 & -8 \\ x_2 & 0 & -1 & -5\\ y_4 & 0 & \mu-1 & \nu-5\\ \hline & 1&3&8 \end{array} \leadsto \begin{array}{c|c|c} & x_4 & -1\\ \hline x_3 & -1 & -3 \\ x_1 & 3 & 8 \\ x_2 & -1 & -5\\ y_4 & \mu-1 & \nu-5\\ \hline & & \end{array} \]
  • Falls $\mu= 1$ und $\nu\not = 5$ gilt, kann der letzte Austausch nicht durchgeführt werden, und das Gleichungssystem \[\begin{pmatrix} 0& 0 & 1 & 1\\ 1 & 2 & 0 & -1\\ 0 & -1 & 2 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}\textbf{x} = \begin{pmatrix} 3\\ 2\\ 1\\ \nu \end{pmatrix} \] ist nicht-lösbar.
  • Falls $\mu= 1$ und $\nu = 5$ gilt, enthält die letzte Zeile keine neue Information und es liegt unterbestimmtes System vor, welches durch \[ \begin{pmatrix} x_1\\ x_2 \\x_3 \end{pmatrix}=\begin{pmatrix} 3\\-1\\-1 \end{pmatrix}x_4-\begin{pmatrix} 8\\-5\\-3 \end{pmatrix} \] gelöst wird. Dies entspricht dem Gleichungssytem: \[ \begin{pmatrix} 0& 0 & 1 & 1\\ 1 & 2 & 0 & -1\\ 0 & -1 & 2 & 1\\ 0 & 1 & 0 & 1 \end{pmatrix}\begin{pmatrix} 3x_4-8\\ -x_4+5\\ -x_4+3\\ x_4 \end{pmatrix} =\begin{pmatrix} 3\\2\\ 1 \\ 5 \end{pmatrix}. \]
  • Für $\mu \not = 1$ kann noch ein weiterer Austauschschritt durchgeführt werden. Als Beispiel soll hier $\mu = 4$ und $\nu = 8$ gewählt werden: \[ \begin{array}{c|c|c} & x_4 & -1\\ \hline x_3 & -1 & -3 \\ x_1 & 3 & 8 \\ x_2 & -1 & -5\\ y_4 & 3 & 3\\ \hline & 1/3&-1 \end{array}\leadsto \begin{array}{c|c} & -1\\ \hline x_3 & -2 \\ x_1 & 5 \\ x_2 & -4\\ x_4 & -1\\ \hline & \end{array} \] Der Lösungsvektor lautet unter Beachtung des Vorzeichens: $\textbf{x} = -\textbf{d} = -\begin{pmatrix} 5 & -4 & -2 & -1 \end{pmatrix}^ \top$. Dies entspricht dem Gleichungssystem \[\begin{pmatrix} 0& 0 & 1 & 1\\ 1 & 2 & 0 & -1\\ 0 & -1 & 2 & 1 \\ 0 & 1 & 0 & 4 \end{pmatrix}\begin{pmatrix} -5 \\ 4 \\ 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 3\\ 2\\ 1\\ 8 \end{pmatrix}. \]

Fazit

Trotz der 'komplizierten Rechenregeln' sollte das Austauschverfahren nicht vernachlässigt werden. Vor allem die manuelle Berechnung von Determinanten verdient eine nähere Betrachtung. Durch den Wegfall von Pivotzeile und Pivotspalte sind deutlich weniger Elemente zu berechnen und zu notieren als in anderen Methoden. Im Idealfall erkennt man eine singuläre Matrix bereits vor der letzten Tabelle ($ \ell = n$). Die Untersuchung der Permutationsmatrix kann ignoriert werden, wenn man die Pivotelemente entsprechend der natürlichen Reihenfolge wählt. Für die Eigenvektoren ist der Aufwand eventuell höher als im Gaußverfahren, die Berechnung erfolgt aber sehr systematisch und lässt sich leicht als Programm umsetzten.
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 658
 
Aufrufstatistik des Artikels
Insgesamt 51 externe Seitenaufrufe zwischen 2020.11 und 2021.08 [Anzeigen]
DomainAnzahlProz
https://google.com2752.9%52.9 %
https://www.bing.com1325.5%25.5 %
https://duckduckgo.com47.8%7.8 %
https://google.at12%2 %
https://www.ecosia.org611.8%11.8 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 4 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.07.03-2021.08.04 (4x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 40 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
202101-06 (13x)https://google.com/
202103-03 (9x)https://google.com/search?q=austauschverfahren matrizen erklärung
202103-03 (7x)https://www.bing.com/search?pc=COSP
202103-06 (6x)https://www.ecosia.org/
202101-06 (5x)https://www.bing.com/

[Top of page]

"Mathematik: Lineare Algebra mit dem Austauschverfahren" | 4 Comments
The authors of the comments are responsible for the content.

Re: Lineare Algebra mit dem Austauschverfahren
von: Gerhardus am: So. 07. Juni 2020 14:26:51
\(\begingroup\)Die Werte im Beispiel-Bild nach Schritt 5,6,7,8 stimmen nicht mit der korrekten Vorgabe von Schritt 8 des Algorithmus überein. Hier ist eine Korrektur notwendig. Für die Schule wäre etwas mehr Erklärung vorteilhaft. \(\endgroup\)
 

Re: Lineare Algebra mit dem Austauschverfahren
von: StefanVogel am: So. 07. Juni 2020 16:44:46
\(\begingroup\)Hallo lewis, auch ich bin ein großer Fan von diesem Verfahren und damit sind wir nicht allein, siehe Wikipedia: Pivotverfahren - Beispiele - Eine direkte Umsetzung. Ergänzen möchte ich eine Variante, in der Pivotzeile und -spalte nicht extra betrachtet werden müssen, so dass die Tabelle "in einem Rutsch" neu berechnet werden kann ohne Rücksicht darauf, ob gerade eine Pivotzeile oder Spalte erreicht ist. Dazu schreibe ich die Pivotzeile nochmal unter die Tabelle mit der Bezeichnung \(\overline{a}_{i,s}\), die Pivotspalte rechts neben die Tabelle mit der Bezeichnung \(\overline{a}_{z,k}\) und das Pivotelement \(p=a_{i,k}\) auf das übrige freie Feld rechts unter der Tabelle. Dann noch vom \(p\) am unteren Rand eine 1 subtrahieren und zum \(p\) am rechten Rand eine 1 addieren \(\begin{array}{c|ccc|c} & x_1 & x_2& x_3 & \overline{a}_{z,k}\\ \hline y_1 & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,2}\\ y_2& a_{2,1}& a_{2,2} & a_{2,3} & a_{2,2}\\ y_3& a_{3,1} & \fbox{p} & a_{3,3} & p+1\\ \hline \overline{a}_{i,s}& a_{3,1} & p-1 & a_{3,3} & p \end{array} \), dann kann die Tabelle neu berechnet werden mit \(a_{z,s}^{\textrm{neu}} =a_{z,s}^{\textrm{alt}}-\overline{a}_{z,k} \cdot p^{-1} \cdot \overline{a}_{i,s}\). Viele Grüße, Stefan \(\endgroup\)
 

Re: Lineare Algebra mit dem Austauschverfahren
von: Goswin am: Mo. 08. Juni 2020 15:11:45
\(\begingroup\)siehe dazu auch: Ganzzahlige Determinantenberechnung\(\endgroup\)
 

Re: Lineare Algebra mit dem Austauschverfahren
von: lewis am: Do. 11. Juni 2020 12:01:31
\(\begingroup\)Vielen Dank für die Rückmeldungen und Hinweise. @Gerhardus Ich habe den genannten Fehler im Rechenschema korrigiert. Eine Bearbeitung für Schüler werde ich noch überdenken. @StefanVogel In der nächsten Zeit werde ich den Artikel um die linearen Gleichungssysteme mit Beispielen ergänzen. @Goswin Das ist eine schlaue Modifikation des Austauschverfahrens, die ich noch nicht kannte. Man spart sich die Division und die Tabellenbezeichnung.👍 Grüße lewis\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]