Problema dei minimi quadrati

Least square problem §

Assumiamo $A\in {\mathbb{C}}^{m\times n}$ di rango massimo ($n$) con $m\ge n$. Il sistema $Ax=b$ è pertanto sovradeterminato, ed in generale non esiste una soluzione $x\in {\mathbb{C}}^n$. Il meglio che si può fare è minimizzare la norma del residuo:

$$x^{\ast }={\text{argmin}}_{x\in {\mathbb{C}}^n}||b-Ax|{|}_2\gamma =||b-A{x}^{\ast }|{|}_2$$

Ciò significa trovare la soluzione nell’immagine $range(A)$ più vicino a $b$.

Decomponiamo il termine noto $b=b_1+b_2$ con $b_1\in range(A)$ e $b_2\in range(A{)}^{\perp }$. Se $b\notin range(A)$ necessariamente $b_2\ne 0$. Per l’ortogonalitèà tra $b_1,Ax$ e $b_2$

$$||b_1+b_2-Ax|{|}_2^2=||b_1-Ax|{|}_2^2+||b_2|{|}_2^2$$

è chiaro che minimizzare questa quantità significa risolvere il sistema $Ax=b_1$. Si ha $\gamma =||b_2|{|}_2$.

Equazioni normali §

Proposizione $range(A{)}^{\perp }=\ker (A^H)$. Dim $z\in range(A{)}^{\perp }$ significa che $0=(Ax{)}^{H}z=x^H{A}^{H}z\forall x$. Questo implica che $A^{H}z=0$, ovvero $z\in \ker (A^H)$. $\square$

Con questa caratterizzazione, stiamo richiedendo che il residuo sia nel ker di $A^H$ ovvero:

$$A^H(b-Ax)=0$$

Questo sistema definisce le cosidette equazioni normali:

$$A^{H}Ax=A^{H}b$$ $$x=(A^{H}A{)}^{-1}{A}^{H}b$$ $$x=A^{+}b$$

dove abbiamo introdottoa la pseudo inversa di Moore-Penrose $A^{+}$. Osservazione La matrice $A^{H}A\in {\mathbb{C}}^{n\times n}$ è invertible siccome abbiamo supposto $A$ di rango massimo.

Osservazione La pseudo inversa è un’inversa sinistra:

$$A^{+}A=(A^{H}A{)}^{-1}{A}^{H}A=I_n$$

Risolvere usando le equazioni normali è pericoloso infatti $\mathcal{K}(A^{H}A)=\mathcal{K}(A{)}^2$.

Soluzione tramite fattorizzazione QR §

Usiamo la Fattorizzazione QR per riscrevere le equazioni normali:

$$A^H(b-Ax)=R^H{Q}^H(b-QRx)=R^H(Q^{H}b-Rx)=0$$

e risolvere il sistema triangolare con le matrici della fattorizzazione ridotta:

$$R_{n}x=Q_n^{H}b=c_1$$

Infatti le prime $n$ colonne di $Q$ sono una base ortonormale di $range(A)$, mentre le restanti $m-n$ del suo ortononale. Dunque:

$$Q^{H}b=\left(\begin{array}{c}{c}_1\\ c_2\end{array}\right)R=\left(\begin{array}{c}{R}_n\\ 0\end{array}\right)$$

Partendo invece dalla norma del residuo

$$x^{\ast }=argmi{n}_{x\in {\mathbb{C}}^n}||b-QRx||=argmi{n}_{x\in {\mathbb{C}}^n}||Q^{H}b-Rx||$$

siccome $Q^H$ è unitaria non cambia la norma $2$. Se decomponiamo $b$ ottiemo:

$$\gamma =||Q^{H}b-R{x}^{\ast }||=||c_2||$$

quindi se calcoliamo la fattorizzazione completa sappiamo anche calcolare $\gamma$ direttamente.