Polinomiale di 20° grado....quanto impiega un PC??

[Kumalo]

Ciao a tutti, scusate la domanda strana, ma c'e' stato un piccolo dibattito in sede universitaria.

La mia domanda e' proprio nel topic, c'e' un articolo, un documento che consenta di stabilire in quanto moderno computer (va bene qualsiasi computer) riesce a trovare le soluzioni di un' equazione di 20° grado?


Piu' che altro e' per una piccola scommessa che abbiamo fatto insieme ad un docente e ormai e' diventata anche una mia piccola curiosita'....

Grazie mille a chiunque si interessi

Byez

[fabrylama]

intendi quanto ci mette un pc a trovare le radici di un polinomio di ventesimo grado? qualche istante direi...

[stbarlet]

un ti89 ci impiega qualche secondo, un computer ( quoto quanto detto sopra) ci mette un istante.

[Wilcomir]

bisogna usare ruffini giusto? se è così penso che ci vorrebbe davvero poco, usando un sistema bruteforce roba dell'ordine di qualche minuto a seconda di quanto sfigata è l'equazione...

ciao!

[fabrylama]

bisogna usare ruffini giusto? se è così penso che ci vorrebbe davvero poco, usando un sistema bruteforce roba dell'ordine di qualche minuto a seconda di quanto sfigata è l'equazione...

ciao!

con ruffini trovi solo radici razionali, niente irrazionali o complesse. comunque io per "istante" mi riferivo al metodo "brute force" ovvero numericamente con il solito metodo di newton.

ps. Kumalo che facoltà fai?

[MaxArt]

con ruffini trovi solo radici razionali, niente irrazionali o complesse.E perché, il brute force che credi che trovi? :fagiano:

[stbarlet]

C'è anche il metodo Newton Rampson!

[fabrylama]

E perché, il brute force che credi che trovi? :fagiano:

tutto?

[stbarlet]

Dipende da come lo usi :p

[fabrylama]

C'è anche il metodo Newton Rampson!

a me risulta che il metodo di newton, quello di newton-ramphson e quello delle tangenti siano la stessa cosa

[MaxArt]

tutto?Sì, ma comunque soluzioni razionali approssimate.
Ruffini, poi, in teoria lo puoi usare per trovare tutto, ma se lo usi (e bene) in maniera simbolica, altrimenti è comunque un metodo brute force.

[pietro84]

Ciao a tutti, scusate la domanda strana, ma c'e' stato un piccolo dibattito in sede universitaria.

La mia domanda e' proprio nel topic, c'e' un articolo, un documento che consenta di stabilire in quanto moderno computer (va bene qualsiasi computer) riesce a trovare le soluzioni di un' equazione di 20° grado?


Piu' che altro e' per una piccola scommessa che abbiamo fatto insieme ad un docente e ormai e' diventata anche una mia piccola curiosita'....

Grazie mille a chiunque si interessi

Byez

con che precisione ti interessa?
appena provato con Matlab7 a risolvere una ventina di equazioni di ventesimo grado.
ci mette meno di un secondo.
Ho un Pentium4, 512MB RAM, Windows xp.

[fabrylama]

Sì, ma comunque soluzioni razionali approssimate.
Ruffini, poi, in teoria lo puoi usare per trovare tutto, ma se lo usi (e bene) in maniera simbolica, altrimenti è comunque un metodo brute force.

cioè con approssimazione numerica non trovi soluzioni complesse ed irrazzionali?

ps. com mathematica ne ho risolte 5 e ci mette in media mezzo secondo

[Pablitox]

Ciao a tutti, scusate la domanda strana, ma c'e' stato un piccolo dibattito in sede universitaria.

La mia domanda e' proprio nel topic, c'e' un articolo, un documento che consenta di stabilire in quanto moderno computer (va bene qualsiasi computer) riesce a trovare le soluzioni di un' equazione di 20° grado?


Piu' che altro e' per una piccola scommessa che abbiamo fatto insieme ad un docente e ormai e' diventata anche una mia piccola curiosita'....

Grazie mille a chiunque si interessi

Byez

appena provato con la ti89T e ci ha messo 1'40" circa

[Sberloz]

Un computer moderno casalingo impiega poche frazioni di secondo, praticamente un batter d'occhi

[Kumalo]

mmmmm allora mi sa che aveva ragione.....

Faccio lo IUSM Istituto Universitario Scienze Motorie

La curiosita' e' nata dal fatto che stavamo analizzando la curva del battito cardiaco secondo andamenti e pendenze di corsa, e ovviamente su 20 rilevamenti in diverse condizioni avevamo un punto in tabella.

