Re: ricerca radici di polinomio di grado qualsiasi (anche non intersecante, ma solo tangente, l'asse X)

From: Soviet_Mario <Soviet.Mario_at_CCCP.MIR>
Date: Mon, 17 Dec 2012 18:30:48 +0100

Il 12/12/2012 01:39, Tommaso Russo, Trieste ha scritto:
> Il 10/12/2012 18:01, Soviet_Mario ha scritto:
>>
>> Vorrei un parere comparativo, relativo ai due metodi, delle tangenti
>> (Newton) e delle secanti o corde.
>> In particolare non sono iper-interessato all'efficienza pura, chi
>> converge prima e chi no, quanto piuttosto a quale ritenete più
>> "resiliente" ad andamenti avversi, tipo come dicevo sopra, la mera
>> tangenza all'asse X (quindi il non potersi avvalere del cambio segno).
>
> Ma nessuno dei due!

grazie Tommaso, sei un amico !

A proposito, aggiungo qualche info sulla natura di questi
polinomi, nel caso esista qualche suggerimento ancora più
utile di quelli che già fai dopo.
Si possono tutti descrivere come

(a1-n1X)^n1*(a2-n2X)^n2*...*(az-nzX)^nz = K* (segue)...
(b1-m1X)^m1*(b2-m2X)^m2*...*(bt-mtX)^mt

dove,
a1 a2 a3 ... az sono positivi (reali)
b1 b2 b3 ... bt sono positivi (reali)
n1 n2 n3 ... nz sono naturali
m1 m2 m3 ... mz sono naturali
K è positivo (reale)

vale inoltre, sempre, che ogni monomio è strettamente
maggiore di zero, per cui il primo membro ed il secondo sono
sempre positivi.

Avevo pensato di ristrutturarlo come

N * (a1/n1 - X)^n1*(a2/n2 - X)^n2*...*(az/nz - X)^nz = K * D * (b1/m1 - X)^m1*(b2/m2 - X)^m2*...*(bt/mt - X)^mt

dove N = n1^n1 * n2^n2 * ... * nz^nz
ed D = m1^m1 * m2^m2 * ... * mt^mt

inglobando le costanti, diventerebbe ancora

(A1 - X)^n1*(A2 - X)^n2*...*(Az - X)^nz -
- K# * (B1 - X)^m1*(B2 - X)^m2*...*(Bt - X)^mt = 0

spostando i due pezzi al primo membro

Praticamente il problema si può anche vedere come trovare le
intersezioni, ad ascisse positive, di due funzioni, entrambe
sempre positive (e definite in un dominio che sia :
X < A1 ∩ X < A2 ∩ ... ∩ X < Az
∩
X < B1 ∩ X < B2 ∩ ... ∩ X < Bt

per dare significato fisico ai termini dentro le parentesi,
che devono essere strettamente positivi, zero escluso

>
>
>> Si consideri anche il grado elevato a sufficienza da rendere parimenti
>> non immediato il calcolo delle derivate esatte (pure calcolabili, dato
>> che i polinomi sono noti), specialmente nel porle uguali a zero per
>> cercare massimi minimi e flessi (nel qual caso il problema ricasca
>> ricorsivamente in quello presente).
>>
>> E' vero che usando il metodo delle secanti la convergenza non è
>> monotòna, sebbene sia comunque garantita anche se la funzione nella zona
>> indagata fa le bizze e cambia curvatura ed ha anche più di una radice ?
>>
>> Se invece nei paraggi non ha nessuna radice, ne trova necessariamente
>> una più lontana o l'andamento diventa caotico ?
>
>
> Mario, mi pare che intendi usare i metodi delle secanti e delle tangenti
> *al di fuori* degli scopi per cui sono stati inventati e dei casi in cui
> garantiscono la convergenza.

ottimo a sapersi. E in effetti sto trovando risultati
aleatori, a volte beccano altre no, e pure la bisezione mi
lascia in braghe di tela

>
> *Entrambi* i metodi garantiscono la convergenza solo se applicati a un
> intervallo chiuso in cui e' certo che vi sia una e una sola radice di
> f=0, e nel quale il prodotto f'*f"

urc ! ! Bella questa, le due derivate consecutive devono
avere segno costante o che si inverte simultaneamente ???
Non c'era su delle fotocopie che mi ha dato una collega di
matematica. Ma che significato geometrico ha il segno del
prodotto delle due derivate ? Inoltre il problema di
studiare il segno delle derivate, è ricorsivamente uguale al
mio problema, dato che sono esse pure polinomi, quindi io
non posso accertare questi segni a meno di non sapere già
risolvere i polinomi

> non cambi mai di segno. Se queste
> condizioni sono soddisfatte, entrambe le convergenze sono monotone e da
> direzione diversa; per questo si usano entrambi i metodi, per terminare
> quando la differenza fra i due e' inferiore alla precisione cercata. Se
> queste condizioni non sono soddisfatte, entrambi i metodi possono
> benissimo divergere. Tantopiu' se nell'intervallo la funzione fa le
> bizze :-)

Mi è capitato invece pure che non convergessero a velocità
ragionevoli, o che trovassero dei minimi locali e
rimanessero intrappolate lì.

>
> Non sono certamente adatti a cercare zeri, e tantomeno zeri multipli, in
> un intervallo su cui dell'andamento di f non si sa nulla.
>
>
> Visto che sai che f e' un polinomio di grado n, io sfrutterei piuttosto
> questa conoscenza.

MODALITA' SPUGNA ON :-) ghghghgh

> Fra due zeri reali di f c'e' sicuramente uno zero di
> f';

ok

> fra due zeri di f' c'e' sicuramente uno zero di f";

ok

> fra due zeri di
> f^m c'e sicuramente uno zero di f^m+1.

ricorsivamente Ok ... inquietante nella sua ovvietà, ma
tant'è ... grazie alla provvidenza, avevo già per mero
sfizio implementato la funzione di derivazione ennesima,
sino al termine costante finale.

>
> Immagino che n sia al piu' dell'ordine del centinaio, >

no no, direi della decina normalmente.

> altrimenti i
> problemi cui vai incontro sono ben altri, di rappresentazione numerica.
> Derivare 300 volte un polinomio di grado 300 e' una banalita':

Vero.

> sopratutto visto che delle derivate qui interessano solo gli zeri, e
> quindi si puo' normalizzare a 1 il coefficente del termine di grado
> massimo di ogni polinomio derivata.

cioè, raccolgo il termine del massimo grado ? Non capisco in
cosa mi semplifichi i calcoli. Come risparmio di memoria è
irrisorio, ma mi complicherebbe la rappresentazione interna
di monomio, con un caso particolare di assenza di
coefficiente che mi ingrippa l'uniforme rappresentazione.

> Deriva f n-1 volte, fino a
> determinare una retta,

bene, quindi se ho un ottavo grado, derivo sette volte.

> e salva tutti i coefficienti di tutte le derivate
> in una matrice n x n+1.

okappa

>
> Ora determina gli estremi inferiore e superiore di un intervallo
> [lower,upper] d'interesse: se la conoscenza del problema reale non ti e'
> d'aiuto,

si, questo lo posso fare e già lo usavo per innescare la
ricerca, il dominio è il più restrittivo di tutte le
condizioni di positività di ciascun monomio.

> puoi usare il teorema di Cauchy: tutti gli zeri reali di un
> polinomio
>
> a_0 + a_1 x + a_2 x^2 ... + a_n x^n
>
> sono compresi nell'intervallo [-a, a] con
>
> a = 1 + max (| a_i/a_n |) , i=/=n.

uhm ... qui mi sono perso completamente.
che valore assume la i ?
è un contatore iterativo (0<=i<n) con cui scandire tutti i
rapporti, e di cui selezionare il massimo ?


>
>
> Parti dalla derivata n-1esima, trova il suo zero x_0 (c'e' di sicuro,
> altrimenti il polinomio non e' di grado n ma inferiore), e verifica se
> cade all'inteno di [lower,upper]. Se cade al di fuori, mantieni un solo
> intervallo

cioè mantengo inalterato l'intervallo che avevo
predeterminato ? Scusa le domande banali, ma non ho
chiaramente intuito dove si debba andare a parare.

> per passare alla derivata n-2esima. Se cade invece
> al'interno, dividi [upper,lower] nei due intervalli [lower,x_0] e
> [x_0,upper]. Per ogni sottointervallo, se la f^n-2 cambia di segno fra
> gli estremi (o E' zero ad uno degli estremi), li' c'e' uno zero, e *uno
> solo*.
>
> Per trovarlo, visto che privilegi la robustezza alla velocita', puoi
> usare il metodo della bisezione, che e' il piu' robusto che si conosca,
> indipendentemente dall'andamento delle derivate: la convergenza e'
> lineare e non superlineare (ma anche il metodo delle tangenti e' lineare
> se la radice e' multipla), ma con funzioni rapide da calcolare come i
> polinomi non sara' certo questo un problema (suggerimento: per calcolare
> i valori dei polinomi usare l'algoritmo di Horner, o almeno conservare
> x^n per il calcolo di x^(n+1), il che rispetto ad Horner si limita a
> raddoppiare il tempo necessario).
>
> Se invece la f^n-2 non cambia di segno, li' semplicemente un suo zero
> non c'e', e puoi passare avanti.
>
> Ad ogni passo trovi gli zeri reali di f^(n-m) compresi fra lower e
> upper, e li usi per definire gli intervalli in cui cercherai gli zeri
> della derivata precedente, essendo sicuro che in ogni intervallo ce n'e'
> al piu' uno; fino ad arrivare agli zeri della derivata di ordine zero,
> ossia del polinomio di partenza.
>

Allora, ora mi ristudio tutto per bene, e rimando eventuali
altri commenti a dopo, ma devo innanzitutto ringraziarti per
la disponibilità e la spiegazione dettagliata.
P.S. non so se alla fine lo farò, perché in fondo è uno
sfizio, e non so manco se e quanto ti possa interessare
(presumo una epsilon piccola a piacere), ma quando/se farò
funzionare al meglio questo programma "didattico" di
risoluzione di multi equilibri, vorrei vedere se per caso su
"Chimica nella Scuola" accettano software oltre ad articoli
di solo testo, e se si, ovviamente ti citerei volentieri
come coautore e consulente matematico.
Ma non sono sicurissimo di perdere interesse (già scarso) a
questo aspetto. Tutto sommato vorrei solo uno strumento di
risoluzione simultanea, per valutare rapidamente in vari
contesti una miriade di formule approssimate che usiamo per
trattare gli equilibri.
ciao
CCCP


>
>


--
1) Resistere, resistere, resistere.
2) Se tutti pagano le tasse, le tasse le pagano tutti
Soviet_Mario - (aka Gatto_Vizzato)
Received on Mon Dec 17 2012 - 18:30:48 CET