Esercizi di Algebra Lineare Il problema dei minimi quadrati
30 aprile 2013
Problema dei minimi quadrati
Data una matrice M ∈ Matn,s(R) e un vettore v ∈ Rn, determinare un vettore u combinazione lineare delle colonne di M , tale che la distanza tra v e u sia minima.
Il vettore a minima distanza da v `e la proiezione ortogonale di v sul sottospazio generato dalle colonne di M . Quindi il problema si traduce in:
Dato un sottospazio W ⊆ Rn (generato dalle colonne di M ) e un vettore v ∈ Rn, determinare la proiezione ortogonale di v su W .
Distinguiamo tre casi, dal pi`u speciale al pi`u generale.
0.1 Problema dei minimi quadrati (I caso)
Sia G una base ortonormale di un sottospazio W di Rn. Allora Mp(E)E = MGE· (MGE)tr= Q · Qtr
Esercizio 1 Sia F = {(1, 0, 1), (2, 1, −2)} e sia v = (1, 1, 1) . Trovare la proiezione di v sul sottospazio V (F ) .
Soluzione Metodo “geometrico”: F `e una base ortogonale, applico la formula pW(v) =
(v·f1)
|f1|2 · f1+(v·f|f 2)
2|2 · f2.
pW(v) = ((1, 1, 1) · (1, 0, 1))
2 · (1, 0, 1) +((1, 1, 1) · (2, 1, −2))
9 · (2, 1, −2)
= 1 · (1, 0, 1) +1
9 · (2, 1, −2)
= (11 9 ,1
9,7 9)
u t Soluzione Metodo “algebrico”: applico la formula Mp(v)E = Mp(E)E MvE.
Il proiettore Mp(E)E `e Q · Qtr dove Q = MGE e G `e la normalizzazione della base ortogonale F . Il proiettore pu`o essere calcolato senza usare radici osservando che Q = MFE·√2/2 0
0 1/3
,
1
quindi
Q · Qtr= MFE·√2/2 0
0 1/3
·√2/2 0
0 1/3
tr
· (MFE)tr= MFE·1/2 0 0 1/9
· (MFE)tr
F := [[1,0,1], [2,1,-2]];
MFE := Transposed(Mat(QQ, F));
Proiett := MFE * DiagMat(QQ, [1/2, 1/9]) * Transposed(MFE); Proiett;
-- [17/18, 2/9, 1/18], -- [2/9, 1/9, -2/9], -- [1/18, -2/9, 17/18]
Avendo calcolato il proiettore Mp(E)E posso facilmente concludere:
MvE := ColMat(QQ, [1,1,1]);
MpvE := Proiett * MvE; MpvE; --> Mat([[11/9], [1/9], [7/9]])
Quindi p(v) = (119,19,79) . ut
0.2 Problema dei minimi quadrati (II caso)
Sia F una base (qualunque) di un sottospazio W di Rn.
Dato un vettore v vogliamo determinarne la proiezione su W , cio`e Mp(v)E .
Teorema 2 Sia F una base di un sottospazio W di Rn, e M = MFE (attenzione: in generale M non `e quadrata!). Allora il proiettore su W `e
Mp(E)E = M (Mtr· M )−1· Mtr
Dim. Sia H base ortonormale e Q = MHE (ortogonale), R = MFH (invertibile), allora M = MFE= MHE· MFH = QR
Mp(E)F = MHF· Mp(E)H
= R−1· Qtr
= R−1· (Rtr−1· Rtr) · Qtr
= (Rtr· R)−1· (QR)tr
= (RtrQtr· QR)−1· (QR)tr
= ((QR)tr· QR)−1· (QR)tr
= (Mtr· M )−1· Mtr
e quindi il proiettore Mp(E)E `e Mp(E)E = MFE· Mp(E)F = M · (Mtr· M )−1· Mtr ut Osservazione:
M ortonormale =⇒ Mtr· M = I . Quindi il proiettore `e M · Mtr (compatibilmente al I caso).
M ortogonale =⇒ Mtr· M = ∆ . Quindi il proiettore `e M · ∆−1· Mtr (come nell’esercizio).
Esercizio 3 Sia F = {(1, 0, 1), (3, 1, −1)} e sia v = (1, 1, 1) . Trovare la proiezione di v sul sottospazio generato da F .
2
Soluzione Applico la formula Mp(v)E = Mp(E)E MvE. M := Transposed(Mat(QQ, [[1,0,1], [3,1,-1]]));
MvE := ColMat(QQ, [1,1,1]);
Proiett := M * Inverse(Transposed(M) * M) * Transposed(M); Proiett;
-- [[17/18, 2/9, 1/18], -- [2/9, 1/9, -2/9], -- [1/18, -2/9, 17/18]])
MpvE := Proiett * MvE; MpvE; --> [[11/9], [1/9], [7/9]]
Quindi p(v) = (119,19,79) . ut
Esercizio 4 Sia F = {(1, 2, 3, 4), (0, 1, 0, 3), (2, 2, 0, 1)} e sia v = (1, 1, 1, 1) . Trovare il vettore u pi`u vicino a v nel sottospazio generato da F .
Soluzione Applico la formula Mp(v)E = Mp(E)E MvE. F := [[1,2,3,4], [0,1,0,3], [2,2,0,1]];
M := Transposed(Mat(QQ, F));
MvE := ColMat(QQ, [1,1,1,1]);
Proiett := M * Inverse(Transposed(M) * M) * Transposed(M); Proiett;
-- [[361/586, 135/293, 15/586, -45/293], -- [135/293, 131/293, -9/293, 54/293], -- [ 15/586, -9/293, 585/586, 3/293], -- [-45/293, 54/293, 3/293, 275/293]]) M_pv_E := Proiett * MvE; M_pv_E;
--> [[278/293], [311/293], [294/293], [287/293]])
Quindi p(v) =2931 (278, 311, 294, 287) . ut
0.3 Problema dei minimi quadrati (III caso)
Sia F un insieme di generatori di un sottospazio W di Rn. Dato un vettore v determinarne la proiezione su W .
Definizione 5 Data una matrice A la pseudoinversa di Moore-Penrose A+ di A `e la matrice che soddisfa le seguenti propriet`a: AA+ e A+A sono simmetriche, e AA+A = A e A+AA+= A+.
In particolare se A `e invertibile allora A+= A−1.
Teorema 6 Sia F un insieme di generatori di un sottospazio W di Rn, e A = MFE (in generale A non `e n´e quadrata n´e di rango massimo!). Allora il proiettore su W `e
Mp(E)E = AA+ Esempio 7 Sia data la matrice
A =
1 1 3 1 0 1 1 0 1 1 0 1
3
(a) Calcolare la pseudoinversa di A . (b) Calcolare il proiettore di A .
(c) Trovare la proiezione di v = (1, 0, 1, 0) sul sottospazio generato dalle colonne di A . Soluzione
(a) Scelgo M sottomatrice di A di rango massimo e calcolo N tale che A = M · Ntr: la terza colonna di A `e uguale alla prima + 2 volte la seconda
A := Mat(QQ, [[1,1,3], [1,0,1], [1,0,1], [1,0,1]]); A;
M := submat(A, [1,2,3,4], [1,2]); M;
N := Mat(QQ, [[1,0], [0,1], [1,2]]); N;
-- verifico
M * Transposed(N) = A; --> true
Applico la formula per il calcolo della pseudoinversa:
A+= N (NtrN )−1(MtrM )−1Mtr AP := N * Inverse(Transposed(N)*N) *
Inverse(Transposed(M)*M) * Transposed(M);
AP;
-- [-1/3, 7/18, 7/18, 7/18], -- [1/3, -2/9, -2/9, -2/9], -- [1/3, -1/18, -1/18, -1/18]
-- verifico
IsSymmetric(A * AP); --> true IsSymmetric(AP * A); --> true A * AP * A = A; --> true AP * A * AP = AP; --> true (b) Mp(E)E = AA+
MvE := ColMat(QQ, [1,0,1,0]);
Proiett := A * AP; Proiett;
-- [1, 0, 0, 0], -- [0, 1/3, 1/3, 1/3], -- [0, 1/3, 1/3, 1/3], -- [0, 1/3, 1/3, 1/3]
(c) Mp(v)E = AA+MvE
MpvE := Proiett * MvE; MpvE; --> Mat([[1], [1/3], [1/3], [1/3]])
Quindi la pseudoinversa di A `e
−1/3 7/18 7/18 7/18 1/3 −2/9 −2/9 −2/9 1/3 −1/18 −1/18 −1/18
, il proiettore di A
` e
1 0 0 0
0 1/3 1/3 1/3 0 1/3 1/3 1/3 0 1/3 1/3 1/3
, e la proiezione di v `e p(v) = (1,13,13,13) .
u t
4