Numerical Analysis/Neville's algorithm code
The basic outline of a Matlab program that evaluates an interpolating polynomial using Neville's Algorithm given inputs of a point at which to evaluate (x0), a matrix of the x terms of the ordered pairs (x), and a matrix of the y terms of the ordered pairs (y) is given below. The numbers in the parenthese at the end of the comments correspond to questions given below the code.
Matlab Code
edit
function p = neville(x0,x,y)
%Inputs: x0-- the point at which to evaluate
% x -- the matrix of the x terms of the ordered pairs
% y -- the matrix of the y terms of the ordered pairs
%Output: p -- the value of the polynomial going through the n data points
n = ____;____ % n is the degree of the polynomial (1)
p = zeros(____,____) % creates the zero matrix p (2)
for i = 1:____ % runs loop from i equals 1 until it reaches end value (3)
p(i,i) = y(i); % when i is equal to j, set the element equal to the corresponding y value
end
for j = 1:____ % runs loop from j equal to 1 until it reaches end value (4)
for i = 1:____ % runs loop from i equal to 1 until it reached end value (5)
p(i,i+j) = ((x(i+j)-x0)*p(i,i+j-1) + (x0-x(i))*p(i+1,i+j))/(x(i+j)-x(i));
% evaluates each element of the matrix, when i is not equal to j, using Neville's Algorithm
end
end
p = p(____,____); % outputs the value of the polynomial going through the
% n data points at the point x0 (6)
Questions
edit(1) Is the degree of the polynomial equal to the length of x minus 1 or the length of x plus one?
Solution:
length of x minus 1
(2) How many rows and columns should matrix p have?
Solution:
n+1 rows and n+1 columns
(3) When should the loop end?
Solution:
when i is equal to the length of x, which is also when i is equal to n+1
(4) When should the loop end?
Solution:
when j is equal to n+1
(5) When should the loop end?
Solution:
when i is equal to n+1-j
(6) What term of the matrix is the output value?
Solution:
p = p(1,n+1)