LU nedbrydning

FONT SIZE:
fontsize_dec
fontsize_inc
Marts 6, 2016 Vagn Wilke L 0 99

I numerisk analyse, LU nedbrydning faktorer en matrix som et produkt af en lavere trekantsmatrix og en øvre trekantsmatrix. Produktet indeholder undertiden en permutation matrix så godt. LU nedbrydning kan ses som matrix form af Gauss-eliminering. Computere normalt løse kvadratiske systemer af lineære ligninger ved hjælp af LU nedbrydning, og det er også et vigtigt skridt, når invertere en matrix eller computing determinanten af ​​en matrix. LU nedbrydning blev introduceret af matematiker Alan Turing i 1948.

Definitioner

Lad A være en kvadratisk matrix. En LU faktorisering refererer til faktorisering af A, med ordentlig række og / eller kolonne orderings eller permutationer, i to faktorer, en lavere trekantet matrix L og en øvre triangulær matrix U,

I den nederste trekantsmatrix alle ovennævnte elementer diagonalen er nul, i den øvre triangulære matrix, alle elementer under diagonalen er nul. For eksempel, for en 3-by-3 matrix A, dens LU nedbrydning ser sådan ud:

Uden en ordentlig bestilling eller permutationer i matricen, kan faktorisering undlader at materialisere. For eksempel er det let at kontrollere, at. Hvis, så er mindst en og skal være nul, hvilket indebærer enten L eller U er ental. Dette er umuligt, hvis A er non-singul. Dette er et proceduremæssigt problem. Det kan fjernes ved blot at omfordele rækkerne af A, således at det første element i den permuterede matrix er forskellig fra nul. Det samme problem i efterfølgende faktoriseringsmetoder trin kan fjernes på samme måde, se den grundlæggende fremgangsmåde nedenfor.

Det viser sig, at en korrekt permutation i rækker er tilstrækkelig til LU faktorisering. LU faktorisering med delvis drejelige refererer ofte til LU faktorisering med kun række permutationer,

hvor L og U er igen nedre og øvre trekantede matricer, og P er en permutation matrix, som, når venstre-ganget til A, omarrangerer rækkerne af A. Det viser sig, at alle kvadratiske matricer kan faktoriserede i denne form, og faktorisering er numerisk stabil i praksis. Dette gør LUP dekomposition en nyttig teknik i praksis.

En LU faktorisering med fuld drejning involverer både række og kolonne permutationer,

hvor L, U og P er defineret som før, og Q er en permutation matrix, omarrangerer kolonner af A.

En LDU nedbrydning er en nedbrydning af formen

hvor D er en diagonal matrix og L og U er enhed trekantede matricer, hvilket betyder, at alle posterne på diagonaler L og U er ét.

Ovenfor vi kræves, at A være en kvadratisk matrix, men disse decompositions kan alle generaliseres til rektangulære matricer samt. I så fald, L og D er kvadratiske matricer som begge har det samme antal rækker som A, og U har nøjagtig de samme dimensioner som A. Øvre trekantede skal fortolkes som havende kun nul poster under hoveddiagonalen, som starter ved det øverste venstre hjørne.

Eksempel

Vi faktorisere følgende 2-for-2 matrix:

En måde at finde LU nedbrydning af dette enkle matrix ville være simpelthen at løse de lineære ligninger ved inspektion. Udvidelse af matrixmultiplikation giver

Dette system af ligninger er underbestemte. I dette tilfælde to ikke-nul elementer af L og U matricer er parametre af opløsningen og kan indstilles vilkårligt til enhver ikke-nul værdi. Derfor at finde den unikke LU nedbrydning, er det nødvendigt at sætte nogle begrænsninger på L og U matricer. For eksempel kan vi bekvemt kræve lavere triangulære matrix L til at være en enhed trekantsmatrix. Derefter system af ligninger har følgende løsning:

Erstatte disse værdier ind i LU nedbrydning over udbytter

Eksistens og entydighed

Kvadratiske matricer

