LU-nedbrydning af en matrix er faktoriseringen af ​​en given kvadratisk matrix i to trekantede matricer, en øvre trekantet matrix og en nedre trekantet matrix, således at produktet af disse to matricer giver den oprindelige matrix. Den blev introduceret af Alan Turing i 1948, som også skabte Turing-maskinen.

LU-dekomponeringsmetode til faktorisering af en matrix som et produkt af to trekantede matricer har forskellige anvendelser såsom en løsning af et ligningssystem, som i sig selv er en integreret del af mange applikationer såsom at finde strøm i et kredsløb og løsning af diskrete dynamiske systemproblemer ; at finde det inverse af en matrix og finde determinanten af ​​matrixen.

Hvad er L U-nedbrydning?

En kvadratisk matrix A kan dekomponeres i to kvadratiske matricer L og U, således at A = L U hvor U er en øvre trekantet matrix dannet som et resultat af at anvende Gauss Elimination Method på A, og L er en nedre trekantet matrix med diagonale elementer. lig med 1.

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

præstationstest

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

Sådan at A = L U dvs.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]

Her er værdien af ​​l_enogtyve, i_elleveosv. kan sammenlignes og findes.

Hvad er Gauss eliminationsmetode?

Gaussisk Elimination, også kendt som Gauss-Jordan Elimination, er en metode, der bruges i lineær algebra til at løse systemer af lineære ligninger og finde det inverse af en matrix. Det er opkaldt efter matematikeren Carl Friedrich Gauss og også matematikeren Wilhelm Jordan, som ydede betydelige bidrag til udviklingen.

Ifølge Gauss eliminationsmetoden:

1. Enhver nulrække skal være nederst i matrixen.
2. Den første ikke-nul-indgang i hver række skal være på højre side af den første ikke-nul-indgang i den foregående række. Denne metode reducerer matrix til række-echelonform.

LU nedbrydningsmetode

For at fremstille enhver kvadratisk matrix i to trekantede matrixer, dvs. den ene er en nedre trekantet matrix, og den anden er en øvre trekantet matrix, kan vi bruge følgende trin.

• Givet et sæt lineære ligninger, konverter dem først til matrixform A X = C hvor A er koefficientmatrixen, X er den variable matrix og C er matrixen af ​​tal på højre side af ligningerne.
• Reducer nu koefficientmatricen A, dvs. matrixen opnået fra koefficienterne for variabler i alle de givne ligninger, således at for 'n' variable har vi en nXn matrix, for at række echelonform ved hjælp af Gauss Elimination Method. Den således opnåede matrix er U.
• For at finde L har vi to metoder. Den første er at antage de resterende elementer som nogle kunstige variable, lave ligninger ved hjælp af A = L U og løse dem for at finde disse kunstige variable. Den anden metode er, at de resterende elementer er multiplikatorkoefficienterne, på grund af hvilke de respektive positioner blev nul i U-matricen. (Denne metode er lidt vanskelig at forstå med ord, men ville blive tydelig i eksemplet nedenfor)
• Nu har vi A (nXn-koefficientmatricen), L (den nXn nedre trekantede matrix), U (den nXn øvre trekantede matrix), X (nX1-matricen af ​​variable) og C (nX1-matrixen af ​​tal til højre- side af ligningerne).
• Det givne ligningssystem er A X = C. Vi erstatter A = L U. Vi har således L U X = C. Vi sætter Z = U X, hvor Z er en matrix eller kunstige variable, og løser først for L Z = C og løser derefter for U X = Z for at finde X eller værdierne af variablerne, som var påkrævet.

Eksempel på LU-nedbrydning

Løs følgende ligningssystem ved hjælp af LU-dekomponeringsmetoden:

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øsning: Her har vi 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}

og

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

sådan at A X = C. Nu overvejer vi først

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

og konverter den til række echelon form ved hjælp af Gauss Elimination Method. Så ved at gøre

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

vi får

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}

Nu ved at gøre

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

Vi får

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

(Husk altid at beholde ’ – ’ skilt imellem, erstat ’ + ’ tegn med to ’ – ’ tegn) Derfor får vi L =

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

og U =

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

(bemærk, at i L matrix,

l_{21} = 4

er fra (1),

l_{31} = 3

er fra (2) og

primtal i java

l_{32} = -2

er fra (3)) Nu antager vi Z

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

og løs 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}

Så det har vi

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

Løsning, får vi

z_1 = 1

,

z_2 = 2

og

z_3 = 5

. Nu løser vi 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}

Derfor får vi

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

indsættelsessorteringsalgoritmer

,

-10x_3 = 5 .

Således er løsningen til det givne system af lineære ligninger

x_1 = 1

,

x_2 = 0.5

,

x_3 = -0.5

og dermed matrixen X =

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

Øvelse om LU-nedbrydning

I LU-nedbrydningen af ​​matrixen

| 2 2 |
| 4 9 |

, hvis de diagonale elementer i U begge er 1, så er den nederste diagonale indgang l22 i L (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

For løsning, se PORT | GATE-CS-2015 (Sæt 1) | Spørgsmål 65 .

Ofte stillede spørgsmål om LU-nedbrydning

Hvad er LU-nedbrydningsmetoden?

LU-nedbrydning, forkortelse for Lower-Upper-dekomponering, er en matrixfaktoriseringsteknik, der bruges til at nedbryde en kvadratisk matrix i produktet af en nedre trekantet matrix (L) og en øvre trekantet matrix (U). Det bruges almindeligvis til at forenkle løsning af systemer af lineære ligninger og beregning af determinanter.

Hvorfor er LU-nedbrydning unik?

LU-nedbrydning er unik, fordi den giver en måde at faktorisere en kvadratisk matrix A i nedre og øvre trekantede matricer (L og U) unikt, hvilket muliggør effektiv løsning af lineære systemer og determinantberegning.

Hvordan beregnes LU-nedbrydning?

LU-dekomponering beregnes ved hjælp af Gauss-eliminering, hvor du transformerer en kvadratisk matrix A til nedre (L) og øvre (U) trekantede matricer ved at udføre rækkeoperationer, mens du holder styr på ændringerne i separate matricer. Denne proces er iterativ og fortsætter, indtil A er fuldstændigt nedbrudt. Metoden med alle trinene til LU-nedbrydning er givet i artiklen.

Når LU-nedbrydning ikke er mulig?

LU-nedbrydning er muligvis ikke mulig, når matrix A er singulær (ikke-inverterbar), eller når den kræver drejning for stabilitet, men pivotelementet bliver nul, hvilket forårsager division med nul under nedbrydningsprocessen.

Er der nogen alternativer til LU-nedbrydning?

Ja, alternativer til LU-nedbrydning inkluderer Kolesky nedbrydning for symmetriske positive bestemte matricer, QR-dekomponering for generelle matricer og egenværdi-baserede metoder som spektral dekomponering og singular value-dekomponering (SVD) til forskellige matrixoperationer og applikationer.

Kan LU-dekomponering anvendes på ikke-kvadratiske matricer?

LU-nedbrydning anvendes typisk på kvadratiske matricer. For rektangulære matricer er QR-nedbrydning mere almindeligt anvendt. Variationer som LUP-nedbrydning kan dog også håndtere rektangulære matricer, hvor P er en permutationsmatrix.