The Problem
Polynomial interpolation is a process that take a set of N points, (x_{i}, y_{i}), and finds a polynomial function, P, such that the line graphing P passes through each of the N points. That is, y_{i} = P(x_{i}), for all 1≤ i ≤ N. Polynomial extrapolation finds the function value of a point, X, along the xaxis that is not within the original data set of N points defining the function. Extrapolating the value of a point within an interpolated polynomial is the goal of the code whose parallelization is described in this article.
Using Lagrange's Formula, you can interpolate the polynomial P and compute a solution for P(X). The computation requires the calculation of N terms that are added together, which describes a polynomial of degree N1. The computation for each term involves 2N2 subtractions and 2N1 multiplications. Plenty of independent computations are available in this formulation, but there is no way to compute an error estimate and it can generate awkward coding that ensures the correct values are used to calculate each term.
An alternative is Neville's algorithm. This formulation uses finite difference calculations as it refines the functional value of increasingly higher degree polynomials. ...


Page viewed 2290 times since Mon 6 Apr 2009, 23:41.