Die LU-Zerlegung einer Matrix ist die Faktorisierung einer gegebenen quadratischen Matrix in zwei Dreiecksmatrizen, eine obere Dreiecksmatrix und eine untere Dreiecksmatrix, sodass das Produkt dieser beiden Matrizen die ursprüngliche Matrix ergibt. Sie wurde 1948 von Alan Turing eingeführt, der auch die Turing-Maschine entwickelte.

Die LU-Zerlegungsmethode zur Faktorisierung einer Matrix als Produkt zweier Dreiecksmatrizen hat verschiedene Anwendungen, beispielsweise die Lösung eines Gleichungssystems, das selbst ein integraler Bestandteil vieler Anwendungen ist, beispielsweise der Stromfindung in einem Schaltkreis und der Lösung diskreter dynamischer Systemprobleme ; Finden der Umkehrung einer Matrix und Finden der Determinante der Matrix.

Was ist LU-Zerlegung?

Eine quadratische Matrix A kann in zwei quadratische Matrizen L und U zerlegt werden, sodass A = L U ist, wobei U eine obere Dreiecksmatrix ist, die als Ergebnis der Anwendung der Gauß-Eliminierungsmethode auf A gebildet wurde, und L eine untere Dreiecksmatrix mit diagonalen Elementen ist gleich 1.

Für A =egin{bmatrix} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{bmatrix} .

Konvertieren Sie ein int in einen String in C++

Wir haben L = egin{bmatrix} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 1 end{bmatrix} und U =egin{bmatrix} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{bmatrix} ;

So dass A = L U, d. h.left[egin{array}{lll} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{array} ight]=left[egin{array}{lll} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 0 end{array} ight] cdot left[egin{array}{ccc} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{array} ight]

Hier ist der Wert von l_{einundzwanzig}, In_elfusw. können verglichen und gefunden werden.

Was ist die Gauß-Eliminationsmethode?

Die Gaußsche Eliminierung, auch bekannt als Gauß-Jordan-Eliminierung, ist eine Methode, die in der linearen Algebra verwendet wird, um lineare Gleichungssysteme zu lösen und die Umkehrung einer Matrix zu finden. Es ist nach dem Mathematiker Carl Friedrich Gauß und dem Mathematiker Wilhelm Jordan benannt, die maßgeblich zu seiner Entwicklung beigetragen haben.

Nach der Gauß-Eliminationsmethode:

1. Jede Nullzeile sollte sich am unteren Rand der Matrix befinden.
2. Der erste Nicht-Null-Eintrag jeder Zeile sollte sich auf der rechten Seite des ersten Nicht-Null-Eintrags der vorhergehenden Zeile befinden. Diese Methode reduziert die Matrix auf die Zeilenstufenform.

LU-Zerlegungsmethode

Um eine beliebige quadratische Matrix in zwei Dreiecksmatrizen umzuwandeln, d. h. eine ist eine untere Dreiecksmatrix und die andere eine obere Dreiecksmatrix, können wir die folgenden Schritte verwenden.

• Konvertieren Sie einen gegebenen Satz linearer Gleichungen zunächst in die Matrixform A X = C, wobei A die Koeffizientenmatrix, X die Variablenmatrix und C die Zahlenmatrix auf der rechten Seite der Gleichungen ist.
• Reduzieren Sie nun die Koeffizientenmatrix A, d. h. die aus den Koeffizienten der Variablen in allen gegebenen Gleichungen erhaltene Matrix, so dass wir für „n“ Variablen eine nXn-Matrix haben, und zwar mithilfe der Gauß-Eliminationsmethode auf Zeilenstufenform. Die so erhaltene Matrix ist U.
• Um L zu finden, haben wir zwei Methoden. Die erste besteht darin, die verbleibenden Elemente als künstliche Variablen anzunehmen, Gleichungen mit A = L U aufzustellen und sie zu lösen, um diese künstlichen Variablen zu finden. Die andere Methode besteht darin, dass die verbleibenden Elemente die Multiplikatorkoeffizienten sind, aufgrund derer die jeweiligen Positionen in der U-Matrix Null wurden. (Diese Methode ist mit Worten etwas schwierig zu verstehen, wird aber im folgenden Beispiel deutlich)
• Nun haben wir A (die nXn-Koeffizientenmatrix), L (die nXn untere Dreiecksmatrix), U (die nXn obere Dreiecksmatrix), X (die nX1-Variablenmatrix) und C (die nX1-Zahlenmatrix auf der rechten Seite). Handseite der Gleichungen).
• Das gegebene Gleichungssystem ist A X = C. Wir ersetzen A = L U. Somit gilt L U X = C. Wir setzen Z = U X, wobei Z eine Matrix oder eine künstliche Variable ist, und lösen zuerst nach L Z = C und dann nach auf U X = Z, um X oder die Werte der erforderlichen Variablen zu finden.

Beispiel einer LU-Zerlegung

Lösen Sie das folgende Gleichungssystem mit der LU-Zerlegungsmethode:

