Mètode de Halley: diferència entre les revisions
Contingut suprimit Contingut afegit
Pàgina nova, amb el contingut: «{{Petició de traducció|en|Halley's method|Usuari:Amical-bot/Matemàtiques/en|--~~~~}}». |
m bot preprocessant article previ a la traduccioo automatica |
||
Línia 1:
In NUMERICAL ANALYSIS , ((((( Halley's method ))))) is a ROOT-FINDING ALGORITHM used for functions of one real variable with a continuous second derivative , i.e. C<SUP>2</SUP> functions. It is named after its inventor EDMOND HALLEY who also discovered HALLEY'S COMET. ..
..
The algorithm is second in the class of HOUSEHOLDER'S METHODS , right after the NEWTON'S METHOD. Like the latter it produces iteratively a sequence of approximations to the root , their RATE OF CONVERGENCE to the root is cubic. Multidimensional versions of this method exist. ..
..
(==) Method (==) ..
..
Like any root-finding method , Halley's method is a numerical algorithm for solving the nonlinear equation &fnof ;(((( x )))) = 0. In this case , the function &fnof ; has to be a function of one real variable. The method consists of a sequence of iterations: ..
..
: <math>x_{n+1} = x_n - \frac {2 f(x_n) f'(x_n)} {2 {[f'(x_n)]}^2 - f(x_n) f''(x_n)} </math> ..
..
beginning with an initial guess (( x )) <sub>0</sub>. ..
..
If &fnof ; is a thrice continuously differentiable function and (( a )) is a zero of &fnof ; but not of its derivative , then , in a neighborhood of (( a )) , the iterates (( x )) <sub>(( n )) </sub> satisfy: ..
..
: <math> .3. x_{n+1} - a .3. \le K \cdot { .3. x_n - a .3. }^3 ,\text{ for some }K > 0.\!</math> ..
..
This means that the iterates converge to the zero if the initial guess is sufficiently close , and that the convergence is cubic. ..
..
(==) Derivation (==) ..
Consider the function ..
..
: <math>g(x) = \frac {f(x)} {\sqrt{ .3. f'(x) .3. }}.</math> ..
..
Any root of &fnof ; which is (( not )) a root of its derivative is a root of (( g )) ; and any root of (( g )) is a root of &fnof ;. Applying NEWTON'S METHOD to (( g )) gives ..
..
: <math>x_{n+1} = x_n - \frac {g(x_n)} {g'(x_n)}</math> ..
..
with ..
..
: <math>g'(x) = \frac {2 {[f'(x)]}^2 - f(x) f''(x)} {2 f'(x) \sqrt{ .3. f'(x) .3. }} , </math> ..
..
and the result follows. Notice that if &fnof ;'(((( c )))) = 0 , then one cannot apply this at (( c )) because (( g )) (((( c )))) would be undefined. ..
..
(==) Cubic convergence (==) ..
Suppose (( a )) is a root of (( f )) but not of its derivative. And suppose that the third derivative of (( f )) exists and is continuous in a neighborhood of (( a )) and (( x )) <sub>(( n )) </sub> is in that neighborhood. Then TAYLOR'S THEOREM implies: ..
..
: <math>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</math> ..
..
and also ..
..
: <math>0 = f(a) = f(x_n) + f'(x_n) (a - x_n) + \frac{f''(\eta)}{2} (a - x_n)^2 ,</math> ..
..
where &xi ; and &eta ; are numbers lying between (( a )) and (( x )) <sub>(( n )) </sub>. Multiply the first equation by <math>2 f'(x_n)\!</math> and subtract from it the second equation times <math>f''(x_n) (a - x_n)\!</math> to give: ..
..
: <math> ..
\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} ..
</math> ..
..
Canceling <math>f'(x_n) f''(x_n) (a - x_n)^2\!</math> and re-organizing terms yields: ..
..
: <math> ..
\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} ..
</math> ..
..
Put the second term on the left side and divide through by <math> 2 [f'(x_n)]^2 - f(x_n) f''(x_n) </math> to get: ..
..
: <math> ..
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. ..
</math> ..
..
Thus: ..
..
: <math> ..
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. ..
</math> ..
..
The limit of the coefficient on the right side as (( x )) <sub>(( n )) </sub> approaches (( a )) is: ..
..
: <math> ..
- \frac{2 f'(a) f(( '(a) - 3 f )) (a) f''(a)} {12 [f'(a)]^2}. ..
</math> ..
..
If we take (( K )) to be a little larger than the absolute value of this , we can take absolute values of both sides of the formula and replace the absolute value of coefficient by its upper bound near (( a )) to get: ..
..
: <math> .3. a - x_{n+1} .3. \leq K .3. a - x_n .3. ^3</math> ..
..
which is what was to be proved. ..
..
(==) References (==) ..
* T.R. Scavo and J.B. Thoo , On the geometry of Halley's method. (( American Mathematical Monthly )) , ((((( 102 ))))):5 (1995) , pp. 417–426. ..
* This article began as a translation from [http://fr.wikipedia.org/w/index.php?title=Itération_de_Halley&oldid=11673690 the equivalent article in French Wikipedia] , retrieved 22 January 2007. ..
..
(==) External links (==) ..
* {{ MathWorld .3. urlname=HalleysMethod .3. title=Halley's method}} ..
* [http://math.fullerton.edu/mathews/n2003/Halley'sMethodMod.html Halley's Method by John H. Mathews] ..
* (( [http://numbers.computation.free.fr/Constants/Algorithms/newton.html 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) ..
..
[[Category:Root-finding algorithms]] ..
..
[[de:Halley-Verfahren]] ..
[[fr:Itération de Halley]] ..
[[pl:Metoda Halleya]] ..
paraulesenllacos ..
..
NUMERICAL ANALYSIS ..
..
ROOT-FINDING ALGORITHM ..
..
C<SUP>2</SUP> ..
..
EDMOND HALLEY ..
..
HALLEY'S COMET ..
..
HOUSEHOLDER'S METHODS ..
..
NEWTON'S METHOD ..
..
RATE OF CONVERGENCE ..
..
NEWTON'S METHOD ..
..
TAYLOR'S THEOREM ..
| |||