Per calcolare la risultante precisa quindi dovevamo fare una equazione di grado n-1 ovvero 20-1=19 e trovare le varie incognite.

Al che io che ho una calcolatrice scientifica con processore da 333mhz impiego 4/5 minuti a trovare le incognite.


Tutto qui pensavo che una di 20° grado ci volesse molto piu' tempo :)


Grazie cmq

[Pablitox]

mmmmm allora mi sa che aveva ragione.....

Faccio lo IUSM Istituto Universitario Scienze Motorie

La curiosita' e' nata dal fatto che stavamo analizzando la curva del battito cardiaco secondo andamenti e pendenze di corsa, e ovviamente su 20 rilevamenti in diverse condizioni avevamo un punto in tabella.

Per calcolare la risultante precisa quindi dovevamo fare una equazione di grado n-1 ovvero 20-1=19 e trovare le varie incognite.

Al che io che ho una calcolatrice scientifica con processore da 333mhz impiego 4/5 minuti a trovare le incognite.


Tutto qui pensavo che una di 20° grado ci volesse molto piu' tempo :)


Grazie cmq

Wow:sofico:

[MaxArt]

Al che io che ho una calcolatrice scientifica con processore da 333mhz impiego 4/5 minuti a trovare le incognite.Pensa che la TI-89 che ti hanno detto ha 12 MHz... :rolleyes:

[fabrylama]

333? quella calcolatrice monta un celeron per caso? :mbe: :asd:

[stbarlet]

Pensa che la TI-89 che ti hanno detto ha 12 MHz... :rolleyes:

Si può anche portare a frequenze più alte :read:

[fsdfdsddijsdfsdfo]

mmmmm allora mi sa che aveva ragione.....

Faccio lo IUSM Istituto Universitario Scienze Motorie

La curiosita' e' nata dal fatto che stavamo analizzando la curva del battito cardiaco secondo andamenti e pendenze di corsa, e ovviamente su 20 rilevamenti in diverse condizioni avevamo un punto in tabella.

Per calcolare la risultante precisa quindi dovevamo fare una equazione di grado n-1 ovvero 20-1=19 e trovare le varie incognite.

Al che io che ho una calcolatrice scientifica con processore da 333mhz impiego 4/5 minuti a trovare le incognite.


Tutto qui pensavo che una di 20° grado ci volesse molto piu' tempo :)


Grazie cmq

è un problema MOLTO piu complesso di quanto tu possa credere.

Quello che fai tu è (mi pare di aver capito) costruire un polinomio dalle interpolazioni. Che è piuttosto facile.


Partendo invece da un polinomio di 20° grado trovare le soluzioni è MOLTO MOLTO difficile.

Esiste un teorema che dimosta che non esistono algoritmi per trovare soluzioni algebriche (esatte) di grado superiore al III.

Con i metodi tradizionali (newton rapson ed affini) l'errore per gradi cosi alti ESPLODE rendendo di fatto il tutto inutilizzabile.


Bisogna correggere le iterate con una prova sul polinomio, rendendo tutto MOOLTO lento.

[stbarlet]

Come calcolano le soluzioni i software dei calcolatrici/pc?

[fsdfdsddijsdfsdfo]

Come calcolano le soluzioni i software dei calcolatrici/pc?

dipende?

di che cosa? di polinomi?

Un unica soluzione o tutte quante?

[Maverick18]

Al che io che ho una calcolatrice scientifica con processore da 333mhz impiego 4/5 minuti a trovare le incognite.


333 Mhz mi sembrano veramente esagerati per una semplice calcolatrice, comunque non dare troppo peso alla frequenza di un cpu per avere un quadro delle prestazioni.

[stbarlet]

dipende?

di che cosa? di polinomi?

Un unica soluzione o tutte quante?

tutte

[fsdfdsddijsdfsdfo]

tutte

non esiste un algoritmo generalizzato efficace. E' un grande problema della matematica moderna, nonchè ciò di cui vorrei occuparmi :D


O sono troppo lunghi, o troppo imprecisi. Ma davvero imprecisi.

ma tu pensi ai polinomi di XX grado.... qui i matematici e gli informatici sbattono la testa quando ne vedono uno di secondo... cercano di ridurre tutto a casi lineari.

[stbarlet]

non esiste un algoritmo generalizzato efficace. E' un grande problema della matematica moderna, nonchè ciò di cui vorrei occuparmi :D


O sono troppo lunghi, o troppo imprecisi. Ma davvero imprecisi.

