Leer Introductie tot Matrixdecompositie | Grondslagen van Lineaire Algebra

Het oplossen van systemen zoals $A \vec{x} = \vec{b}$ kan computationeel intensief zijn, vooral bij grote systemen.

Matrixdecompositie vereenvoudigt dit proces door matrix $A$ op te splitsen in eenvoudigere delen – die vervolgens stapsgewijs kunnen worden opgelost.

LU versus QR

De matrix $A$ wordt gedecomponeerd in andere gestructureerde matrices.

LU-decompositie

Splits $A$ in een Lagere en Bovenste driehoeksmatrix:

Gebaseerd op Gauss-eliminatie;
Werkt het beste voor vierkante matrices.

A = LU

QR-decompositie

Splits $A$ in een Orthogonale en Bovenste matrix:

Vaak gebruikt voor niet-vierkante matrices;
Ideaal voor kleinste-kwadratenproblemen of wanneer LU niet toepasbaar is.

A = QR

LU-decompositie

Begin met een vierkante matrix:

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

Het doel is om dit te schrijven als:

A = LU

Waarbij:

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

Deze decompositie is mogelijk als A vierkant en inverteerbaar is.

Belangrijke punten:

Lagere driehoeksmatrices hebben alleen nullen boven de diagonaal, wat voorwaartse substitutie vereenvoudigt;
Bovenste driehoeksmatrices hebben nullen onder de diagonaal, waardoor achterwaartse substitutie eenvoudig wordt;
Een orthogonale matrix heeft kolommen die orthonormale vectoren zijn (vectoren met lengte 1 die loodrecht op elkaar staan);
Deze eigenschap behoudt vectorlengte en hoeken, wat nuttig is bij het oplossen van kleinste-kwadratenproblemen en het verbeteren van numerieke stabiliteit.

Gauss-eliminatie

Pas Gauss-eliminatie toe om het element onder het linksbovenste pivot te elimineren:

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

Dit levert op:

R'_2 = [0, -1.5]

De bijgewerkte matrices worden dan:

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

En uit onze rijoperatie volgt:

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

Belangrijke punten:

Gauss-eliminatie elimineert systematisch de elementen onder het pivotelement in elke kolom door geschaalde versies van de pivotrij af te trekken van de onderliggende rijen;
Dit proces transformeert A in een bovendiagonale matrix U;
De vermenigvuldigingsfactoren die gebruikt worden om deze elementen te elimineren, worden opgeslagen in L, waardoor we A kunnen weergeven als het product LU.

Resultaat van LU-decompositie

We verifiëren:

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 het stelsel $A \vec{x} = \vec{b}$ in twee stappen worden opgelost:

Los $L \vec{y} = \vec{b}$ op met voorwaartse substitutie;
Los $U \vec{x} = \vec{y}$ op met achterwaartse substitutie.

QR-decompositie

We willen een matrix $A$ uitdrukken als een product van twee matrices:

A = QR

Waarbij:

$A$ de invoermatrix is (bijvoorbeeld data, coëfficiënten, enz.);
$Q$ een orthogonale matrix is (de kolommen zijn orthonormale vectoren);
$R$ een bovendiagonale matrix is.

Een voorbeeld van de vorm:

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}

Deze decompositie wordt vaak gebruikt wanneer:

Matrix A niet vierkant is;
Bij het oplossen van kleinste-kwadratenproblemen;
LU-decompositie niet stabiel is.

Wat zijn orthonormale vectoren?

Orthogonale vectoren

Twee vectoren $u, v$ zijn orthogonaal als hun inwendig product nul is:

u \cdot v = 0

Genormaliseerde vector

Een vector $u$ is genormaliseerd wanneer $|u| = 1$ .

Orthonormale verzameling

Een verzameling vectoren $\{q_1, q_2, ..., q_k\}$ is orthonormaal als elke vector eenheidslengte heeft en ze onderling orthogonaal zijn:

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

