From root Thu Jan 23 04:39 MET 1997 Received: from Star.Flashnet.It by ten.dimi.uniud.it with SMTP id AA15221 (5.67a/IDA-1.5 for ); Thu, 23 Jan 1997 04:39:33 +0100 Received: from ngbellia.flashnet.it (ppp-009.isdn.flashnet.it [194.247.165.9]) by star.flashnet.it (8.8.4/8.7) with SMTP id EAA00216 for ; Thu, 23 Jan 1997 04:39:32 +0100 Return-Path: Message-Id: <32E6DD1A.10AA@flashnet.it> Date: Thu, 23 Jan 1997 04:38:02 +0100 From: ngbellia@flashnet.it X-Mailer: Mozilla 3.0 (Win95; I) Mime-Version: 1.0 To: Maurizio Paolini Subject: Re: RADICI REALI E COMPLESSE ESATTE References: <199701221449.PAA00564@fusine> Content-Transfer-Encoding: quoted-printable X-Mime-Autoconverted: from 8bit to quoted-printable by star.flashnet.it id EAA00216 X-Lines: 174 Status: RO Gentilissimo Prof. Paolini. Prima di addormentarmi ho meditato sull'algoritmo di Newton ed eccomi pronto a commentare la sua e-mail. Nel ringraziarLa le invio cordiali saluti. Nicol=F2 Giuseppe Bell=ECa Maurizio Paolini wrote: >=20 > Egregio Sig. Bellia, >=20 > trovo ora il tempo per una risposta sulla questione del confronto tra i > due metodi. >=20 > Per inciso, le chiederei di non spedirmi documenti scritti in "word": i= n > 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. >=20 > ------------------------ >=20 > Vorrei prima di tutto fissare le idee, considerando la prima fase del s= uo > algoritmo, cioe' l'identificazione della prima radice, nella forma in c= ui > era riportato nel suo documento "bellia04.doc", e senza tenere conto > degli errori di arrotondamento, cioe' operando in aritmetica esatta. >=20 > ------------------------ >=20 > Metodo di Newton (penso di non dirle nulla di sostanzialmente nuovo): >=20 > Il problema da risolvere e' p(x) =3D 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: >=20 > x_1 =3D x_0 - p(x_0)/p'(x_0) >=20 > e, iterativamente, dato x_k si calcola >=20 > x_{k+1} =3D x_k - p(x_k)/p'(x_k) >=20 > Poi c'e' un certo numero di teoremi, di cui parlero' piu' avanti, che > permettono di dare condizioni sufficienti a garantire che la succession= e > 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_*. >=20 > ------------------------ >=20 > Cio' che sostengo e' che la prima fase del suo metodo coincide con il m= etodo > di Newton applicato a partire dal valore di innesco x_0 =3D 0 (qui e ne= l > 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 >=20 > x_k =3D t_1 + t_2 + ... + t_k, >=20 > dove t_i, per i da 1 a k, indicano le successive traslazioni ottenute c= on il > suo metodo. CONCORDO PERFETTAMENTE E NON HO BISOGNO DI ALCUNA DIMOSTRAZIONE IN QUANTO LA COSA MI E' INTUITIVAMENTE CHIARA. IO TRASLO LA MIA FUNZIONE DELLE STESSE QUANTITA' CON LE QUALI NEWTON SI=20 AVVICINA ALLA RADICE: CIO' MI E' EVIDENTE DI PER SE STESSO. SE QUANTO SEGUE SERVE A DIMOSTRARE LA VERITA' DI QUANTO PRECEDE VORREI CHE=20 VENISSE SALTATO IN QUANTO LO SFORZO PER CAPIRE TUTTO IL SIMBOLISMO MI DISTOGLIE DAI DUE PROCEDIMENTI. ACCERTATO CHE LA PRIMA RADICE CALCOLATA CON I DUE METODI E' LA STESSA, QUELLO CHE A ME INTERESSA CAPIRE E' COME SI PROCEDE CON IL METODO DI NEWTON PER CALCOLARE LA SUCCESSIVA RADICE. IO VORREI CHE LEI CORTESEMENTE RIPRENDESSE IL DISCORSO DA QUESTO PUNTO. >=20 > Dimostrazione: >=20 > Dimostriamo per prima cosa che x_1 =3D t_1. Questo e' facile perche' p= er il > metodo di Newton si ha x_1 =3D x_0 - p(x_0)/p'(x_0), ma x_0 =3D 0, qu= indi > p(x_0) =3D p(0) e' il coefficiente del termine di grado 0 del polinomio= , e > p'(x_0) =3D p'(0) e' il coefficiente del termine di grado 1 del polinom= io, quindi >=20 > x_1 =3D - A_n/A_{n-1} =3D t_1. >=20 > Poi si procede per induzione, supponendo valida la tesi per k, la vogli= o > dimostrare per k+1. >=20 > Osservo anche che il polinomio p(x) puo' essere scritto nella cosiddett= a > "forma traslata" >=20 > p(x) =3D (x - x_k)^n + b_1 (x - x_k)^{n-1} + ... + b_{n-1} (x - x_k) + = b_n , >=20 > dove i coefficienti b_1, b_2, ..., b_n sono proprio le quantita' calcol= ate > quando si effettua la traslazione k-esima, in effetti, il risultato del= la > 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. >=20 > Ora il metodo di Newton fornisce >=20 > x_{k+1} =3D x_k - p(x_k)/p'(x_k), >=20 > ma e' immediato verificare che, usando la forma traslata, p(x_k) =3D b_= n, e > p'(x_k) =3D b_{n-1}, cioe' >=20 > x_{k+1} =3D x_k + t_{k+1} =3D t_1 + t_2 + ... + t_{k+1}. (QED) >=20 > ----------------------- >=20 > Il metodo di Newton ha poi la classica interpretazione grafica che perm= ette > 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". >=20 > ----------------------- >=20 > Gradirei un commento su questo prima di approfondire il discorso. >=20 > Vorrei aggiungere che non mi pare che lei stia smontando le mie obiezio= ni, > come afferma nella sua home-page, esse sono esattamente quelle che eran= o > all'inizio del nostro scambio di opinioni, e cioe' che ritengo il suo m= etodo > 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 l= o > considero peggiore sia dal punto di vista degli errori di arrotondament= o > che del tempo di calcolo. CREDO DI AVERLE DIMOSTRATO CHE L'ESATTEZZA DEL MIO METODO E' PARI A QUELLA DI=20 NEWTON FACENDO L'ULTIMA TRASLAZIONE CORRETTIVA PONENDO K COME SOMMA DI TUTTE LE TRASLAZIONI CHE HANNO PORTATO LA FUNZIONE SULL'ORIGINE. DEL RESTO IO POTREI ARRIVARE ALLA PRIMA RADICE ANCHE CON IL METODO DI NEWTON. QUELLO CHE CONTA PER ME E' OTTENERE LE RIDOTTE. >=20 > > Speriamo di essere riusciti ad accendere qualche fuoco. > Questo lo spero vivamente anch'io. >=20 > Cordiali saluti. >=20 > Maurizio Paolini