Chebyshev method

A method for obtaining a class of iteration algorithms (cf. 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. [2]). The method can be extended to functional equations (cf. [3]).

References

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

Comments

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

References

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