M??tode de Newton

De Viquip??dia

En c??lcul num??ric, el m??tode de Newton, o m??tode de Newton-Raphson, ??s un algoritme per tal de trobar aproximacions del zero d'una funci?? amb valors reals.

Taula de continguts

1 Hist??ria
2 El m??tode
3 Imatge gr??fica
4 Observacions
5 Exemple
6 Algoritme
7 Generalitzaci??

[edita] Hist??ria

El m??tode Newton va ser descobert per Isaac Newton i publicat al Method of Fluxions al 1736. Tot i que aquest m??tode tamb?? sigui descrit per Joseph Raphson a Analysis Aequationum al 1690, cal dir que el Method of Fluxions ja havia estat escrit al 1671.

[edita] El m??tode

Suposem que la funci?? $f\,$ ??s cont??nuament diferenciable dues vegades a l'interval $\left[a,b\right]\,$ , o sigui $f\in C^{2}\left[a,b\right]\,$ . I existeix un zero de la funci?? en aquest interval. Direm que $\alpha\in\left[a,b\right]\,$ ??s la soluci?? si $f\left(\alpha\right)=0\,$ .

Sigui $x_0\in\left[a,b\right]\,$ una aproximaci?? a la soluci?? $\alpha \,$ tal que $f'\left(x_0\right)\ne 0\,$ . Si escrivim el polinomi de Taylor de primer grau per a $f\left(x\right)\,$ al voltant de $x_0\,$ , tindrem: $f(x)=f(x_{0})+(x-x_{0})f^{\prime }(x)+\frac{(x-x_{0})^{2}}{2}f^{\prime \prime }(\xi (x))\,$

Per?? com que $f(\alpha)=0\,$ , aquest anterior polinomi de Taylor, el podem escriure de la forma: $0=f(x_{0})+(\alpha-x_{0})f^{\prime }(x)+\frac{(\alpha-x_{0})^{2}}{2}f^{\prime \prime }(\xi (\alpha))\,$ .

En aquest punt, el m??tode de Newton suposa que el terme $(\alpha-x_{0})^{2}\,$ ser?? menyspreable, i que: $0\approx f(x_0)+(\alpha-x_0)f'(x)\,$ ,

i a??llant $\alpha\,$ :

$\alpha\approx x_0-\frac{f(x_0)}{f'(x_0)}\,$ ,

que ha de ser una millor aproximaci?? cap a $\alpha\,$ . Anomenem $x_1\,$ a aquesta millor aproximaci??. Per inducci?? definim una successi?? de valors de $x_n\,$ , que es pot escriure de la forma: $x_n=x_{(n-1)}-\frac{f(x_{(n-1)})}{f'(x_{(n-1)})}\,$ , amb $n\ge 1\,$ .

[edita] Imatge gr??fica

Imatge:M??tode de Newton.png

L'aproximaci?? gr??fica ??s la seg??ent: S'escull un valor de l'abscissa raonablement pr??xim al aut??ntic zero. En aquest punt, es reempla??a la corba per la seva tangent, i es calcula el zero d'aquesta recta tangent. Aquest zero, normalment, ??s m??s pr??xim al zero de la funci??, que el valor inicial. Aquest proc??s es reitera, fins arribar a una aproximaci?? que es d??na per bona. En el cas de la gr??fica, a partir de $x_0\,$ , s'anir?? trobant la successi?? $x_1,x_2,...\,$ , fins a arribar a un cert valor que es donar?? com a soluci?? de $\alpha\,$ .

[edita] Observacions

La fallada d'aquest m??tode, normalment ve motivada per l'anul??laci?? del valor de la derivada en algun punt entre el valor del zero de la funci?? i el valor $x_0\,$ inicial que s'hagi agafat com aproximaci?? d'arrencada. No cal dir que l'efici??ncia d'aquest m??tode tamb?? est?? en saber trobar una aproximaci?? inicial suficientment pr??xima a la soluci??.

[edita] Exemple

Suposem que es vulgui trobar un valor de la $x\,$ que fa que $x-\cos x=0\,$ . Es pot intuir que existeix un valor entre 0 i 1 que ha de complir aquesta condici??.

La derivada de la funci?? ??s: $1+\sin x\,$ , sempre ??s >0.

Es pot agafar com a valor d'inici: $x_0=0.5\,$ .

I d'aqu??:

$x_1=0.5-\frac{0.5-\cos 0.5}{1+\sin 0.5}=0.75522\,$

$x_2=0.75522-\frac{0.75522-\cos 0.75522}{1+\sin 0.75522}=0.73914\,$

$x_3=0.73914-\frac{0.73914-\cos 0.73914}{1+\sin 0.73914}=0.73909\,$

$x_4=0.73909-\frac{0.73909-\cos 0.73909}{1+\sin 0.73909}=0.73909\,$

Valor que evidentment soluciona el problema, dins l'aproximaci?? en qu?? s'ha treballat.

[edita] Algoritme

Algoritme M??tode_Newton
funci?? func(x:real): real; /retorna el valor de la funci?? en x.
funci?? deriv(x:real): real;/retorna el valor de la derivada en x.
 
var.x0=W: real;/W allunyat de V, per evitar que |x0-x1|<Tol.
   x1=V: real;  /V=aproximaci?? inicial.
   Tol: real;/Tol=marge m??xim d'error que s'acceptar??.
   n=N: enter;/controla el n??mero d'iteracions, m??xim N.
 
fer 
   mentre [n>0] i [|x0-x1|>Tol] fer
      x0=x1;
      x1=x0-func(x0)/deriv(x0); 
      n=n-1;
   fi mentre;
   si n>0
      SORTIDA=x1;
   altrament
      SORTIDA=ERROR;
   fi si;
fi proc??s;

[edita] Generalitzaci??

Es pot tamb?? utilitzar el m??tode de Newton per tal de resoldre sistemes de n equacions (generalment no lineals), aix?? representa trobar els zeros de les funcions cont??nuament derivables $F:R^n\rightarrow R^n\,$ .

Si designem per $\mathbf{J}(\mathbf{x})\,$ la matriu jacobiana d'aquest sistema de funcions, el m??tode de Newton en aquest cas, es pot escriure amb el seg??ent proc??s iteratiu: