LU nedbrydning

12-04-2017 Knud Passer L
FONT SIZE:
fontsize_dec
fontsize_inc

I lineær algebra LU nedbrydning eller LUP nedbrydning eller nedbrydning af Doolittle er en faktorisering af en matrix i en nedre triangulær matrix, en øvre trekantsmatrix og en permutationsmatricen. Denne nedbrydning bruges i numerisk analyse til løsning af et system af lineære ligninger, at beregne den inverse af en matrix eller at beregne determinanten af ​​en matrix.

Definition

Er en invertibel matrix. Så kan nedbrydes som:

hvor er en permutationsmatricen, er en lavere trekantet matrix med diagonal ensartet og er en øvre trekantet matrix.

Hovedidéen

Nedbrydningen ligner algoritmen ifølge Gauss. Gauss elimination forsøger at løse matrix ligning:

Elimineringen proces producerer en øvre trekantsmatrix og konverterer bæreren

Da det er en øvre trekantsmatrix, kan dette system af ligninger løses nemt ved at erstatte bagud.

Ved nedbrydning, men det er ikke transformeres og ligningen kan skrives som:

så du kan genbruge den nedbrydning, hvis du ønsker at løse det samme system til et andet.

I det mere generelle tilfælde, hvor faktoriseringen af ​​matricen omfatter også anvendelsen af ​​udveksling af række i matricen, er det også indført en permutationsmatricen, og systemet bliver:

Løsningen af ​​dette system tillader bestemmelse af luftfartsselskabet forsøgte.

Algoritme

Ved at anvende sæt af elementære transformationer af matricen konstrueret en øvre triangulære matrix fra denne del. Denne metode kaldes Gauss metode. Disse transformationer er alle elementære matrix af lineære transformationer af kombinatorisk. Antag, at både produktet af N transformationer, derefter den øverste trekantede matrix er:

Den inverse matrix er:

Da Gauss-algoritmen bruger kun den tredje form af tre typer af elementære transformationer for at gøre øverste trekantede matrix, kan det udledes, at alle er trekantede. Som et produkt af også:

Det er lavere trekantet.

Den har altså nedbrydning af matricen i produktet og:

Applikationer

Inverse

Den faktorisering bruges også til at beregne den inverse matrix af. Faktisk:

hvorfra:

Determinant

En anden anvendelse af denne nedbrydning er at beregne determinanten af ​​matrixen. Faktisk:

derefter til sætning af Binet:

Vel vidende, at determinanten af ​​en permutationsmatricen gælder, hvis dette svarer til et lige antal permutationer, ellers, og at det opnås, at:

Vel vidende, at determinanten af ​​en trekantet matrix er givet ved produktet af de vilkår på hoveddiagonalen, vi har, at:

men også, at vilkårene på de vigtigste diagonal er af alt, så kan vi endelig konkludere:

hvor antallet af rækken swaps gjort i processen, og de vilkår og angiver udtrykket i række og kolonne, henholdsvis og matricer.