Lære Introduktion til Matrixdekomposition | Grundlæggende Lineær Algebra

Løsning af systemer som $A \vec{x} = \vec{b}$ kan være beregningsmæssigt krævende, især for store systemer.

Matrixdekomponering forenkler denne proces ved at opdele matrixen $A$ i enklere dele – som derefter kan løses i etaper.

LU vs QR

Vi dekomponerer matrixen $A$ i andre strukturerede matricer.

LU-dekomponering

Opdel $A$ i en nedre og øvre trekantsmatrix:

Opbygges ved hjælp af Gauss-elimination;
Fungerer bedst for kvadratiske matricer.

A = LU

QR-dekomponering

Opdel $A$ i en ortogonal og øvre matrix:

Ofte brugt til ikke-kvadratiske matricer;
Ideel til mindste kvadraters problemer eller når LU fejler.

A = QR

LU-dekomponering

Start med en kvadratisk matrix:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Målet er at skrive dette som:

A = LU

Hvor:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Denne dekomponering er mulig hvis A er kvadratisk og invertibel.

Vigtige punkter:

Nedre trekantsmatricer har alle nul over diagonalen, hvilket forenkler fremadsubstitution;
Øvre trekantsmatricer har nuller under diagonalen, hvilket gør baglæns substitution ligetil;
En ortogonal matrix har søjler, der er ortonormale vektorer (vektorer med længde 1, der er vinkelrette);
Denne egenskab bevarer vektorlængde og vinkler, hvilket er nyttigt ved løsning af mindste kvadraters problemer og forbedrer numerisk stabilitet.

Gaussisk elimination

Anvend Gaussisk elimination for at eliminere elementet under det øverste venstre pivot:

R_2 \rarr R_2 - \frac{6}{4}R_1

Dette giver:

R'_2 = [0, -1.5]

Så de opdaterede matricer bliver:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Og ud fra vores rækkeoperation ved vi:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Vigtige pointer:

Gaussisk elimination eliminerer systematisk elementer under pivotelementet i hver kolonne ved at trække skalerede versioner af pivotrækken fra rækkerne nedenunder;
Denne proces omdanner A til en øvre triangulær matrix U;
De multiplikatorer, der bruges til at eliminere disse elementer, gemmes i L, hvilket gør det muligt at repræsentere A som produktet LU.

LU-dekompositionsresultat

Vi verificerer:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nu kan systemet $A \vec{x} = \vec{b}$ løses i to trin:

Løs $L \vec{y} = \vec{b}$ ved fremad substitution;
Løs $U \vec{x} = \vec{y}$ ved bagud substitution.

QR-dekomposition

Målet er at udtrykke en matrix $A$ som et produkt af to matricer:

A = QR

Hvor:

$A$ er inputmatricen (f.eks. data, koefficienter osv.);
$Q$ er en ortogonal matrix (dens søjler er ortonormale vektorer);
$R$ er en øvre triangulær matrix.

Et eksempel på opdeling af form:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Denne dekomposition anvendes ofte når:

Matrix A er ikke kvadratisk;
Løsning af mindste kvadraters problemer;
LU-dekomposition ikke er stabil.

Hvad er ortonormale vektorer?

Ortogonale vektorer

To vektorer $u, v$ er ortogonale, hvis deres prikprodukt er nul:

u \cdot v = 0

Normaliseret vektor

En vektor $u$ er normaliseret, når $|u| = 1$ .

Ortonormalt sæt

Et sæt af vektorer $\{q_1, q_2, ..., q_k\}$ er ortonormalt, hvis hver har enhedslængde og de er indbyrdes ortogonale:

q_i \cdot q_j = \begin{cases} 1,\ \text{hvis}\ \ i = j,\\ 0,\ \text{hvis}\ \ i \neq j. \end{cases}

Betydning: ortonormale søjler i $Q$ bevarer geometrien, forenkler projektioner og forbedrer numerisk stabilitet.

Definer matrixen A

Lad os starte med dette eksempel:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Vi vil bruge Gram-Schmidt-processen til at finde matricerne $Q$ og $R$ , så $A=QR$ . Gram-Schmidt-processen skaber et ortonormalt sæt af vektorer ud fra søjlerne i $A$ .

Dette betyder, at vektorerne i $Q$ alle er vinkelrette (ortogonale) på hinanden og har enhedslængde (normaliseret). Denne egenskab forenkler mange beregninger og forbedrer numerisk stabilitet ved løsning af ligningssystemer.

Målet her er derfor:

At gøre søjlerne i $Q$ ortonormale;
At skabe matrixen $R$ , som vil indeholde projektionerne.

Beregn første basisvektor

Vi udtrækker den første søjle af $A$ :

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

For at normalisere denne beregner vi normen:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Derefter:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Dette er den første ortonormale vektor for $Q$ .

Sådan normaliseres en vektor

Givet en vektor:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Vi beregner dens norm:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Derefter normaliseres:

\hat{v} = \frac{1}{|v|}v

Eksempel:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Så vores normaliserede vektor er:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Når vi ved, hvordan man normaliserer og ortogonaliserer vektorer, kan vi anvende Gram-Schmidt-processen til at danne $Q$ -matrixen og bruge den til at beregne $R$ i QR-dekompositionen.

Beregn q₂ ved hjælp af Gram-Schmidt

For at beregne $q_2$ starter vi med den anden søjle af $A$ :

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Dernæst projiceres $a_2$ på $q_1$ :

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Fjern projektionen fra $a_2$ :

u_2 = a_2 - r_{12}q_1

Normaliser derefter (som vist ovenfor):

q_2 = \frac{u_2}{|u_2|}

Nu danner både $q_1$ og $q_2$ det ortonormale grundlag for $Q$ . Du samler nu det endelige resultat:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Disse opfylder:

