Sistemi sovradeterminati e metodo dei minimi quadrati

[phate82]

ciao a tutti!

mi sono imbattuto nei sistemi sovradeterminati durante lo studio della fattorizzazione QR per le matrici rettangolari di rango massimo. Prima di fare le mie domande, cerco di esporre in due parole quello che ho capito per essere sicuro che non ci siano errori di comprensione alla base . Un sistema sovradeterminato è tale se la matrice dei coefficienti ha un numero di righe maggiore del numero di colonne. Tale sistema è risolvibile in modo esatto (cioè con residuo nullo) se e solo se il vettore dei termini noti appartiene allo spazio vettoriale generato dai vettori colonna della matrice dei coefficienti (ovvero se si può scrivere come combinazione lineare degli stessi). Se questa condizione non è verificata, è possibile trovare una soluzione del sistema nel senso dei minimi quadrati, ossia (se indichiamo il sistema con Ax=b) si cerca quella soluzione x* tale che ||b-Ax*|| sia minimo. Qui sorge la prima domanda: non ho ben capito a livello "grafico" come funziona questo metodo dei minimi quadrati...b è fuori dallo spazio vettoriale generato dai vettori colonna di A, mentre Ax* è un vettore di questo spazio...ma in pratica Ax* sarebbe il vettore meno distante da b? non mi è chiara la storia della proiezione di b sullo spazio vettoriale ecc ecc

Poi..per risolvere il sistema nel senso dei minimi quadrati, mi scrivo il sistema alle equazioni normali, la cui soluzione esatta è la x* che cerco. Per semplificare la risoluzione di questo sistema posso utilizzare la attorizzazione QR della matrice A. Ho letto che l'utilizzo della fattorizzazione QR è auspicabile anche per evitare l'amplificazione di errori di arrotondamento (mi sembra)...qualcuno potrebbe chiarirmi il perchè?

Infine mi è sorto un ultimo dubbio..se mi trovo di fronte ad un sistema sovradeterminato, in cui però il vettore dei termini noti appartiene al famoso spazio vettoriale, come me la trovo la soluzione esatta del sistema? posso comunque usare il metodo dei minimi quadrati, cioè risolvere il sistema alle equazioni normali, trovando in questo caso una soluzione con residuo nullo? o c'è qualche altro modo per trovare la soluzione esatta?

mi scuso per la lunghezza del post e spero di non aver detto troppe fesserie

[dissonance]

Se hai un sistema sovradimensionato, diciamo

(1) $Ax=b$, dove $A\inCC^{m \times n}$ con $m>n$

in generale esso è incompatibile, quindi il problema (1) non ha soluzione. Passiamo allora al problema

(2) $||b-Ax^{**}||_2^2="min"_{x \in CC^n} ||b-Ax||_2^2$

ovvero trovare il vettore $x^{**}\inCC^n$ che minimizza lo scarto (o residuo) quadratico dal vettore dei termini noti. A differenza del problema (1), il (2) è ben posto, ovvero ha una e una sola soluzione, a patto di aggiungere una piccola ipotesi in più, peraltro verificata in modo naturale in tutte le applicazioni: le colonne di $A$, che chiamo $A_1...A_n$, devono essere linearmente indipendenti.

Infatti sussiste il seguente teorema (cfr. Gohberg Goldberg Basic Operator Theory, §I.6)

Sia $E$ uno spazio vettoriale dotato del prodotto scalare $(*,*)$, $M$ un sottospazio, $f\inE$. Sono equivalenti:

a) $f_0$ è un elemento di $M$ tale che $||f-f_0||<||f-g||$ per ogni $g\inM$, $||g-f_0||>0$; ($f_0$ è l'elemento di $M$ che meglio approssima l'elemento $f$)
b) $f_0 \in M,\ f-f_0 \bot M$.

Questo vuol dire che quando hai una norma indotta da un prodotto scalare, puoi trasportare ogni problema di tipo "minimizzare la distanza di $f$ dal sottospazio $M$", che in genere è molto difficile, ad un problema di tipo "proiettare ortogonalmente $f$ su $M$": infatti la condizione $f-f_0\botM$ significa esattamente che $f_0$ è la proiezione ortogonale di $f$ su $M$:

        Internet Explorer richiede Adobe SVG Viewer per visualizzare il grafico

Il problema di realizzare proiezioni ortogonali è molto più semplice del precedente ed ha una soluzione esplicita nel caso in cui $M$ abbia una base finita $A_1, ..., A_n$ (la confusione con le colonne di $A$ non è casuale). Ora però è tardi e devo interrompere, ci risentiamo domani. Buonanotte.

[dissonance]

