Newsgroup: it.comp.lang.c++
Titolo: Risolvere un sistema lineare 4x4

  Dovrei risolvere due sistemi lineari di 4 equazioni in 4 incognite,
di cui ho la matrice dei coefficienti (float) e il vettore dei termini
noti. Una matrice è del tipo
a 0 c 0
0 f g 0
i j k l
m n o p
e devo risolverla solo una volta. L'altra è del tipo
a b c 0
e f g 0
i j 0 l
m n 0 p
e devo risolverla decine di volte al secondo. Cosa potrei usare che
non mi complichi troppo la vita?
Ipotesi 1: appoggiarmi ad una libreria specializzata tipo Lapack++
(che, per quello che devo fare, mi sembra come prendere un aereo per
andare a comprare il pane, e le cui firme dei metodi non mi sembrano
molto user-friendly)
Ipotesi 2: usare il metodo di Cramer, cosa che però implica il calcolo
del determinante della matrice; e il determinante di una matrice 4x4 è
dispendioso da calcolare senza usare programmazione dinamica (a meno
che non debba implementare un metodo veloce... ma allora tanto vale
implementare una fattorizzazione LU con cui risolvere tutto il
sistema!)
Ipotesi 3: sviluppare a manina le formule (es. per sostituzione) e
scriverle direttamente...
  Ci sono altre librerie C++ non commerciali che lo fanno in modo
"semplice"? Mi servirebbe un singolo metodo che risolve un sistema 4x4
(o che calcola il determinante in modo veloce). Se può servire,
sviluppo su Linux...
  Consigli?
  Grazie...
--
  Narcolessico
 
http://binaryunit.blogspot.com

 c'è la soluzione dei sistemi lineari.
Grazie, se in poco trovo un equivalente in Octave seguirò il tuo
consiglio. Ti ricordi mica il nome esatto della funzione/comando?
PS: perchè chiedi l'annullamento automatico del messaggio dopo un tot
di giorni?
--
  Narcolessico
 
http://binaryunit.blogspot.com

 Apx.
Saluti ed auguri di buona Pasqua
Manlio Perillo

 scriverle direttamente...
Io utilizzerei la 2, (o se preferisci la 3, che è lo stesso). Infatti un 
algoritmo generico ti creerebbe comunque un ciclo, che in questo caso, 
penso, ti farebbe perdere tempo. Inoltre la presenza di alcuni zeri 
potrebbe semplificarti un po' la formula.
E.

 tuoconsiglio. Ti ricordi mica il nome esatto della funzione/comando?
Per il calcolo simbolico, matlab e'... lasciamo perdere le volgarita',
e diciamo semplicemente "scomodo". Ti consiglio di provare
maple/mathematica (se hai un universita' che fornisce uno di questi,
come capitava a me qualche anno fa) oppure macsyma (se non sbaglio lo
spelling, dovrebbe essere l'equivalente opensource). Sono fatti
esplicitamente per il calcolo simbolico.
Ciao,
Marco
 
-- 
I'm using an evaluation license of nemo since 218 days.
You should really try it!
http://www.malcom-mac.com/nemo

  Ho provato Maxima... è fantastico! Il determinante di una matrice
4x4 mi è venuto così:
a*(f*(k*p-l*o)-g*(j*p-l*n)+h*(j*o-k*n))+
-b*(e*(k*p-l*o)-g*(i*p-l*m)+h*(i*o-k*m))+
+c*(e*(j*p-l*n)-f*(i*p-l*m)+h*(i*n-j*m))+
-d*(e*(j*o-k*n)-f*(i*o-k*m)+g*(i*n-j*m))
Non è cortissima, ma devo ancora sistemare gli zeri al loro posto. Ho
chiesto la soluzione del sistema e ho ottenuto delle formule simili a
questa; tanto vale evitare Cramer e calcolare direttamente le
soluzioni. Per ottimizzare, userò formule specifiche per ogni matrice.
@?manu*: quali altri ng frequentiamo io e te? :)
  Grazie a tutti per i consigli.
--
  Narcolessico
 
http://binaryunit.blogspot.com

 matrice.
Metti gli zeri nella forma simbolica (fai due versioni della cos), e
usa la funzione di semplificazione per semplificare.Poi fatti un po'
di raccoglimenti a mano, e il gioco e' fatto :)
E non usare Cramer, usa la sua funzione di soluzione dei sistemi.
--*PaN!*
 
-- 
I'm using an evaluation license of nemo since 219 days.


  E non usare Cramer, usa la sua funzione di soluzione dei sistemi.
Ovviamente non ho letto la seconda frase, in cui dici esattamente
quello che ti ho scritto :)


 soluzioni. Per ottimizzare, userň formule specifiche per ogni matrice.


 numerica", la perdita di precisione nel sottrarre quantita' "vicine".
Sottoscrivo.
Anche se mi par difficile trovare queste condizioni nelle matrici
citate dall'op, e' una cosa di cui tenere conto.
--*PaN!*
 
-- 
I'm using an evaluation license of nemo since 219 days.


  In effetti non ho specificato nulla sull'applicazione. Nella prima
