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

From: Tommaso Russo, Trieste <trusso_at_tin.it>
Date: Wed, 12 Dec 2012 01:39:27 +0100

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!


> 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.

*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" 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 :-)

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. Fra due zeri reali di f c'e' sicuramente uno zero di
f'; fra due zeri di f' c'e' sicuramente uno zero di f"; fra due zeri di
f^m c'e sicuramente uno zero di f^m+1.

Immagino che n sia al piu' dell'ordine del centinaio, altrimenti i
problemi cui vai incontro sono ben altri, di rappresentazione numerica.
Derivare 300 volte un polinomio di grado 300 e' una banalita':
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. Deriva f n-1 volte, fino a
determinare una retta, e salva tutti i coefficienti di tutte le derivate
in una matrice n x n+1.

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, 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.


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 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.



--
TRu-TS
Buon vento e cieli sereni
Received on Wed Dec 12 2012 - 01:39:27 CET