Lære Introduksjon til Matrisedekomponering | Grunnleggende Lineær Algebra

Å løse systemer som $A \vec{x} = \vec{b}$ kan være beregningsmessig krevende, spesielt for store systemer.

Matrisedekomponering forenkler denne prosessen ved å dele matrisen $A$ opp i enklere deler – som vi deretter kan løse trinnvis.

LU vs QR

Vi dekomponerer matrisen $A$ i andre strukturerte matriser.

LU-dekomponering

Deler $A$ opp i en nedre og en øvre triangulær matrise:

Bygges ved hjelp av Gauss-eliminasjon;
Fungerer best for kvadratiske matriser.

A = LU

QR-dekomponering

Deler $A$ opp i en ortogonal og en øvre matrise:

Ofte brukt for ikke-kvadratiske matriser;
Ideell for minste kvadraters problemer eller når LU ikke fungerer.

A = QR

LU-dekomponering

Start med en kvadratisk matrise:

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

Målet vårt er å 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 dekomponeringen er mulig hvis A er kvadratisk og inverterbar.

Viktige punkter:

Nedre triangulære matriser har alle nullverdier over diagonalen, noe som forenkler fremoversubstitusjon;
Øvre triangulære matriser har nullverdier under diagonalen, noe som gjør bakoversubstitusjon enkel;
En ortogonal matrise har kolonner som er ortonormale vektorer (vektorer med lengde 1 som er ortogonale);
Denne egenskapen bevarer vektorlengde og vinkler, noe som er nyttig ved løsning av minste kvadraters problemer og forbedrer numerisk stabilitet.

Gauss-eliminasjon

Bruk Gauss-eliminasjon for å eliminere elementet under det øverste venstre pivot-elementet:

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

Dette gir oss:

R'_2 = [0, -1.5]

De oppdaterte matrisene blir da:

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

Og fra radoperasjonen vet vi:

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

Viktige punkter:

Gauss-eliminasjon eliminerer systematisk elementene under pivotelementet i hver kolonne ved å trekke fra skalerte versjoner av pivot-raden fra radene under;
Denne prosessen omformer A til en øvre triangulær matrise U;
Multiplisatorene som brukes for å eliminere disse elementene lagres i L, slik at vi kan representere A som produktet LU.

Resultat av LU-dekomponering

Vi verifiserer:

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}

Nå kan systemet $A \vec{x} = \vec{b}$ løses i to steg:

Løs $L \vec{y} = \vec{b}$ ved fremoversubstitusjon;
Løs $U \vec{x} = \vec{y}$ ved bakoversubstitusjon.

QR-dekomponering

Vi ønsker å uttrykke en matrise $A$ som et produkt av to matriser:

A = QR

Hvor:

$A$ er innmatrisen (for eksempel data, koeffisienter, osv.);
$Q$ er en ortogonal matrise (kolonnene er ortonormale vektorer);
$R$ er en øvre triangulær matrise.

Et eksempel på oppdeling:

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 dekomponeringen brukes ofte når:

Matrisen A ikke er kvadratisk;
Løsning av minste kvadraters problemer;
LU-dekomponering ikke er stabil.

Hva er ortonormale vektorer?

Ortogonale vektorer

To vektorer $u, v$ er ortogonale hvis deres skalarprodukt er null:

u \cdot v = 0

Normalisert vektor

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

Ortonormalt sett

Et sett med vektorer $\{q_1, q_2, ..., q_k\}$ er ortonormalt hvis hver vektor har lengde én og de er gjensidig ortogonale:

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

Hvorfor det er viktig: ortonormale kolonner i $Q$ bevarer geometrien, forenkler projeksjoner og gir bedre numerisk stabilitet.

Definer matrisen A

La oss starte med dette eksempelet:

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

Vi skal bruke Gram-Schmidt-prosessen for å finne matriser $Q$ og $R$ slik at $A=QR$ . Gram-Schmidt-prosessen lager et ortonormalt sett med vektorer fra kolonnene i $A$ .

Dette betyr at vektorene i $Q$ er ortogonale (vinkelrette) på hverandre og har lengde én (normalisert). Denne egenskapen forenkler mange beregninger og gir bedre numerisk stabilitet ved løsning av ligningssystemer.

Målet her er å:

Gjøre kolonnene i $Q$ ortonormale;
Lage matrisen $R$ som vil inneholde projeksjonene.

Beregn første basisvektor

Vi tar ut den første kolonnen i $A$ :

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

For å normalisere denne, beregner vi normen:

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

Deretter:

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 vektoren for $Q$ .

Hvordan normalisere en vektor

Gitt en vektor:

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

Vi beregner normen:

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

Deretter normaliserer vi:

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

Eksempel:

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

Så vår normaliserte vektor er:

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

Når vi vet hvordan vi normaliserer og ortogonaliserer vektorer, kan vi bruke Gram-Schmidt-prosessen til å danne $Q$ -matrisen, og bruke den til å beregne $R$ i QR-dekomponeringen.

Beregn q₂ ved hjelp av Gram-Schmidt

For å beregne $q_2$ , starter vi med den andre kolonnen i $A$ :

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

Deretter projiserer du $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 projeksjonen fra $a_2$ :

u_2 = a_2 - r_{12}q_1

Normaliser deretter (som vist ovenfor):

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