Enhver kvadratisk matrix indrømmer en LUP faktorisering. Hvis er invertibel, så er det indrømmer et LU faktorisering hvis og kun hvis alle dets førende vigtigste mindreårige non-singul r. Hvis er en enestående matrix af rang, så er det indrømmer et LU faktorisering, hvis de første førende vigtigste mindreårige non-singul r, selvom det omvendte er ikke tilfældet.

Hvis en firkant, invertibel matrix har en LDU faktorisering med alle diagonale firmaer i L og U lig med 1, så er faktorisering er unik. I så fald, at LU faktorisering er også unik, hvis vi kræver, at diagonalen i består af dem.

Symmetriske positive konkrete matricer

Hvis A er en symmetrisk positiv bestemt matrix, kan vi arrangere spørgsmål, så U er den konjugerede transponerede L. Det vil sige, kan vi skrive A som

Denne nedbrydning kaldes Cholesky nedbrydning. Den Cholesky nedbrydning altid eksisterer og er unik. Desuden beregning af Cholesky dekomposition er mere effektiv og numerisk mere stabile end computing nogle andre LU nedbrydning.

Generelle matricer

For en matrix over en felt, er de nøjagtige nødvendige og tilstrækkelige betingelser, hvorunder det har en LU faktorisering kendt. Betingelserne er udtrykt i rækken af ​​visse undermatricer. Gauss elimination algoritme til opnåelse LU nedbrydning er også blevet udvidet til denne mest generelle tilfælde.

Algoritmer

LU nedbrydning er dybest set en modificeret form af Gauss-eliminering. Vi omdanne matricen A i en øvre triangulær matrix U ved at fjerne posterne under hoveddiagonalen. Den Doolittle algoritme gør afskaffelse kolonne efter kolonne starter fra venstre, ved at multiplicere A til venstre med atomare lavere trekantede matricer. Det resulterer i en enhed lavere trekantsmatrix og en øvre trekantsmatrix. Den Crout algoritme er lidt anderledes og konstruerer en nedre triangulær matrix og en enhed øvre trekantsmatrix.

Beregning af LU nedbrydning ved hjælp af en af ​​disse algoritmer kræver 2n / 3 floating point operationer, ignorerer lavere ordens led. Delvis drejning tilføjer kun en kvadratisk sigt; dette er ikke tilfældet for fuld drejning.

Lukket formel

Når en LDU faktorisering eksisterer og er unik der er en lukket formel for elementerne i L, D og U i form af forholdene mellem determinanter for visse undermatricer af den oprindelige matrix A. Navnlig og for, er forholdet mellem det primære delmatrix til hovedstolen delmatrix.

Doolittle algoritme

I betragtning af en N × N matrix

vi definerer

Vi eliminere matrixelementer nedenfor hoveddiagonalen i n'te søjle af A ved tilsætning til den i'te række af denne matrix det n'te række multipliceret med

for. Dette kan gøres ved at multiplicere A til venstre med den nedre triangulære matrix

Vi sætter

Efter N-1 trin, vi elimineret alle matrix elementer under hoveddiagonalen, så vi får en øvre triangulær matrix A. Vi finder nedbrydningen

Betegne den øvre triangulære matrix A med U, og. Fordi den inverse af en lavere trekantsmatrix Ln er igen en nedre triangulær matrix, og multiplikation af to nedre trekantede matricer er igen en nedre triangulær matrix, følger det, at L er en lavere trekantsmatrix. Desuden kan det ses, at

Vi får.

Det er klart, at for denne algoritme til arbejdet, er man nødt til at have på hvert trin. Hvis denne antagelse mislykkes på et tidspunkt, er man nødt til at udveksle n'te række med en anden række under den, før du fortsætter. Dette er grunden til LU nedbrydning i generelle ser ud.

Crout og LUP algoritmer