ma tu pensi ai polinomi di XX grado.... qui i matematici e gli informatici sbattono la testa quando ne vedono uno di secondo... cercano di ridurre tutto a casi lineari.

ok.. capisco.

Ma ad esempio.. chessò.. derive? una ti89?

[fsdfdsddijsdfsdfo]

ok.. capisco.

Ma ad esempio.. chessò.. derive? una ti89?

una ti89 dando una lettura veloce al manuale mi pare che non ne dia la possibilità (di trovare tutte le radici) e non saprei

Derive non credo ti faccia trovare tutte le radici, mi pare che il suo algoritmo funzioni proprio male (ha gravi problemi alla base, e per questo è stato abbandonato)

Matlab, programma serio e documentato, invece usa una sorta di correlazione geometrica. Si riconduce il polinomio ad una matrice che ha un particolare significato dal punto di vista geometrico e...

The algorithm simply involves computing the eigenvalues of the companion matrix:

A = diag(ones(n-1,1),-1);
A(1,:) = -c(2:n+1)./c(1);
eig(A)

It is possible to prove that the results produced are the exact eigenvalues of a matrix within roundoff error of the companion matrix A, but this does not mean that they are the exact roots of a polynomial with coefficients within roundoff error of those in c.


Spiegazione: Il metodo funziona. E' veloce.

E l'errore è piccolo se misurato rispetto alla matrice. Ma può essere molto grande rispetto al polinomio.

[MaxArt]

Si può anche portare a frequenze più alte :read:Pensa che 12 MHz era la frequenza del mio primo 286... :doh:

Esiste un teorema che dimosta che non esistono algoritmi per trovare soluzioni algebriche (esatte) di grado superiore al III.Al quarto. ;) Il risultato è dovuto ad Evariste Galois.

333 Mhz mi sembrano veramente esagerati per una semplice calcolatrice, comunque non dare troppo peso alla frequenza di un cpu per avere un quadro delle prestazioni.La HP nelle sue calcolatrici di punta usa frequenze di 203 MHz, non so che tipo sia questa con una da 333 MHz...

ma tu pensi ai polinomi di XX grado.... qui i matematici e gli informatici sbattono la testa quando ne vedono uno di secondo... cercano di ridurre tutto a casi lineari.:mbe: Io no...
Sino al secondo grado non ho problemi, per terzo e quarto mi prendo un riferimento per le formule cardaniche.
Ma il vero casino è quando si hanno a che fare con equazioni differenziali non lineari...

[fsdfdsddijsdfsdfo]

Al quarto. ;) Il risultato è dovuto ad Evariste Galois.


è vero :D:D MEA CULPA


:mbe: Io no...
Sino al secondo grado non ho problemi, per terzo e quarto mi prendo un riferimento per le formule cardaniche.


il problema è che usando polinomi di secondo grado quando fai molti calcoli il numero di operazioni cresce MOLTO velocemente, in grado di rendere in fretta il problema non risolvibile

Poter avere un metodo lineare permette di controllare in ogni momento la crescita del numero di operazioni.

Io finchè non mi sono trovato a diretto contatto con questi problemi non mi sono accorto di quanto limitata fosse la potenza dei nostri pc.


Ma il vero casino è quando si hanno a che fare con equazioni differenziali non lineari...

e quà non so. Le ho iniziate l'anno scorso, sto ancora facendo i metodi algebrici. QUelli numerici l'anno prossimo :D

[stbarlet]

Pensa che 12 MHz era la frequenza del mio primo 286... :doh:

Al quarto. ;) Il risultato è dovuto ad Evariste Galois.

La HP nelle sue calcolatrici di punta usa frequenze di 203 MHz, non so che tipo sia questa con una da 333 MHz...

:mbe: Io no...
Sino al secondo grado non ho problemi, per terzo e quarto mi prendo un riferimento per le formule cardaniche.
Ma il vero casino è quando si hanno a che fare con equazioni differenziali non lineari...


Non ditelo a Lucrezio ( e magari frà un pò pure a me :asd:)..



PS ma non è che uno di voi volenterosi matematici :read: fa un bel trattatino su ognuno dei simboli di derivata/differenziale?

[fabrylama]

ho provato con mathematica con 5 polinomi a caso del ventesimo grado, imponendogli una WorkingPrecision di 100 cifre, ci mette un istante, tira fuori anche le soluzioni complesse e provando a reinserirla nel polinomio da un valore dell'ordine di 1x10^-95 che mi pare un ottimo zero.

[Tommy81]

Io ho provato con Mathcad a risolvere una di ventesimo grado e ci ha messo un istante. Anche a me ha trovato le soluzioni non reali.

