Rechner für Dreiecksmatrix

Dreiecksmatrix unter Verwednung von Gauß- und Bareiss-Verfahren.

Unten gibt es zwei Rechner für Dreiecksmatrizen.
Der erste verwendet das Gauß-Verfahren, der zweite nutzt das Bareiss-Verfahren. Eine Beschreibung der Verfahren und deren Theorie kann man weiter unten finden.

PLANETCALC, Dreiecksmatrix  (Gauß Verfahren)

Dreiecksmatrix (Gauß Verfahren)

Zahlen nach dem Dezimalpunkt: 4
Dreiecksmatrix (Gauß Verfahren)
 
Dreiecksmatrix (Gauß Verfahren mit maximaler Auswahl in einer Spalte)
 
Dreiecksmatrix (Gauß Verfahren mit maximaler Auswahl in der gesamten Matrix)
 



PLANETCALC, Dreiecksmatrix (Bareiss Verfahren)

Dreiecksmatrix (Bareiss Verfahren)

Zahlen nach dem Dezimalpunkt: 4
Dreiecksmatrix (Bareiss Verfahren)
 
Dreiecksmatrix (Bareiss- Verfahren mit maximaler Auswahl in einer Spalte)
 
Dreiecksmatrix (Bareiss-Verfahren mit maximaler Auswahl in der gesamten Matrix)
 



Zuerst gibt es eine Notation einer Dreiecksmatrix oder Zeilenstufenmatrix:
Die Matrix hat eine Zeilenstufenform, wenn:

  1. Alle Zeilen mit Null, wenn es welche gibt, am unteren Ende der Matrix stehen
  2. Der Zeilenführer (die erste nicht-Null Zahl von links, auch Pivot genannt) von einer Nichtnull Riehe ist immer rechts von dem Zeilenführer der obenliegenden Zeile
  3. Alle nicht-Nullen Zeilen (Zeilen mit mindestens einem nicht-Null Element) sind über den Zeilen, die nur aus Nullen bestehen.

Ein Beispiel einer Zeilenstufenmatrix:
1 0 2 5
0 3 0 0
0 0 0 4
Die Notation einer Dreiecksmatrix ist schmaler und wird nur für quadratische Matrizen verwendet. „Eine Dreiecksmatrix ist eine quadratische Matrix, wo alle Elemente unter Hauptdiagonale Nullen sind.“

Ein Beispiel für eine obere Dreiecksmatrix:
1 0 2 5
0 3 1 3
0 0 4 2
0 0 0 3
Übrigens, die Determinante einer Dreiecksmatrix wird einfach durch das Multiplizieren aller diagonalen Elemente berechnet
Man kann sich fragen, was an einer Zeilenstufen (oder Dreiecks-) Matrix so interessant ist. Diese beiden Matrizen haben eine erstaunliche Eigenschaft – eine rechteckige Matrix kann mit einer elementaren Transformation in eine Zeilenstufenmatrix reduziert werden.

So was ist diese elementare Transformation?
Elementare Matrixtransformationen sind die folgenden Operationen:

  1. Zeilentausch (eine Zeile innerhalb der Matrix kann mit einer anderen Zeile getauscht werden)
  2. Zeilenmultiplikation (jedes Element in einer Zeile kann mit einer nicht-Null Konstanten multipliziert werden)
  3. Zeilenaddition (eine Zeile kann mit der Summe von dieser Zeile und das Vielfache einer anderen Zeile ersetzt werden)

Was jetzt?
Elementare Matrixtransformationen behalten die Äquivalenz der Matrizen bei. Und wenn man sich daran erinnert, dass das System der linearen algebraischen Gleichungen nur in einer Matrixform geschrieben werden, bedeutet dies, dass die elementaren Matrixtransformationen nicht die Lösungsmengen des linearen algebraischen Gleichungssystem , welche diese Matrix darstellt, verändert.
Durch die Triangulation der AX=B linearen Gleichungsmatrix zu A'X = B', das heißt mit der entsprechenden Spalte-B Transformation, kann man die sogenannte „Rücksubstitution“ durchführen.

Um dies zu erklären, verwenden wir die obige Matrix und schreiben das Gleichungssystem in eine gemeinsame Form um (die Spalte B wurde von mir erstellt):

1*x_1 + 0*x_2 + 2 * x_3 + 5 * x_4 = 10 \\ 0*x_1 + 3*x_2 + 1 * x_3 + 3 * x_4 = 7 \\ 0*x_1 + 0*x_2 + 4 * x_3 + 2 * x_4 = 5 \\ 0*x_1 + 0*x_2 + 0 * x_3 + 3 * x_4 = 9

Es ist klar, dass man zuerst x_4 finden muss, und dann in die vorherige Gleichung einsetzt, dann x_3 suchen usw., - von der letzten Gleichung zur ersten. Das ist, was man als Rücksubstitution bezeichnet.

