Halley process

The Halley method (also method of touching hyperbolas ) is, similar to the Newton method , a method of numerical mathematics for the determination of zeros of real functions . In contrast to Newton's method, it has the order of convergence 3, but requires the second derivative in addition to the first. It is named after the astronomer Edmond Halley , who also determined the law of return of Halley's comet named after him . A comparable process is the Euler-Chebyshev process . ${\displaystyle f(x)=0}$ ${\displaystyle f\colon \mathbb {R} \to \mathbb {R} }$

Description of the procedure

Let a real function with continuous second derivative and let a be a simple zero of , i. H. . Then converges for starting points close to those by the iteration ${\displaystyle f}$ ${\displaystyle f\in C^{2}(\mathbb {R} ,\mathbb {R} )}$ ${\displaystyle f}$ ${\displaystyle f'(a)\neq 0}$ ${\displaystyle x_{0}}$ ${\displaystyle a}$

${\displaystyle x_{k+1}=x_{k}-{\frac {2\cdot f(x_{k})f'(x_{k})}{2f'(x_{k})^{2}-f(x_{k})f''(x_{k})}}}$, k = 0, 1, 2, ...

generated sequence of successive approximations with cubic order of convergence against . ${\displaystyle (x_{k})_{k\in \mathbb {N} }}$ ${\displaystyle a}$

Variants of this method are the irrational or parabolic Halley method originally used by Halley with the iteration rule

${\displaystyle x_{k+1}=x_{k}-{\frac {2f(x_{k})}{f'(x_{k})}}\cdot \left(1+{\sqrt {1-2{\frac {f(x_{k})f''(x_{k})}{f'(x)^{2}}}}}\right)^{-1}}$,

and, as a generalization of this, the Laguerre method

${\displaystyle x_{k+1}=x_{k}-{\frac {nf(x_{k})}{f'(x_{k})}}\cdot \left(1+(n-1){\sqrt {1-{\frac {n}{n-1}}{\frac {f(x_{k})f''(x_{k})}{f'(x)^{2}}}}}\right)^{-1}}$.

For polynomials, the degree is set equal to. Since the term below the root can become negative, these two variants can also converge to complex zeros for purely real polynomials and real starting values. For the determination of the square root of complex numbers, which is necessary in subsequent iterations, the solution with a positive real part must always be selected so that the denominator has the largest possible amount. ${\displaystyle n}$

motivation

Let be a real function with continuous second derivative, and let be a simple zero of , i. H. . Then the function progression from in the vicinity of is “bent straight” in the second order by considering the function instead . This construction is independent of the zero. The Newton method is now applied to. It is ${\displaystyle f}$ ${\displaystyle f\in C^{2}(\mathbb {R} ,\mathbb {R} )}$ ${\displaystyle a}$ ${\displaystyle f}$ ${\displaystyle f'(a)\neq 0}$ ${\displaystyle f}$ ${\displaystyle a}$ ${\displaystyle f}$ ${\displaystyle g(x)={\tfrac {f(x)}{\sqrt {|f'(x)|}}}}$ ${\displaystyle g}$

${\displaystyle {\begin{aligned}g'(x)&={\bigl (}f(x)\cdot |f'(x)|^{-1/2}{\bigr )}'\\[0.5em]&=f'(x)\cdot |f'(x)|^{-1/2}+f(x)\cdot (-{\tfrac {1}{2}})|f'(x)|^{-3/2}{\text{sign}}(f'(x))\,f''(x)\\[1em]&={\frac {2f'(x)^{2}-f(x)f''(x)}{2f'(x){\sqrt {|f'(x)|}}}}\end{aligned}}}$

and therefore