Nå danner både $q_1$ og $q_2$ det ortonormale basiset for $Q$ . Du setter nå sammen det endelige resultatet:

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

Disse tilfredsstiller:

A = QR

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 8

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Awesome!

Completion rate improved to 1.96

Sveip for å vise menyen

Å løse systemer som $A \vec{x} = \vec{b}$ kan være beregningsmessig krevende, spesielt for store systemer.

Matrisedekomponering forenkler denne prosessen ved å dele matrisen $A$ opp i enklere deler – som vi deretter kan løse trinnvis.

LU vs QR

Vi dekomponerer matrisen $A$ i andre strukturerte matriser.

LU-dekomponering

Deler $A$ opp i en nedre og en øvre triangulær matrise:

Bygges ved hjelp av Gauss-eliminasjon;
Fungerer best for kvadratiske matriser.

A = LU

QR-dekomponering

Deler $A$ opp i en ortogonal og en øvre matrise:

Ofte brukt for ikke-kvadratiske matriser;
Ideell for minste kvadraters problemer eller når LU ikke fungerer.

A = QR

LU-dekomponering

Start med en kvadratisk matrise:

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

Målet vårt er å 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 dekomponeringen er mulig hvis A er kvadratisk og inverterbar.

Viktige punkter:

Nedre triangulære matriser har alle nullverdier over diagonalen, noe som forenkler fremoversubstitusjon;
Øvre triangulære matriser har nullverdier under diagonalen, noe som gjør bakoversubstitusjon enkel;
En ortogonal matrise har kolonner som er ortonormale vektorer (vektorer med lengde 1 som er ortogonale);
Denne egenskapen bevarer vektorlengde og vinkler, noe som er nyttig ved løsning av minste kvadraters problemer og forbedrer numerisk stabilitet.

Gauss-eliminasjon

Bruk Gauss-eliminasjon for å eliminere elementet under det øverste venstre pivot-elementet:

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

Dette gir oss:

R'_2 = [0, -1.5]

De oppdaterte matrisene blir da:

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

Og fra radoperasjonen vet vi:

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

Viktige punkter:

Gauss-eliminasjon eliminerer systematisk elementene under pivotelementet i hver kolonne ved å trekke fra skalerte versjoner av pivot-raden fra radene under;
Denne prosessen omformer A til en øvre triangulær matrise U;
Multiplisatorene som brukes for å eliminere disse elementene lagres i L, slik at vi kan representere A som produktet LU.

Resultat av LU-dekomponering

Vi verifiserer:

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}

Nå kan systemet $A \vec{x} = \vec{b}$ løses i to steg:

Løs $L \vec{y} = \vec{b}$ ved fremoversubstitusjon;
Løs $U \vec{x} = \vec{y}$ ved bakoversubstitusjon.

QR-dekomponering

Vi ønsker å uttrykke en matrise $A$ som et produkt av to matriser:

A = QR

Hvor:

$A$ er innmatrisen (for eksempel data, koeffisienter, osv.);
$Q$ er en ortogonal matrise (kolonnene er ortonormale vektorer);
$R$ er en øvre triangulær matrise.

Et eksempel på oppdeling:

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 dekomponeringen brukes ofte når:

Matrisen A ikke er kvadratisk;
Løsning av minste kvadraters problemer;
LU-dekomponering ikke er stabil.

Hva er ortonormale vektorer?

Ortogonale vektorer

To vektorer $u, v$ er ortogonale hvis deres skalarprodukt er null:

u \cdot v = 0

Normalisert vektor

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

Ortonormalt sett

Et sett med vektorer $\{q_1, q_2, ..., q_k\}$ er ortonormalt hvis hver vektor har lengde én og de er gjensidig ortogonale:

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

Hvorfor det er viktig: ortonormale kolonner i $Q$ bevarer geometrien, forenkler projeksjoner og gir bedre numerisk stabilitet.

Definer matrisen A

La oss starte med dette eksempelet:

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

Vi skal bruke Gram-Schmidt-prosessen for å finne matriser $Q$ og $R$ slik at $A=QR$ . Gram-Schmidt-prosessen lager et ortonormalt sett med vektorer fra kolonnene i $A$ .

Målet her er å:

Gjøre kolonnene i $Q$ ortonormale;
Lage matrisen $R$ som vil inneholde projeksjonene.

Beregn første basisvektor

Vi tar ut den første kolonnen i $A$ :

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

For å normalisere denne, beregner vi normen:

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

Deretter:

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 vektoren for $Q$ .

Hvordan normalisere en vektor

Gitt en vektor:

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

Vi beregner normen:

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

Deretter normaliserer vi:

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

Eksempel:

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

Så vår normaliserte vektor er:

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

Når vi vet hvordan vi normaliserer og ortogonaliserer vektorer, kan vi bruke Gram-Schmidt-prosessen til å danne $Q$ -matrisen, og bruke den til å beregne $R$ i QR-dekomponeringen.

Beregn q₂ ved hjelp av Gram-Schmidt

For å beregne $q_2$ , starter vi med den andre kolonnen i $A$ :

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

Deretter projiserer du $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 projeksjonen fra $a_2$ :

u_2 = a_2 - r_{12}q_1

Normaliser deretter (som vist ovenfor):

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

Nå danner både $q_1$ og $q_2$ det ortonormale basiset for $Q$ . Du setter nå sammen det endelige resultatet:

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

Disse tilfredsstiller:

A = QR

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 8