-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
1/57
Universidad Politcnica de MadridEscuela Tcnica Superior de Ingenieros Industriales
Matemticas de la EspecialidadIngeniera Elctrica
Funciones de interpolaciny aproximacin
Jos Luis de la Fuente [email protected]@upm.es
Clase_interpolacin_aproximacin_funciones_2014.pdf
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
2/57
ndice
Introduccin Interpolacin polinmica Polinomios de Lagrange Polinomios de Newton Polinomios Ortogonales Interpolacin polinmica por trozos Interpolacin de Hermite Interpolacin por splines cbicas
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
3/57
Introduccin
Lecture Lecture 88 InterpolationInterpolation
LinearLinear InterpolationInterpolation
QuadraticQuadratic InterpolationInterpolation
PolynomialPolynomial InterpolationInterpolation
PiecewisePiecewise Polynomial InterpolationPolynomial Interpolation
Numerical MethodsNumerical Methods for for CivilCivil EngineersEngineers
Mongkol JIRAVACHARADETS U R A N A R E E INSTITUTE OF ENGINEERINGUNIVERSITY OF TECHNOLOGY SCHOOL OF CIVIL ENGINEERING
Visual Interpolation
Vehicle speed is approximately 49 km/h
0
20
4060
80
100
120
km/h
Figure 10.2
kmh20
40
60 80 100
120 140
12 1234
56
789
1110
NMM: Interpolation page 2
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
4/57
Fonts == interpolation
how do we contain our interpolation?splinesPostscript (Adobe): rasterization on-the-fly. Fonts, etc are defined ascubic Bezier curves (linear interpolation between lower order Beziercurves)TrueType (Apple): similar, quadratic Bezier curves, thus cannot convertfrom TrueType to PS (Type1) losslessly
T. Gambill (UIUC) CS 357 April 12, 2011 2 / 29
Why Splines?
truetype fonts, postscript,metafontsgraphics surfacessmooth surfaces are neededhow do we interpolatesmoothly a set of data?keywords: Bezier Curves,splines, B-splines, NURBSbasic tool: piecewiseinterpolation
T. Gambill (UIUC) CS 357 April 12, 2011 3 / 29
La interpolacin tiene como objeto, en general, la obtencin de nuevospuntos a partir del conocimiento de un conjunto discreto de ellos.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
5/57
La idea es obtener una funcin que se verifique en todos los puntos conocidos yque permita calcular tantos nuevos como se desee.
Examples Polynomial interpolation Piecewise polynomial interpolation
Basic motivations
I Plotting a smooth curve through discrete data points
Suppose we have a sequence of data points
Coordinates x1 x2 xnFunction y1 y2 yn
I Try to plot a smooth curve (a continuous differentiable function)
connecting these discrete points.
Por ejemplo, encontrar el valor de y para un x cualquiera en un experimento enel que se han obtenido un conjunto de puntos .x;y/.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
5/82
La interpolacin tiene como objeto la obtencin de nuevos puntos apartir del conocimiento de un conjunto discreto de ellos.
Por ejemplo, encontrar el valor de y para un x cualquiera en unexperimento en el que se han obtenido un conjunto de puntos.x;y/.
Interpolation between data points
known datay
x
Consider a set of xy data collected during an experiment.
We use interpolation technique to estimate y at x where theres no data.
What is the corresponding value of y for this x ?
BASIC IDEASBASIC IDEAS
From the known data ( xi , yi ), interpolate
Determining coefficient a1, a2, . . . , an of basis function F(x)
F(x) = a1F1(x) + a2F2(x) + . . . + anFn(x)
Polynomials are often used as the basis functions.
F(x) = a1 + a2 x + a3 x2 + . . . + an xn-1
ixxxFy = for )(
nn
ii
ii
yx
yxyx
yx
MM
MM
11
11
++
interpolateyx
y
xx
y
F(x)
y Datos conocidos
Cul es el valor dey que corresponde aeste x?
x
La interpolacin se puede ver como lo inverso de la evaluacin de una funcin.En sta, se pide evaluar un valor de y para un valor dado de x. En lainterpolacin, dados esos puntos, calcular la funcin que pueda generarlos.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
6/57
La aproximacin busca obtener una funcin que de resultados tan cercanoscomo sea posible a los de otra, o a un conjunto de datos, no necesariamentepasando por todos ellos.
Por ejemplo, aproximar una funcin para evitar tener que evaluar sucomplicada expresin: la de la distribucin normal estndar,
N.x/ D 1p2
x1
ey2=2 dy:
Obtener una funcin terica preestablecida que mejor se ajusta a puntosempricos (ajustes por mnimos cuadrados).
Tambin, poder derivar o integrar valores dados en forma de tabla. Hacer pasar por datos discretos funciones continuas y derivables, : : :
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
7/57
Interpolacin vs. aproximacin o ajuste.
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
8/83
Interpolacin vs. aproximacin y ajuste.Interpolation v.s. Curve Fitting
known datay
x
interpolationcurve fit
Curve fitting: fit function & data not exactly agree
Interpolation: function passes exactly through known data
Interpolation & Extrapolation
Interpolation approximate within the range of independent variable
of the given data set.
Extrapolation approximate outside the range of independent variable
of the given data set.
xx1 x2
y
y Datos conocidosFuncin aproximadaInterpolacin
x El ajuste, en general, busca predecir una tendencia o elcomportamiento de datos de acuerdo con un modelo dado;la interpolacin, que la funcin, o funciones, a que de lugar incluyatodos los datos conocidos, habitualmente buenos.
En general,la aproximacin o ajuste busca predecir una tendencia, o el
comportamiento de datos, acorde con un modelo establecido;
la interpolacin que la funcin, o funciones, a que de lugar incluya todos losdatos conocidos, habitualmente buenos.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
8/57
Numricamente: para obtener una funcin f .x/ de interpolacin, un primerenfoque consiste en obtenerla como combinacin lineal de un conjunto defunciones base.
Si se considera un conjunto de n funciones base, j , j D 1; : : : ; n, se pretendeque
f .x/ DnijD1
cjj .x/:
Las funciones base pueden ser diversas: Polinomios, polinomios por trozos o porciones Funciones racionales Funciones trigonomtricas Otras.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
9/57
Si se tienen m datos (de un muestreo de una funcin, de un experimento, etc.)a los que se quiere aproximar una funcin, y n funciones base, despus de unsencillo proceso se llega a un sistema de ecuaciones lineales
nijD1
cjj .xi/ D f .xi/; i D 1; : : : ; m:
Este sistema: Si m > n, lo normal es que sea incompatible y habra que resolverlo
mediante tcnicas de mnimos cuadrados.
Si m < n, el sistema tendr muchas soluciones. Si m D n se puede determinar una nica funcin.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
10/57
Comprobar, ejecutar y discutir el fichero Interpolacion_eje1.m
>> Interpolacion_eje1p =
-0.0022 0.1802 0.3544p =
-0.0000 0.0017 -0.0529 0.6705 -0.6192
xdat = [1 5 10 30 50];ydat = log(xdat);plot(xdat,ydat, o)hold on
pause
p = polyfit(xdat,ydat,2)xvet=1:0.1:50;plot(xvet,polyval(p,xvet))hold on
pause
p = polyfit(xdat,ydat,4)plot(xvet,polyval(p,xvet))
0 5 10 15 20 25 30 35 40 45 50-1
0
1
2
3
4
5
6
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
11/57
Clases EPFL: Position du problme
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
12/57
Interpolacin polinmica
Teorema principal de la interpolacin polinmica Sean .x1; y1/, .x2; y2/,: : : ; .xn; yn/ n duplas de puntos con distintas xi . Existe un polinomio, y slouno, P , de grado n 1 o menor, que satisface P.xi/ D yi , i D 1; : : : ; n.
La polinmica es la forma ms extendida de interpolacin. En la expresinnijD1
cjj .xi/ D f .xi/; i D 1; : : : ; n;
como funciones base se escogen los monomios j .x/ D xj1. Da lugar apn1.x/ D c1 C c2x C c3x2 C C cnxn1 cuyos coeficientes ci son la
solucin del sistema lineal1 Ac D
2641 x1 xn111 x2 xn12::: ::: : : : :::1 xn xn1n
375264c1c2:::cn
375 D264f .x1/f .x2/:::f .xn/
375.1A es una matriz de Vandermonde
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
13/57
Ejemplo. Consideremos los precios de gas natural que siguen:Ao x 2007 2008 2009 2010 2011 2012Precio y 133,5 132,2 138,7 141,5 137,6 144,2
year=[2007 2008 2009 2010 2011 2012];precio=[133.5 132.2 138.7 141.5 137.6 144.2];M = vander(year);a = M\precio;x=linspace(min(year),max(year));p=polyval(a,x);plot(year,precio ,o,x,p,-);
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
14/57
Copiar y pegar en Matlab. Luego usar Interpolacion_eje2.
>> Interpolacion_eje2Warning: Matrix is close to singular or badly scaled.
Results may be inaccurate. RCOND = 7.482181e-033.> In Interpolacion_eje2 at 4
year=[2007 2008 2009 2010 2011 2012];precio=[133.5 132.2 138.7 141.5 137.6 144.2];M = vander(year);a = M\precio;x=linspace(min(year),max(year));p=polyval(a,x);plot(year,precio ,o,x,p,-);hold on
pause
x1 = 2007:1:2012;y = interp1(year,precio,x1,linear);plot(year,precio,o,x1,y,-)hold on
pause
ys = year-mean(year);A = vander(ys);a = A\precio;ds = x - mean(year);p = polyval(a,ds);plot(year,precio,o,x,p,-);
2006 2006.5 2007 2007.5 2008 2008.5 2009 2009.5 2010 2010.5 2011128
130
132
134
136
138
140
142
144
146
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
15/57
Polinomios de Lagrange
Si se tienen dos puntos .x1; y1/ y .x2; y2/, el polinomio lineal que los interpolaes
p1.x/ D c1 C c2x;siendo los coeficientes c1 y c2:
c1 D y1x2 y2x1x2 x1 y c2 D
y2 y1x2 x1 :
Sustituyndolos en la expresin de p1.x/, y reordenndola, queda
p1.x/ D y1 x x2x1 x2 C y2
x x1x2 x1 D y1l1.x/C y2l2.x/:
l1 y l2 son los polinomios de interpolacin de Lagrange de primer orden.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
16/57
En general, para un conjunto de datos, .xi ; yi/, i D 1; : : : ; n, las funcionesbase de Lagrange en Pn1 son
lj .x/ D
nYkD1kj
.x xk/
nYkD1kj
.xj xk/; j D 1; : : : ; n:
Las funciones lj .x/ son polinomios de grado n 1 y cumplen que
lj .xi/ D ij D(1 si i D j0 si i j ; i; j D 1; : : : ; n:
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
17/57
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
15/83
En la figura se ven las funciones base de Lagrange parax D 0 0;25 0;50 0;75 1T .
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10.6
0.4
0.2
0
0.2
0.4
0.6
0.8
1
1.2
x
l k(x)
Funciones base de Lagrange para x=[0.00, 0.25, 0.50, 0.75, 1.00]
l1
l2
l3
l4
l5
Con esta base, la matriz de antes, A, ya no es la de Vandermonde, sino laidentidad, I , y el polinomio de interpolacin
pn1.x/ D y1l1.x/C y2l2.x/C C ynln.x/:
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
18/57
Cdigo de Matlab para obtener la interpolacin con polinomios de Lagrange.
function [l,L]=lagrang_int(x,y)% Calcula el polinomio de interpolacin de Lagrange% x e y vectores de datos; l, coeficientes polinomio resultante,% L polinomio base
N=length(x)-1; l=0;for m=1:N+1
P=1;for k=1:N+1
if k~=m, P=conv(P,poly(x(k)))/(x(m)-x(k)); endendL(m,:)=P; % Polinomios de Lagrange basel=l+y(m)*P; % Coeficientes el polinomio resultante
end
% do_Lagrange_intx = [-2 -1 1 2]; y=[-6 0 0 6];l = lagrang_int(x,y)xx = [-2:0.02:2]; yy = polyval(l,xx);plot(xx,yy,b,x,y,o)
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
19/57
El resultado es el de la figura.
2 1.5 1 0.5 0 0.5 1 1.5 26
4
2
0
2
4
6
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
20/57
Volvamos sobre el problema de los precios del gas natural.% do_Lagrange_int_gas_1year = [2007 2008 2009 2010 2011 2012];precio= [133.5 132.2 138.7 141.5 137.6 144.2];ys = year-mean(year);l = lagrang_int(ys,precio)x = linspace(min(year),max(year),200);ds = x - mean(year);p=polyval(l,ds); plot(year,precio ,o,x,p,-);
2007 2008 2009 2010 2011 2012130
135
140
145
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
21/57
Polinomios de Newton
El polinomio de interpolacin de Newton tiene la formapn1.x/ D c1 C c2.x x1/C c3.x x1/.x x2/C
C cn.x x1/.x x2/ .x xn1/:
Las funciones base de Newton son
j .x/ Dj1jkD1
.x xk/; j D 1; : : : ; n:
Para i < j , j .xi/ D 0, por lo que la matriz A es triangular inferior, conaij D j .xi/.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
22/57
En la figura se ven las funciones base de Newton parax D 0 0;50 1;00 1;50 2T .
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
22/58
En la figura se ven las funciones base de Newton parax D 0 0;50 1;00 1;50 2T .
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 20.5
0
0.5
1
1.5
2
2.5
3
x
New
k(x)
Funciones base de Newton para x=[0.00, 0.50, 1.00, 1.50, 2.00]
1
2 3 4 5
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
23/57
Ejemplo
Calculemos el polinomio de interpolacin de Newton para los puntos.2;27/, .0;1/ y .1; 0/.
El sistema que hay que resolver es241 0 01 x2 x1 01 x3 x1 .x3 x1/.x3 x2/
3524c1c2c3
35 D 24y1y2y3
35 : Sustituyendo 241 0 01 2 0
1 3 3
3524c1c2c3
35 D 242710
35 ;cuya solucin es c D 27 13 4T . El polinomio es pues
p.x/ D 27C 13.x C 2/ 4.x C 2/x:
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
24/57
El clculo polinomio de interpolacin de Newton se puede optimizar usando lasdiferencias divididas.
Volviendo a la expresin matricial general anterior para un polinomio desegundo grado,241 0 01 x2 x1 0
1 x3 x1 .x3 x1/.x3 x2/
3524c1c2c3
35 D 24y1y2y3
35 ;si se sustrae de la segunda fila la primera, y de la tercera tambin la primera, setiene 241 0 00 x2 x1 0
0 x3 x1 .x3 x1/.x3 x2/
3524c1c2c3
35 D 24 y1y2 y1y3 y1
35 :
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
25/57
Si se divide la segunda fila por .x2 x1/ y la tercera por .x3 x1/ se llega a
241 0 00 1 00 1 x3 x2
3524c1c2c3
35 D26666664
y1
y2 y1x2 x1y3 y1x3 x1
37777775 :De la segunda fila se obtiene que c2 D .y2 y1/=.x2 x1/.
Se introducen ahora las diferencias divididas de primer ordenf x1; x2 y2 y1
x2 x1 y f x1; x3 y3 y1x3 x1 :
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
26/57
Si se sustrae la tercera fila de la segunda se llega a241 0 00 1 00 0 x3 x2
3524c1c2c3
35 D264 y1f x1; x2f x1; x3 f x1; x2
375 : Si se divide la tercera fila por x3 x2 se llega a241 0 00 1 0
0 0 1
3524c1c2c3
35 D264 y1f x1; x2f x1; x2; x3
375 ;donde
f x1; x2; x3 f x1; x3 f x1; x2x3 x2
no trivialD f x2; x3 f x1; x2x3 x1 :
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
27/57
Lo no trivialf x1; x3 f x1; x2
x3 x2 Dy3y1x3x1
y2y1x2x1
x3 x2 D.x3 x1/
y3y1x3x1
y2y1x2x1
.x3 x2/.x3 x1/ D
y3 y2 C y2 y1 y2y1x2x1
.x3 x2 C x2 x1/
.x3 x2/.x3 x1/
Dy3y2x3x2 C
y2y1x3x2
.y2y1/.x3x2/
.x2x1/.x3x2/ .y2y1/.x2x1/.x2x1/.x3x2/
x3 x1 Dy3y2x3x2
y2y1x2x1
x3 x1 Df x2; x3 f x1; x2
x3 x1
Con estas frmulas de recurrencia, para un polinomio de segundo grado,c1 D f x1 D y1c2 D f x1; x2 D y2 y1
x2 x1
c3 D f x1; x2; x3 D f x2; x3 f x1; x2x3 x1 D
y3y2x3x2
y2y1x2x1
x3 x1 En general
f xi ; : : : ; xj D f xiC1; : : : ; xj f xi ; : : : ; xj1xj xi :
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
28/57
Las diferencias divididas se pueden calcular en forma de tablax f f ; f ; ; f ; ; ; x1 f x1
f x1; x2
x2 f x2 f x1; x2; x3
f x2; x3 f x1; x2; x3; x4
x3 f x3 f x2; x3; x4
f x3; x4
x4 f x4
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
29/57
Ejemplo
Calcular el polinomio de interpolacin de Newton dex 1 3
20 2
y 3 1343 5
3
La tabla de diferencias divididas es:x f f ; f ; ; f ; ; ; 1
32
0
2
3
134
3
53
12
16
23
13
53
2
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
30/57
El polinomio es entoncesp3.x/ D 3C 12.x 1/C 13.x 1/
x 3
2
2.x 1/ x 32
x
D 3 103x C 16
3x2 2x3:
Este programa realiza la interpolacin de Newton.function [n,DD]=Newton_int_1(x,y)% Interpolacin con polinomios de Newton% Vectores de entrada x e y; salida: coeficientes en n y dif. en DD
N = length(x)-1;DD = zeros(N+1,N+1); DD(1:N+1,1) = y(:);for k=2:N+1
for m=1:N+2-kDD(m,k)=(DD(m+1,k-1)-DD(m,k-1))/(x(m+k-1)-x(m)); % Diferencias divididas
endend
a = DD(1,:); n = a(N+1);for k=N:-1:1
n = [n a(k)] - [0 n*x(k)]; % n(x)*(x-x(k-1))+a_k-1end
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
31/57
Ahora resolvamos un ejemplo cualquiera con este programa.%do_newton_int_1.mx=[-2 -1 1 2 4]; y=[-6 0 0 6 60]; % datos ordenados[n,DD] = Newton_int_1(x,y)n0 = lagrang_int(x,y) % por comparar con Lagrangex = [1 2 4 -1 -2]; y=[0 6 60 0 -6]; % orden aleatorio datos[n1,DD]= Newton_int_1(x,y)xx = [-2: 0.02 : 4]; yy = polyval(n,xx);clf, plot(xx,yy,b-,x,y,o) % se dibuja ltimo caso
2 1 0 1 2 3 410
0
10
20
30
40
50
60
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
32/57
La salida de Matlab sera (ojo! coeficientes=pol. Lagrange):>> do_newton_int_1n =
0 1 0 -1 0DD =
-6 6 -2 1 00 0 2 1 00 6 7 0 06 27 0 0 0
60 0 0 0 0n0 =
Columns 1 through 30.000000000000000 1.000000000000000 0.000000000000000
Columns 4 through 5-1.000000000000000 0
n1 =0 1 0 -1 0
DD =0 6 7 1 06 27 5 1 0
60 12 1 0 00 6 0 0 0
-6 0 0 0 0>>
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
33/57
Resolvamos a mano el ejemplo anterior con la tabla.>> x=[1 3/2 0 2];>> y=[3 13/4 3 5/3];>> [n DD]=Newton_int_1(x,y)n =Columns 1 through 3-2.000000000000000 5.333333333333334 -3.333333333333334Column 43.000000000000000
DD =Columns 1 through 33.000000000000000 0.500000000000000 0.3333333333333333.250000000000000 0.166666666666667 -1.6666666666666673.000000000000000 -0.666666666666667 01.666666666666667 0 0Column 4-2.000000000000000
000
>>
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
34/57
Polinomios Ortogonales
Otra base interesante para interpolacin es la del espacio vectorial depolinomios ortogonales Pn.
El producto interior de dos polinomios p y q, hp; qi, en el intervalo a; b, sedefine como
hp; qi Dl ba
p.x/q.x/!.x/ dx;
donde !.x/ es una funcin de peso no negativa. Los polinomios p y q sonortogonales si hp; qi D 0.
Un conjunto de polinomios fpig es ortonormal si
hpi ; pj i D(1 para i D j0 para i j:
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
35/57
Se puede usar cualquier procedimiento de ortogonalizacin, por ejemploGram-Schmidt, para obtener una base ortonormal de un espacio de polinomios.
Por ejemplo, si !.x/ D 1, y en el intervalo 1; 1 se aplica Gram-Schmidt alos monomios 1, x, x2, x3; : : :, escalando los resultados para que pk.1/ D 1,para cada k, se obtienen los polinomios de Legendre
1; x; .3x2 1/=2; .5x3 3x/=2;.35x4 30x2 C 3/8; .63x5 70x3 C 15x/=8; : : : ;
los primeros n de los cuales forman una base ortogonal de Pn1. Su frmulageneral es
pi.x/ D 12i i
d i
dxi
.x2 1/i :
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
36/57
En la figura se representan los seis primeros polinomios de Legendre.
Otros polinomios ortogonales conocidos:Polinomio Smbolo Intervalo Funcin de pesoLegendre Pk 1; 1 1Chebyshev, primer tipo Tk 1; 1 .1 x2/1=2Chebyshev, segundo tipo Uk 1; 1 .1 x2/1=2Jacobi Jk 1; 1 .1 x/.1C x/; ; > 1Laguerre Lk 0;1/ exHermite Hk .1;1/ ex2
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
37/57
Los polinomios ortogonales tienen propiedades muy tiles para algoritmosnumricos.
Satisfacen frmulas de recurrencia que los hacen fciles de generar y evaluar:pkC1.x/ D .kx C k/pk.x/ kpk1.x/:
La de los polinomios de Legendre, por ejemplo, es
.k C 1/PkC1.x/ D .2k C 1/xPk.x/ kPk1.x/:
Tambin se usan frecuentemente para aproximar por mnimos cuadradosfunciones mediante polinomios de cualquier grado, pues la ortogonalidad haceque la matriz del sistema que se resuelve sea diagonal.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
38/57
Los polinomios de Chebyshev son otro tipo de polinomios de uso frecuente. En su forma trigonomtrica se definen, para x 2 1; 1, por la identidad
Tk.x/ D cos.k arc cos.x//adems de que T0.x/ D 1 y T1.x/ D 1. La frmula de recurrencia de trestrminos es
TkC1.x/ D 2xTk.x/ Tk1.x/:
Los primeros son pues1; x; 2x2 1; 4x3 3x;
8x4 8x2 C 1; 16x5 20x3 C 5x; : : : ;
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
39/57
Los cinco primeros los representa esta grfica.
Su propiedad quizs ms interesante es la equialternancia, o equioscilacin, pueslos sucesivos puntos extremos tienen igual magnitud pero signo distinto, comose aprecia en la figura.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
40/57
En interpolacin polinmica de puntos de una funcin continua, el error mximoen un intervalo se minimiza si se escogen como puntos de interpolacin lasraces de los extremos de un polinomio de Chebyshev de grado adecuado: losnudos o puntos de Chebyshev.
Los puntos de un polinomio de Chebyshev Tk son los k ceros o races de esepolinomio, es decir,
xi D cos2i 12k
; i D 1; : : : ; k
y los kC 1 puntos extremos (mximos y mnimos), incluidos los de los extremosdel intervalo, es decir
xi D cosi
k
; i D 0; : : : ; k:
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
41/57
Los puntos de Chebyshev son las abcisas de los puntos igualmente espaciados alo largo de la semicircunferencia de radio 1 en R2.
cs412: introduction to numerical analysis 10/12/10
Lecture 10: Introduction to Splines
Instructor: Professor Amos Ron Scribes: Mark Cowlishaw, Nathanael Fillmore
1 Review of Chebyshev Points
Last time we talked briefly about using Chebyshev points for polynomial interpolation. The idea isthat our choice of interpolation points can have a large impact on the error of our interpolant. Recallthe expression for error in polynomial interpolation (Given f the function we are approximating,interval [a, b], interpolation points ~x = (x0, x1, . . . , xn), and interpolant pn):
E(t) = f(t) pn(t) = f(n+1)(c)
(n+ 1)!(
ni=0
(t xi))
(a)
(for some c [a, b]) (1)
If we know a great deal about the function f , then we may be able to choose points so as toreduce the error. If we dont have such information about the function, however, the best we cando is to reduce the product (a). The Chebyshev points effectively minimize the maximum value ofthe product (a).
1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Figure 1: Choosing Chebyshev Points
Recall the process for selecting Chebyshev points over an interval [a, b], as shown in Figure 1:
1. Draw the semicircle on [a, b] centered at the midpoint ((a+ b)/2).
2. To select N + 1 points, split the semicircle into N arcs of equal length.
3. Project the arcs onto the x-axis, giving the following formula for each Chebyshev point xj
xj =a+ b
2+b a2
cos(j piN
)(for j = 0, 1, . . . , N)
1
Usar puntos de Chebyshev como abcisas de interpolacin, en vez de puntosigualmente espaciados, tiene ventajas interesantes. Por ejemplo, se quiereinterpolar puntos de la funcin de Runge
f .x/ D 11C 25x2
en el intervalo 1; 1.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
42/57
Usando puntos igualmente espaciados en las abcisas fenmeno de Runge ylos puntos de Chebyshev, el resultado que se obtiene con polinomios de Newtones el que sigue.
1 0.5 0 0.5 10.5
0
0.5
1
1.5
2
1 0.5 0 0.5 10.2
0
0.2
0.4
0.6
0.8
1
1.2
El programa que se ha usado es este.% Chebyshev_ejemplo_1.mf = @(x) 1./(1+25*x.^2); n = 11;xe = linspace(-1,1,n);xc = cos((2*(1:n)-1)*pi/2/n);t = -1:.01:1;c = Newton_int_1(xe,f(xe)); t1 = polyval(c,t);subplot(121), plot(t,f(t),b,t,t1,r,xe,f(xe),o)c = Newton_int_1(xc,f(xc)); t1 = polyval(c,t);subplot(122), plot(t,f(t),b,t,t1,r,xc,f(xc),o)
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
43/57
Se puede probar que el polinomio de Chebyshev de grado n que mejor interpola,o aproxima, puntos de una funcin f .x/ usando puntos de Chebyshev es:
p.x/D 1nC 1
nC1XiD1
f .xi/c0
CnikD1
2
nC 1
nC1XiD1
Tk.xi/f .xi/
!ck
Tk.x/:
Para calcular el valor de ese p.x/ en determinados puntos se puede usar elalgoritmo de Clenshaw:
nikD0
ckTk.x/ D u0 xu1;
dondeun D cn; un1 D cn1 C 2xun yuj D cj C 2xujC1 ujC2; j D n 2; n 1; : : : ; 0:
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
44/57
Los dos programas que siguen calculan ese polinomio y lo evalan paradeterminados puntos.
function [c,x] = chebpol_int(fn,n)x = cos((2*(1:n)-1)*pi/2/n);y = feval(fn,x);T = [zeros(n,1) ones(n,1)];c = [sum(y)/n zeros(1,n-1)];a = 1;for k = 2:n
T = [T(:,2) a*x.*T(:,2)-T(:,1)];c(k) = sum(T(:,2).* y)*2/n;a = 2;
end
function u = chebpol_clenshaw(c,x)n = length(c);u = c(n)*ones(size(x));if n > 1
ujp1 = u;u = c(n-1)+2*x*c(n);for j = n-2:-1:1
ujp2 = ujp1;ujp1 = u;u = c(j)+2*x.*ujp1-ujp2;
endu = u-x.*ujp1;
end
Si se utilizan con>> f = @(x) 1./(1+25*x.^2);>> [c,x] = chebpol_int(f,11);>> t = -1:.01:1;>> plot(t,f(t),b,t,chebpol_clenshaw(c,t),r,x,f(x),ok)
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
45/57
Da como resultado:
1 0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 10.2
0
0.2
0.4
0.6
0.8
1
1.2
que es la misma grfica de antes.
Aqu se pueden ver otras aproximaciones.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
46/57
Interpolacin polinmica por trozos Como hemos podido ver, algunas veces, al interpolar mediante un nicopolinomio un conjunto amplio de datos se suelen producir resultados pocosatisfactorios en forma de oscilaciones.
Una mejora consiste en interpolar cada intervalo entre datos mediante un nicopolinomio u otra funcin.
La interpolacin ms simple es un segmento de lnea recta entre cada dos datoso nudos.
Aqu se pueden ver algunos casos.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
47/57
Interpolacin de Hermite
Esta interpolacin tiene en cuenta los valores de la funcin a aproximar porinterpolacin en puntos concretos y el de sus derivadas.
Cada tramo es un polinomio de tercer grado con primera derivada continua enlos extremos.
El nmero de ecuaciones que se aade as al sistema lineal que subyace en elproceso es significativo.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
48/57
Supongamos que se quiere aproximar f .x/ en el intervalo xi ; xd , medianteinterpolacin con un polinomio de tercer grado
p.x/ D aC b.x xi/C c.x xi/2 C d.x xi/2.x xd /;y que f .xi/ D yi , f .xd / D yd , p.xi/ D yi , p.xd / D yd , p0.xi/ D si yp0.xd / D sd .
Necesitaremos calcular a, b, c y d . La derivada del polinomio esp0.x/ D b C 2c.x xi/C d
2.x xi/.x xd /C .x xi/2
.
Sustituyendo los valores conocidos se tiene quea D yi aC b.xd xi/C c.xd xi/2 D ydb D si b C 2c.xd xi/C d.xd xi/2 D sd :
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
49/57
Escribiendo esto en forma matricial,266641 0 0 0
0 1 0 0
1 xi xd .xd xi/2 00 1 2.xd xi/ .xd xi/2
3777526664a
b
c
d
37775 D26664yisiydsd
37775 : Si se tienen n nudos o datos, har falta determinar 4.n 1/ parmetros de lospolinomios.
El que se requiera que interpolen esos n datos aade 2.n 1/ ecuaciones, puescada n 1 cbica debe verificar los valores en sus extremos.
El que tengan derivadas continuas aade otras n 2 ecuaciones para cadapunto de unin.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
50/57
El total de ecuaciones es 3n 4, lo que deja 4.n 1/ 3nC 4 D nparmetros libres.
La interpolacin por tanto no es nica, por lo que se pueden fijar mscondiciones para esos grados de libertad: monotonicidad, convexidad, etc.
La funcin que realiza esta aproximacin en Matlab es pchip.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
51/57
Una sesin de trabajo con un ejemplo sencillo puede ser>> x = -3:3;>> y = [-1 -1 -1 0 1 1 1];>> t = -3:.01:3;>> p = pchip(x,y,t);>> plot(x,y,o,t,p,-)>> legend(datos,pchip,3)
3 2 1 0 1 2 31
0.8
0.6
0.4
0.2
0
0.2
0.4
0.6
0.8
1
datospchip
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
52/57
Interpolacin por splines cbicas
Una spline es una curva definida, normalmente, mediante polinomios de gradok, con continuidad hasta la derivada k 1.
Una spline cbica es un polinomio de tercer grado con continuidad hasta lasegunda derivada.
La idea de interpolar mediante splines es usar varias frmulas, cada unacorrespondiente a un polinomio de grado bajo, para pasar a travs de variospuntos.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
53/57
El ejemplo ms simple es un spline lineal, en el que se conectan los puntos ainterpolar mediante segmentos de recta.
En la figura se muestra un ejemplo de spline lineal y el mismo con spline cbica.
166 | CHAPTER 3 Interpolation
2. Build a Matlab program to evaluate the cosine function correct to 10 decimal places usingChebyshev interpolation. Start by interpolating on a fundamental domain [0,/2], and extendyour answer to inputs between 104 and 104. You may want to use some of the Matlab codewritten in this chapter.
3. Carry out the steps of Computer Problem 2 for lnx, for inputs x between 104 and 104. Use[1,e] as the fundamental domain. What is the degree of the interpolation polynomial thatguarantees 10 correct digits? Your program should begin by nding the integer k such thatek x < ek+1. Then xek lies in the fundamental domain. Demonstrate the accuracy of yourprogram by comparing it with Matlabs log command.
4. Let f (x) = e|x|. Compare evenly spaced interpolation with Chebyshev interpolation byplotting degree n polynomials of both types on the interval [1,1], for n = 10 and 20. Forevenly spaced interpolation, the left and right interpolation base points should be 1 and 1. Bysampling at a 0.01 step size, create the empirical interpolation errors for each type, and plot acomparison. Can the Runge phenomenon be observed in this problem?
5. Carry out the steps of Computer Problem 4 for f (x) = ex2 .
3.4 CUBIC SPLINESSplines represent an alternative approach to data interpolation. In polynomial interpola-tion, a single formula, given by a polynomial, is used to meet all data points. The idea ofsplines is to use several formulas, each a low-degree polynomial, to pass through the datapoints.
The simplest example of a spline is a linear spline, in which one connects the dotswithstraight-line segments. Assume that we are given a set of data points (x1,y1), . . . , (xn,yn)with x1 < < xn. A linear spline consists of the n 1 line segments that are drawnbetween neighboring pairs of points. Figure 3.12(a) shows a linear spline where, betweeneach neighboring pair of points (xi,yi), (xi+1,yi+1), the linear function y = ai + bix isdrawn through the two points. The given data points in the gure are (1,2), (2,1), (4,4),and (5,3), and the linear spline is given by
1 2 3 4 5
1
2
3
4
y
x1 2 3 4 5
1
2
3
4
y
x
(a) (b)Figure 3.12 Splines through four data points. (a) Linear spline through (1,2), (2,1),
(4,4), and (5,3) consists of three linear polynomials given by (3.15). (b) Cubic spline
through the same points, given by (3.16).
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
54/57
Como en el caso de Hermite, las splines cbicos para interpolar n puntos de unafuncin imponen 3n 4 condiciones, ms n 2 adicionales por requerirse lacontinuidad de la segunda derivada.
Los dos grados de libertad adicionales se fijan si, por ejemplo, Las primeras derivadas en los extremos izquierdo y derecho se fijan en
sendos valores.
Las segundas derivadas en los extremos son cero. Las primeras y segundas derivadas en los extremos son iguales dos a dos, etc.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
55/57
Ejemplo
Estudiemos la interpolacin de tres puntos .x1; y1/, .x2; y2/ y .x3; y3/. Los polinomios de los dos tramos podran ser
p1.x/ D 1 C 2x C 3x2 C 4x3p2.x/ D 1 C 2x C 3x2 C 4x3:
Se necesitan 8 ecuaciones para determinar los parmetros.
El que las cbicas pasen por los puntos dados impone las siguientes condiciones1 C 2x1 C 3x21 C 4x31 D y11 C 2x2 C 3x22 C 4x32 D y21 C 2x2 C 3x22 C 4x32 D y21 C 2x3 C 3x23 C 4x33 D y3:
La continuidad de las primeras derivadas en x2 impone esta condicin2 C 23x2 C 34x22 D 2 C 23x2 C 34x22:
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
56/57
La continuidad de las segundas derivadas en x2 impone esta otra23 C 64x2 D 23 C 64x2:
Por definicin, se impone que las segundas derivadas en los extremos sean cero,lo que hace que
23 C 64x1 D 0 y 23 C 64x3 D 0:
Todo en forma matricial queda2666666664
1 x1 x21 x
31 0 0 0 0
1 x2 x22 x
32 0 0 0 0
0 0 0 0 1 x2 x22 x
32
0 0 0 0 1 x3 x23 x
33
0 1 2x2 3x22 0 1 2x2 3x22
0 0 2 6x2 0 0 2 6x20 0 2 6x1 0 0 0 0
0 0 0 0 0 0 2 6x3
3777777775
2666666664
12341234
3777777775D
2666666664
y1y2y3y40
0
0
0
3777777775:
Resolviendo este sistema se obtiene la solucin deseada.
-
h i j
d e f g
a b c
10 8 7
9 4 6 5
1 2 3
57/57
La funcin que realiza esta aproximacin en Matlab es spline. Una sesin de trabajo puede ser, comparando con Hermite,
x = -3:3;y = [-1 -1 -1 0 1 1 1];t = -3:.01:3;p = pchip(x,y,t);s = spline(x,y,t);plot(x,y,o,t,p,-,t,s,-.)legend(datos,pchip,spline,4)
3 2 1 0 1 2 31.5
1
0.5
0
0.5
1
1.5
datospchipspline