egin{equation*} x_1 + x_2 + x_3 = 1 end{equation*} egin{equation*} 4x_1 + 3x_2 – x_3 = 6 end{equation*} egin{equation*} 3x_1 + 5x_2 + 3x_3 = 4 end{equation*}

Lösung: Hier gilt A =

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} , X = egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

Und

C = egin{bmatrix} 1 6 4 end{bmatrix}

so dass A X = C. Nun betrachten wir zunächst

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix}

und konvertieren Sie es mithilfe der Gauß-Eliminierungsmethode in eine Zeilenstufenform. Also, indem man es tut

egin{equation} R_2 o R_2 – 4R_1 end{equation} egin{equation} R_3 o R_3 – 3R_1 end{equation}

wir bekommen

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} sim

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 2 & 0 end{bmatrix}

Nun, indem ich es tue

egin{equation} R_3 o R_3 – (-2)R_2 end{equation}

Wir bekommen

sim egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(Denken Sie daran, immer das Zeichen „-“ dazwischen zu lassen und das Zeichen „+“ durch zwei Zeichen „-“ zu ersetzen.) Daher erhalten wir L =

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix}

und U =

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(Beachten Sie, dass in der L-Matrix

l_{21} = 4

ist aus (1),

l_{31} = 3

ist aus (2) und

l_{32} = -2

ist aus (3)) Nun nehmen wir Z an

= egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

und löse L Z = C.

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix} egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

= egin{bmatrix} 1 6 4 end{bmatrix}

Also haben wir

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

array.sort in Java

Lösen, wir bekommen

z_1 = 1

,

z_2 = 2

Und

z_3 = 5

. Jetzt lösen wir U X = Z

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix} egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

= egin{bmatrix} 1 2 5 end{bmatrix}

Deshalb bekommen wir

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

,

-10x_3 = 5 .

Somit lautet die Lösung des gegebenen linearen Gleichungssystems

x_1 = 1

,

Numpy-Punktprodukt

x_2 = 0.5

,

x_3 = -0.5

und daher die Matrix X =

egin{bmatrix} 1 0.5 -0.5 end{bmatrix}

Übung zur LU-Zerlegung

In der LU-Zerlegung der Matrix

| 2 2 |
| 4 9 |

, wenn die Diagonalelemente von U beide 1 sind, dann ist der untere Diagonaleintrag l22 von L (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

Zur Lösung siehe TOR | GATE-CS-2015 (Set 1) | Frage 65 .

FAQs zur LU-Zerlegung

Was ist die LU-Zerlegungsmethode?

LU-Zerlegung, kurz für Lower-Upper-Zerlegung, ist eine Matrixfaktorisierungstechnik, mit der eine quadratische Matrix in das Produkt einer unteren Dreiecksmatrix (L) und einer oberen Dreiecksmatrix (U) zerlegt wird. Es wird häufig verwendet, um die Lösung linearer Gleichungssysteme und die Berechnung von Determinanten zu vereinfachen.

Warum ist die LU-Zerlegung einzigartig?

Die LU-Zerlegung ist einzigartig, da sie eine Möglichkeit bietet, eine quadratische Matrix A eindeutig in untere und obere Dreiecksmatrizen (L und U) zu faktorisieren, was eine effiziente Lösung linearer Systeme und Determinantenberechnungen ermöglicht.

Wie wird die LU-Zerlegung berechnet?

Die LU-Zerlegung wird mithilfe der Gaußschen Eliminierung berechnet, wobei Sie eine quadratische Matrix A in untere (L) und obere (U) Dreiecksmatrizen umwandeln, indem Sie Zeilenoperationen ausführen und dabei die Änderungen in separaten Matrizen verfolgen. Dieser Prozess ist iterativ und wird fortgesetzt, bis A vollständig zerlegt ist. Die Methode mit allen Schritten zur LU-Zerlegung ist im Artikel angegeben.

Wann ist eine LU-Zerlegung nicht möglich?

Eine LU-Zerlegung ist möglicherweise nicht möglich, wenn die Matrix A singulär (nicht invertierbar) ist oder aus Stabilitätsgründen eine Pivotierung erfordert, aber das Pivotelement Null wird, was während des Zerlegungsprozesses zu einer Division durch Null führt.

Gibt es Alternativen zur LU-Zerlegung?

Ja, Alternativen zur LU-Zerlegung umfassen Cholesky-Zersetzung für symmetrische positiv definite Matrizen, QR-Zerlegung für allgemeine Matrizen und eigenwertbasierte Methoden wie Spektralzerlegung und Singularwertzerlegung (SVD) für verschiedene Matrixoperationen und -anwendungen.

Kann die LU-Zerlegung auf nichtquadratische Matrizen angewendet werden?

Die LU-Zerlegung wird typischerweise auf quadratische Matrizen angewendet. Bei rechteckigen Matrizen wird häufiger die QR-Zerlegung verwendet. Variationen wie die LUP-Zerlegung können jedoch auch rechteckige Matrizen verarbeiten, wobei P eine Permutationsmatrix ist.