View source for Chebyshev method

{{TEX|done}}

A method for obtaining a class of iteration algorithms (cf. [[Iteration algorithm|Iteration algorithm]]) for finding a simple real root of an equation

$$f(x)=0,\tag{1}$$

where $f$ is a sufficiently smooth function.

The basis of the method lies in the formal representation of the inverse function $x=F(y)$ of $f(x)$ via the Taylor formula. If $\alpha$ is a sufficiently close approximation to a root of equation \ref{1}, if $c_0=\beta=f(\alpha)$ and if $f'(\alpha)\neq0$, then

$$x=F(y)=\alpha+\sum_{n\geq1}d_n(y-\beta)^n,\tag{2}$$

where the coefficients $d_n$ are defined recursively from the identity $x\equiv F(f(x))$ using the Taylor coefficients $c_n$ of the function $f(x)=\sum_{n\geq0}c_n(x-\alpha)^n$. Putting $y=0$ in \ref{2}, one obtains the relation

$$x=\alpha-\frac{f(\alpha)}{f'(\alpha)}-\left(\frac{f(\alpha)}{f'(\alpha)}\right)^2\frac{f''(\alpha)}{2f'(\alpha)}+\tag{3}$$

$$-\left(\frac{f(\alpha)}{f'(\alpha)}\right)^3\left(\frac12\left(\frac{f''(\alpha)}{f'(\alpha)}\right)^2-\frac{f'''(\alpha)}{6f'(\alpha)}\right)+$$

$$-\left(\frac{f(\alpha)}{f'(\alpha)}\right)^4\left(\frac58\left(\frac{f''(\alpha)}{f'(\alpha)}\right)^3-\frac{5f''(\alpha)f'''(\alpha)}{12(f'(\alpha))^2}+\frac{f^{IV}(\alpha)}{24f'(\alpha)}\right)-\mathinner{\ldotp\ldotp\ldotp\ldotp}$$

Taking a certain number of terms on the right-hand side of \ref{3} gives a formula for the iteration algorithm; with two terms, for example, one obtains Newton's method, while with three terms one obtains an iteration method of the form

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}-\left(\frac{f(x_n)}{f'(x_n)}\right)^2\frac{f''(x_n)}{2f'(x_n)},\quad n=0,1,\mathinner{\ldotp\ldotp\ldotp\ldotp}\tag{4}$$

The rate of convergence of the $x_n$ to $x$ increases with the number of terms of \ref{3} taken into consideration (cf. [[#References|[2]]]). The method can be extended to functional equations (cf. [[#References|[3]]]).

====References====
<table><TR><TD valign="top">[1a]</TD> <TD valign="top">  P.L. Chebyshev,  , ''Collected works'' , '''5''' , Moscow-Leningrad  (1951)  pp. 7–25  (In Russian)</TD></TR><TR><TD valign="top">[1b]</TD> <TD valign="top">  P.L. Chebyshev,  , ''Collected works'' , '''5''' , Moscow-Leningrad  (1951)  pp. 173–176  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M.I. Nechepurenko,   ''Uspekhi Mat. Nauk'' , '''9''' :  2  (1954)  pp. 163–170</TD></TR></table>



====Comments====
This method is also called Chebyshev's root-finding method. A related approach is based on inverse interpolation, cf. [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Ralston,   "A first course in numerical analysis" , McGraw-Hill  (1965)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.J. Davis,   "Interpolation and approximation" , Dover, reprint  (1975)  pp. 108–126</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F.B. Hildebrand,   "Introduction to numerical analysis" , McGraw-Hill  (1974)</TD></TR></table>