Dieser Zeilenreduktionsalgorithmus wird auch als Gauß-Verfahren bezeichnet, Das Gauß-Verfahren ist ein klassisches Verfahren, um lineare Gleichungen zu lösen. Es wird aus das Gaußsche Eliminierungsverfahren genannt, da es ein Verfahren ist der sukzessiven Eliminierung von Variablen ist. Zusammen mit den elementaren Transformationen kann man ein Gleichungssystem in eine Zeilenstufen (oder Dreiecks) Form reduzieren, wo alle Variablen platziert sind (vom Start zum Ende).

Nun ein paar Gedanken zu diesem Verfahren.
Wie kann man die Variable x_1 in der zweiten Gleichung gleich Null haben?
Indem man die erste Gleichung davon subtrahiert, dann mit dem Faktor \frac{a_{21}}{a_{11}} multipliziert.
Hier ist ein Beispiel

2*x_1 + 3*x_2 + 4 * x_3 = 10 \\ 6*x_1 + 3*x_2 - 4 * x_3 = 7

Null x_1 in der ersten Gleichung

6*x_1 + 3*x_2 - 4 * x_3 - \frac{6}{2}(2*x_1 + 3*x_2 + 4 * x_3)= 7 - \frac{6}{2}10 \\ 6*x_1 + 3*x_2 - 4 * x_3 - 6*x_1 - 9*x_2 - 12 * x_3 = 7 - 30 \\ -6*x_2 - 16 * x_3 = -23

Es gibt kein x_1 in der zweiten Gleichung.
Generell kann das Gauß-Verfahren wie folgt dargestellt werden:

 \begin{matrix}For\, j = 0,..., N-2 \\ \qquad \qquad For\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \vec{a_i} - \frac{a_{ij}}{a_{jj}} \vec{a_j} \end{matrix}

wobei N – Zeilendimension ist,

\vec{a_i} - i-Zeile,
a_{ij} - Element in i Zeile, j Spalte

Dies scheint ein tolles Verfahren zu sein, jedoch gibt es ein Problem – die Division durch math>a{jj} die in der Formel vorkommt. Erstens, falls ein diagonales Element gleich Null ist, funktioniert das Verfahren nicht. Zweitens, während der Berechnung wird die Abweichung steigen, je weiter umso höher. Daher wird das Ergebnis nicht genau sein.
Für die Abweichungsreduktion werden dann Modifikation zum Gauß-Verfahren verwendet. Dies basieren darauf, dass je größer der Nenner ist, desto kleiner die Abweichung ist. Diese Modifikation sind Gauß-Verfahren mit der maximalen Auswahl in einer Spalte und das Gauß-Verfahren mit der maximalen Auswahl für die gesamte Matrix. Wie die Namen andeuten, wir vor jedem Stamm des Variablenausschluss das Element mit dem Maximalwert für eine Zeile (oder gesamte Matrix) gesucht und die Zeilenpermutation durchgeführt, so dass es mit a
{jj} die Position wechselt.

Jedoch gibt es eine radikale Veränderung des Gauß-Verfahren – das Bareiss Verfahren.
Wie kann man die Division entfernen? Durch das Multiplizieren der Reihe \vec{a_i} durch a_{jj}, vor der Subtraktion. Danach muss man \vec{a_i} subtrahieren, und dann ohne die Division mit a_{ij} multiplizieren.
 \vec{a_i} \leftarrow a_{jj}\vec{a_i} - a_{ij} \vec{a_j} .
Dies sieht gut aus, aber es gibt ein Problem, das ein Elementwert durch die Berechnung steigt.

Bareiss ermöglicht es, den obigen Ausdruck durch a_{j-1,j-1} zu dividieren, und hat gezeigt, dass für die anfänglichen Matrixelemente mit ganzen Zahlen auch nach dem Ergebnis ganze Zahlen hat. Dies wird auch für die Null Zeile a_{-1,-1}=1 angenommen.

Das der Bareiss Algorithmus integrale Elemente einer Anfangsmatrix in eine Dreiecksmatrix mit integralen Elementen reduzieren kann, z.B. ohne Abweichungsakkumulation, ist eine sehr wichtige Eigenschaft für maschinelle Arithmetik.

Der Bareiss-Algorithmus kann folgendermaßen dargestellt werden:
 \begin{matrix} a_{-1,-1}=1 \\For\, j = 0,..., N-2 \\ \qquad \qquad For\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \frac{a_{jj}\vec{a_i} - a_{ij} \vec{a_j}}{a_{j-1,j-1}} \end{matrix}

Der Algorithmus kann wie das Gauß-Verfahren mit der maximalen Auswahl einer Spalte (oder gesamten Matrix) und einer Neuordnung der entsprechenden Zeile (Zeilen oder Spalten) modifiziert werden.

URL zum Clipboard kopiert
PLANETCALC, Rechner für Dreiecksmatrix

Kommentare