next up previous
Next: About this document ... Up: interpolation Previous: Neville algorithm

Algorithm

As we add one more point to the list of interpolated points, Eq. (1) tells us how to compute the value of the new interpolating polynomial. The matrix structure of the interpolating table suggests introducing a matrix $Q_{i,j}$ to hold the $i$th row and $j$th column in the format

$x_0$ $Q_{0,0}$        
    $Q_{1,1}$      
$x_1$ $Q_{1,0}$   $Q_{2,2}$    
    $Q_{2,1}$   $Q_{3,3}$  
$x_2$ $Q_{2,0}$   $Q_{3,2}$   $Q_{4,4}$
    $Q_{3,1}$   $Q_{4,3}$  
$x_3$ $Q_{3,0}$   $Q_{4,2}$    
    $Q_{4,1}$      
$x_4$ $Q_{4.0}$        
so that $Q_{i,j} = P_{i-j,i-j+1,\ldots{},i}$. Converting Eq (1) to the $Q$'s gives

\begin{displaymath}
Q_{i,j}(x) = \frac{(x - x_{i-j})Q_{i,j-1}(x)
-(x - x_i)Q_{i-1,j-1}(x)}{x_i - x_{i-j}},
\end{displaymath}

for $i = j,\ldots{}n-1$ for each $j = 1,2,\ldots{}$ and with the initial values $Q_{i,0} = y_i$.

We leave the construction of the pseudocode and the computer code as an exercise. With care the algorithm can be designed so it keeps only one column of the matrix, saving computer memory. The trick is to run the inner loop over $i$ backwards so the fresh values for the $j$th column do not overwrite values still needed from the $j-1$st column.


next up previous
Next: About this document ... Up: interpolation Previous: Neville algorithm