Belang: orthonormale kolommen in $Q$ behouden de geometrie, vereenvoudigen projecties en verbeteren de numerieke stabiliteit.

Definieer de matrix A

Laten we beginnen met dit voorbeeld:

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

We gebruiken het Gram-Schmidt-proces om matrices $Q$ en $R$ te vinden zodat $A=QR$ . Het Gram-Schmidt-proces vormt een orthonormale verzameling vectoren uit de kolommen van $A$ .

Dit betekent dat de vectoren in $Q$ allemaal loodrecht (orthogonaal) op elkaar staan en eenheidslengte (genormaliseerd) hebben. Deze eigenschap vereenvoudigt veel berekeningen en verbetert de numerieke stabiliteit bij het oplossen van stelsels.

Het doel is hier om:

De kolommen van $Q$ orthonormaal te maken;
De matrix $R$ te creëren die de projecties encodeert.

Bereken de eerste basisvector

We nemen de eerste kolom van $A$ :

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

Om deze te normaliseren, berekenen we de norm:

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

Dan:

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

Dit is de eerste orthonormale vector voor $Q$ .

Hoe een vector te normaliseren

Gegeven een vector:

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

We berekenen de norm:

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

Daarna normaliseren:

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

Voorbeeld:

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

Dus, onze genormaliseerde vector is:

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

Zodra we weten hoe we vectoren moeten normaliseren en orthogonaliseren, kunnen we het Gram-Schmidt-proces toepassen om de $Q$ -matrix te vormen en deze gebruiken om $R$ te berekenen in de QR-decompositie.

Bereken q₂ met behulp van Gram-Schmidt

Om $q_2$ te berekenen, beginnen we met de tweede kolom van $A$ :

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

Vervolgens projecteer je $a_2$ op $q_1$ :

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

Verwijder de projectie van $a_2$ :

u_2 = a_2 - r_{12}q_1

Normaliseer vervolgens (zoals hierboven getoond):

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

Nu vormen zowel $q_1$ als $q_2$ de orthonormale basis voor $Q$ . Stel nu het eindresultaat samen:

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

Deze voldoen aan:

A = QR

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 8

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Suggested prompts:

Can you explain the main differences between LU and QR decomposition?

How do I know when to use LU decomposition versus QR decomposition?

Can you walk me through the steps of the Gram-Schmidt process in more detail?

Awesome!

Completion rate improved to 1.96

Veeg om het menu te tonen

Het oplossen van systemen zoals $A \vec{x} = \vec{b}$ kan computationeel intensief zijn, vooral bij grote systemen.

Matrixdecompositie vereenvoudigt dit proces door matrix $A$ op te splitsen in eenvoudigere delen – die vervolgens stapsgewijs kunnen worden opgelost.

LU versus QR

De matrix $A$ wordt gedecomponeerd in andere gestructureerde matrices.

LU-decompositie

Splits $A$ in een Lagere en Bovenste driehoeksmatrix:

Gebaseerd op Gauss-eliminatie;
Werkt het beste voor vierkante matrices.

A = LU

QR-decompositie

Splits $A$ in een Orthogonale en Bovenste matrix:

Vaak gebruikt voor niet-vierkante matrices;
Ideaal voor kleinste-kwadratenproblemen of wanneer LU niet toepasbaar is.

A = QR

LU-decompositie

Begin met een vierkante matrix:

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

Het doel is om dit te schrijven als:

A = LU

Waarbij:

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

Deze decompositie is mogelijk als A vierkant en inverteerbaar is.

Belangrijke punten:

Lagere driehoeksmatrices hebben alleen nullen boven de diagonaal, wat voorwaartse substitutie vereenvoudigt;
Bovenste driehoeksmatrices hebben nullen onder de diagonaal, waardoor achterwaartse substitutie eenvoudig wordt;
Een orthogonale matrix heeft kolommen die orthonormale vectoren zijn (vectoren met lengte 1 die loodrecht op elkaar staan);
Deze eigenschap behoudt vectorlengte en hoeken, wat nuttig is bij het oplossen van kleinste-kwadratenproblemen en het verbeteren van numerieke stabiliteit.

