Impara Introduzione alla Decomposizione delle Matrici

La risoluzione di sistemi come $A \vec{x} = \vec{b}$ può essere computazionalmente onerosa, specialmente per sistemi di grandi dimensioni.

La decomposizione di matrici semplifica questo processo scomponendo la matrice $A$ in parti più semplici - che possono poi essere risolte in fasi successive.

LU vs QR

La matrice $A$ viene scomposta in altre matrici strutturate.

Decomposizione LU

Scomposizione di $A$ in una matrice triangolare inferiore e una superiore:

Costruita tramite eliminazione di Gauss;
Funziona meglio per matrici quadrate.

A = LU

Decomposizione QR

Scomposizione di $A$ in una matrice ortogonale e una superiore:

Spesso utilizzata per matrici non quadrate;
Ideale per problemi ai minimi quadrati o quando la LU non è applicabile.

A = QR

Decomposizione LU

Si parte da una matrice quadrata:

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

L'obiettivo è scrivere questa matrice come:

A = LU

Dove:

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

Questa decomposizione è possibile se A è quadrata e invertibile.

Punti importanti:

Le matrici triangolari inferiori hanno tutti gli elementi sopra la diagonale uguali a zero, semplificando la sostituzione in avanti;
Le matrici triangolari superiori hanno zeri sotto la diagonale, rendendo immediata la sostituzione all'indietro;
Una matrice ortogonale ha colonne che sono vettori ortonormali (vettori di lunghezza 1 e perpendicolari tra loro);
Questa proprietà preserva la lunghezza e gli angoli dei vettori, utile nella risoluzione dei minimi quadrati e nel miglioramento della stabilità numerica.

Eliminazione di Gauss

Applicare l'eliminazione di Gauss per eliminare l'elemento sotto il pivot in alto a sinistra:

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

Questo ci dà:

R'_2 = [0, -1.5]

Quindi le matrici aggiornate diventano:

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

E dall'operazione sulle righe, sappiamo che:

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

Punti importanti:

L'eliminazione di Gauss elimina sistematicamente gli elementi sotto il pivot in ogni colonna sottraendo versioni scalate della riga del pivot dalle righe sottostanti;
Questo processo trasforma A in una matrice triangolare superiore U;
I moltiplicatori utilizzati per eliminare questi elementi sono memorizzati in L, permettendo di rappresentare A come il prodotto LU.

Risultato della Decomposizione LU

Verifica:

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}

Ora il sistema $A \vec{x} = \vec{b}$ può essere risolto in due passaggi:

Risolvere $L \vec{y} = \vec{b}$ tramite sostituzione in avanti;
Risolvere $U \vec{x} = \vec{y}$ tramite sostituzione all'indietro.

Decomposizione QR

Si vuole esprimere una matrice $A$ come prodotto di due matrici:

A = QR

Dove:

$A$ è la matrice di input (ad esempio dati, coefficienti, ecc.);
$Q$ è una matrice ortogonale (le sue colonne sono vettori ortonormali);
$R$ è una matrice triangolare superiore.

Esempio di scomposizione delle forme:

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}

Questa decomposizione viene spesso utilizzata quando:

La matrice A non è quadrata;
Si risolvono problemi ai minimi quadrati;
La decomposizione LU non è stabile.

Cosa sono i vettori ortonormali?

Vettori ortogonali

Due vettori $u, v$ sono ortogonali se il loro prodotto scalare è zero:

u \cdot v = 0

Vettore normalizzato

Un vettore $u$ è normalizzato quando $|u| = 1$ .

Insieme ortonormale

Un insieme di vettori $\{q_1, q_2, ..., q_k\}$ è ortonormale se ciascuno ha lunghezza unitaria ed è mutuamente ortogonale:

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

Perché è importante: colonne ortonormali in $Q$ preservano la geometria, semplificano le proiezioni e migliorano la stabilità numerica.

Definizione della matrice A

Partiamo da questo esempio:

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

Utilizzeremo il processo di Gram-Schmidt per trovare le matrici $Q$ e $R$ tali che $A=QR$ . Il processo di Gram-Schmidt crea un insieme ortonormale di vettori a partire dalle colonne di $A$ .

Questo significa che i vettori in $Q$ sono tutti perpendicolari (ortogonali) tra loro e hanno lunghezza unitaria (normalizzati). Questa proprietà semplifica molti calcoli e migliora la stabilità numerica nella risoluzione dei sistemi.

Quindi, l'obiettivo qui è:

Rendere le colonne di $Q$ ortonormali;
Creare la matrice $R$ che codificherà le proiezioni.

Calcolo del primo vettore base

Estraiamo la prima colonna di $A$ :

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

Per normalizzarla, calcoliamo la norma:

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

Poi:

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

Questo è il primo vettore ortonormale per $Q$ .

Come normalizzare un vettore

Dato un vettore:

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

Calcoliamo la sua norma:

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

Poi normalizziamo:

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

Esempio:

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

Quindi, il nostro vettore normalizzato è:

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

Una volta che sappiamo come normalizzare e ortogonalizzare i vettori, possiamo applicare il processo di Gram-Schmidt per formare la matrice $Q$ e utilizzarla per calcolare $R$ nella decomposizione QR.

Calcolo di q₂ con Gram-Schmidt

Per calcolare $q_2$ , si parte dalla seconda colonna di $A$ :

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

Successivamente, si proietta $a_2$ su $q_1$ :

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

Si rimuove la proiezione da $a_2$ :

u_2 = a_2 - r_{12}q_1

