MATLAB; Lagrange Polynomial, an Interesting Error

Question

In my school homework I was given a problem, that required me to calculate Lagrange polynomial. The data set (x,y) involved x = 0,1,2....20, while y = x - 0.3*rand() + 1; Then we were asked to observed Runge's Phenomenon. After that, we were asked to compute Chebyshev Nodes around the edge to remove this phenomenon. Well, this is where I somehow got stuck. The Lagrange polynomial I'm calculating, at this moment, is not going through every data point.

The lagrange polynomial function I used is,

function P = lagrangepoly(x, y)
   %checks if two inputs vectors are obtained
   if nargin ~= 2
      error('The function accepts only two arguments of equal length'); 
   end
   
   sz = size(x); %size of x
   sz2 = size(y); % size of y
   
   %checks if size of x and size of y matches and they are row vectors
   if (sz(1) ~= sz2(1)) || (sz(2) ~= sz2(2)) || (sz(1) ~= 1)
       error('Mismatch in length or unsupported arguments.');
   end
   
   %takes the length of thevectors
   len = sz(2);
   
   %creating a emplt 1xlen container
   P = zeros(1, len);
   for i=1:1:len
       %poly evaluates all the convolution of [1 -x(j)] except at x(i)
       %prod evaluates all the product of (x(i) - x(j)) except at x(i)
       P = P + (poly(x((1:len)~=i)) ./ prod(x(i)-x((1:len)~=i))) .* y(i);
   end
end

And the dataset I'm using for this, is: xn = [0 0.5000 1.0000 2.0000 3.0000 4.0000 5.0000 6.0000 7.0000 8.0000 9.0000 10.0000 11.0000 12.0000 13.0000 14.0000 15.0000 16.0000 17.0000 18.0000 19.0000 19.5000 20.0000];

yn =[0.7363 1.4701 1.7802 2.8232 3.9698 4.9934 5.9747 6.8635 7.9435 8.9775 9.9013 10.9318 11.8988 12.8343 13.7095 14.9318 15.8800 16.7028 17.8614 18.7046 19.8505 20.2849 20.7036];

The curve I'm getting can be seen

The blue curve gives the original dataset, and the green curve gives the points evaluated from the polynomial. Can anyone give me suggestion on how do I remove this error. I think this is some kind of precision error. Thanks in advance.

Answer 1

Congratulations! You are the 10 millionth (and 3) person to have run into this problem. :)

It is precision. A Lagrange polynomial through 21 points will be a 20'th degree polynomial.

So you are raising numbers on the order of 20 to the 20th power. Then you are adding and subtracting them from other numbers that may be on the order of 1. (However you evaluate that polynomial, it will cause these same issues.)

What is the range of numbers that a double can handle? About 16 decimal digits. Expect to see numerical garbage. No surprise, you did.

How do you avoid it? Don't use high order polynomials! (By the way, the reason you were given this example is to see exactly that result. Every first class in numerical methods has such an example in it.)