Newton Interpolation Formula
A number of different formulae were given by Newton, however two of these formulae are more common. One of these formulae is used when the independent variable assumes values with equal intervals while the other is applicable when the intervals are not equal. The first formula is referred to as “Newton’s formula for equal intervals”, and the second formula is referred to as “Newton’s formula for unequal intervals”. In the subsequent tutorials we discuss the difference table. Next we look at Newton’s formula for equal intervals, and we talk about divided differences. Finally, Newton’s formula for unequal intervals is explored.
The Difference Table
Suppose the initial value of the independent variable $$\left( X \right)$$ is “$$a$$” and the common class interval is “$$h$$”. The successive values of the independent variable could then be written symbolically as $$a$$ , $$\left( {a + h} \right),\left( {a + 2h} \right),\left( {a + 3h} \right), \cdots $$ etc., and the corresponding values of the dependent variable may be written symbolically as $$f\left( a \right),$$ $$f\left( {a + h} \right),$$ $$f\left( {a + 2h} \right),f\left( {a + 3h} \right),…$$etc. The data thus looks as follows:
|
$$X$$
|
$$a$$
|
$$a + h$$
|
$$a + 2h$$
|
$$a + 3h$$
|
$$a + 4h$$
|
|
$$f\left( X \right)$$
|
$$f\left( a \right)$$
|
$$f\left( {a + h} \right)$$
|
$$f\left( {a + 2h} \right)$$
|
$$f\left( {a + 3h} \right)$$
|
$$f\left( {a + 4h} \right)$$
|
In general the independent variable may be written as $$\left( {a + Xh} \right)$$ and the corresponding values of the dependent variable as $$f\left( {a + Xh} \right)$$. The problem of interpolation here requires that, given $${X_o} = a + Xh$$, find the value of $$f\left( {{X_o}} \right)$$ or $$f\left( {a + Xh} \right)$$. In order to determine the value of $$f\left( {{X_o}} \right)$$ we need to construct the “difference table”.
The quantity $$f\left( {a + h} \right) – f\left( a \right)$$ is denoted by $$\Delta f\left( a \right)$$ and is called the first difference of $$f\left( a \right)$$. Similarly, the first difference of $$f\left( {a + h} \right)$$ is $$f\left( {a + 2h} \right) – f\left( {a + h} \right)$$ and is denoted by $$\Delta f\left( {a + h} \right)$$. Other first order differences are
\[\begin{gathered} \Delta f\left( {a + 2h} \right) = f\left( {a + 3h} \right) – f\left( {a + 2h} \right) \\ \Delta f\left( {a + 3h} \right) = f\left( {a + 4h} \right) – f\left( {a + 3h} \right) \\ ……………………………………………….. \\ ………………………………………………..\end{gathered} \]
NOTE: The symbol $$\Delta $$ is read as delta, thus $$\Delta f\left( a \right)$$ means delta $$f\left( a \right),{\Delta ^2}f\left( a \right)$$ is read as delta two $$f\left( a \right)$$, etc.
Moreover, the quantity $$\Delta f\left( {a + h} \right) – f\left( a \right)$$ is denoted by $${\Delta ^2}f\left( a \right)$$ and is called the second order difference of $$f\left( a \right)$$. Other second order differences would be
\[\begin{gathered} \,\,{\Delta ^2}f\left( {a + h} \right) = \Delta f\left( {a + 2h} \right) – \Delta f\left( {a + h} \right) \\ {\Delta ^2}f\left( {a + 2h} \right) = \Delta f\left( {a + 3h} \right) – \Delta f\left( {a + 2h} \right) \\ ……………………………………………………… \\ ………………………………………………………\end{gathered} \] The second order difference is in fact the difference of the first order differences. The quantity \[{\Delta ^2}f\left( {a + h} \right) – {\Delta ^2}f\left( a \right)\] is denoted by \[{\Delta ^3}f\left( a \right)\] and is called the third order difference of $$f\left( a \right)$$ and so on.
|
DIFFERENCE TABLE
|
|||||
|
$$X$$
|
$$f\left( X \right)$$
|
\[{\Delta ^1}\]
|
\[{\Delta ^2}\]
|
\[{\Delta ^3}\]
|
\[{\Delta ^4}\]
|
|
$$a$$
|
$$f\left( a \right)$$
|
$$\Delta f\left( a \right)$$
|
$${\Delta ^2}f\left( a \right)$$
|
$${\Delta ^3}f\left( a \right)$$
|
$${\Delta ^4}f\left( a \right)$$
|
|
$$a + h$$
|
$$f\left( {a + h} \right)$$
|
$$\Delta f\left( {a + h} \right)$$
|
$${\Delta ^2}f\left( {a + h} \right)$$
|
$${\Delta ^3}f\left( {a + h} \right)$$
|
$${\Delta ^4}f\left( {a + h} \right)$$
|
|
$$a + 2h$$
|
$$f\left( {a + 2h} \right)$$
|
$$\Delta f\left( {a + 2h} \right)$$
|
$${\Delta ^2}f\left( {a + 2h} \right)$$
|
$${\Delta ^3}f\left( {a + 2h} \right)$$
|
$$ \vdots $$
|
|
$$a + 3h$$
|
$$f\left( {a + 3h} \right)$$
|
$$\Delta f\left( {a + 3h} \right)$$
|
$${\Delta ^2}f\left( {a + 3h} \right)$$
|
$$ \vdots $$
|
$$ \vdots $$
|
|
$$a + 4h$$
|
$$f\left( {a + 4h} \right)$$
|
$$\Delta f\left( {a + 4h} \right)$$
|
$$ \vdots $$
|
$$ \vdots $$
|
$$ \vdots $$
|
|
$$a + 5h$$
|
$$f\left( {a + 5h} \right)$$
|
$$ \vdots $$
|
$$ \vdots $$
|
$$ \vdots $$
|
$$ \vdots $$
|
Similarly, differences of higher order than the fourth may be written. The first entry in the 2nd column (i.e. $$f\left( a \right)$$ is called the leading term and the differences in the first row, i.e. $$\Delta f\left( a \right)$$, $${\Delta ^2}f\left( a \right)$$, … etc.), are called the leading differences. These are in fact the values which we will use in our formula of interpolation.
The presentation of the difference table in this form appears rather difficult, but in practice it is very simple to construct. The entries in column 3 (1st differences) are obtained by subtracting each entry in column 2 from the entry immediately following it (with the proper algebraic sign). In this way there will be one less entry in column 3 than in column 2. Similarly, entries in column 4 are obtained by subtracting each entry in column 3 from the entry immediately following it. Again, there will be one less entry in column 4 than in column 3. This process of taking the difference continues till there is only one entry in one column. In fact there is one less number of differences than the number of entries in the second column. Thus, if there are five entries in the second column, the difference table will be constructed only up to a fourth order, i.e. $${\Delta ^4}f\left( a \right)$$ .
THE FORMULA
\[\begin{gathered} f\left( {{X_o}} \right) = f\left( {a + Xh} \right) \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \,f\left( a \right) + X\Delta f\left( a \right) + \frac{{X\left( {X – 1} \right)}}{{2 \times 1}}{\Delta ^2}f\left( a \right) + \frac{{X\left( {X – 1} \right)\left( {X – 2} \right)}}{{3 \times 2 \times 1}}{\Delta ^3}f\left( a \right) + \cdots \, \\ \end{gathered} \]
The values of $$f\left( a \right),\Delta f\left( a \right),{\Delta ^2}f\left( a \right)$$ are the leading terms and the leading differences (given in the 1st row of the difference table). To find the value of $$X$$, equate the given value of $${X_o}$$ to $$a + Xh$$. i.e. $$a + Xh = {X_o}$$
Here $$a$$ and $$h$$ are already known from the first column, “$$a$$” being the first term and $$h$$ the common class interval. Hence if $${X_o}$$, $$a$$ and $$h$$ are known, $$X$$ may be obtained from the above equation. If it is difficult to calculate $$X$$ from the above equation, one may use the following formula to compute $$X$$ as such:
\[X = \frac{{{X_o} – a}}{h}\]
It should be noted that the formula for any specific problem will be written up to a difference of the order one less than the number of terms.