function [q,Q]=Neville(x_input,y_input,x,eps)  
% Neville插值法  
% 输入采样点横纵坐标，求值的点的横坐标和容许误差
% 输出该点纵坐标近似值和递推表

%  NUMERICAL METHODS: Matlab Programs
% (c) 2007 by Xie Liling
%  Complementary Software to accompany the textbook:
%  Information and Computing Science: A Laboratory Course

m=length(x_input);
Q=zeros([m,m]);
%初始化
Q(:,1)=[y_input]';

format long
for i=2:m
    for j=2:i
        Q(i,j)=((x-x_input(i-j+1))*Q(i,j-1)-(x-x_input(i))*Q(i-1,j-1))/(x_input(i)-x_input(i-j+1));
        if abs(Q(i,j)-Q(i,j-1))<eps
            break;
        end
    end
end
q=Q(m,m);
end