[fabrylama]

Io ho provato con Mathcad a risolvere una di ventesimo grado e ci ha messo un istante. Anche a me ha trovato le soluzioni non reali.

con quante cifre ha fatto i calcoli?

[fsdfdsddijsdfsdfo]

ho provato con mathematica con 5 polinomi a caso del ventesimo grado, imponendogli una WorkingPrecision di 100 cifre, ci mette un istante, tira fuori anche le soluzioni complesse e provando a reinserirla nel polinomio da un valore dell'ordine di 1x10^-95 che mi pare un ottimo zero.

l'errore non è grande per tutti i polinomi. Ma può diventare grande facilmente. E' il range della norma ad aumentare, non l'errore in se.


Prova ad esempio a calcolare le soluzioni del polinomio (x-1)^20

[Kumalo]

Cmq ora ho diciamo capito un bel po' la situazione, vi ringrazio molto, la calcolatrice entro un paio di giorni vi dico marca e modello, e' di un mio amico che fa ingegneria elettronica me l'ha prestata proprio per questo esame di Biomeccanica dato che io allo iusm non faccio propriamente materie scientifiche.

Cmq grazie mille davvero non pensavo di sollevare cosi' tanta curiosita' :)

Saluti

[fabrylama]

l'errore non è grande per tutti i polinomi. Ma può diventare grande facilmente. E' il range della norma ad aumentare, non l'errore in se.


Prova ad esempio a calcolare le soluzioni del polinomio (x-1)^20

allora, prima la ho espansa, perchè altrimenti mathematica la risolveva al volo, e quindi fa:
x^20 - 20 x^19 + 190 x^18 - 1140 x^17 + 4845 x^16 - 15504 x^15 +
38760 x^14 - 77520 x^13 + 125970 x^12 - 167960 x^11 + 184756 x^10 -
167960 x^9 + 125970 x^8 - 77520 x^7 + 38760 x^6 - 15504 x^5 +
4845 x^4 - 1140 x^3 + 190 x^2 - 20 x + 1 = 0

inserita in mathematica con precisione nei calcoli di 20 cifre
NSolve[x^20 - 20 x^19 + 190 x^18 - 1140 x^17 + 4845 x^16 - 15504 x^15 +
38760 x^14 - 77520 x^13 + 125970 x^12 - 167960 x^11 + 184756 x^10 -
167960 x^9 + 125970 x^8 - 77520 x^7 + 38760 x^6 - 15504 x^5 +
4845 x^4 - 1140 x^3 + 190 x^2 - 20 x + 1 == 0, x,
WorkingPrecision -> 20]

come soluzione:
{{x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x ->
1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x ->
1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x ->
1.}, {x -> 1.}, {x -> 1.}}

tutto questo in un tempo impercettibile, invece con una precisione di 10 cifre da dei risultati sbagliati.

[kikino]

allora, prima la ho espansa, perchè altrimenti mathematica la risolveva al volo, e quindi fa:
x^20 - 20 x^19 + 190 x^18 - 1140 x^17 + 4845 x^16 - 15504 x^15 +
38760 x^14 - 77520 x^13 + 125970 x^12 - 167960 x^11 + 184756 x^10 -
167960 x^9 + 125970 x^8 - 77520 x^7 + 38760 x^6 - 15504 x^5 +
4845 x^4 - 1140 x^3 + 190 x^2 - 20 x + 1 = 0

inserita in mathematica con precisione nei calcoli di 20 cifre
NSolve[x^20 - 20 x^19 + 190 x^18 - 1140 x^17 + 4845 x^16 - 15504 x^15 +
38760 x^14 - 77520 x^13 + 125970 x^12 - 167960 x^11 + 184756 x^10 -
167960 x^9 + 125970 x^8 - 77520 x^7 + 38760 x^6 - 15504 x^5 +
4845 x^4 - 1140 x^3 + 190 x^2 - 20 x + 1 == 0, x,
WorkingPrecision -> 20]

come soluzione:
{{x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x ->
1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x ->
1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x -> 1.}, {x ->
1.}, {x -> 1.}, {x -> 1.}}

tutto questo in un tempo impercettibile, invece con una precisione di 10 cifre da dei risultati sbagliati.

Basta mettere l'istruzione Nsolve come argomento di Timing[] e ti conta quanto impiega per rispolvere l'equazione. Sul mio 0.203 secondi

[fabrylama]

Basta mettere l'istruzione Nsolve come argomento di Timing[] e ti conta quanto impiega per rispolvere l'equazione. Sul mio 0.203 secondi

sul mio 0.063 (mathematica 6)