Mètode de Halley

En càlcul numèric el mètode de Halley és un algorisme per trobar arrels que es fa servir per a funcions d'una variable real amb un segona derivada continua, és a dir funcions de classe C². Se li posa el nom del seu inventor Edmond Halley que també va descobrir el Cometa de Halley.

L'algorisme és el segon en la classe dels mètodes de Householder, just després del Mètode de Newton. Igual com el mètode de Newton, produeix iterativament una successió d'aproximacions a l'arrel, la seva velocitat de convergència a l'arrel és cúbica. Hi ha versions pluridimensionals d'aquest mètode.

Mètode

Com qualsevol mètode de càlcut d'arrels, el mètode de Halley és un algorisme numèric per resoldre l'equació no lineal ƒ(x) = 0. En aquest cas, la funció ƒ ha de ser una funció d'una variable real. El mètode consta d'una successió d'iteracions:

x n + 1 = x n − 2 f ( x n ) f ′ ( x n ) 2 [ f ′ ( x n ) ] 2 − f ( x n ) f ″ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {2f(x_{n})f'(x_{n})}{2{[f'(x_{n})]}^{2}-f(x_{n})f''(x_{n})}}}

començant amb una suposició inicial x 0.

Si ƒ és una funció tres vegades contínuament derivable i a és un zero de ƒ però no de la seva derivada, llavors, en un veinatge de a, les iteracions x n satisfan:

| x n + 1 − a | ≤ K ⋅ | x n − a | 3 ,  per a algun  K > 0. {\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{3},{\text{ per a algun }}K>0.\!}

Això significa que les iteracions convergeixen al zero el valor inicial és suficientment proper, i que la convergència és cúbica.

Deducció

Considereu la funció

g ( x ) = f ( x ) | f ′ ( x ) | . {\displaystyle g(x)={\frac {f(x)}{\sqrt {|f'(x)|}}}.}

Qualsevol arrel de ƒ que no sigui una arrel de la seva derivada és una arrel de g i qualsevol arrel de g és una arrel de ƒ. El Mètode de Newton aplicat a g dona

x n + 1 = x n − g ( x n ) g ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}

amb

g ′ ( x ) = 2 [ f ′ ( x ) ] 2 − f ( x ) f ″ ( x ) 2 f ′ ( x ) | f ′ ( x ) | , {\displaystyle g'(x)={\frac {2{[f'(x)]}^{2}-f(x)f''(x)}{2f'(x){\sqrt {|f'(x)|}}}},}

i d'aquí se'n segueix el resultat. Fixeu-vos que si f′(c) = 0, llavors no es pot aplicar això a c perquè g(c) seria indefinit.

Convergència cúbica

Suposeu que a és una arrel de f però no de la seva derivada. I suposeu que e la tercera derivada de f existeix i és contínua en un veinatge de a i x n està en aquell veinatge. Llavors El teorema de taylor implica:

0 = f ( a ) = f ( x n ) + f ′ ( x n ) ( a − x n ) + f ″ ( x n ) 2 ( a − x n ) 2 + f ‴ ( ξ ) 6 ( a − x n ) 3 {\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(x_{n})}{2}}(a-x_{n})^{2}+{\frac {f'''(\xi )}{6}}(a-x_{n})^{3}}

i també

0 = f ( a ) = f ( x n ) + f ′ ( x n ) ( a − x n ) + f ″ ( η ) 2 ( a − x n ) 2 , {\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(\eta )}{2}}(a-x_{n})^{2},}

on ξ; i η; són nombres que estan entre a i xn. Multiplicant la primera equació per 2 f ′ ( x n ) {\displaystyle 2f'(x_{n})\!} i restant-li la segona equació multiplicada per f ″ ( x n ) ( u n − x n ) {\displaystyle f''(x_{n})(un-x_{n})\!} dona:

0 = 2 f ( x n ) f ′ ( x n ) + 2 [ f ′ ( x n ) ] 2 ( a − x n ) + f ′ ( x n ) f ″ ( x n ) ( a − x n ) 2 + f ′ ( x n ) f ‴ ( ξ ) 3 ( a − x n ) 3 − f ( x n ) f ″ ( x n ) ( a − x n ) − f ′ ( x n ) f ″ ( x n ) ( a − x n ) 2 − f ″ ( x n ) f ″ ( η ) 2 ( a − x n ) 3 . {\displaystyle {\begin{aligned}0&{}=2f(x_{n})f'(x_{n})+2[f'(x_{n})]^{2}(a-x_{n})\\&{}+f'(x_{n})f''(x_{n})(a-x_{n})^{2}+{\frac {f'(x_{n})f'''(\xi )}{3}}(a-x_{n})^{3}\\&{}-f(x_{n})f''(x_{n})(a-x_{n})-f'(x_{n})f''(x_{n})(a-x_{n})^{2}\\&{}-{\frac {f''(x_{n})f''(\eta )}{2}}(a-x_{n})^{3}.\end{aligned}}}

