Mètode de Halley

De Viquipèdia
Dreceres ràpides: navegació, cerca

En càlcul numèric el mètode de Halley és un algorisme per trobar arrels que es fa servirva per a funcions d'una variable real amb un segona derivada continua, és a dir funcions de classe C2. Se li posa el nom del seu inventor Edmond Halley que també va descobrir el Cometa 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[modifica | modifica el codi]

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 - \frac {2 f(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 | \le 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ó[modifica | modifica el codi]

Considereu la funció

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 dóna

x_{n+1} = x_n - \frac {g(x_n)} {g'(x_n)}

amb

g'(x) = \frac {2 {[f'(x)]}^2 - f(x) f''(x)} {2 f'(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[modifica | modifica el codi]

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) + \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) + \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)\! i restant-li la segona equació multiplicada per f''(x_n) (un - x_n)\! dóna:


\begin{align}
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 + \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{align}

Anul·lant f'(x_n) f''(x_n) (a - x_n)^2\! i reorganitzant els termes resulta:


\begin{align}
0 = 2 f(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{align}

Posant el segon terme a l'esquerra costat i dividint-ho tot entre  2 [f'(x_n)]^2 - f(x_n) f''(x_n) s'aconsegueix:


a - x_n = \frac{- 2 f(x_n) f'(x_n)}{2 [f'(x_n)]^2 - f(x_n) f''(x_n)}
- \frac{2 f'(x_n) f'''(\xi) - 3 f''(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} = 
- \frac{2 f'(x_n) f'''(\xi) - 3 f''(x_n) f''(\eta)} {12 [f'(x_n)]^2 - 6 f(x_n) f''(x_n)} (a - x_n)^3.

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


- \frac{2 f'(a) f'''(a) - 3 f''(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}| \leq K |a - x_n|^3

que és el què s'havia de demostrar.

Referències[modifica | modifica el codi]

  • 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[modifica | modifica el codi]