Namespaces
Variants
Actions

Chebyshev method

From Encyclopedia of Mathematics
Revision as of 17:21, 28 June 2015 by Ivan (talk | contribs) (TeX)
Jump to: navigation, search


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)
How to Cite This Entry:
Chebyshev method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Chebyshev_method&oldid=11619
This article was adapted from an original article by V.I. Lebedev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article