Matrice Tridiagonale Simmetrica con Vincoli
Salve a tutti ho un'assoluta necessità di trovare un algoritmo facilemente implementabile al pc che dia la possibilità di risolvere una matrice con vincoli.
Ovvero, conosco tutti gli elementi della matrice (A) e il vettore noto (b).
Devo risolvere Ax=b e come vincolo ho 2 valori, in particolare nel mio caso la prima e l'ultima componente del vettore x.
La matrice è tridiagonale simmetrica.
Qualcuno conosce come potrei risolvere?
Vi ringrazio!
Per cortesia qualcuno risponda!! Ne ho davvero bisogno!
Ovvero, conosco tutti gli elementi della matrice (A) e il vettore noto (b).
Devo risolvere Ax=b e come vincolo ho 2 valori, in particolare nel mio caso la prima e l'ultima componente del vettore x.
La matrice è tridiagonale simmetrica.
Qualcuno conosce come potrei risolvere?
Vi ringrazio!
Per cortesia qualcuno risponda!! Ne ho davvero bisogno!
Risposte
Ciao,
in pratica possiedi fissati due soluzioni di due variabili?
"zannas":
Devo risolvere Ax=b e come vincolo ho 2 valori, in particolare nel mio caso la prima e l'ultima componente del vettore x.
in pratica possiedi fissati due soluzioni di due variabili?
Dici che la matrice è simmetrica, quindi è quadrata n x n.
Se è di rango pieno, non puoi specificare a capocchia la prima e l'ultima componente del vettore soluzione.
Se è di rango non superiore a n-2, se ne può parlare.
Dicci di più.
Se è di rango pieno, non puoi specificare a capocchia la prima e l'ultima componente del vettore soluzione.
Se è di rango non superiore a n-2, se ne può parlare.
Dicci di più.
alla fine ho risolto.
E' di rango pieno e ho la prima e l'ultima componente del vettore soluzione prefissate.
Ho il numero di equazioni > numero incongnite.
Alla fine ho risolto cercando la soluzione che minimizza lo scarto.
Se volete più informazioni ditemelo che ri-cerco e vi linko il pdf a cui mi sono ispirato
E' di rango pieno e ho la prima e l'ultima componente del vettore soluzione prefissate.
Ho il numero di equazioni > numero incongnite.
Alla fine ho risolto cercando la soluzione che minimizza lo scarto.
Se volete più informazioni ditemelo che ri-cerco e vi linko il pdf a cui mi sono ispirato
Se hai più equazioni (m) che incognite (n) la matrice non è quadrata e non può essere simmetrica come hai detto.
Se è di rango pieno (n), non puoi assegnare a piacere due componenti del vettore soluzione.
Quello che puoi fare è, come dici, minimizzare lo scarto risolvendo ai minimi quadrati, ad esempio mediante decomposizione in valori singolari (SVD), il sistema m x n-2
$[[A_{1\ 2},...,A_{1\ n-1}],[...,...,...],[A_{m\ 2},...,A_{m\ n-1}]] [[x_2],[...],[x_{n-1}]] = [[b_1-A_{1\ 1}x_1-A_{1\ n}x_n],[...],[b_m-A_{m\ 1}x_1-A_{m\ n}x_n]]$
In questo modo i vincoli, almeno, sono rispettati.
Se è di rango pieno (n), non puoi assegnare a piacere due componenti del vettore soluzione.
Quello che puoi fare è, come dici, minimizzare lo scarto risolvendo ai minimi quadrati, ad esempio mediante decomposizione in valori singolari (SVD), il sistema m x n-2
$[[A_{1\ 2},...,A_{1\ n-1}],[...,...,...],[A_{m\ 2},...,A_{m\ n-1}]] [[x_2],[...],[x_{n-1}]] = [[b_1-A_{1\ 1}x_1-A_{1\ n}x_n],[...],[b_m-A_{m\ 1}x_1-A_{m\ n}x_n]]$
In questo modo i vincoli, almeno, sono rispettati.
@vpindarico: come ha specificato zannas, in questo caso la matrice è quadrata ma le "equazioni in più" sono sul vincolo che due delle incognite sono date.
@zannas: conoscendo il valore di \(x_1\), dalla prima equazione \(a_1x_1 + a_2x_2 = b_1\) ricavi al volo \(x_2\); avendo \(x_1\) e \(x_2\), dalla seconda ricavi immediatamente \(x_3\) e così via fino alla fine.
Arrivato all'ultima riga, ottieni una relazione di uguaglianza: se è vera, il problema ammette soluzione esatta; se è falsa, allora non c'è soluzione e devi cercare una soluzione approssimata, come hai fatto tu.
@zannas: conoscendo il valore di \(x_1\), dalla prima equazione \(a_1x_1 + a_2x_2 = b_1\) ricavi al volo \(x_2\); avendo \(x_1\) e \(x_2\), dalla seconda ricavi immediatamente \(x_3\) e così via fino alla fine.
Arrivato all'ultima riga, ottieni una relazione di uguaglianza: se è vera, il problema ammette soluzione esatta; se è falsa, allora non c'è soluzione e devi cercare una soluzione approssimata, come hai fatto tu.
"Raptorista":
@vpindarico: come ha specificato zannas, in questo caso la matrice è quadrata ma le "equazioni in più" sono sul vincolo che due delle incognite sono date.
Dici? Eppure zannas scrive, fuor di metafora:
Ho il numero di equazioni > numero incongnite.
Secondo te si avrebbe un sistema quadrato n x n più
$x_1=val_1$
$x_n=val_n$
?
Ma in questo caso sarebbe immediato sostituire e ridursi ad un sistema m x n-2
Comunque, in generale, sarebbe buona cosa se chi pone la domanda postasse anche un esempio, per evitare di correre dietro alle farfalle.
È vero, invece, che ho completamente e colpevolmente trascurato il fatto che il sistema è tridiagonale. E sì che sta scritto persino nel titolo.
"vpindarico":
Eppure zannas scrive, fuor di metafora:
Ho il numero di equazioni > numero incongnite.
Secondo te si avrebbe un sistema quadrato n x n più
$x_1=val_1$
$x_n=val_n$
?
Ma in questo caso sarebbe immediato sostituire e ridursi ad un sistema m x n-2
Capisco e concordo con ciò che dici; potrei risponderti che è una questione di gusti, e in questo caso il modo più semplice di procedere mi sembra quello di risolvere il sistema e vedere se le soluzioni sono compatibili con le condizioni aggiuntive, per una semplice questione di come è fatta la matrice [e perché, come hai detto tu, con una matrice quadrata perdi le proprietà di simmetria e tridiagonalità].
Detto ciò, se tanto poi uno deve ripiegare su una soluzione del tipo "minimi quadrati", questi discorsi sono un po' inutili XD
...forse mi sono spiegato male, ma Raptorista mi pare abbia capito il problema.
Allora, avevo una matrice (A) tridiagonale simmetrica.
Dovevo risolvere Ax=b con x1 e xn fissati a priori (= i famosi vincoli). Quindi al momento n equazioni.
A questo punto ho riscritto il sistema ottenendo m=n-2 incognite e n equazioni. Ottengo una matrice che non è più quadrata.
Ho risolto il tutto cercando la soluzione che minimizza lo scarto. Tutto qui.
Il file pdf a cui mi sono ispirato è stato: http://linux3.dti.supsi.ch/~smt/courses ... nversa.pdf
Allora, avevo una matrice (A) tridiagonale simmetrica.
Dovevo risolvere Ax=b con x1 e xn fissati a priori (= i famosi vincoli). Quindi al momento n equazioni.
A questo punto ho riscritto il sistema ottenendo m=n-2 incognite e n equazioni. Ottengo una matrice che non è più quadrata.
Ho risolto il tutto cercando la soluzione che minimizza lo scarto. Tutto qui.
Il file pdf a cui mi sono ispirato è stato: http://linux3.dti.supsi.ch/~smt/courses ... nversa.pdf
"zannas":
...forse mi sono spiegato male, ma Raptorista mi pare abbia capito il problema.
Ho risolto il tutto cercando la soluzione che minimizza lo scarto. Tutto qui.
Il file pdf a cui mi sono ispirato è stato: http://linux3.dti.supsi.ch/~smt/courses ... nversa.pdf
Le dispense che hai linkato propongono le equazioni normali, che in generale peggiorano il condizionamento del problema originario. Tieni presente che potresti usare in alternativa la decomposizione in valori singolari.
hai un qualche link teorico-pratico riguardante ciò?
http://en.wikipedia.org/wiki/Singular_v ... omposition
http://www.uwlax.edu/faculty/will/svd/index.html
http://www.math.umn.edu/~lerman/math5467/svd.pdf
Golub + Van Loan, Matrix Computations, §2.5
Press + Teukolsky + Vetterling + Flannery, Numerical Recipes in C, §2.6
Il manuale della libreria open source GSL (GNU Scientific Library) alla voce gsl_linalg_svd_decomp
http://www.uwlax.edu/faculty/will/svd/index.html
http://www.math.umn.edu/~lerman/math5467/svd.pdf
Golub + Van Loan, Matrix Computations, §2.5
Press + Teukolsky + Vetterling + Flannery, Numerical Recipes in C, §2.6
Il manuale della libreria open source GSL (GNU Scientific Library) alla voce gsl_linalg_svd_decomp
interessante!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo