function a=Interp(x,y) a=Inverpv(x,y This computes the vandermonde polynomial interpolant where %o x is a column n-vector with distinct components and y is a column n-vector %o a is a column n-vector with the property that if (X)=a(1)+a(2)x+…a(n)x^(n-1) o then %p(X()=y(1),i=1n n=length(X V=ones(n, n) for i=2: n Set up column J V(:j)=X*V(:-1) end a 2n3/3 flops
function a = InterpV(x,y) % a = InverpV(x,y) % This computes the Vandermonde polynomial interpolant where % x is a column n-vector with distinct components and y is a % column n-vector. % % a is a column n-vector with the property that if % % p(x) = a(1) + a(2)x + ... a(n)x^(n-1) % then % p(x(i)) = y(i), i=1:n n = length(x); V = ones(n,n); for j=2:n % Set up column j. V(:,j) = x.*V(:,j-1); end a = V\y; 2n3 /3 flops
Nested multipication pr(=a+.+anx atx=z n-length(a); zpower=1 pval=a(1) for i=2: n zpower-z zpower pval=pval+a(i)*zpower er
Nested Multipication p x a a x x z n n = + + n = − − ( ) ... at 1 1 1 n=length(a); zpower=1; pval=a(1); for i=2:n zpower=z*zpower; pval=pval+a(i)*zpower; end
Horner's ruler m-or=a+a,x+a3x+aux =(a4x+a2)x+a2)x+a1 m=length(z) n-length(a) nF=length(a) pval=zeros(m, 1) pval=a(n) Many points Forj=1: m fori=n-1:-1:1 pval(=a(n) pval=z pval+a(1) fori=n-1:-1:1 end pval=zo *pval(+a(i) end: enc d
Horner's ruler 4 3 2 1 3 4 2 1 1 2 3 (( ) ) ( ) a x a x a x a pn x a a x a x a x = + + + − = + + + n=length(a); pval=a(n); for i=n-1:-1:1 pval=z*pval+a(i); end m=length(z);n=length(a); pval=zeros(m,1); For j=1:m pval(j)=a(n); for i=n-1:-1:1 pval(j)=z(j)*pval(j)+a(i); end;end Many points
Evalute at many points Function pval=Horner V(a, 2) mF=length(z); n=length(a) pval=a(n *ones(m, 1) fork=n-1:-1:1 pval=z "pval+a(k) en 2m flops All: 2mn flops 6 Script see next page
0 2 4 6 -2 -1 0 1 2 0 2 4 6 -2 -1 0 1 2 0 2 4 6 -2 -1 0 1 2 0 2 4 6 -2 -1 0 1 2 Evalute at many points Function pval=HornerV(a,Z) m=length(z);n=length(a); pval=a(n)*ones(m,1); for k=n-1:-1:1 pval=z.*pval+a(k); end 2m flops All:2mn flops Script see next page
o Script File: Show V 1% Plots 4 random cubic interpolants of sin(x)on [0, 2pi] %o Uses the vandermonde method close a :0-linspace(0, 2 pi, 100) yo= sin(x0) for eg=1: 4 Display cubic interpolants of sin(x). The abscissas are chosen x=2*pi*sort(rand( 4, 1) randomly sin(X a=Interp( y) p Val= Horner v(a,]O) subplot(2, 2, eg plot( xo, y0, 0, p Val, x,y, * axiS([02*p-22]) end
% Script File: ShowV % Plots 4 random cubic interpolants of sin(x) on [0,2pi]. % Uses the Vandermonde method. close all x0 = linspace(0,2*pi,100)'; y0 = sin(x0); for eg=1:4 x = 2*pi*sort(rand(4,1)); y = sin(x); a = InterpV(x,y); pVal = HornerV(a,x0); subplot(2,2,eg) plot(x0,y0,x0,pVal,'--',x,y,'*') axis([0 2*pi -2 2]) end Display cubic interpolants of sin(x). The abscissas are chosen randomly