Poi si normalizza (come mostrato sopra):

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

Ora sia $q_1$ che $q_2$ formano la base ortonormale per $Q$ . Si può ora assemblare il risultato finale:

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

Questi soddisfano:

A = QR

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 4. Capitolo 8

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

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

Scorri per mostrare il menu

La risoluzione di sistemi come $A \vec{x} = \vec{b}$ può essere computazionalmente onerosa, specialmente per sistemi di grandi dimensioni.

La decomposizione di matrici semplifica questo processo scomponendo la matrice $A$ in parti più semplici - che possono poi essere risolte in fasi successive.

LU vs QR

La matrice $A$ viene scomposta in altre matrici strutturate.

Decomposizione LU

Scomposizione di $A$ in una matrice triangolare inferiore e una superiore:

Costruita tramite eliminazione di Gauss;
Funziona meglio per matrici quadrate.

A = LU

Decomposizione QR

Scomposizione di $A$ in una matrice ortogonale e una superiore:

Spesso utilizzata per matrici non quadrate;
Ideale per problemi ai minimi quadrati o quando la LU non è applicabile.

A = QR

Decomposizione LU

Si parte da una matrice quadrata:

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

L'obiettivo è scrivere questa matrice come:

A = LU

Dove:

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

Questa decomposizione è possibile se A è quadrata e invertibile.

Punti importanti:

Le matrici triangolari inferiori hanno tutti gli elementi sopra la diagonale uguali a zero, semplificando la sostituzione in avanti;
Le matrici triangolari superiori hanno zeri sotto la diagonale, rendendo immediata la sostituzione all'indietro;
Una matrice ortogonale ha colonne che sono vettori ortonormali (vettori di lunghezza 1 e perpendicolari tra loro);
Questa proprietà preserva la lunghezza e gli angoli dei vettori, utile nella risoluzione dei minimi quadrati e nel miglioramento della stabilità numerica.

Eliminazione di Gauss

Applicare l'eliminazione di Gauss per eliminare l'elemento sotto il pivot in alto a sinistra:

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

Questo ci dà:

R'_2 = [0, -1.5]

Quindi le matrici aggiornate diventano:

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

E dall'operazione sulle righe, sappiamo che:

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

Punti importanti:

L'eliminazione di Gauss elimina sistematicamente gli elementi sotto il pivot in ogni colonna sottraendo versioni scalate della riga del pivot dalle righe sottostanti;
Questo processo trasforma A in una matrice triangolare superiore U;
I moltiplicatori utilizzati per eliminare questi elementi sono memorizzati in L, permettendo di rappresentare A come il prodotto LU.

Risultato della Decomposizione LU

Verifica:

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}

Ora il sistema $A \vec{x} = \vec{b}$ può essere risolto in due passaggi:

Risolvere $L \vec{y} = \vec{b}$ tramite sostituzione in avanti;
Risolvere $U \vec{x} = \vec{y}$ tramite sostituzione all'indietro.

Decomposizione QR

Si vuole esprimere una matrice $A$ come prodotto di due matrici:

A = QR

Dove:

$A$ è la matrice di input (ad esempio dati, coefficienti, ecc.);
$Q$ è una matrice ortogonale (le sue colonne sono vettori ortonormali);
$R$ è una matrice triangolare superiore.

Esempio di scomposizione delle forme:

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}

Questa decomposizione viene spesso utilizzata quando:

La matrice A non è quadrata;
Si risolvono problemi ai minimi quadrati;
La decomposizione LU non è stabile.

Cosa sono i vettori ortonormali?

Vettori ortogonali

Due vettori $u, v$ sono ortogonali se il loro prodotto scalare è zero:

u \cdot v = 0

Vettore normalizzato

Un vettore $u$ è normalizzato quando $|u| = 1$ .

Insieme ortonormale

Un insieme di vettori $\{q_1, q_2, ..., q_k\}$ è ortonormale se ciascuno ha lunghezza unitaria ed è mutuamente ortogonale:

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

Perché è importante: colonne ortonormali in $Q$ preservano la geometria, semplificano le proiezioni e migliorano la stabilità numerica.

Definizione della matrice A

Partiamo da questo esempio:

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

Utilizzeremo il processo di Gram-Schmidt per trovare le matrici $Q$ e $R$ tali che $A=QR$ . Il processo di Gram-Schmidt crea un insieme ortonormale di vettori a partire dalle colonne di $A$ .

Quindi, l'obiettivo qui è:

Rendere le colonne di $Q$ ortonormali;
Creare la matrice $R$ che codificherà le proiezioni.

Calcolo del primo vettore base

Estraiamo la prima colonna di $A$ :

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

Per normalizzarla, calcoliamo la norma:

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

Poi:

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

Questo è il primo vettore ortonormale per $Q$ .

Come normalizzare un vettore

Dato un vettore:

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

Calcoliamo la sua norma:

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

Poi normalizziamo:

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

Esempio:

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

Quindi, il nostro vettore normalizzato è:

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

Calcolo di q₂ con Gram-Schmidt

Per calcolare $q_2$ , si parte dalla seconda colonna di $A$ :

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

Successivamente, si proietta $a_2$ su $q_1$ :

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

Si rimuove la proiezione da $a_2$ :

u_2 = a_2 - r_{12}q_1

Poi si normalizza (come mostrato sopra):

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

Ora sia $q_1$ che $q_2$ formano la base ortonormale per $Q$ . Si può ora assemblare il risultato finale:

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

Questi soddisfano:

A = QR

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 4. Capitolo 8