Rozkład LU macierzy polega na rozłożeniu danej macierzy kwadratowej na czynniki na dwie macierze trójkątne, jedną górną macierz trójkątną i jedną dolną macierz trójkątną, tak że iloczyn tych dwóch macierzy daje pierwotną macierz. Został wprowadzony przez Alana Turinga w 1948 roku, który również stworzył maszynę Turinga.

Metoda rozkładu LU polegająca na faktoryzacji macierzy jako iloczynu dwóch macierzy trójkątnych ma różne zastosowania, takie jak rozwiązanie układu równań, który sam w sobie jest integralną częścią wielu zastosowań, takich jak znajdowanie prądu w obwodzie i rozwiązywanie dyskretnych problemów układu dynamicznego ; znajdowanie odwrotności macierzy i znajdowanie wyznacznika macierzy.

Co to jest rozkład LU?

Macierz kwadratową A można rozłożyć na dwie macierze kwadratowe L i U w taki sposób, że A = L U gdzie U jest górną macierzą trójkątną utworzoną w wyniku zastosowania metody eliminacji Gaussa na A, a L jest dolną macierzą trójkątną, której elementy przekątne są równy 1.

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

średnie drzewa

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

Takie, że A = L U tj.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]

Tutaj wartość l_{dwadzieścia jeden}, W_jedenaścieitp. można porównać i znaleźć.

Na czym polega metoda eliminacji Gaussa?

Eliminacja Gaussa, znana również jako eliminacja Gaussa-Jordana, to metoda stosowana w algebrze liniowej do rozwiązywania układów równań liniowych i znajdowania odwrotności macierzy. Został nazwany na cześć matematyka Carla Friedricha Gaussa, a także matematyka Wilhelma Jordana, którzy wnieśli znaczący wkład w jego rozwój.

Zgodnie z metodą eliminacji Gaussa:

1. Każdy wiersz zerowy powinien znajdować się na dole macierzy.
2. Pierwszy niezerowy wpis w każdym wierszu powinien znajdować się po prawej stronie pierwszego niezerowego wpisu w poprzednim wierszu. Metoda ta redukuje macierz do postaci rzutu wierszowego.

Metoda rozkładu LU

Aby przekształcić dowolną macierz kwadratową w dwie macierze trójkątne, tj. jedna z nich jest dolną macierzą trójkątną, a druga górną macierzą trójkątną, możemy wykonać następujące kroki.

• Mając dany zestaw równań liniowych, najpierw przekształć je w postać macierzową A X = C, gdzie A jest macierzą współczynników, X jest macierzą zmiennych, a C jest macierzą liczb po prawej stronie równań.
• Teraz skróć macierz współczynników A, czyli macierz otrzymaną ze współczynników zmiennych we wszystkich podanych równaniach tak, aby dla n zmiennych otrzymaliśmy macierz nXn, do postaci rzutu wierszowego metodą eliminacji Gaussa. Otrzymana w ten sposób macierz to U.
• Aby znaleźć L, mamy dwie metody. Pierwsza polega na przyjęciu pozostałych elementów jako zmiennych sztucznych, ułożeniu równań za pomocą A = LU i rozwiązaniu ich w celu znalezienia tych sztucznych zmiennych. Druga metoda polega na tym, że pozostałe elementy stanowią współczynniki mnożnika, dzięki którym odpowiednie pozycje w macierzy U osiągnęły wartość zerową. (Ta metoda jest trochę trudna do zrozumienia słowami, ale stanie się jasna w poniższym przykładzie)
• Teraz mamy A (macierz współczynników nXn), L (dolna macierz trójkątna nXn), U (górna macierz trójkątna nXn), X (macierz zmiennych nX1) i C (macierz liczb nX1 po prawej stronie- strona równań).
• Dany układ równań to A X = C. Podstawiamy A = L U. Zatem mamy L U X = C. Wstawiamy Z = U X, gdzie Z jest macierzą lub sztucznymi zmiennymi i najpierw rozwiązujemy L Z = C, a następnie rozwiązujemy U X = Z, aby znaleźć X lub wartości zmiennych, co było wymagane.