Per riprendere il filo, riscrivo il problema (2) che stiamo cercando di risolvere:

(2) trovare $x^{**}\inCC^n$ tale che $||b-Ax^{**}||_2^2="min"_{x \in CC^n} ||b-Ax||_2^2$.

Come dicevo prima, questo è un problema di minimo e se lasciato in questa forma è un problema molto difficile. Pertanto lo trasformeremo ulteriormente usando il risultato del post precedente, facendolo diventare un problema di proiezione ortogonale. Chiamiamo $V=CC^n$, $M={z_1A_1+...+z_nA_n\ |\ z_1, ..., z_n \in CC}$ (=spazio vettoriale generato dalle colonne di $A$). $V$ è uno spazio a prodotto scalare: $(x, y)=sum_{k=1}^nx_ky_k$, e la norma risultante è proprio $||*||_2$, quella che compare nel problema (2). Osserviamo che $Ax=x_1A_1+...+x_nA_n$, e che al variare di $x\inCC^n$ questa espressione descrive tutti i vettori del sottospazio $M$ ($A_1, ..., A_n$ è una base di $M$. A questo serviva l'ipotesi che le colonne di $A$ fossero linearmente indipendenti).

Il problema (2) è quindi il problema di trovare la migliore approssimazione possibile di $b$ con vettori di $M$, e il teorema del post precedente ci assicura che esso è equivalente al problema

(3) trovare $x^{**}\in CC^n$ tale che $b-Ax^{**} \bot M$.

che possiamo ancora semplificare, osservando che $b-Ax^{**}\bot M$ è equivalente a $b-Ax^{**} \bot A_1, ..., b-Ax^{**} \bot A_n$ (ricordo che gli elementi di $M$ sono tutti e soli i vettori della forma $x_1A_1+...+x_nA_n$). In conclusione siamo pervenuti al problema

(3) trovare $x^{**}\inCC^n$ tale che $b-Ax^{**} \bot A_i,\ i=1, 2, ..., n$.

Questo problema, a differenza di tutti i precedenti, è pronto per essere risolto. Imponiamo infatti la condizione

$b-Ax^{**} \bot A_i,\ i=1, 2, ..., n$; ovvero
$(b-Ax^{**}, A_i)=0,\ i=1, 2, ..., n$; si tratta di una relazione lineare in $x^{**}$ (questo è un punto notevolissimo: siamo partiti dal problema (2) che è potenzialmente un incubo, e lo abbiamo ridotto ad un problema lineare!) e difatti dopo qualche conto essa si riduce al sistema di equazioni lineari

(4) $A^HAx^{**}=A^Hb$.

che è la formulazione definitiva. Regola mnemonica: siamo partiti da

(1) $Ax=b$;

per arrivare a (4) dobbiamo semplicemente moltiplicare a sinistra per $A^H$ ambo i membri. Dietro questa semplice operazione, però, c'è il pacco di teoria che ho cercato di sintetizzare in questi post (SE&O).

Da adesso in poi inizia la parte algoritmica: mentre è sempre vero che $A^HA$ è definita positiva, quindi in linea teorica il sistema è risolubile con algoritmi per matrici definite positive (Cholesky ad esempio), nessuno garantisce che $A^HA$ sia una matrice ben condizionata. E allora ci sono dei metodi che permettono di aggirare questa complicazione (come il metodo di Golub, oppure la fattorizzazione QR di cui hai letto). Ma purtroppo questo è un argomento del quale mi intendo poco.

[seven]

Ciao Dissonance, potresti dirmi gentilmente per cosa sta il pedice 2 della norma quadro del residuo?

[dissonance]

Non c'è bisogno di quotare tutto il messaggio, bastano le due righe incriminate. Comunque \(\lVert \cdot \rVert_2\) è una delle notazioni per la norma euclidea in \(\mathbb{C}^n\).

[seven]

Tra l'altro il post è anche un pò vecchiotto.. ma il pedice dunque può essere omesso o c'è il rischio di una qualche ambiguità?

[dissonance]

Di solito nel contesto dell'algebra lineare numerica si usa scrivere \(\lvert x \rvert_p\) oppure \(\lVert x \rVert_p\) per indicare la "norma \(p\)" di un vettore \(x \in \mathbb{C}^n\), ovvero

\[\lvert x \rvert_p^p=\sum_{j=1}^n \lvert x_j \rvert^p, \quad \lvert x \rvert_{\infty}=\max(\lvert x_j\rvert\mid j=1\ldots n).\]

Se lo ometti i più capiranno che ti riferisci alla "norma \(2\)", quella usuale in questo tipo di spazi.

[seven]

capito, dunque se mi riferisco alla norma 2 posso ometterlo

saluti