Code covered by the BSD License

# Lagrange Interpolator Polynomial

### Dan Ellis (view profile)

28 Nov 2006 (Updated )

Find the polynomial (defined by its coefficients) passing through a set of points.

lagrangepoly(X,Y,XX)
```function [P,R,S] = lagrangepoly(X,Y,XX)
%LAGRANGEPOLY  Lagrange interpolation polynomial fitting a set of points
%   [P,R,S] = LAGRANGEPOLY(X,Y)  where X and Y are row vectors
%   defining a set of N points uses Lagrange's method to find
%   the N-1th order polynomial in X that passes through these
%   points.  P returns the N coefficients defining the polynomial,
%   in the same order as used by POLY and POLYVAL (highest order first).
%   Then, polyval(P,X) = Y.  R returns the x-coordinates of the N-1
%   extrema of the resulting polynomial (roots of its derivative),
%   and S returns the y-values  at those extrema.
%
%   YY = LAGRANGEPOLY(X,Y,XX) returns the values of the polynomial
%   sampled at the points specified in XX -- the same as
%   YY = POLYVAL(LAGRANGEPOLY(X,Y)).
%
%   Example:
%   To find the 4th-degree polynomial that oscillates between
%   1 and 0 across 5 points around zero, then plot the interpolation
%   on a denser grid inbetween:
%     X = -2:2;  Y = [1 0 1 0 1];
%     P = lagrangepoly(X,Y);
%     xx = -2.5:.01:2.5;
%     plot(xx,polyval(P,xx),X,Y,'or');
%     grid;
%   Or simply:
%     plot(xx,lagrangepoly(X,Y,xx));
%
%   Note: if you are just looking for a smooth curve passing through
%   a set of points, you can get a better fit with SPLINE, which
%   fits piecewise polynomials rather than a single polynomial.
%

% 2006-11-20 Dan Ellis dpwe@ee.columbia.edu

%  http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html

% Make sure that X and Y are row vectors
if size(X,1) > 1;  X = X'; end
if size(Y,1) > 1;  Y = Y'; end
if size(X,1) > 1 || size(Y,1) > 1 || size(X,2) ~= size(Y,2)
error('both inputs must be equal-length vectors')
end

N = length(X);

pvals = zeros(N,N);

% Calculate the polynomial weights for each order
for i = 1:N
% the polynomial whose roots are all the values of X except this one
pp = poly(X( (1:N) ~= i));
% scale so its value is exactly 1 at this X point (and zero
% at others, of course)
pvals(i,:) = pp ./ polyval(pp, X(i));
end

% Each row gives the polynomial that is 1 at the corresponding X
% point and zero everywhere else, so weighting each row by the
% desired row and summing (in this case the polycoeffs) gives
% the final polynomial
P = Y*pvals;

if nargin==3
% output is YY corresponding to input XX
YY = polyval(P,XX);
% assign to output
P = YY;
end

if nargout > 1
% Extra return arguments are values where dy/dx is zero
% Solve for x s.t. dy/dx is zero i.e. roots of derivative polynomial
% derivative of polynomial P scales each power by its power, downshifts
R = roots( ((N-1):-1:1) .* P(1:(N-1)) );
if nargout > 2
% calculate the actual values at the points of zero derivative
S = polyval(P,R);
end
end
```