${\displaystyle H_{f}(x)=N_{g}(x)=x-{\frac {g(x)}{g'(x)}}=x-{\frac {2f(x)f'(x)}{2f'(x)^{2}-f(x)f''(x)}}}$

The same rule arises from the more general Householder method in the second order

${\displaystyle H_{f}(x)=x+2{\frac {(1/f)'(x)}{(1/f)''(x)}}}$

example

The iteration for the square root of z. B. a = 5 results in the iteration rule ${\displaystyle f(x)=x^{2}-a}$

${\displaystyle H_{f}(x)=x\,{\frac {x^{2}+3a}{3x^{2}+a}}=x\,{\frac {x^{2}+15}{3x^{2}+5}}}$

and with it the calculation table

${\displaystyle k}$	${\displaystyle x_{k}}$	${\displaystyle f(x_{k})}$
0	3.00000000000000000000000000000000000000000000000000000000000	4.00000000000
1	2.250000000000000000000000000000000000000000000000000000000	0.0625000000000
2	2.23606811145510835913312693498452012383900928792569659442724	5.99066414899E-7
3	2.23606797749978969640929385361588622700967141237081284965284	5.37483143712E-22
4th	2.23606797749978969640917366873127623544061835961152572427090	0.000000000000

The result is a sequence of 0, 1, 5, 21,> 60 valid digits, i.e. H. tripling in every step. The Newton method has the following procedure:

${\displaystyle G_{f}(x)={\frac {x^{2}+a}{2x}}={\frac {x^{2}+5}{2x}}}$

In a direct comparison, the Halley method shows the faster convergence. However, it requires more arithmetic operations per step.

Cubic convergence

Let f be three times continuously differentiable. Since a was assumed to be the zero of f , the following applies approximately . More precisely, the two-sided estimate applies to an interval I containing a according to the mean value theorem of differential calculus ${\displaystyle f(x)=f(x)-f(a)\approx f'(a)(x-a)}$

${\displaystyle {\tfrac {|f(x)|}{\max _{z\in I}|f'(z)|}}\leq |x-a|\leq {\tfrac {|f(x)|}{\min _{z\in I}|f'(z)|}}}$,

d. H. both as well . It is therefore sufficient to determine the ratio of the function values ​​from one iteration step to the next. ${\displaystyle x-a=O(f(x))}$ ${\displaystyle f(x)=O(x-a)}$

Irrational or parabolic Halley method

The second degree Taylor expansion of f is

${\displaystyle f{\bigl (}x+h{\bigr )}=f(x)+f'(x)\,h+{\tfrac {1}{2}}f''(x)\,h^{2}+O{\bigl (}h^{3}{\bigr )}}$.

This results in an approximation using a parabola that touches the graph of at the point of second order. If small enough, this parabola has a zero point that is clearly close to , namely at ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle x}$

${\displaystyle {\begin{aligned}h&=-{\frac {2f(x)}{f'(x)+{\text{sign}}(f'(x)){\sqrt {f'(x)^{2}-2f(x)f''(x)}}}}\\[0.5em]&=-{\frac {2f(x)}{f'(x)\,\left(1+{\sqrt {1-2f(x)f'(x)^{-2}f''(x)}}\right)}}\end{aligned}}}$

The corresponding iteration is

${\displaystyle x_{k+1}=x_{k}-{\frac {2f(x_{k})}{f'(x_{k})+{\text{sign}}(f'(x_{k})){\sqrt {f'(x_{k})^{2}-2f(x_{k})f''(x_{k})}}}}}$.

Since the denominator of is different from zero in the vicinity of a zero , the following applies . Because of this construction of , the first three terms of the Taylor expansion vanish, therefore . ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle h=O(f(x))}$ ${\displaystyle h}$ ${\displaystyle f(x_{k+1})=O(h^{3})=O(f(x_{k})^{3})}$

This form of the procedure was originally proposed by E. Halley. If you redevelop the root , you get the rational or hyperbolic Halley method that is common today. ${\displaystyle {\sqrt {1+y}}=1+{\tfrac {1}{2}}y+O(y^{2})}$

Hyperbolic Halley Method

If one uses the identity in the Taylor expansion of , then one can convert this into a fraction of into linear functions, i. H. is approximated in the vicinity of by a hyperbolic function, and from this the zero point is subsequently determined: ${\displaystyle f(x+h)}$ ${\displaystyle (a+bh)(a-bh)=a^{2}-b^{2}h^{2}=a^{2}+O(h^{2})}$ ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle x}$

${\displaystyle {\begin{array}{rl}f{\bigl (}x+h{\bigr )}=&f(x)+{\bigl (}f'(x)+{\tfrac {1}{2}}f''(x)h{\bigr )}\,h+O{\bigl (}h^{3}{\bigr )}\\\\=&f(x)+{\frac {f'(x)^{2}h}{f'(x)-{\frac {1}{2}}f''(x)h}}+O{\bigl (}h^{3}{\bigr )}\\\\=&{\frac {f(x)f'(x)+h(f'(x)^{2}-{\frac {1}{2}}f(x)f''(x))}{f'(x)-{\frac {1}{2}}f''(x)h}}+O{\bigl (}h^{3}{\bigr )}\ .\\\end{array}}}$

The function is thus approximated by a hyperbola in touch to also second order. The numerator of the hyperbolic function disappears for , from which the Halley iteration (see above) results. Again, and with it ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle h=-{\tfrac {2f(x)f'(x)}{2f'(x)^{2}-f(x)f''(x)}}}$ ${\displaystyle h=O(f(x))}$

${\displaystyle f(H_{f}(x))=O(h^{3})=O(f(x)^{3})\,}$

This then follows for the Halley iteration

${\displaystyle x_{k+1}-a=H_{f}(x_{k})-a=O(f(H_{f}(x_{k})))=O\left(f(x_{k})^{3}\right)=O\left((x_{k}-a)^{3}\right)\ ,}$

d. H. the cubic convergence.

Multi-dimensional expansion

The method can be expanded to include functions of several variables . The same binomial trick can be used to produce a hyperbolic function. However, it should be noted that ${\displaystyle F:\mathbb {R} ^{n}\to \mathbb {R} ^{n}}$

1. that is a matrix that is assumed to be invertible, ${\displaystyle F'(x)}$
2. that is a third order tensor , more precisely a vector-valued symmetric bilinear form, and ${\displaystyle F''(x)}$
3. that the incompletely evaluated second derivative , which is also a matrix, generally does not commute with the matrix . ${\displaystyle F''(x)(v,\cdot )}$ ${\displaystyle F'(x)}$

These are not obstacles, these properties just make the calculation a little more confusing. It denotes the usual Newton step and is the correspondingly modified second order term. Then for the Taylor expansion in ${\displaystyle s=-F'(x)^{-1}F(x)}$ ${\displaystyle C(u,v)={\tfrac {1}{2}}F'(x)^{-1}F''(x)(u,v)}$ ${\displaystyle x}$

${\displaystyle {\begin{aligned}F(x+t)&=F(x)+F'(x)t+{\tfrac {1}{2}}F''(x)(t,t)+O(t^{3})\\[0.5em]&=F'(x)\,{\Bigl (}-s+t+C(t,t){\Bigr )}+O(t^{3})\quad {\text{d. h.}}\\[0.5em]F'(x)^{-1}F(x+t)&={\Bigl (}-s+{\bigl (}I+C(t,\cdot ){\bigr )}\,t+O(t^{3}){\Bigr )}\\[0.5em]&={\Bigl (}-s+{\bigl (}I-C(t,\cdot ){\bigr )}^{-1}\,t+O(t^{3}){\Bigr )}\\[0.5em]&={\bigl (}I-C(t,\cdot ){\bigr )}^{-1}\,{\bigl (}-s+C(t,s)+t+O(t^{3}){\bigr )}\end{aligned}}}$

The linear part of the counter is now set to zero and further transformed. The symmetry of : ${\displaystyle t}$ ${\displaystyle C(.,.)}$

${\displaystyle 0=-s+C(t,s)+t=-s+{\bigl (}I+C(s,\cdot ){\bigr )}\,t\quad \iff \quad t={\bigl (}I+C(s,\cdot ){\bigr )}^{-1}\,s}$

If the short notations are now replaced by the original expressions, this results

${\displaystyle \textstyle {\begin{aligned}t&=-{\Bigl (}I-{\tfrac {1}{2}}F'(x)^{-1}F''(x){\bigl (}F'(x)^{-1}F(x),\cdot {\bigr )}{\Bigr )}^{-1}\;F'(x)^{-1}F(x)\\[0.5em]&=-{\Bigl (}F'(x)-{\tfrac {1}{2}}F''(x){\bigl (}F'(x)^{-1}F(x),\cdot {\bigr )}{\Bigr )}^{-1}\;F(x)\end{aligned}}}$.

One can easily convince oneself that this formula reduces in the one-dimensional case to the Halley iteration. The resulting iteration step of the multi-dimensional Halley method can be determined in 3 simpler steps:

1. Newton step: solve ${\displaystyle F'(x_{k})s_{k}=-F(x_{k})}$
2. Correction of the Newton step: Solve ${\displaystyle \left(F'(x_{k})+{\tfrac {1}{2}}F''(x_{k})(s_{k},\cdot )\right)t_{k}=-F(x_{k})}$
3. Set ${\displaystyle x_{k+1}=x_{k}+t_{k}}$

If the 2nd derivative is Lipschitz continuous , then the method converges locally cubic.

Since it was assumed to be small, it is no longer necessary to find the inverse of the large bracket. The binomial trick (or the Taylor formula of the first degree) can be used again to create the simpler expression, which is identical except for terms of the third order (now in F (x) ) ${\displaystyle F(x)}$

${\displaystyle {\begin{aligned}t=&-{\Bigl (}I+{\tfrac {1}{2}}F'(x)^{-1}F''(x){\bigl (}F'(x)^{-1}F(x),\cdot {\bigr )}{\Bigr )}\;F'(x)^{-1}F(x)\\[0.5em]=&-F'(x)^{-1}F(x)-{\tfrac {1}{2}}F'(x)^{-1}F''(x){\bigl (}F'(x)^{-1}F(x),F'(x)^{-1}F(x){\bigr )}\end{aligned}}}$

to obtain. The iteration derived from this is the Euler-Chebyshev method .

literature

• TR Scavo, JB Thoo: On the geometry of Halley's method. In: American Mathematical Monthly , Volume 102, 1995, number 5, pp. 417-426.
• Hubert Schwetlick: Numerical solution of nonlinear equations. German Science Publishing House, 1979.

Web links

• Eric W. Weisstein : Halley's method . In: MathWorld (English).
• Pascal Sebah, Xavier Gourdon: Newton's method and high order iterations . 2001, section "Cubic Iteration"

This article was based on the article en: Halley's method of the English Wikipedia (as of January 26, 2007).