Gauss-eliminatie

Pas Gauss-eliminatie toe om het element onder het linksbovenste pivot te elimineren:

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

Dit levert op:

R'_2 = [0, -1.5]

De bijgewerkte matrices worden dan:

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

En uit onze rijoperatie volgt:

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

Belangrijke punten:

Gauss-eliminatie elimineert systematisch de elementen onder het pivotelement in elke kolom door geschaalde versies van de pivotrij af te trekken van de onderliggende rijen;
Dit proces transformeert A in een bovendiagonale matrix U;
De vermenigvuldigingsfactoren die gebruikt worden om deze elementen te elimineren, worden opgeslagen in L, waardoor we A kunnen weergeven als het product LU.

Resultaat van LU-decompositie

We verifiëren:

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 het stelsel $A \vec{x} = \vec{b}$ in twee stappen worden opgelost:

Los $L \vec{y} = \vec{b}$ op met voorwaartse substitutie;
Los $U \vec{x} = \vec{y}$ op met achterwaartse substitutie.

QR-decompositie

We willen een matrix $A$ uitdrukken als een product van twee matrices:

A = QR

Waarbij:

$A$ de invoermatrix is (bijvoorbeeld data, coëfficiënten, enz.);
$Q$ een orthogonale matrix is (de kolommen zijn orthonormale vectoren);
$R$ een bovendiagonale matrix is.

Een voorbeeld van de vorm:

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}

Deze decompositie wordt vaak gebruikt wanneer:

Matrix A niet vierkant is;
Bij het oplossen van kleinste-kwadratenproblemen;
LU-decompositie niet stabiel is.

Wat zijn orthonormale vectoren?

Orthogonale vectoren

Twee vectoren $u, v$ zijn orthogonaal als hun inwendig product nul is:

u \cdot v = 0

Genormaliseerde vector

Een vector $u$ is genormaliseerd wanneer $|u| = 1$ .

Orthonormale verzameling

Een verzameling vectoren $\{q_1, q_2, ..., q_k\}$ is orthonormaal als elke vector eenheidslengte heeft en ze onderling orthogonaal zijn:

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

Belang: orthonormale kolommen in $Q$ behouden de geometrie, vereenvoudigen projecties en verbeteren de numerieke stabiliteit.

Definieer de matrix A

Laten we beginnen met dit voorbeeld:

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

We gebruiken het Gram-Schmidt-proces om matrices $Q$ en $R$ te vinden zodat $A=QR$ . Het Gram-Schmidt-proces vormt een orthonormale verzameling vectoren uit de kolommen van $A$ .

Het doel is hier om:

De kolommen van $Q$ orthonormaal te maken;
De matrix $R$ te creëren die de projecties encodeert.

Bereken de eerste basisvector

We nemen de eerste kolom van $A$ :

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

Om deze te normaliseren, berekenen we de norm:

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

Dan:

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

Dit is de eerste orthonormale vector voor $Q$ .

Hoe een vector te normaliseren

Gegeven een vector:

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

We berekenen de norm:

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

Daarna normaliseren:

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

Voorbeeld:

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

Dus, onze genormaliseerde vector is:

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

Bereken q₂ met behulp van Gram-Schmidt

Om $q_2$ te berekenen, beginnen we met de tweede kolom van $A$ :

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

Vervolgens projecteer je $a_2$ op $q_1$ :

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

Verwijder de projectie van $a_2$ :

u_2 = a_2 - r_{12}q_1

Normaliseer vervolgens (zoals hierboven getoond):

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

Nu vormen zowel $q_1$ als $q_2$ de orthonormale basis voor $Q$ . Stel nu het eindresultaat samen:

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

Deze voldoen aan:

A = QR

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 8