Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Liniowe zadanie aproksymacji średniokwadratowej
funkcja przybliżana f ( x ),
siatka węzłów xi , i = 0,...,m, fi = f ( xi )
dane: punkty węzłowe ( xi , fi ) i = 0,...,m
współczynniki wagowe wi > 0 i = 0,...,m
funkcje bazowe �i ( x ) i = 0,...,n
n
*
funkcja aproksymująca f ( x ) = ci�i ( x )
"
i=0
m
*
szukane stałe ci takie by ( f ( xi ) - fi )2 wi min
"
i=0
W2 - 1
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Notacja:
dla dowolnych funkcji f (�" ), g(�" ), przy danej siatce
węzłów i wsp. wagowych
m
f , g := f ( xi )g( xi )wi
"
i=0
Jeżeli f , g = 0 to funkcje f (�" ), g(�" ), nazywamy
ortogonalnymi.
Jeżeli fi , f = 0 dla i `" j i fi , fi `" 0
to funkcje
j
fi (�" ), i = 1,2,... układem (rodziną) funkcji
ortogonalnych.
W2 - 2
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Twierdzenie
Jeżeli funkcje bazowe są liniowo niezależne to liniowe
zadanie aproksymacji średniokwadratowej ma jedyne
rozwiązanie. Rozwiązanie to spełnia układ równań
normalnych;
�0,�0 �1,�0 L �n,�0 Ą#c0 f ,�0
Ą# ń# Ą# ń#
ń#
ó#
�0,�1 �1,�1 L �n,�1 Ą#ó#c1 Ą# ó# f ,�1 Ą#
ó# Ą# ó# Ą#
ó# Ą#
=
ó# L L L L Ą# M ó# L Ą#
ó# Ą#
ó#
�0,�n �1,�n L �n,�n Ą#ó#cn Ą# ó# f ,�n Ą#
Ł# Ś#
Ł# Ś# Ł# Ś#
Jeżeli funkcje bazowe są rodziną funkcji ortogonalnych to
rozwiązanie upraszcza się do:
f ,�i
ci = , i = 0,...,n
�i ,�i
W2 - 3
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Przykład
�i( x ) = xi , i = 0,...,n
1
x0 = 0, x1 = , ... , xm = 1, m=10
m
wi = 1, i = 0,...,m
n el. max. mac. odwr. n el. max. mac. odwr.
1 0.9 8 1.9908e+010
2 12.5 9 1.4199e+012
3 375 10 2.4218e+014
4 9 874
5 252 828
6 8 771 904
7 3.9133e+008
W2 - 4
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Wielomiany Czebyszewa
Tn( x ) = cos( n arc cos x ) - 1 d" x d" 1, n = 0,1,...
T0( x ) = 1 T1( x ) = x, Tn+1( x ) = 2xTn( x ) - Tn-1( x ) n = 1,2,...
Współczynnik wiodący wielomianu Tn( x ) jest równy
2n-1 dla n=1,2,.
Tn( -x ) = ( -1 )nTn( x )
Wielomian Tn+1( x ) ma n+1 zer
( 2k + 1 )Ą
xk = cos , k = 0,1,...,n, n = 0,1,....
2( n + 1 )
W2-5
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Układ wielomianów T0( x ),T1( x ),...,Tn( x ) jest
ortogonalny względem wag wi = 1 i węzłów xi , które są
zerami wielomianu Tn+1( x ):
0 dla i `" j
ż#
�#
n + 1
Ti ,Tj = dla i = j `" 0
�#
�#n 2 1 dla i = j = 0
+
�#
W2-6
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
1
0
-1
-1 -0.5 0 0.5
1
0
-1
-1 -0.5 0 0.5
1
0
-1
-1 -0.5 0 0.5
1
0
-1
-1 -0.5 0 0.5
1
0
-1
-1 -0.5 0 0.5
W2-7
T10(x)
T4(x)
T60(x)
T30(x)
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Zadanie wielomianowej aproksymacji jednostajnej
funkcja przybliżana f ( x ),
siatka węzłów xi , i = 0,...,m, fi = f ( xi )
dane: punkty węzłowe ( xi , fi ) i = 0,...,m
n
*
funkcja aproksymująca f ( x ) = ai xi ma być
"
i=0
wielomianem stopnia co najwyżej n
*
szukane stałe ai takie by max f ( xi ) - fi min
i
Tw. Weierstrassa
Jeżeli funkcja f(x) jest ciągła w skończonym przedziale
[a,b], to dla każdego � > 0 istnieje wielomian Pn( x )
stopnia n, taki że dla każdego x "[a,b], f ( x ) - Pn( x ) < �
W2-8
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Interpolacja
funkcja przybliżana f ( x ),
siatka węzłów xi , i = 0,...,n, fi = f ( xi )
Dla dowolnych, różnych n+1 punktów węzłowych istnieje
dokładnie jeden wielomian interpolacyjny stopnia, co
najwyżej n taki, że
P( xi ) = fi dla i=0,1,...,n
Wzór interpolacyjny Lagrange a
n n
x - xk
P( x ) = fi
" "
xi
i =0 k =0 - xk
k `"i
W2-9
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Współczynniki wielomianu interpolacyjnego
P( x ) = cn xn + cn-1xn-1 +L+ c1x + c0
można obliczyć z:
n n-1
Ą# ń# cn fn
x0 x0 L x0 1 Ą# ń# Ą# ń#
ó#
n n-1
fn-1Ą#
x1 x1 L x1 1Ą#ó# Ą# ó# Ą#
ó# Ą#
ó#cn-1Ą# ó#
ó#
ó# Ą# ó# Ą#
M = M
M M O M MĄ#
ó# Ą#
ó# Ą# ó# Ą#
n n-1
macierz Vandermonde a,
c1 f1
xn-1 L xn-1 1Ą#ó# Ą# ó# Ą#
n-1
ó#x
n n-1
ó#
c0 f0
xn xn L xn 1Ą#ó# Ą# ó# Ą#
Ł# Ś# Ł# Ś#
Ł# Ś#
jest nieosobliwa jeśli węzły xi są różne, ale z
le uwarunkowana (trudno ją
odwrócić)
W2-10
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
cn , cn-1,Lc1, c0 to możemy obliczyć jego
Jeśli wielomian P(x) ma współczynniki
P( x0 ), P( x1 ),LP( xm )w punktach x0 , x1,Lxm :
wartości
n n-1
P( x0 ) Ą# ń# cn
Ą# ń# x0 x0 L x0 1 Ą# ń#
ó#
ó# Ą#
n n-1
P( x1 )
x1 x1 L x1 1Ą#ó# Ą#
ó# Ą#
ó# Ą# ó#cn-1Ą#
ó#
ó# M Ą# = ó# Ą#
M
M M O M MĄ#
ó# Ą#
ó#P( xm-1 )Ą# ó# Ą#
n n
c1
xm-1 L xm-1 1Ą#ó# Ą#
m-1 -1
ó#x
ó# Ą#
n n
ó#
ó# Ą#
P( xm ) c0
xm xm-1 L xm 1Ą#ó# Ą#
Ł# Ś# Ł# Ś#
Ł# Ś#
Schemat Hornera:
n=3
( ) (( ) )
P( x ) = c3x3 + c2x2 + c1x + c0 c3x + c2 x2 + c1x + c0 c3x + c2 x + c1 x + c0
= =
więc:
c2 c1 c0
c3= a3 a3x a2x a1x
a2=c2+a3x a1=c1+a2x P(x)=c0+a1x
W2-11
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Interpolacja przez rodzinę trójkątną
�0( x ) = 1
�1( x ) = ( x - x0 )
�2( x ) = ( x - x0 )( x - x1 )
P( x ) = cn�n( x )+ cn-1�n-1( x )+L+ c1�1( x )+ c0
,
L
�n( x ) = ( x - x0 )( x - x1 )L( x - xn-1 )
f0 = P( x0 ) = c0 �! c0 = f0
f1 - c0
f1 = P( x1 ) = c1( x1 - x0 )+ c0 �! c1 =
x1 - x0
f2 = P( x2 ) = c2( x2 - x0 )( x2 - x1 )+ c1( x2 - x0 ) + c0 �! c2 = L
& & & & ..
W2-12
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Rekurencyjne tworzenie wielomianów interpolacyjnych
Reszta wzoru interpolacyjnego:
Jeżeli funkcja f (�" ) ma ciągłe pochodne do rzędu n+1 a
P(�" ) jest wielomianem interpolacyjnym stopnia n, to
n
1
( n+1 )
f ( x ) - P( x ) = f (� ) ( x - xi )
"
( n + 1 )! i =0
gdzie � jest pewnym punktem z najmniejszego przedziału
domkniętego zawierającego x, x0 ,..., xn
W2-13
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
1
Przykład: y( x ) =
1 + ( 5x )2
węzły równoodległe w [-1,1] węzły Czebyszewa w [-1,1]
w=[];x=[];y=[];apr=[]; w=[];x=[];y=[];apr=[];
xx=-1:.01:1;yy=1./(1+(5*xx).^2); xx=-1:.01:1;yy=1./(1+(5*xx).^2);
for n=4:16 for n=4:16
h=2/n;
for i=1:n+1 for i=1:n+1
x(n,i)=-1+(i-1)*h; x(n,1:n+1)=-seqcheb(n+1,2);
end end
y(n,1:n+1)=1./(1+(5*x(n,1:n+1)).^2); y(n,1:n+1)=1./(1+(5*x(n,1:n+1)).^2);
w=polyfit(x(n,1:n+1),y(n,1:n+1),n); w=polyfit(x(n,1:n+1),y(n,1:n+1),n);
apr(n,:)=polyval(w,xx); apr(n,:)=polyval(w,xx);
end end
W2-14
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
1
0.8
0.6
0.4
0.2
0
-0.2
-1 -0.5 0 0.5 1
n=5,6,7
W2-15
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
2
1
0
-1
-2
-3
-4
-1 -0.5 0 0.5 1
n=8,9,10,11,12
W2-16
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
1
0.8
0.6
0.4
0.2
0
-0.2
-1 -0.5 0 0.5 1
n=5,6,7
W2-17
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
1.2
1
0.8
0.6
0.4
0.2
0
-1 -0.5 0 0.5 1
n=8,9,10,11,12
W2-18
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Interpolacja odcinkowa
Czemu budować wielomian interpolacyjny wysokiego stopnia na
całym przedziale?
Interpolacja odcinkowo liniowa
[] przyjmujemy
xk , xk+1
W przedziale
fk+1 - fk
L( x ) = fk + ( x - xk )
xk+1 - xk
L(x) jest ciągłą funkcja w całej dziedzinie x, ale pierwsza pochodna L (x), nie jest
ciągła.
W2-19
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Odcinkowa interpolacja sześcienna Hermite a
Interpolacja wielomianem stopnia 3, który spełnia 4 warunki: 2 nałożone na
wartosci funkcji i 2 na (nieznane) wartości pochodnej.
Jeśli znamy i wartości funkcji i jej pierwszej pochodnej w punktach węzłowych
interpolacja Hermite a może odtworzyć te wartości. Jeśli nie znamy wartości
pochodnej (nachyleń funkcji) trzeba je w jakis sposób narzucić. Sposobymoga być
różne, na przykład w procedurach Matlaba pchip i spline: .
nachylenia pchip
W2-20
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
Interpolacja przez funkcje sklejane (splines) (sześcienne)
Interpolacja wielomianami stopnia 3 o ciagłej drugiej pochodnej.
Koncepcja funkcji sklejanych pojawia się także w problemach:
interpolacji i aproksymacji funkcji wielowymiarowych,
interpolacji wielomianami wyższego stopnia,
interpolacji z adaptacja węzłów.
W2-21
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne ET3 wykład 2
W2-22