Newton interpolation and least squares approximation

(1)

Emma Perracchione

Corso di Calcolo Numerico per Ingegneria Meccanica - Matr. PARI (Univ. PD)

Gli esercizi sono presi dal libro: S. De Marchi, D. Poggiali, Exercices of numerical calculus with solutions in Matlab/Octave

A.A. 2018/2019

(2)

Newton interpolation and least squares approximation Materiale

Materiale

TUTTO IL MATERIALE SI TROVA AL SEGUENTE LINK E VERRA’

AGGIORNATO AD OGNI LEZIONE.

https://www.math.unipd.it/~emma/CN1819.html

(3)

Newton interpolation and least squares approximation Remarks

Introduction

For a given set of points (x_i, f_i), i = 0, . . . , n, the Lagrange polynomial Πn is the polynomial of degree n that assumes at each value x_i the corresponding value f_i.

In this lecture, we will construct the polynomial interpolant via Newton’s form.

It is susceptible to Runge’s phenomenon of large oscillation.

(4)

Newton interpolation and least squares approximation Remarks

Newton

The interpolating polynomial in Newton form is:

Π_n(x ) :=

n

X

i =0

f [x₀, . . . , x_i]ω_i(x ),

where f [x0] = f0 and for i = 1, . . . , n:

f [x₀, . . . , x_i] = f [x₁, . . . , x_i] − f [x₀, . . . , x_{i −1}]

xi− x₀ .

For the error note that:

R(x ) = ω_n+1f [x₀, . . . , x_n, x ] = ω_n+1(x )fⁿ⁺¹(ξ) (n + 1)!, for x0 < ξ < xn.

(5)

Newton interpolation and least squares approximation Exercises

Exercise 1

Exercise

Write a scipt called Esercizio1 and consider the function:

f (x ) = x + e^x + 20

1 + x² − 5, x ∈ [−2, 2].

Determine the interpolant in Newton’s form on 12 equispaced points.

Compute and display the maximum interpolation error for 100 equispaced points on x ∈ (−2, 2).

(6)

Exercise 1

function [yt,b]=NewtonInterp(x,y,xt)

% Newton form of the interpolating polynomial n=length(x); b=y;

for i=2:n for j=2:i

add=eps*((x(i)-x(j-1))<1.e-5);

b(i)=(b(i)-b(j-1))/(x(i)-x(j-1)+add);

end end

% part2: Horner scheme for evaluating the polynomial for i=1:length(xt)

yt(i)=b(n);

for k=n-1:-1:1

yt(i)=yt(i)*(xt(i)-x(k))+b(k);

end end

(7)

Newton interpolation and least squares approximation Matlab pre-built routines

Polyfit and polyval

The coefficients of the interpolating polynomial can be obtained via the command polyfit.

At first, let us see the Matlab help.

>> help polyfit

polyfit Fit polynomial to data.

P = polyfit(X,Y,N) finds the coefficients of a polynomial P(X) of degree N that fits the data Y best in a

least-squares sense. P is a row vector of length N+1 containing the polynomial coefficients in

descending powers,

P(1)*X^N + P(2)*X^(N-1) +...+ P(N)*X + P(N+1).

... ...

Reference page for polyfit Other functions named polyfit

(8)

Polyfit and polyval

For evaluating the interpolant, let us see the Matlab help for polyval.

>>help polyval

polyval Evaluate polynomial.

Y = polyval(P,X) returns the value of a polynomial P evaluated at X. P is a vector of length N+1 whose elements are the coefficients of the

polynomial in descending powers.

Y = P(1)*X^N + P(2)*X^(N-1) + ... + P(N)*X + P(N+1) ...

Remark

Note that, when interpolating we need to specify the degree. What about if the degree m n, where n + 1 is the number of points? This leads to least square methods.

(9)

Least squares methods

The Matlab help tells us that polyfit computes the coefficients of the polynomial of degree m that approximates betterthe data (x_i, f_i), i = p, . . . , n in the least squares sense, i.e. it finds Π_m so that it minimizes

kf − Π_mk₂= v u u t

n

X

i =1

|f (x_i) − Πm(xi)|².

If m = 1, we talk about linear regression. In that case Π₁ = ax + b.

In general, we use the command polyfit as before and we only specify the desired degree m.

(10)

Exercise 2

Exercise

On an empty script (called Esercizio2) copy and paste the following code:

clear all close all a=0; b=1;

h =0.05; x=a:h:b; % equispaced points

y=0.1+x+(10^(-1))*rand(size(x)); % the data

and find the best linear approximation, i.e. find Π1 in the least squares sense. Evaluate the approximant on 100 equispaced points. Plot both the points and Π1 on the same figure.

Hint

Do this exercise by considering the Matlab help for polyfit and polyval.

(11)

A demo file a=0; b=2*pi;

h=0.01; x=a:h:b; % nodes

y=sin(2*x)+(10^(-1))*rand(size(x)); % perturbed data for n=0:8

coeff=polyfit(x,y,n); % computes the coefficients z=polyval(coeff,x); % evaluate the polynomial err2=norm(z-y,2); % computes the residual

fprintf(’\n \t n: %2.0f norma2: %1.2e’,n,err2);

% plot the results

ht=1/10000; u=a:ht:b; v=polyval(coeff,u);

plot(x,y,’r.’); hold on; plot(u,v,’k-’,’LineWidth’,2);

titlestr=strcat(’Minimi quadrati di grado:’,num2str(n));

title(titlestr);

legend(’Dati’,’Approx. Minimi quadrati’); hold off;

pause(.5);

end

(12)

Exercise 3

Exercise

Take the script DemoMinimiQuadrati in your folder and renamed as Esercizio3. After commenting it together, do the following:

Change the vector of function values with the function cos(2*x).

Try with higher degrees n< 15.

Substitute the for cicle with a while.