The idea behind the Newton method is to use a hierarchic scheme so that by adding a further supporting point only one term has to be added to the previously determined polynomial. This is based on the following ansatz:
\(p(x_0)=y_0\), since all other terms contain a factor \((x-x_0)\), which is zero for \(x=x_0\).
\(p(x_1)=y_0+y_{(0,1)}(x_1-x_0)\), since all other terms contain a factor \((x-x_1)\), which is zero for \(x=x_1\).
In general, \(p(x_k)=y_0+y_{(0,1)}(x_k-x_0)+y_{(0,1,2)}(x_k-x_0)(x_k-x_1)+\ldots+y_{(0,1,2,\dots,k)}(x_k-x_0)(x_k-x_1)\cdots(x_k-x_{k-1})\).
Note that when increasing the degree of \(p\) from \(n\) to \(n+1\) by adding an extra term according to this hierarchic scheme, there is no conflict with the interpolation at \(x_0,x_1,\ldots,x_n\) since the added term vanishes at all these points. On the other hand, since it vanishes only at these points, it will alter the behavior of the interpolating polynomial between these points.
From the condition \(p(x_1)=y_1=y_0+y_{(0,1)}(x_1-x_0)\) we are able to determine \(y_{(0,1)}=\frac{y_1-y_0}{x_1-x_0}\).
From the condition \(p(x_2)=y_2\) we have \(y_0+y_{(0,1)}(x_2-x_0)+y_{(0,1,2)}(x_2-x_0)(x_2-x_1)=y_2\),
which allows to determine \(y_{(0,1,2)}\), and so on. However, to determine higher coefficients one usually
uses the technique of divided
differences.1
Example:
Consider again the following points: \((x_0,y_0)
= (0,1)\); \((x_1,y_1) = (1,6)\); \((x_2,y_2) = (2,15)\). The hierarchic scheme leads to \(y_0 = 1\), \(y_{(0,1)}=\frac{y_1-y_0}{x_1-x_0}=\frac{6-1}{1-0}=5\), and \(y_{(0,1,2)}=\frac{y_2-y_0-y_{(0,1)}(x_2-x_0)}{(x_2-x_0)(x_2-x_1)}=\frac{15-1-5(2-0)}{(2-0)(2-1)}=\frac{4}{2}=2\).
Therefore, \(p(x)=1+5(x-0)+2(x-0)(x-1)=1+3x+2x^2\).
1See, e.g., http://www.maths.lancs.ac.uk/
|
|
|
|
© J. Carstensen (Comp. Math.)