Mètode de Newton

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

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.

El mètode

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

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

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

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

i aïllant <math>\alpha\,</math>:

<math>\alpha\approx x_0-\frac{f(x_0)}{f'(x_0)}\,</math>,

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

Imatge gràfica

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 <math>x_0\,</math>, s'anirà trobant la successió <math>x_1,x_2,...\,</math>, fins a arribar a un cert valor que es donarà com a solució de <math>\alpha\,</math>.

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 <math>x_0\,</math> 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ó.

Exemple

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

La derivada de la funció és: <math>1+\sin x\,</math>, sempre és >0.

Es pot agafar com a valor d'inici: <math>x_0=0.5\,</math>.

I d'aquí:

<math>x_1=0.5-\frac{0.5-\cos 0.5}{1+\sin 0.5}=0.75522\,</math>

<math>x_2=0.75522-\frac{0.75522-\cos 0.75522}{1+\sin 0.75522}=0.73914\,</math>

<math>x_3=0.73914-\frac{0.73914-\cos 0.73914}{1+\sin 0.73914}=0.73909\,</math>

<math>x_4=0.73909-\frac{0.73909-\cos 0.73909}{1+\sin 0.73909}=0.73909\,</math>

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

Algorisme

Algorisme 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;

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 <math>F:R^n\rightarrow R^n\,</math>.

Si designem per <math>\mathbf{J}(\mathbf{x})\,</math> 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:

<math>\mathbf{x^{k}=x^{(k-1)}-J(x^{(k-1)})^{-1}F(x^{(k-1)})}\,</math>.

Expressió que recorda força l'anterior.

Vegeu també

• Mètode de Halley