A proposito di sistemi lineari
Visto che si parlava di sistemi lineari e visto che stanotte
non riuscivo a dormire, stavo pensando a qualche metodo
per risolvere velocemente dal punto di vista computazionale
un sistema lineare.
Mi è venuto in mente il seguente metodo che si applica ad ogni
sistema quadrato e forse è suscettibile di generalizzazioni.
Immagino che tale metodo già esista e se non esiste sarà perchè
computazionalmente fa più schifo di quanto mi sembra.
Infatti l'idea di base è molto semplice. Consideriamo in sistema
$2\times2$ (due equazioni e due incognite), geometricamente si
ricercano le intersezioni di due rette nel piano, che possiamo supporre
non entrambe ortogonali agli assi, altrimenti il problema si banalizza.
Dunque esiste un asse, diciamo l'asse $x$ per comodità, tale che ogni
ortogonale ad $x$ interseca entrambe le rette del sistema. Fissiamoci
allora un punto $x_0$ sull'asse $x$ e calcoliamo le intersezioni
fra la retta $x=x_0$ e le due rette date. Abbiamo due punti $A,B$. Calcoliamo
ora l'angolo formato dalle due rette date con questa retta $x=x_0$. Si hanno
le seguenti possibilità
1) le intersezioni coincidono e gli angoli trovati sono uguali: allora le due rette
coincidono. Fine.
2) le intersezioni coincidono e gli angoli trovatisono diversi: allora siamo stati
fortunati e abbiamo trovato subito l'unica soluzione. Fine.
3) le intersezioni non coincidono e gli angoli sono uguali: allora le rette sono parallele
e dunque non possono esservi soluzioni. Fine.
4) le intersezioni non coincidono e gli angoli sono diversi, a tal punto le rette sono
sicuramente incidenti in un punto $P$ che pensiamo vertice del triangolo $APB$ di cui
conosciamo un lato $AB$ e tutti gli angoli, dunque tale triangolo è unicamente determinato
ed è facile calcolarne la lunghezza del lato $AP$. A tal punto per determinare esplicitamente
l'intersezione $P$ basterà muoversi lungo la retta passante per $A$ percorrendo un tratto
di lunghezza $AP$. Fine.
Caso generale (sistema $n\timesn$
non perdo neanche tempo a scriverlo: si può supporre che esista un asse tale che ogni iperpiano
ortogonale intersechi tutti gli altri iperpiani, si calcolano gli angoli formati dai vari iperpiani e
nell'unico caso non banale resta univoamente definito un simplesso di dimensione $n$....
Costo Computazionale:
1)bisogna inizialmente trovare l'asse rispetto al quale lavorare... penso che non costi molto
2)bisogna calcolare tutti gli angoli (che sono $n$)... penso che non costi molto (mi sembra di
ricordare che ci siano delle formulette carine carine per farlo
3)bisogna calcolare la base del simplesso che è a sua volta un
simplesso di dimensione $n-1$ e quindi equivale a fare un determinante
$(n-1)\times(n-1)$
4)bisogna calcolare quanto sta lontano il punto di intersezione...
non ho idea di quanto costi...
non riuscivo a dormire, stavo pensando a qualche metodo
per risolvere velocemente dal punto di vista computazionale
un sistema lineare.
Mi è venuto in mente il seguente metodo che si applica ad ogni
sistema quadrato e forse è suscettibile di generalizzazioni.
Immagino che tale metodo già esista e se non esiste sarà perchè
computazionalmente fa più schifo di quanto mi sembra.
Infatti l'idea di base è molto semplice. Consideriamo in sistema
$2\times2$ (due equazioni e due incognite), geometricamente si
ricercano le intersezioni di due rette nel piano, che possiamo supporre
non entrambe ortogonali agli assi, altrimenti il problema si banalizza.
Dunque esiste un asse, diciamo l'asse $x$ per comodità, tale che ogni
ortogonale ad $x$ interseca entrambe le rette del sistema. Fissiamoci
allora un punto $x_0$ sull'asse $x$ e calcoliamo le intersezioni
fra la retta $x=x_0$ e le due rette date. Abbiamo due punti $A,B$. Calcoliamo
ora l'angolo formato dalle due rette date con questa retta $x=x_0$. Si hanno
le seguenti possibilità
1) le intersezioni coincidono e gli angoli trovati sono uguali: allora le due rette
coincidono. Fine.
2) le intersezioni coincidono e gli angoli trovatisono diversi: allora siamo stati
fortunati e abbiamo trovato subito l'unica soluzione. Fine.
3) le intersezioni non coincidono e gli angoli sono uguali: allora le rette sono parallele
e dunque non possono esservi soluzioni. Fine.
4) le intersezioni non coincidono e gli angoli sono diversi, a tal punto le rette sono
sicuramente incidenti in un punto $P$ che pensiamo vertice del triangolo $APB$ di cui
conosciamo un lato $AB$ e tutti gli angoli, dunque tale triangolo è unicamente determinato
ed è facile calcolarne la lunghezza del lato $AP$. A tal punto per determinare esplicitamente
l'intersezione $P$ basterà muoversi lungo la retta passante per $A$ percorrendo un tratto
di lunghezza $AP$. Fine.
Caso generale (sistema $n\timesn$
non perdo neanche tempo a scriverlo: si può supporre che esista un asse tale che ogni iperpiano
ortogonale intersechi tutti gli altri iperpiani, si calcolano gli angoli formati dai vari iperpiani e
nell'unico caso non banale resta univoamente definito un simplesso di dimensione $n$....
Costo Computazionale:
1)bisogna inizialmente trovare l'asse rispetto al quale lavorare... penso che non costi molto
2)bisogna calcolare tutti gli angoli (che sono $n$)... penso che non costi molto (mi sembra di
ricordare che ci siano delle formulette carine carine per farlo
3)bisogna calcolare la base del simplesso che è a sua volta un
simplesso di dimensione $n-1$ e quindi equivale a fare un determinante
$(n-1)\times(n-1)$
4)bisogna calcolare quanto sta lontano il punto di intersezione...
non ho idea di quanto costi...
Risposte
"ubermensch":
3)bisogna calcolare la base del simplesso che è a sua volta un
simplesso di dimensione $n-1$ e quindi equivale a fare un determinante
$(n-1)\times(n-1)$
Questo computazionalmente é molto pesante: viene $(n-1)!$ operazioni usando lo sviluppo di Laplace... direi che la complessitá é assolutamente proibitiva...
Comunque anche nel campo ultra-noto dei sistemi lineari ci sono molte cose interessanti da vedere. Ad esempio un metodo risolutivo molto efficiente e che, in aritmetica esatta, teoricamente fornisce la soluzione esatta dopo $n$ iterazioni é il metodo del gradiente coniugato:
http://en.wikipedia.org/wiki/Conjugate_gradient_method
che peró funziona solo su metrici hermitiane. Altrimenti un algortimo molto potente é il GMRES:
http://en.wikipedia.org/wiki/Gmres
che é quello usato da Matlab nel caso di matrici sparse di grandi dimensione. (altrimenti di solito si usano metodi LU)
*** EDIT ***
Da notare la data del GMRES: 1986. Recentissimo.
non pensavo costasse cosi tanto fare quel determinante...
...
ti ringrazio per i link, ma il realtà non è che mi interessi tanto questo
problema... ho postato un'idea che mi era venuta...
...
ti ringrazio per i link, ma il realtà non è che mi interessi tanto questo
problema... ho postato un'idea che mi era venuta...
"ubermensch":
ti ringrazio per i link, ma il realtà non è che mi interessi tanto questo
problema... ho postato un'idea che mi era venuta...
Non preoccuparti non è un "compito per casa"!
Ho aggiunto i link solo per completezza...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo