Lära Introduktion till Matrisuppdelning | Grunder i Linjär Algebra

Svep för att visa menyn

Att lösa system som $A \vec{x} = \vec{b}$ kan vara beräkningsmässigt krävande, särskilt för stora system.

Matrisuppdelning förenklar denna process genom att dela upp matrisen $A$ i enklare delar – vilka vi sedan kan lösa stegvis.

LU vs QR

Vi dekomponerar matrisen $A$ i andra strukturerade matriser.

LU-uppdelning

Delar upp $A$ i en nedre och övre triangulär matris:

Byggs med Gausselimination;
Fungerar bäst för kvadratiska matriser.

A = LU

QR-uppdelning

Delar upp $A$ i en ortogonal och övre matris:

Används ofta för icke-kvadratiska matriser;
Idealisk för minsta kvadratproblem eller när LU misslyckas.

A = QR

LU-uppdelning

Börja med en kvadratisk matris:

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

Målet är att skriva detta som:

A = LU

Där:

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

Denna uppdelning är möjlig om A är kvadratisk och inverterbar.

Viktiga punkter:

Nedre triangulära matriser har alla nollor ovanför diagonalen, vilket förenklar framåt substitution;
Övre triangulära matriser har nollor under diagonalen, vilket gör bakåt substitution enkel;
En ortogonal matris har kolumner som är ortonormala vektorer (vektorer med längd 1 som är vinkelräta);
Denna egenskap bevarar vektorlängd och vinklar, vilket är användbart vid lösning av minsta kvadratproblem och förbättrar numerisk stabilitet.

Gausselimination

Tillämpa Gausselimination för att eliminera elementet under det övre vänstra pivotelementet:

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

Detta ger oss:

R'_2 = [0, -1.5]

Så de uppdaterade matriserna blir:

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

Och från vår radoperation vet vi:

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

Viktiga punkter:

Gausselimination eliminerar systematiskt element under pivotelementet i varje kolumn genom att subtrahera skalade versioner av pivotraden från raderna under;
Denna process transformerar A till en övre triangulär matris U;
De multiplikatorer som används för att eliminera dessa element lagras i L, vilket gör det möjligt att representera A som produkten LU.

LU-faktoriseringens resultat

Vi verifierar:

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ösas i två steg:

Lös $L \vec{y} = \vec{b}$ med framåtsubstitution;
Lös $U \vec{x} = \vec{y}$ med bakåtsubstitution.

QR-faktorisering

Vi vill uttrycka en matris $A$ som en produkt av två matriser:

A = QR

Där:

$A$ är din inmatningsmatris (t.ex. data, koefficienter, etc.);
$Q$ är en ortogonal matris (dess kolumner är ortonormala vektorer);
$R$ är en övre triangulär matris.

Ett exempel på formuppdelning:

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}

Denna faktorisering används ofta när:

Matrisen A är inte kvadratisk;
Lösning av minsta kvadratproblem;
LU-faktorisering är instabil.

Vad är ortonormala vektorer?

Ortogonala vektorer

Två vektorer $u, v$ är ortogonala om deras skalärprodukt är noll:

u \cdot v = 0

Normaliserad vektor

En vektor $u$ är normaliserad när $|u| = 1$ .

Ortonormalt system

En mängd vektorer $\{q_1, q_2, ..., q_k\}$ är ortonormal om varje vektor har längd ett och de är ömsesidigt ortogonala:

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

Varför det är viktigt: ortonormala kolumner i $Q$ bevarar geometri, förenklar projektioner och förbättrar numerisk stabilitet.

Definiera matrisen A

Vi börjar med detta exempel:

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

Vi kommer att använda Gram-Schmidt-processen för att hitta matriserna $Q$ och $R$ så att $A=QR$ . Gram-Schmidt-processen skapar ett ortonormalt system av vektorer från kolumnerna i $A$ .

Detta innebär att vektorerna i $Q$ är ortogonala mot varandra och har längd ett (normaliserade). Denna egenskap förenklar många beräkningar och förbättrar numerisk stabilitet vid lösning av ekvationssystem.

Målet här är att:

Göra kolumnerna i $Q$ ortonormala;
Skapa matrisen $R$ som kommer att representera projektionerna.

Beräkna första basvektorn

Vi tar ut den första kolumnen i $A$ :

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

För att normalisera denna beräknar vi normen:

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

Sedan:

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

Detta är den första ortonormala vektorn för $Q$ .

Hur man normaliserar en vektor

Givet en vektor:

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

Vi beräknar dess norm:

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

Sedan normaliserar vi:

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

Exempel:

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

Så vår normaliserade vektor är:

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

När vi vet hur man normaliserar och ortogonaliserar vektorer kan vi använda Gram-Schmidt-processen för att bilda matrisen $Q$ och använda den för att beräkna $R$ i QR-splittringen.