From paolini Wed Jan 22 15:49:33 1997 To: ngbellia@flashnet.it Subject: Re: RADICI REALI E COMPLESSE ESATTE X-Sun-Charset: US-ASCII Content-Length: 4176 X-Lines: 116 Status: RO Egregio Sig. Bellia, trovo ora il tempo per una risposta sulla questione del confronto tra i due metodi. Per inciso, le chiederei di non spedirmi documenti scritti in "word": in studio non ho un PC, e non posso stamparli se non con grosse difficolta'; a tutt'ora non ho idea di cosa ci sia nell'attachment che aveva incluso nell'ultima mail. ------------------------ Vorrei prima di tutto fissare le idee, considerando la prima fase del suo algoritmo, cioe' l'identificazione della prima radice, nella forma in cui era riportato nel suo documento "bellia04.doc", e senza tenere conto degli errori di arrotondamento, cioe' operando in aritmetica esatta. ------------------------ Metodo di Newton (penso di non dirle nulla di sostanzialmente nuovo): Il problema da risolvere e' p(x) = 0, dove p e' una generica funzione (almeno derivabile), e nel nostro caso p(x) sara' un polinomio in x di grado n. Dato un valore di innesco x_0 si calcola x_1 con la formula: x_1 = x_0 - p(x_0)/p'(x_0) e, iterativamente, dato x_k si calcola x_{k+1} = x_k - p(x_k)/p'(x_k) Poi c'e' un certo numero di teoremi, di cui parlero' piu' avanti, che permettono di dare condizioni sufficienti a garantire che la successione delle x_k converge ad una soluzione x_* del problema. Per convergenza intendo dire che la differenza x_* - x_k tende a zero quando k tende all'infinito. Altri teoremi permettono di stabilire a quale velocita' le iterate x_k convergono a x_*. ------------------------ Cio' che sostengo e' che la prima fase del suo metodo coincide con il metodo di Newton applicato a partire dal valore di innesco x_0 = 0 (qui e nel seguito x_0 indica x con l'indice 0, mentre x^n indichera' x elevato a n). Coincide nel senso che l'iterata x_k ottenuta con il metodo di Newton vale proprio x_k = t_1 + t_2 + ... + t_k, dove t_i, per i da 1 a k, indicano le successive traslazioni ottenute con il suo metodo. Dimostrazione: Dimostriamo per prima cosa che x_1 = t_1. Questo e' facile perche' per il metodo di Newton si ha x_1 = x_0 - p(x_0)/p'(x_0), ma x_0 = 0, quindi p(x_0) = p(0) e' il coefficiente del termine di grado 0 del polinomio, e p'(x_0) = p'(0) e' il coefficiente del termine di grado 1 del polinomio, quindi x_1 = - A_n/A_{n-1} = t_1. Poi si procede per induzione, supponendo valida la tesi per k, la voglio dimostrare per k+1. Osservo anche che il polinomio p(x) puo' essere scritto nella cosiddetta "forma traslata" p(x) = (x - x_k)^n + b_1 (x - x_k)^{n-1} + ... + b_{n-1} (x - x_k) + b_n , dove i coefficienti b_1, b_2, ..., b_n sono proprio le quantita' calcolate quando si effettua la traslazione k-esima, in effetti, il risultato della traslazione k-esima consiste in una traslazione del polinomio originale di una quantita' t_1 + t_2 + ... + t_k, che per l'ipotesi induttiva vale proprio x_k. Ora il metodo di Newton fornisce x_{k+1} = x_k - p(x_k)/p'(x_k), ma e' immediato verificare che, usando la forma traslata, p(x_k) = b_n, e p'(x_k) = b_{n-1}, cioe' x_{k+1} = x_k + t_{k+1} = t_1 + t_2 + ... + t_{k+1}. (QED) ----------------------- Il metodo di Newton ha poi la classica interpretazione grafica che permette di interpretare x_{k+1} come l'intersezione con l'asse delle x della tangente alla curva nel punto di coordinate (x_k, p(x_k)). In effetti il metodo di Newton e' spesso chiamato "metodo delle tangenti". ----------------------- Gradirei un commento su questo prima di approfondire il discorso. Vorrei aggiungere che non mi pare che lei stia smontando le mie obiezioni, come afferma nella sua home-page, esse sono esattamente quelle che erano all'inizio del nostro scambio di opinioni, e cioe' che ritengo il suo metodo equivalente al metodo di Newton, dal punto di vista matematico (se non si tiene conto degli errori di arrotondamento e dei tempi di calcolo, come affermo nella mia lettera al Direttore di Famiglia Cristiana), mentre lo considero peggiore sia dal punto di vista degli errori di arrotondamento che del tempo di calcolo. > Speriamo di essere riusciti ad accendere qualche fuoco. Questo lo spero vivamente anch'io. Cordiali saluti. Maurizio Paolini