Approssimazione media dei minimi quadrati

Descrizione del problema

Suppongo di avere le coppie di dati con nodi a due a due distinti, e numerosi. Cerco

dove è una base, e
per ogni , cioè è il polinomio che minimizza lo scarto quadratico medio. Inoltre, introducendo nella sommatoria pesi positivi, in modo da dare più importanza a determinati addendi rispetto ad altri, si ha
lo scopo è quello di minimizzare lo scarto quadratico medio pesato.

Determinazione del sistema

Considero per semplicità la base canonica dell'insieme dei polinomi, quindi . Considero

e inserendo l'espressione di nel lato destro della formula 1:
che è un funzionale nei parametri da determinare. Cerco il valore dei parametri per cui ottengo la minimizzazione di .


Il minimo rende stazionario il gradiente di , quindi calcolo le derivate parziali. Per ogni , si ha

e invertendo le sommatorie
Ho un sistema lineare di equazioni nelle incognite . Riscrivendo il tutto in maniera compatta ho il sistema:
dove
mentre
Per dimostrare che la soluzione di tale sistema è un minimo, analizzo la matrice . Devo verificare che l'hessiana è definita positiva e simmetrica.


Proposizione 5.1

La matrice è definita positiva, (e di conseguenza esiste unica la soluzione del problema, e è un minimo per .)

 
Dimostrazione

Fattorizzo la matrice per decomporla in pezzi, nella forma

è una matrice rettangolare di righe e colonne, con , è una matrice quadrata , mentre è .


è definita nel modo seguente.

La matrice della forma è detta matrice delle equazioni normali pesate. Il termine noto si può scrivere come . DIMOSTRO CHE È SIMMETRICA.
perché è diagonale.


DIMOSTRO CHE È DEFINITA POSITIVA


Per ogni , devo dimostrare che

e definecdo si ha

Supponiamo che abbia rango massimo. Allora , e siccome è definita positiva per definizione, .


DIMOSTRO CHE HA RANGO MASSIMO


Caso particolare: Consideriamo . Allora

Per esteso
Questa è la sottomatrice principale della matrice di Vandermonde. Siccome i nodi sono a due a due distinti, la Vandermonde è non singolare, allora ogni sua sottomatrice ha colonne linearmente indipendenti. ha rango massimo.


Considerando per lo spazio una qualsiasi altra base invece di quella canonica, vale la medesima proprietà. Infatti la matrice del cambiamento di base è non singolare e quindi il rango è conservato.

 



Nel caso della base canonica dei polinomi,

In particolare:

Ho una matrice con elementi costanti lungo le antidiagonali. Una matrice con questa struttura viene chiamata matrice di Henkel.

Ricerca della soluzione del sistema

Data la scrittura , l'approssimazione ai minimi quadrati, come impostato inizialmente, consiste nella risoluzione del sistema sovradeterminato di equazioni in incognite. Infatti, per minimizzare la norma del residuo, risolvo

Non c'è una soluzione classica di questo sistema, ma devo cercare una soluzione più debole.


Per minimizzare la norma euclidea del residuo, voglio determinare il vettore tale che

Invece di determinare la soluzione di cerco la soluzione di
(sistema delle equazioni normali). Se suppongo di avere pesi generici, posso definire
Posso pensare questa norma come la norma euclidea al quadrato di .

Possibilità per la risoluzione del sistema dei minimi quadrati

Prima possibilità: Considero la fattorizzazione di Cholesky, per matrici simmetriche e definite positive come .


Risolvo quindi i sistemi

Consideriamo per semplicità .


Analizzo il costo computazionale nella costruzione di :

ha elementi, e ognuno richiede prodotti. è simmetrica quindi basta calcolare metà degli elementi, per un totale di operazioni.


Siccome il costo della fattorizzazione di Cholesky di è , in totale ho: operazioni. Quando i dati sono molti ( grande) si hanno problemi di accuratezza e di rappresentabilità nella fattorizzazione di Cholesky.

Fattorizzazione QR per la risoluzione del sistema dei minimi quadrati

Supponiamo di avere di rango massimo (nel problema corrisponde a ). Calcoliamo la fattorizzazione QR di .


Considerata (nel caso di matrici rettangolari ho colonne da annullare), ottengo una matrice con righe e colonne, suddivisa in due blocchi: triangolare superiore e blocco trapezoidale di zeri delle sottocolonne annullate.


Il blocco superiore è sicuramente non singolare, perché ha rango massimo.

ma siccome è unitaria converva la norma 2:
e ponendo , siccome ha due blocchi e il secondo è nulo, e siccome , si ha
Cerco
che per quanto appena osservato è
Il primo addendo è minimo quando
e rimane

Si conclude che, data la matrice , si calcola la fattorizzazione e si risolve quindi

Il costo è per la fattorizzazione e per la risoluzione del sistema lineare, e in totale
che è maggiore di quello della fattorizzazione di Cholesky. Questo metodo però è più sicuro della fattorizzazione di Cholesky.

Relazione tra i due metodi

Tornando al problema di approssimazione, ci si chiede qual è la relazione tra che viene dall'applicazione della ad generica e che ottengo facendo la Cholesky. Queste matrici sono uguali a meno di matrici di fase (diagonali unitarie).

e differisce per una matrice di fase da .


Nel caso di pesi diversi da 1, si deve considerare la norma euclidea pesata e si può ripetere il procedimento analogo. Considero la norma 2 di

quindi considero QR di .

Condizionamento

Applicando la QR ad A, . Costruendo con la Cholesky, si ha . Quindi le equazioni normali hanno lo svantaggio di un indice di condizionamento quadrato rispetto a quello di .

 PrecedenteSuccessivo