LU-faktorisering

Frå Wikipedia – det frie oppslagsverket
Hopp til navigering Hopp til søk

Ei LU-faktorisering innanføre lineær algebra er ei matrisefaktorisering som deler opp ei matrise til i ei nedre triangulær matrise og ei øvre triangulær matrise. LU-faktoriseringa finst for alle kvadratiske matriser og er numerisk stabil. Ho har fleire bruksområde særleg innanføre numerisk lineær algebra, mellom anna for å løysa likningssystem, finna determinantar, rekna ut invers og å undersøkja om ei gjeven matrise er singulær.

Definisjon[endre | endre wikiteksten]

LU-faktoriseringa finst for alle kvadratiske matriser og er definert til å vera

Her er L er ei nedre triangulær matrise medan U er ei øvre triangulær matrise.

Motivering[endre | endre wikiteksten]

LU faktoriseringa kan motiverast fullt og heilt ut frå gaussisk eliminasjon på ei matrise A til ho vert ei øvre triangulær matrise U.

Kvar operasjon på ein rad i den gaussiske eliminasjonen kan uttrykkjast ved elementære matriser der eit tal x på indeks i matrisa svarar til å leggja rad m gongar verdien x til rad n. For å få matrisa A på ei øvre triangulær form så vert kvar radoperasjon å leggja ein rad til ein rad under. I den elementære matrisa svarer dette til at n alltid vil vera større eller lik m. Altså vil alle elementærmatrisene vera nedre triangulære.

Produkt av nedre triangulære matriser er også ei nedre triangulær matrise. Inversen av ei nedre triangulær matrise er også nedre triangulær. Altså vil;

Ein kan rekna ut LU-faktoriseringa direkte ved å finna dei elementære matrisene, men numerisk er ikkje dette ei optimal løysing.

Bruksområde[endre | endre wikiteksten]

Løysa likningssystem[endre | endre wikiteksten]

Ettersom LU-faktoriseringa faktoriserer i to triangulære matriser kan ein nytta forlengssubstitusjon etterfølgd av baklengssubstitusjon for å finna løysinga. Dette kan vera ein god del meir rekneeffektivt enn å nytta gaussisk eliminasjon direkte.

Når ein har ei LU faktorisering av matrisa så kan ein løysa systemet ved ved først framlengssubstitusjon etterfølgd av baklengssubstitusjon. Ein løyser først systemet med nedre triangulære matrisa ved framlengssubstitusjon og finn y. Ein gjev dette til systemet med den øvre triangulære matrisa og nyttar baklengssubstitusjon for å løysa det øvre triangulære likningssystemet og finn x.

Inversutrekning[endre | endre wikiteksten]

Inversen av ei matrise A rekna ut i frå LU-faktoriseringa hennar er gjeven som:

Singularitet[endre | endre wikiteksten]

Om alle diagonalelement i både L og U er noko anna enn 0, så er matrisa ikkje-singulær.

Determinant[endre | endre wikiteksten]

Determinanten kan reknast ut ved