A = QR

Var alt klart?

Tak for dine kommentarer!

Sektion 4. Kapitel 8

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Awesome!

Completion rate improved to 1.96

Stryg for at vise menuen

Løsning af systemer som $A \vec{x} = \vec{b}$ kan være beregningsmæssigt krævende, især for store systemer.

Matrixdekomponering forenkler denne proces ved at opdele matrixen $A$ i enklere dele – som derefter kan løses i etaper.

LU vs QR

Vi dekomponerer matrixen $A$ i andre strukturerede matricer.

LU-dekomponering

Opdel $A$ i en nedre og øvre trekantsmatrix:

Opbygges ved hjælp af Gauss-elimination;
Fungerer bedst for kvadratiske matricer.

A = LU

QR-dekomponering

Opdel $A$ i en ortogonal og øvre matrix:

Ofte brugt til ikke-kvadratiske matricer;
Ideel til mindste kvadraters problemer eller når LU fejler.

A = QR

LU-dekomponering

Start med en kvadratisk matrix:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Målet er at skrive dette som:

A = LU

Hvor:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Denne dekomponering er mulig hvis A er kvadratisk og invertibel.

Vigtige punkter:

Nedre trekantsmatricer har alle nul over diagonalen, hvilket forenkler fremadsubstitution;
Øvre trekantsmatricer har nuller under diagonalen, hvilket gør baglæns substitution ligetil;
En ortogonal matrix har søjler, der er ortonormale vektorer (vektorer med længde 1, der er vinkelrette);
Denne egenskab bevarer vektorlængde og vinkler, hvilket er nyttigt ved løsning af mindste kvadraters problemer og forbedrer numerisk stabilitet.

Gaussisk elimination

Anvend Gaussisk elimination for at eliminere elementet under det øverste venstre pivot:

R_2 \rarr R_2 - \frac{6}{4}R_1

Dette giver:

R'_2 = [0, -1.5]

Så de opdaterede matricer bliver:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Og ud fra vores rækkeoperation ved vi:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Vigtige pointer:

Gaussisk elimination eliminerer systematisk elementer under pivotelementet i hver kolonne ved at trække skalerede versioner af pivotrækken fra rækkerne nedenunder;
Denne proces omdanner A til en øvre triangulær matrix U;
De multiplikatorer, der bruges til at eliminere disse elementer, gemmes i L, hvilket gør det muligt at repræsentere A som produktet LU.

LU-dekompositionsresultat

Vi verificerer:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nu kan systemet $A \vec{x} = \vec{b}$ løses i to trin:

Løs $L \vec{y} = \vec{b}$ ved fremad substitution;
Løs $U \vec{x} = \vec{y}$ ved bagud substitution.

QR-dekomposition

Målet er at udtrykke en matrix $A$ som et produkt af to matricer:

A = QR

Hvor:

$A$ er inputmatricen (f.eks. data, koefficienter osv.);
$Q$ er en ortogonal matrix (dens søjler er ortonormale vektorer);
$R$ er en øvre triangulær matrix.

Et eksempel på opdeling af form:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Denne dekomposition anvendes ofte når:

Matrix A er ikke kvadratisk;
Løsning af mindste kvadraters problemer;
LU-dekomposition ikke er stabil.

Hvad er ortonormale vektorer?

Ortogonale vektorer

To vektorer $u, v$ er ortogonale, hvis deres prikprodukt er nul:

u \cdot v = 0

Normaliseret vektor

En vektor $u$ er normaliseret, når $|u| = 1$ .

Ortonormalt sæt

Et sæt af vektorer $\{q_1, q_2, ..., q_k\}$ er ortonormalt, hvis hver har enhedslængde og de er indbyrdes ortogonale:

q_i \cdot q_j = \begin{cases} 1,\ \text{hvis}\ \ i = j,\\ 0,\ \text{hvis}\ \ i \neq j. \end{cases}

Betydning: ortonormale søjler i $Q$ bevarer geometrien, forenkler projektioner og forbedrer numerisk stabilitet.

Definer matrixen A

Lad os starte med dette eksempel:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Vi vil bruge Gram-Schmidt-processen til at finde matricerne $Q$ og $R$ , så $A=QR$ . Gram-Schmidt-processen skaber et ortonormalt sæt af vektorer ud fra søjlerne i $A$ .

Målet her er derfor:

At gøre søjlerne i $Q$ ortonormale;
At skabe matrixen $R$ , som vil indeholde projektionerne.

Beregn første basisvektor

Vi udtrækker den første søjle af $A$ :

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

For at normalisere denne beregner vi normen:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Derefter:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Dette er den første ortonormale vektor for $Q$ .

Sådan normaliseres en vektor

Givet en vektor:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Vi beregner dens norm:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Derefter normaliseres:

\hat{v} = \frac{1}{|v|}v

Eksempel:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Så vores normaliserede vektor er:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Når vi ved, hvordan man normaliserer og ortogonaliserer vektorer, kan vi anvende Gram-Schmidt-processen til at danne $Q$ -matrixen og bruge den til at beregne $R$ i QR-dekompositionen.

Beregn q₂ ved hjælp af Gram-Schmidt

For at beregne $q_2$ starter vi med den anden søjle af $A$ :

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Dernæst projiceres $a_2$ på $q_1$ :

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Fjern projektionen fra $a_2$ :

u_2 = a_2 - r_{12}q_1

Normaliser derefter (som vist ovenfor):

q_2 = \frac{u_2}{|u_2|}

Nu danner både $q_1$ og $q_2$ det ortonormale grundlag for $Q$ . Du samler nu det endelige resultat:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Disse opfylder:

A = QR

Var alt klart?

Tak for dine kommentarer!

Sektion 4. Kapitel 8