Przykład rozkładu LU

Rozwiąż następujący układ równań, korzystając z metody rozkładu LU:

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*}

Rozwiązanie: Tutaj mamy 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}

I

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

tak, że A X = C. Teraz najpierw rozważymy

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

i przekonwertuj go do postaci rzutu wierszowego, stosując metodę eliminacji Gaussa. Więc robiąc

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

dostajemy

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}

Teraz, robiąc

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

Dostajemy

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

(Pamiętaj, aby zawsze zachować znak „-” pomiędzy nimi, znak „+” zastąpić dwoma znakami „-”). Otrzymujemy zatem L =

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

i U =

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

(zauważ, że w macierzy L,

l_{21} = 4

pochodzi z (1),

l_{31} = 3

pochodzi z (2) i

jak przekonwertować znak na ciąg

l_{32} = -2

pochodzi z (3)) Zakładamy teraz, że Z

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

i rozwiąż 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}

Więc mamy

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

Rozwiązując, otrzymujemy

z_1 = 1

,

z_2 = 2

I

z_3 = 5

. Teraz rozwiązujemy 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}

Dlatego otrzymujemy

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

,

-10x_3 = 5 .

Zatem rozwiązaniem danego układu równań liniowych jest

x_1 = 1

polecenie arp-a

,

x_2 = 0.5

,

x_3 = -0.5

i stąd macierz X =

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

Ćwiczenie na dekompozycji LU

W rozkładzie LU macierzy

| 2 2 |
| 4 9 |

, jeśli obydwa elementy przekątne U wynoszą 1, wówczas dolny wpis przekątny L22 wynosi (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

Aby zapoznać się z rozwiązaniem, zobacz BRAMA | GATE-CS-2015 (zestaw 1) | Pytanie 65 .

Często zadawane pytania dotyczące rozkładu LU

Na czym polega metoda rozkładu LU?

Dekompozycja LU, skrót od rozkładu dolnego i górnego, to technika faktoryzacji macierzy stosowana do rozbicia macierzy kwadratowej na iloczyn dolnej macierzy trójkątnej (L) i górnej macierzy trójkątnej (U). Jest powszechnie stosowany w celu uproszczenia rozwiązywania układów równań liniowych i obliczania wyznaczników.

Dlaczego rozkład LU jest wyjątkowy?

Rozkład LU jest wyjątkowy, ponieważ umożliwia jednoznaczne rozłożenie macierzy kwadratowej A na dolne i górne macierze trójkątne (L i U), umożliwiając wydajne rozwiązywanie układów liniowych i obliczanie wyznaczników.

Jak oblicza się rozkład LU?

Rozkład LU oblicza się za pomocą eliminacji Gaussa, podczas której przekształca się macierz kwadratową A w dolną (L) i górną (U) macierz trójkątną, wykonując operacje na wierszach, śledząc jednocześnie zmiany w oddzielnych macierzach. Proces ten jest iteracyjny i trwa aż do całkowitego rozkładu A. Metodę ze wszystkimi etapami rozkładu LU podano w artykule.

Kiedy rozkład LU nie jest możliwy?

Rozkład LU może nie być możliwy, gdy macierz A jest pojedyncza (nieodwracalna) lub gdy wymaga obrotu dla stabilności, ale element obrotowy staje się zerem, powodując dzielenie przez zero podczas procesu rozkładu.

Czy są jakieś alternatywy dla rozkładu LU?

Tak, alternatywy dla rozkładu LU obejmują Rozkład Choleskiego dla symetrycznych macierzy dodatnio określonych, rozkładu QR dla macierzy ogólnych oraz metod opartych na wartościach własnych, takich jak rozkład widmowy i rozkład wartości osobliwych (SVD) dla różnych operacji i zastosowań na macierzach.

Czy rozkład LU można zastosować do macierzy innych niż kwadratowe?

Rozkład LU jest zwykle stosowany do macierzy kwadratowych. W przypadku macierzy prostokątnych częściej stosuje się rozkład QR. Jednak odmiany takie jak rozkład LUP mogą również obsługiwać macierze prostokątne, gdzie P jest macierzą permutacji.