Anul·lant f ′ ( x n ) f ″ ( x n ) ( a − x n ) 2 {\displaystyle f'(x_{n})f''(x_{n})(a-x_{n})^{2}\!} i reorganitzant els termes resulta:

0 = 2 f ( x n ) f ′ ( x n ) + ( 2 [ f ′ ( x n ) ] 2 − f ( x n ) f ″ ( x n ) ) ( a − x n ) + ( f ′ ( x n ) f ‴ ( ξ ) 3 − f ″ ( x n ) f ″ ( η ) 2 ) ( a − x n ) 3 . {\displaystyle {\begin{aligned}0=2f(x_{n})f'(x_{n})&+{\big (}2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n}){\big )}(a-x_{n})\\&+\left({\frac {f'(x_{n})f'''(\xi )}{3}}-{\frac {f''(x_{n})f''(\eta )}{2}}\right)(a-x_{n})^{3}.\end{aligned}}}

Posant el segon terme a l'esquerra costat i dividint-ho tot entre 2 [ f ′ ( x n ) ] 2 − f ( x n ) f ″ ( x n ) {\displaystyle 2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})} s'aconsegueix:

a − x n = − 2 f ( x n ) f ′ ( x n ) 2 [ f ′ ( x n ) ] 2 − f ( x n ) f ″ ( x n ) − 2 f ′ ( x n ) f ‴ ( ξ ) − 3 f ″ ( x n ) f ″ ( η ) 6 ( 2 [ f ′ ( x n ) ] 2 − f ( x n ) f ″ ( x n ) ) ( a − x n ) 3 . {\displaystyle a-x_{n}={\frac {-2f(x_{n})f'(x_{n})}{2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}}-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{6(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n}))}}(a-x_{n})^{3}.}

Així:

a − x n + 1 = − 2 f ′ ( x n ) f ‴ ( ξ ) − 3 f ″ ( x n ) f ″ ( η ) 12 [ f ′ ( x n ) ] 2 − 6 f ( x n ) f ″ ( x n ) ( a − x n ) 3 . {\displaystyle a-x_{n+1}=-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{12[f'(x_{n})]^{2}-6f(x_{n})f''(x_{n})}}(a-x_{n})^{3}.}

El límit del coeficient de la dreta quan x n tendeix a a és:

− 2 f ′ ( a ) f ‴ ( a ) − 3 f ″ ( a ) f ″ ( a ) 12 [ f ′ ( a ) ] 2 . {\displaystyle -{\frac {2f'(a)f'''(a)-3f''(a)f''(a)}{12[f'(a)]^{2}}}.}

Si s'agafa K una mica més gran que el valor absolut d'això, es pot prendre valors absoluts dels dos costats de la fórmula i canviar el valor absolut del coeficient per la seva fita superior a prop de a per obtenir:

| a − x n + 1 | ≤ K | a − x n | 3 {\displaystyle |a-x_{n+1}|\leq K|a-x_{n}|^{3}}

que és el que s'havia de demostrar.

Referències

  • T.R. Scavo and J.B. Thoo, On the geometry of Halley's method. American Mathematical Monthly, 102:5 (1995), pp. 417–426.

Enllaços externs

  • Weisstein, Eric W., «Halley's method» a MathWorld (en anglès).
  • Halley's Method by John H. Mathews
  • Newton's method and high order iterations, Pascal Sebah and Xavier Gourdon, 2001 (the site has a link to a Postscript version for better formula display)