Minimi quadrati
27 novembre 2008
In questa nota si indicherà sempre con V uno spazio vettoriale reale di dimensione finita n.
Definizione 1. Una norma su V è una funzione||·|| : V 7→ R tale che ∀x, y ∈ V
e λ∈ R: 1. ||x|| ≥ 0;
2. ||x|| = 0 implica x = 0;
3. ||x + y|| ≤ ||x|| + ||y|| (disuguaglianza triangolare). 4. ||λx|| = |λ|||x||.
Esempio 1. Per ogni intero p≥ 1 la funzione
||x||p= n X i=1 |xi|p !1p
è una norma su Rn, come pure
||x||∞ = max i=1,...,n{|xi|}.
La norma|| · ||2 che si ottiene per p = 2 è detta norma euclidea.
Sistemi iperdeterminati
Si consideri il sistema lineare descritto dall’equazione matriciale
ove A è una matrice n× m, X il vettore delle indeterminate e B un vettore colonna di Rn. Tale sistema ammette soluzione se, e solamente se, il vettore colonna B appartiene all’immagine dell’applicazione lineare f : Rm 7→ Rn indotta dalla matrice A. È ben noto che per verificare l’esistenza di tale soluzione è possibile applicare il teorema di Rouché–Capelli, confrontando la dimensione dello spazio vettoriale generato dalle colonne di A con la dimensione dello spazio vettoriale generato da queste unitamente al vettore B; in tale modo il calcolo da effettuare è un confronto fra ranghi.
Diremo che un sistema è iperdeterminato se esso non ammette soluzione. Vogliamo trovare una formulazione più generale rispetto (1), tale che: 1. Quando il sistema è risolubile fornisca la soluzione cercata.
2. Offra la risposta “migliore possibile” quando il sistema è iperdetermina-to.
Si fissi una norma in Rne si consideri ora il problema di trovare tutti i vettori X∈ Rmtali che
||AX − B|| (2)
sia minimo; ovvero trovare tutti gli X tali che per ogni Z = AY appartenente all’immagine di A si abbia
||AX − B|| ≤ ||Z − B||.
Osserviamo che||AX − B|| = ||0|| = 0 se, e solamente se X è soluzione di (1). Chiaramente 0 è in questo caso il minimo valore che la norma può assumere. Pertanto, per sistemi risolubili, i problemi (1) e (2) sono equivalenti ed è ben chiaro che cosa si possa intendere per soluzione “migliore possibile”.
In generale, l’eventuale soluzione di (2) quando (1) non è risolubile dipende strettamente dal tipo di norma considerato.
Esempio 2. Consideriamo il sistema
1 1 1 x = b1 b2 b3
con b1 ≥ b2 ≥ b3 ≥ 0. Chiaramente, a meno che b1, b2 e b3 non siano tutti uguali, tale sistema non è risolubile. Consideriamo il problema (2) associato per 3 norme differenti:
• ||Ax − b||1: in questo caso cerchiamo di minimizzare la quantità |x − b1| + |x − b2| + |x − b3|.
• ||Ax − b||2: minimizzare la norma equivale a minimizzare la quantità 2ϕ(x) = (x−b1)2+(x−b2)2+(x−b3)2 = 3x2−2(b1+b2+b3)x+(b21+b 2 2+b 2 3) In particolare, calcolando la derivata si ottiene
dϕ
dx = 3x − (b1+ b2 + b3), da cui x = 1
3(b1+ b2 + b3), cioè x è la media aritmentica delle entrate del vettore dei termini noti.
• ||Ax − b||∞: in questo caso dobbiamo considerare la quantità max{|x − b1|, |x − b2|, |x − b3|} .
Poiché b2 è compreso fra b1 e b3, il massimo coincide con max{|x − b1|, |x − b3|} .
In particolare, il valore di x che minimizza quest’ultima espressione è proprio la media x = 1
2(b1+ b3).
Ci occuperemo ora in detteglio delle tecniche risolutive per il problema (2) quando le stime siano effettuate rispetto la norma euclidea.
Questo è motivato da essenzialmente due fattori: 1. la funzione ϕ(X) = 1
2||AX − B|| 2
2 è in questo caso differenziabile (come pure per tutti i valori di p tali che 1 < p <∞);
2. esiste un prodotto scalare di Rnche induce esattamente la norma con-siderata e tale prodotto consentirà di ben rappresentare la situazione geometrica in esame.
Distinguiamo un approccio di tipo analitico e un approccio di tipo geometrico al problema.
Approccio analitico
Consideriamo il funzionale Rn 7→ R dato da ϕ(X) = 1
2||AX − B|| 2 2.
Chiaramente, se X che minimizza ϕ(X), allora X è una soluzione del problema (2). A tal fine, studiamo i punti estremali del funzionale, ovvero cerchiamo di risolvere l’equazione
∇ϕ(X) = 0. (3)
Un calcolo diretto mostra che ∂ϕ ∂Xi = a1i(a11x1+ a12x2+ . . . + a1mxm− b1)+ a2i(a21x1+ a22x2+ . . . + a2mxm− b2)+ .. . ani(an1x1+ an2x2+ . . . + anmxm− bn) = a1i a2i . . . ani A x1 x2 .. . xm − B .
Scrivendo ora in forma matriciale le equazioni ∂ϕ
∂Xi = 0,
al variare di i = 1, . . . , m si ottiene che il gradiente di ϕ si annulla se, e solamente se, X è soluzione del sistema
(ATA)X = ATB. (4)
Pertanto, per risolvere il problema (2) rispetto || · ||2 si deve a risolvere il sistema lineare (4). Le m equazioni in m incognite di tale sistema sono dette equazioni normali del problema.
Osserviamo che, in generale le equazioni normali ammettono esattamente una soluzione se, e solamente se, la matrice quadrata ATAè non singolare. Questa condizione è esattamente quella per cui il problema (2) ammette una unica soluzione rispetto la norma|| · ||2.
Approccio algebrico
L’approccio analitico mostrato nel precedente paragrafo consente di ottenere le equazioni normali del problema in modo rapido; d’altro canto esso non rende evidente il motivo per cui il sistema dato dalle equazioni normali sia lineare.
Vediamo ora come sia possibile ottenere la medesima soluzione utilizzando strumenti prettamente algebrici.
Definizione 2. Un proiettore Π : Rn 7→ Rn è una applicazione lineare tale che
Π2 = Π.
L’immagine Π(x) di un vettore x è detta ombra di x secondo Π.
Osserviamo che la matrice P associata ad un proiettore, chiaramente, soddisfa la condizione
P2 = P. Una matrice di tale tipo è detta idempotente.
Teorema 1. Sia Π : Rn 7→ Rn un proiettore. Allora, =Π = ker(I − Π) e =(I − Π) = ker Π. In particolare
Rn==Π ⊕ =(I − Π).
Dimostrazione. Consideriamo un vettore x ∈ =Π. Allora esiste y ∈ Rn tale che x = Πy. Poiché Π2 = Π, abbiamo
Π(x) = Π2(y) = Π(y) = x;
pertanto x∈ ker(I − Π). Viceversa, se x ∈ ker(I − Π), si ha Π(x) = x;
dunque x∈=Π e la prima parte della tesi segue. La proprietà per (I − Π) è conseguenza del fatto che
(I − Π)2 = (I − Π)(I − Π) = (I − 2Π + Π2) = (I − Π), per cui anche (I − Π) è un proiettore.
L’idea alla base dell’approccio geometrico al problema (2) è quella di associare all’immagine U dell’applicazione lineare indotta da A un proiettore ΠU tale che:
1. ∀x ∈ U : ΠU(x) = U;
2. ∀b ∈ Rn : Π
U(b)∈ U e, per ogni x ∈ U,
Osserviamo che noto il proiettore ΠUcon le proprietà sopra elencate possiamo passare dal sistema lineare originario AX = B ad un nuovo sistema, che sappiamo essere risolubile,
AX = Π(B) (5)
e che, sotto le ipotesi, tale sistema è sicuramente lineare.
Supponiamo infatti che eXsia una soluzione di (5) che U indichi l’immagine di A. Allora, per ogni W ∈ Rm,
||AeX − B|| = ||AeX − Π(B) + Π(B) − B|| ≤ ||AeX − Π(B)|| + ||Π(B) − B|| = ||Π(B) − B|| = minZ∈U||Z − B|| ≤ ||AW − B||.
Pertanto eX minimizza la quantità ||AX − B|| e, conseguentemente, esso è soluzione di (2).
Mostreremo ora come costruire il proiettore ΠU desiderato quando si considera la|| · ||2 e ottenere un sistema lineare equivalente alla (5).
Definizione 3. Sia V uno spazio vettoriale sul campo R. Si dice prodotto
scalare ogni applicazioneh·, ·i : V × V 7→ R che è 1. bilineare, ovvero∀x, y, z ∈ V e λ ∈ R:
hx + λy, zi = hx, zi + λhy, zi, hx, λy + zi = λhx, yi + hx, zi; 2. simmetrica, ovvero
hx, yi = hy, xi; 3. definita positiva, ovvero∀x ∈ V,
hx, xi ≥ 0;
hx, xi = 0 se, e solamente se x = 0.
Teorema 2. Assegnato un prodotto scalare h·, ·i, la funzione ||x|| = hx, xi1
2
Dimostrazione. I fatti che||x|| ≥ 0 e ||x|| = 0 se, e solamente se x = 0 sono conseguenza immediata della definita positività del prodotto scalare. Inoltre, per la bilinearità, abbiamo
||λx||2 =hλx, λxi = λ2hx, xi.
Resta da dimostrare la disuguaglianza triangolare. Calcoliamo dapprima ||x + αy||2 =hx + αy, x + αyi =||x||2+ 2αhx, yi + α2||y||2.
Per la definita positività del prodotto scalare, la quantità scritta non può mai essere negativa; pertanto, il discriminante dell’equazione in α a sinistra deve essere negativo. Ne seguehx, yi2 <||x||2||y||2. Estraendo le radici quadrate si ottiene
|hx, yi| < ||x|| ||y||. (6)
La disuguaglianza (6) è detta disuguaglianza di Schwarz. Applicando tale disuguaglianza all’espansione di||x + y||2 si ha
||x + y||2 =hx + y, x + yi = ||x||2+ 2hx, yi +||y||2 ≤||x||2+ 2||x||||y|| + ||y||2, da cui, per la positività della norma,
||x + y|| ≤ ||x|| + ||y||. La tesi segue.
A meno di cambiamenti di riferimento, esiste essenzialmente un unico prodotto scalare in Rn. Questi, in un opportuno riferimento, è dato da
hx, yi = n X
i=1 xiyi.
Se x e y sono vettori colonna, tale prodotto si può anche scrivere come hx, yi = xTy. La norma indotta è ||x|| = n X i=1 x2i !12 , che coincide esattamente con||x||2.
Teorema 3. Sia V uno spazio vettoriale reale di dimensione finita e V∗ il suo duale. L’applicazione Θ : V 7→ V∗ che associa ad ogni x∈ V
Θx :
V → R
y → hx, yi
è un isomorfismo.
Dimostrazione. Poiché il prodotto scalare è bilineare, abbiamo che, per ogni
x fissato e per ogni y, z ∈ V, λ ∈ R:
Θx(y + λz) =hx, y + λzi = hx, yi + λhx, zi = Θx(y) + λΘx(z).
Pertanto il codominio di Θ è proprio V∗. Inoltre, per ogni x, y, z ∈ V,
Θx+λy(z) =hx + λy, zi = hx, zi + λhy, zi = Θx(z) + λΘy(z) = (Θx+ λΘy)(z);
quindi, Θ è una applicazione lineare. Siccome dim V = dim V∗, per dimostrare che Θ è un isomorfismo basta far vedere che ker Θ ={0}. Infatti, se x ∈ ker Θ, allora per ogni y∈ V,
Θx(y) = hx, yi = 0.
In particolare, Θx(x) = 0, da cui, per la definita positività del prodotto scalare,
x = 0.
Definizione 4. Sia U un sottospazio vettoriale di Rn. Il complemento or-togonale di U, indicato con U⊥ è l’insieme di tutti i vettori x
∈ Rn tali che hx, yi = 0 per ogni y ∈ U.
Teorema 4. Il complemento ortogonale di U è un sottospazio vettoriale di Rn. Inoltre
Rn= U⊕ U⊥.
Dimostrazione. I vettori di U⊥ sono esattamente l’annullatore dell’immagine di U in V∗ mediante Θ. Pertanto, essi costituiscono un sottospazio vettoriale di dimensione n − dim U. Inoltre, se x∈ U ∩ U⊥, allora il prodotto scalare di
x con ogni vettore di Rn(incluso se stesso) è 0, per cui x = 0.
Usando la teoria degli annullatori, si vede rapidamente che U⊥⊥= U.
Definizione 5. Per ogni x∈ Rn si dice proiezione ortogonale su U di x ogni vettore y ∈ U tale che
Poiché Rn= U⊕ U⊥, ogni x
∈ Rnsi può scrivere in modo unico
x = a + b,
ove a∈ U e b ∈ U⊥. Pertanto esiste per ogni vettore x almeno una proiezione ortogonale su U.
Teorema 5. La proiezione ortogonale y di x∈ Rnsu U è unica.
Dimostrazione. Siano y, y0due proiezioni ortogonali di x su U. Allora, y−y0 ∈ U⊥; d’altro canto y, y0 ∈ U. Ne segue y − y0 ∈ U ∩ U⊥ e dunque y = y0.
Conseguenza immediata del Teorema 5 è che per ogni y ∈ U si ha ΠU(y) = y, cioè che ogni vettore in U è fissato da ΠU. Per mostrare che ΠU è effettivamente un proiettore ai sensi della Definizione 2 dobbiamo ora far vedere che essa è una applicazione lineare.
Teorema 6. La proiezione ortogonale su U è una applicazione lineare Rn → U. Dimostrazione. Siano x, z∈ Rne λ in R. Per definizione, i vettori x − ΠU(x) e z − ΠU(z) appartengono ad U⊥. In particolare, il vettore
x − ΠU(x) + λ (z − ΠU(z)) = x + λz − (ΠU(x) + λΠU(z))
appartiene anche esso a U⊥. Conseguentemente Π
U(x) + λΠU(z)∈ U è una proiezione di x + λz. Per il Teorema 5, la proiezione di x + λz è unica. Pertanto
ΠU(x + λz) = ΠU(x) + λΠU(z),
cioè la proiezione ortogonale su U è lineare.
Usando ora il Teorema 1 e il fatto che U⊥ =ker Π
U, si ha che ogni vettore
x∈ Rn si può scrivere come somma
x = ΠU(x) + ΠU⊥(x).
Possiamo ora dimostrare che le proiezioni ortogonali godono della proprietà minimizzante che ci serve.
Teorema 7 (Teorema di approssimazione). Sia x ∈ Rn e U un sottospazio vettoriale. Allora, per ogni y∈ U con y 6= ΠU(x) si ha
Dimostrazione. Poniamo p = ΠU(x). Per le proprietà delle proiezioni ortogo-nali, x − p∈ U⊥ e p − y∈ U; pertanto, hx − p, p − yi = 0. Allora, ||x − y||2 2 = hx − y, x − yi = h(x − p) + (p − y), (x − p) + (p − y)i = ||x − p||2 2+ 2hx − p, p − yi +||p − y||22 =||x − p||22 +||p − y||22 Ora, se p 6= y, si ha||p − y||2 > 0 e, conseguentemente,||x − y||2 >||x − p||2. La tesi segue.
Il Teorema 7 mostra che la proiezione ortogonale gode di entrambe pro-prietà richieste per il proiettore Π da usarsi nella (5). Dunque, ogni vettore X tale che
AX = ΠU(B), (7)
ove U è l’immagine della applicazione lineare associata ad A è soluzione del problema (2) rispetto|| · ||2.
Dobbiamo ora dimostrare che la (7) è equivalente alle equazioni normali del sistema. Premettiamo un teorema.
Teorema 8. Sia A una matrice n× m. Allora, per ogni x ∈ Rn, y
∈ Rmvettori colonna si ha
hx, Ayi = hATx, yi.
In particolare, usando la notazione del Teorema 3 si ha Θx(Ay) = ΘATx(y).
Si osservi che Θx è un elemento del duale (Rn)∗di Rn mentre ΘATx è
un elemento del duale (Rm)∗
di Rm. In particolare, l’applicazione lineare A : Rm→ Rninduce una applicazione lineare A∗
: (Rn)∗ → (Rm)∗ fra gli spazi vettoriali duali; tale applicazione lineare è detta aggiunta di A.
Dimostrazione. Per ogni x∈ Rn,y∈ Rmsi ha
hx, Ayi = xTAy = (xTAy)T =yTATx = hy, ATxi = hATx, yi.
Se eXsoddisfa la (7), allora, per costruzione della proiezione ortogonale, B − A eX∈ U⊥, cioè, usando il Teorema 8, per ogni Z = AW ∈ U
al variare di W in Rm.
Ne segue AT(B − A eX) = 0, cioè che eXdeve essere soluzione delle equazioni normali
(ATA)X = ATB.
Viceversa, se ^Xè soluzione delle equazioni normali, allora per ogni W ∈ Rm,
0 =hW, AT(B − A ^X)i = hAW, B − A ^Xi;
pertanto, per ogni Y = AW ∈=A = U si ha hY, B−A ^Xi = 0, da cui B−A ^X ∈ U⊥.
Applicazioni ed esempi
Un esempio di applicazione dei sistemi iperdeterminati è dato dalla teoria dell’interpolazione.
Consideriamo dapprima un insieme di n punti (xi, yi) per i = 1, . . . , n assegnati nel piano cartesiano ordinario. Vogliamo trovare la retta y = mx+b che meglio approssima i punti assegnati, minimizzando la distanza euclidea rispetto l’insieme considerato.
A tal fine scriviamo il sistema lineare in nelle due indeterminate m, b dato dalle equazioni
mxi+ b = yi
al variare di i = 1, . . . , n. La matrice incompleta di tale sistema è
A = x1 1 x2 1 .. . xn 1 .
Le equazioni normali sono date da
ATAm b = AT y1 y2 .. . yn
Svolgendo i calcoli si ottiene x2 1+ x22+ . . . + x2n x1+ x2 + . . . xn x1+ x2+ . . . + xn n m b =x1y1+ x2y2+ . . . + xnyn y1+ y2+ . . . + yn ,
ovvero, in forma più compatta, Pn i=1x 2 i Pn i=1xi Pn i=1xi n m b = Pn i=1xiyi Pn i=1yi .
Il caso più generale, è il seguente: consideriamo un insieme di funzioni reali di variabile reale f0(x), f1(x), . . . fm(x) e assegnamo un insieme di n coppie ordinate (xi, yi). Si vogliono trovare degli scalari a0, a1, . . . , amtali che la funzione
f(x) = a0f0(x) + a1f1(x) + . . . + amfm(x)
sia la migliore approssimante possibile per le coppie assegnate, nel senso che la quantità y1 y2 .. . yn − f(x1) f(x2) .. . f(xn) 2
sia la più piccola possibile. Per raggiungere il nostro obiettivo consideriamo il sistema lineare dato da
f0(x1) f1(x1) . . . fm(x1) f0(x2) f1(x2) . . . fm(x2) .. . f0(xn) f1(xn) . . . fm(xn) a0 a1 .. . am = y0 y1 .. . yn
e cerchiamo una soluzione approssimata. Scriviamo la matrice incompleta M di questo sistema come giustapposizione di vettori colonna. Pertanto, avremo M = M0 M1 . . . Mm con Mi= fi(x1) fi(x2) .. . fi(xn) .
La posizione (i, j) della matrice S = MTMconterrà proprio il prodotto scalare hMi, Mji. Similmente, la i–esima riga di MTY, ove Y è il vettore colonna degli yisarà data dahMi, Yi. Pertanto, tenuto conto della simmetria del prodotto scalare, il sistema da risolvere qualora si cerchi una approssimazione ai minimi quadrati è
hM0, M0i hM0, M1i . . . hM0, Mmi hM0, M1i hM1, M1i . . . hM1, Mmi .. . ... hM0, Mmi hM1, Mmi . . . hMm, Mmi a0 a1 .. . am = hM0, Yi hM1, Yi .. . hMm, Yi
In particolare, il sistema ammette una unica soluzione se, e solamente se, il determinante della matrice simmetrica S è diverso da 0.
