Namespaces
Variants
Actions

Difference between revisions of "Aitken scheme"

From Encyclopedia of Mathematics
Jump to: navigation, search
(MSC 65D05)
(eqref)
 
Line 2: Line 2:
  
 
A method for computing the value at a point $x$ of the interpolation polynomial $L_n(x)$ with respect to the nodes $x_0,\ldots,x_n$, based on the successive application of the formula
 
A method for computing the value at a point $x$ of the interpolation polynomial $L_n(x)$ with respect to the nodes $x_0,\ldots,x_n$, based on the successive application of the formula
$$\label{eq:1}
+
\begin{equation}
 +
\label{eq:1}
 
L_k(x) = L_{(0,\ldots,k)}(x) = \frac{1}{x_k - x_0} \left\vert{ \begin{array}{cc} L_{(0,\ldots,k-1)} & x_0 - x \\ L_{(1,\ldots,k)} & x_k - x \end{array} }\right\vert
 
L_k(x) = L_{(0,\ldots,k)}(x) = \frac{1}{x_k - x_0} \left\vert{ \begin{array}{cc} L_{(0,\ldots,k-1)} & x_0 - x \\ L_{(1,\ldots,k)} & x_k - x \end{array} }\right\vert
$$
+
\end{equation}
 
where $L_{(i,\ldots,m)}(x)$ is the interpolation polynomial with interpolation nodes $x_i,\ldots,x_m$, in particular, $L_{(i)}(x) = x_i$ (see [[Interpolation formula]]). The process of computations by means of \eqref{eq:1} may finish if the values of two interpolation polynomials of consecutive degrees coincide in the required number of decimal places. The Aitken scheme is convenient for interpolating the values of a function given in the form of a table (of values), by renumbering the interpolation nodes in the order in which $|x - x_i|$ increases.
 
where $L_{(i,\ldots,m)}(x)$ is the interpolation polynomial with interpolation nodes $x_i,\ldots,x_m$, in particular, $L_{(i)}(x) = x_i$ (see [[Interpolation formula]]). The process of computations by means of \eqref{eq:1} may finish if the values of two interpolation polynomials of consecutive degrees coincide in the required number of decimal places. The Aitken scheme is convenient for interpolating the values of a function given in the form of a table (of values), by renumbering the interpolation nodes in the order in which $|x - x_i|$ increases.
  

Latest revision as of 14:03, 30 April 2023

2020 Mathematics Subject Classification: Primary: 65D05 [MSN][ZBL]

A method for computing the value at a point $x$ of the interpolation polynomial $L_n(x)$ with respect to the nodes $x_0,\ldots,x_n$, based on the successive application of the formula \begin{equation} \label{eq:1} L_k(x) = L_{(0,\ldots,k)}(x) = \frac{1}{x_k - x_0} \left\vert{ \begin{array}{cc} L_{(0,\ldots,k-1)} & x_0 - x \\ L_{(1,\ldots,k)} & x_k - x \end{array} }\right\vert \end{equation} where $L_{(i,\ldots,m)}(x)$ is the interpolation polynomial with interpolation nodes $x_i,\ldots,x_m$, in particular, $L_{(i)}(x) = x_i$ (see Interpolation formula). The process of computations by means of \eqref{eq:1} may finish if the values of two interpolation polynomials of consecutive degrees coincide in the required number of decimal places. The Aitken scheme is convenient for interpolating the values of a function given in the form of a table (of values), by renumbering the interpolation nodes in the order in which $|x - x_i|$ increases.

References

[1] I.S. Berezin, N.P. Zhidkov, "Computing methods" , 1 , Pergamon (1973) (Translated from Russian)
[2] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)


Comments

Aitken published the gist of his method in [a1]. Aitken's scheme is disadvantageous when a number of interpolations must be carried out over the same range. In such cases, an alternative to the computation of the Lagrange polynomials is the use of divided differences in the construction of Newton's interpolation formula.

References

[a1] A.C. Aitken, "On interpolation by iteration of proportional parts, without the use of differences" Proc. Edinburgh Math. Soc. 3 : 2 (1932) pp. 56–76
[a2] F.B. Hildebrand, "Introduction to numerical analysis" , McGraw-Hill (1974)
How to Cite This Entry:
Aitken scheme. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Aitken_scheme&oldid=36063
This article was adapted from an original article by M.K. Samarin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article