matrice i coefficenti sono tutti numeri naturali minori di 1300; i
valori delle incognite nella prima matrice diventano i coefficienti
del secondo sistema. Per il primo, sistemando gli zeri, Maxima ha
prodotto:
x = (c1*(h*k*n-f*k*p)+b*(c2*k*p-c3*g*p+h*(c3*o-c4*k))+d*(f*(c4*k-c3*o)-
c2*k*n+c3*g*n)) /
(b*(e*k*p-g*i*p+h*(i*o-k*m))+d*(f*(k*m-i*o)-e*k*n+g*i*n))
y = (...)
c'è una sola divisione tra numeri interi, quindi quello che mi
preoccupa sono solo eventuali overflow. Devo ancora controllare il
range effettivo dei numeri in input, ma credo che con un long con
segno dovrei farcela con ampio margine di sicurezza (nel caso peggiore
moltiplicherò 4 numeri minori di 1300 tra loro).
Per la seconda matrice, ottengo:
x=(c*(c2*(j*p-l*n)+f*(c4*l-c3*p))+c1*g*(l*n-j*p)+b*g*(c3*p-c4*l)) /
(c*(e*(j*p-l*n)+f*(l*m-i*p))+a*g*(l*n-j*p)+b*g*(i*p-l*m))
y = (...)
anche qui, una sola divisione. Il caso di parametri uguali a zero è
rarissimo (e, comunque, non ci possono essere più di k zeri
contemporaneamente, credo con k=2), quindi sia denominatore che
numeratore non dovrebbero (de)crescere fino a dare problemi. Infine
devo arrotondare ad un intero, quindi la precisione che mi interessa è
solo al primo decimale.
Mi rendo conto che il mio ragionamento è zeppo di condizionali e
controlli "a occhio", ma al momento non serve una grande precisione né
accuratezza. Al momento mi serve un sistema appena funzionante, ma
ottenuto quello riprenderò il mio bel libro di analisi numerica e
andrò a calcolare il numero di condizionamento delle matrici e la
precisione del calcolo in base al range di input, che è sottoposto a
diversi vincoli.
PS: Max può stare tranquillo: niente elettromedicali per ora, solo
finger tracking ;)
--
  Narcolessico
 
http://binaryunit.blogspot.com

 solofinger tracking ;)
Potrebbe essere sempre usato in futuro per trackare la mano di un
chirurgo ed eseguire in modo robotizzato un'operazione a cuore aperto
:)


 :)
Beh, prima o poi di qualcosa si muore :D
--
  Narcolessico
 
http://binaryunit.blogspot.com

 guasterebbe...
Se il denominatore s'annulla e il numeratore pure significhera' anche
che il sistema ha soluzione, ma non e' unica, il che e' in contrasto
con quanto hai detto prima (una e una sola soluzione). Inoltre il
fatto che c1 sia nullo se b e d sono nulli, mi fa sospettare che ci
sia qualcosa in piu' rispetto ad un sistema 4x4...
Non hai in realta' 5 incognite e un vincolo non lineare (chesso'
quadratico) vero?!? :)


 sia qualcosa in piu' rispetto ad un sistema 4x4...
No, è che ho copiato la prima matrice invertendo le prime due righe
(l'avrò presa da altri appunti). E mi sono appena accorto di un
errore: la seconda riga della prima matrice dovrebbe essere "0 f 0 h"
e non "0 f g 0". Invertendo le prime due righe si ha:
0 b 0 d
e 0 g 0
i j k l
m n o p
da cui si vede subito che b=d=0 => c1=0
--
  Narcolessico
 
http://binaryunit.blogspot.com

  da cui si vede subito che b=d=0 => c1=0
Ok, mi mancava il fatto che c1 fosse la soluzioe del primo sistema.
Ma quindi son sistemi omogenei?


 Ma quindi son sistemi omogenei?
No... Volevo vedere quando il denominatore della frazione si
azzerasse, e uno dei casi in cui si azzera è quando  b e d sono nulli.
Ma se b e d sono  nulli, allora anche c1 lo è (perchè la prima
equzione del sistema è b*y+d*w = c1, con y e w incognite); ovvero, la
matrice ha rango inferiore a 4 e ci sono infinite soluzioni. Ma
parlavo dell'ipotesi in cui b=d=0, non di una cosa che avviene sempre.
L'ultimo passaggio era: so per certo che i valori della matrice
producono sempre un sistema determinato, con una ed una sola
soluzione; per cui b=d=0 (o, più in genere, una frazione indeterminata
o una divisione per zero) non dovrebbero avvenire mai, se non per
cancellazione numerica (ovvero per errori di precisione).
--
  Narcolessico
 
http://binaryunit.blogspot.com

  No...
Ah ecco, mi tornano piu' cose... altrimenti se avessero avuto sempre
una e una sola soluzione, questa sarebbe sempre stata nulla, ma a
questo punto mi pareva troppo strano.
--
Marco
 
-- 
I'm using an evaluation license of nemo since 220 days.


 m n 0 p
In entrambi i casi, utilizzerei il metodo specifico, visto che queste 
forme sono note e fisse, quindi andrei con il metodo 3. Di sicuro il 
metodo è molto ottimizzabile, quindi ti garantisce il massimo delle 
performance.
In alternativa utilizzerei la riduzione LU che viene fatta in due tempi; 
se nel secondo sistema a cambiare sono i soli termini noti, si fa il 
primo passo offline e il secondo passo online, risparmiando una metà del 
tempo.