LU-faktorisering

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

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

$A=LU$

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

Motivering

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

$E_{n}...E_{2}E_{1}A=U\,$

Kvar operasjon på ein rad i den gaussiske eliminasjonen kan uttrykkjast ved elementære matriser der eit tal x på indeks $n\times m$ 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 $E_{n},..,E_{2},E_{1}$ 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;

$A=(E_{n}...E_{2}E_{1})^{-1}U\quad \Rightarrow \quad A=E_{1}^{-1}E_{2}^{-1}...E_{n}^{-1}U\quad \Rightarrow \quad A=LU$

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

Bruksområde

Løysa likningssystem

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 $A=LU$ så kan ein løysa systemet ved $LUx=b$ ved først framlengssubstitusjon etterfølgd av baklengssubstitusjon. Ein løyser først systemet med nedre triangulære matrisa $Ly=b$ ved framlengssubstitusjon og finn y. Ein gjev dette til systemet med den øvre triangulære matrisa $Ux=y$ og nyttar baklengssubstitusjon for å løysa det øvre triangulære likningssystemet og finn x.