Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-1
Interpolacja
funkcja przybliżana
)
x
(
f
,
siatka węzłów
)
x
(
f
f
,
n
,...,
i
,
x
i
i
i
====
====
0
Dla dowolnych, różnych n+1 punktów węzłowych istnieje
dokładnie jeden wielomian interpolacyjny stopnia, co
najwyżej n taki, że
i
i
f
)
x
(
P
====
dla i=0,1,...,n
Wzór interpolacyjny Lagrange’a
∏
∏
∏
∏
∑
∑
∑
∑
≠≠≠≠
====
====
−−−−
−−−−
====
n
i
k
k
k
i
k
n
i
i
x
x
x
x
f
)
x
(
P
0
0
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-2
Jeśli wielomian P(x) ma współczynniki
0
1
1
c
c
,
c
,
c
,
n
n
L
−
to możemy obliczyć jego
wartości
)
x
(
P
),
x
(
P
),
x
(
P
m
L
1
0
w punktach
m
x
,
x
,
x
L
1
0
:
=
−
−
−
−
−
−
−
−
−
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
0
1
1
0
1
1
1
1
c
c
c
c
x
x
x
x
x
x
x
x
x
x
x
x
)
x
(
P
)
x
(
P
)
x
(
P
)
x
(
P
n
n
m
n
m
n
m
m
n
m
n
m
n
n
n
n
m
m
M
L
L
M
M
O
M
M
L
L
M
Schemat Hornera:
n=3
0
1
2
2
3
3
c
x
c
x
c
x
c
)
x
(
P
+
+
+
=
=
(
)
0
1
2
2
3
c
x
c
x
c
x
c
+
+
+
=
(
)
(
)
0
1
2
3
c
x
c
x
c
x
c
+
+
+
więc:
c
2
c
1
c
0
c
3
= a
3
a
3
x
a
2
x
a
1
x
a
2
=c
2
+a
3
x
a
1
=c
1
+a
2
x
P(x)=c
0
+a
1
x
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-3
Współczynniki wielomianu interpolacyjnego
0
1
1
1
c
x
c
x
c
x
c
)
x
(
P
n
n
n
n
+
+
+
+
=
−
−
L
można obliczyć z:
=
−
−
−
−
−
−
−
−
−
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
f
f
f
f
c
c
c
c
x
x
x
x
x
x
x
x
x
x
x
x
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
0
1
1
1
1
M
M
L
L
M
M
O
M
M
L
L
macierz
Vandermonde’a
,
jest nieosobliwa jeśli węzły x
i
są różne, ale źle uwarunkowana (trudno ją
odwrócić)
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-4
Interpolacja przez rodzinę trójkątną
)
x
x
(
)
x
x
)(
x
x
(
)
x
(
)
x
x
)(
x
x
(
)
x
(
)
x
x
(
)
x
(
)
x
(
n
n
1
1
0
1
0
2
0
1
0
1
−
−
−
−
=
−
−
=
−
=
=
L
L
ϕ
ϕ
ϕ
ϕ
,
0
1
1
1
1
c
)
x
(
c
)
x
(
c
)
x
(
c
)
x
(
P
n
n
n
n
+
+
+
+
=
−
−
ϕ
ϕ
ϕ
L
0
0
0
0
0
f
c
c
)
x
(
P
f
=
⇒
=
=
0
1
0
1
1
0
0
1
1
1
1
x
x
c
f
c
c
)
x
x
(
c
)
x
(
P
f
−
−
=
⇒
+
−
=
=
L
=
⇒
+
−
+
−
−
=
=
2
0
0
2
1
1
2
0
2
2
2
2
c
c
)
x
x
(
c
)
x
x
)(
x
x
(
c
)
x
(
P
f
…………..
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-5
Rekurencyjne tworzenie wielomianów interpolacyjnych
Niech
)
(
,...,
1
,
0
x
k
i
i
i
P
będzie wielomianem stopnia nie
większego od k, spełniającym równania węzłów
k
i
,...,
i
,
i
1
0
:
k
j
j
i
f
j
i
x
k
i
i
i
P
,...,
0
)
(
,...,
1
,
0
=
=
Wtedy zachodzi wzór rekurencyjny
n
i
i
f
x
i
P
,...,
0
)
(
=
=
0
)
(
1
,...,
1
,
0
)
0
(
)
(
,...,
2
,
1
)
0
(
)
(
,...,
1
,
0
i
x
k
i
x
x
k
i
i
i
P
k
i
x
x
x
k
i
i
i
P
i
x
x
x
k
i
i
i
P
−
−
−
−
−
=
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-6
Metoda
Aitken’a
0
x
0
0
f
)
x
(
P
====
1
x
1
1
f
)
x
(
P
====
)
x
(
P
,1
0
2
x
2
2
f
)
x
(
P
====
)
x
(
P
,2
0
)
x
(
P
,
, 2
1
0
3
x
3
3
f
)
x
(
P
====
)
x
(
P
,3
0
)
x
(
P
,
, 3
1
0
)
x
(
P
,
,
,
3
2
1
0
4
x
4
4
f
)
x
(
P
====
)
x
(
P
,4
0
)
x
(
P
,
, 4
1
0
)
x
(
P
,
,
,
4
2
1
0
)
x
(
P
,
,
,
,
4
3
2
1
0
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-7
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
i
i
i
i
i
i
i
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
P
y
x
x
x
m
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
P
y
x
x
x
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
x
x
P
x
P
y
x
x
x
x
x
x
P
x
x
x
P
x
x
x
P
x
P
y
x
x
x
x
P
y
x
x
x
x
P
x
P
x
P
x
P
x
P
y
x
x
x
i
−
−
−
=
−
−
−
=
−
−
−
=
−
−
−
=
=
−
−
−
−
=
−
−
−
=
−
−
−
=
=
−
−
−
−
=
−
−
−
=
=
−
−
−
−
=
=
−
=
−
=
−
−
−
−
−
1
,
2
,
,
1
,
0
1
,
,
1
,
0
1
,
,
1
,
0
2
,
1
,
0
2
,
1
,
0
2
,
2
,
1
,
0
1
,
0
1
,
0
1
,
1
,
0
0
0
0
,
0
3
2
3
,
1
,
0
3
2
,
1
,
0
2
3
,
2
,
1
,
0
3
1
3
,
0
3
1
,
0
1
3
,
1
,
0
3
0
3
3
0
0
3
,
0
3
3
3
3
2
1
2
,
0
2
1
,
0
1
2
,
1
,
0
2
0
2
2
0
0
2
,
0
2
2
2
2
1
0
1
1
0
0
1
,
0
1
1
1
1
0
0
0
0
,
,
1
,
0
,
2
,
1
,
0
,
1
,
0
,
0
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
3
)
(
)
(
)
(
)
(
)
(
)
(
)
(
2
)
(
)
(
)
(
)
(
1
)
(
0
)
(
)
(
)
(
)
(
)
(
K
K
K
K
K
O
M
M
M
M
M
M
M
K
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-8
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
)
x
x
(
)
(
f
)!
n
(
)
x
(
P
)
x
(
f
n
i
i
)
n
(
∏
∏
∏
∏
====
++++
−−−−
++++
====
−−−−
0
1
1
1
ξξξξ
gdzie
ξξξξ
jest pewnym punktem z najmniejszego przedziału
domkniętego zawierającego
n
x
,...,
x
,
x
0
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-9
Przykład:
2
5
1
1
)
x
(
)
x
(
y
++++
====
węzły równoodległe w [-1,1]
węzły Czebyszewa w [-1,1]
w=[];x=[];y=[];apr=[];
xx=-1:.01:1;yy=1./(1+(5*xx).^2);
for n=4:16
h=2/n;
for i=1:n+1
x(n,i)=-1+(i-1)*h;
end
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);
apr(n,:)=polyval(w,xx);
end
w=[];x=[];y=[];apr=[];
xx=-1:.01:1;yy=1./(1+(5*xx).^2);
for n=4:16
for i=1:n+1
x(n,1:n+1)=-seqcheb(n+1,2);
end
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);
apr(n,:)=polyval(w,xx);
end
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-10
-1
-0.5
0
0.5
1
-0.2
0
0.2
0.4
0.6
0.8
1
n=5,6,7
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-11
-1
-0.5
0
0.5
1
-4
-3
-2
-1
0
1
2
n=8,9,10,11,12
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-12
-1
-0.5
0
0.5
1
-0.2
0
0.2
0.4
0.6
0.8
1
n=5,6,7
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne wykład 3
W3-13
-1
-0.5
0
0.5
1
0
0.2
0.4
0.6
0.8
1
1.2
n=8,9,10,11,12