Den LUP nedbrydning algoritme af Cormen et al. generaliserer Crout matrix nedbrydning. Det kan beskrives som følger.

  • Hvis har en nul post i sin første række, så tag en permutation matrix sådan, at har en nul indgang i øverste venstre hjørne. Ellers tager for identitet matrix. Lad.
  • Lad være matrix, man får fra ved at slette både den første række og første kolonne. Nedbrydes rekursivt. Gøre fra ved først at tilføje et nul række over og derefter tilføje den første kolonne i til venstre.
  • Gøre fra ved først at tilføje et nul række over og et nul søjle til venstre og derefter erstatte den øverste venstre indgang med 1. gøre fra på samme måde og definere. Lade være det modsatte af.
  • På dette tidspunkt, er den samme som, bortset fra den første række. Hvis den første række af er nul, så, idet begge har første række nul, og følger efter ønske. Ellers og har samme nul post i øverste venstre hjørne, og for nogle øverste trekantede kvadratisk matrix med dem på diagonalen. Nu er en nedbrydning af den ønskede form.

Teoretisk kompleksitet

Hvis to matricer af orden n kan multipliceres i tid M, hvor M≥n for nogle a & gt; 2, så LU nedbrydning kan beregnes i tid O (M). Dette betyder for eksempel, at en O algoritme eksisterer baseret på Kobbersmeden-Winograd algoritme.

Sparsomme matrix nedbrydning

Særlige algoritmer er blevet udviklet til at faktorisere store sparsomme matricer. Disse algoritmer forsøge at finde sparsomme faktorer L og U. Ideelt er udgifterne til beregning bestemmes af antallet af ikke-nul, frem af størrelsen af ​​matrixen.

Disse algoritmer bruger friheden til at udveksle rækker og kolonner for at minimere fill-in.

Generel behandling af orderings der minimerer fill-in kan behandles ved hjælp af grafteori.

Applikationer

Løsning af lineære ligninger

Givet et system af lineære ligninger i matrix form,

vi ønsker at løse ligningen for x givet A og b. Antag vi har allerede fået LUP nedbrydning af en sådan, at vi kan omskrive ligningen ækvivalent som

I dette tilfælde opløsningen gøres på to logiske trin:

  • Først, vi løse ligningen for y;
  • For det andet, vi løse ligningen for x.

Bemærk, at vi i begge tilfælde har at gøre med trekantede matricer, der kan løses direkte ved frem og tilbage substitution uden at bruge Gauss elimination proces.

Den ovennævnte fremgangsmåde kan gentagne gange anvendes til at løse ligningen flere gange til forskellige b. I dette tilfælde er det hurtigere at udføre en LU nedbrydning af matricen A én gang og derefter løse de trekantede matricer for forskellige b, frem for at anvende Gauss-eliminering hver gang. Den matricer L og U kunne tænkes at have "kodet" Gaussisk elimination proces.

Omkostningerne ved at løse et system af lineære ligninger er ca. operationer med flydende komma, hvis matricen har størrelse. Dette gør det dobbelt så hurtigt som algoritmer baseret på QR nedbrydning, som koster omkring floating point operationer, når husbonden refleksioner bruges. Af denne grund er LU nedbrydning foretrækkes sædvanligvis.

Invertere en matrix

Ved løsning ligningssystemer, er b normalt behandlet som en vektor med en længde svarende til højden af ​​matrix A. I stedet for vektor b, vi har matricen B, hvor B er en n-by-p matrix, således at vi forsøger at finde en matrix X:

Vi kan bruge den samme algoritme præsenterede tidligere for at løse for hver kolonne i matrix X. Antag nu, at B er identiteten matrix af størrelse n. Det følger heraf, at resultatet X skal være det omvendte af A.

Beregning af determinanten

I betragtning af LUP nedbrydning af en kvadratisk matrix A, kan determinanten af ​​A beregnes enkelt som

Den anden ligning fremgår, at determinanten af ​​en trekantsmatrix er simpelthen produktet af dets diagonale poster, og at determinanten af ​​en permutationsmatricen er lig med hvor S er antallet af rækker udvekslinger i nedbrydningen.

I tilfælde af LU nedbrydning med fuld drejning, lig også højre side af ovenstående ligning, hvis vi lader S være det samlede antal udvekslinger række og kolonne.

Samme metode let gælder for LU nedbrydning ved at indstille P lig med identitetsmatricen.

  0   0
Forrige artikel Altenburg
Næste artikel Deidson Araújo Maia

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha