Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne
Kilka dowodów
Interpolacja
Twierdzenie (istnienie i jednoznaczność wielomianu interpolacyjnego):
Dla każdych, różnych n+1 węzłów istnieje dokładnie jeden wielomian interpolacyjny stopnia
nie większego niż n .
Dowód:
Istnienie: wynika bezpośrednio ze wzoru interpolacyjnego Lagrange’a.
Jednoznaczność:
Załóżmy istnienie dwóch wielomianów interpolacyjnych P oraz Q , każdy stopnie nie
wyższego niż n:
i
i
f
x
P
=
)
(
,
i
i
f
x
Q
=
)
(
for i=0,1,...,n.
wtedy P-Q jest tez wielomianem stopnia nie wyższego niż n i zeruje się w n+1 punktach x
i
i=0,1,...,n, musi być więc wielomianem zerowym.☻
Twierdzenie (rekurencyjne tworzenie wielomianów interpolacyjnych)
)
(
,...,
1
,
0
x
Niech
k
i
i
i
P
oznacza wielomian stopnia nie wyższego niż k, spełniający warunki
interpolacji w węzłach o numerach
:
k
i
i
i
,...,
,
1
0
k
j
j
i
f
j
i
x
k
i
i
i
P
,...,
0
)
(
,...,
1
,
0
=
=
Obowiązuje następująca zależność rekurencyjna
n
i
i
f
x
i
P
,...,
0
)
(
=
=
0
)
(
1
,...,
1
,
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
−
−
−
−
−
=
Dowód:
0
)
0
(
1
,...,
0
0
)
0
(
1
,...,
1
,
0
)
0
(
)
0
(
,...,
2
,
1
)
0
0
(
)
0
(
,...,
1
,
0
i
f
i
x
k
i
i
P
i
x
k
i
x
i
x
k
i
i
i
P
k
i
x
i
x
i
x
k
i
i
i
P
i
x
i
x
i
x
k
i
i
i
P
=
−
=
=
−
−
−
−
−
=
k
i
f
k
i
x
k
i
i
P
i
x
k
i
x
k
i
x
k
i
i
i
P
k
i
x
k
i
x
k
i
x
k
i
i
i
P
i
x
k
i
x
k
i
x
k
i
i
i
P
=
=
=
−
−
−
−
−
=
)
(
,...,
1
0
)
(
1
,...,
1
,
0
)
(
)
(
,...,
2
,
1
)
0
(
)
(
,...,
1
,
0
for 0<j<k:
0
)
(
1
,...,
1
,
0
)
(
)
(
,...,
2
,
1
)
0
(
)
(
,...,
1
,
0
i
x
k
i
x
j
i
x
k
i
i
i
P
k
i
x
j
i
x
j
i
x
k
i
i
i
P
i
x
j
i
x
j
i
x
k
i
i
i
P
−
−
−
−
−
=
=
1
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne
=
j
i
f
i
x
k
i
x
j
i
f
k
i
x
j
i
x
j
i
f
i
x
j
i
x
=
−
−
−
−
0
)
(
)
0
(
☻
Wielomiany Czebyszewa
Definicja i podstawowe własności:
1.
,...
1
,
0
,
1
1
)
arccos
cos(
)
(
=
≤
≤
−
=
n
x
x
n
x
T
n
2.
,...
2
,
1
)
(
)
(
2
)
(
,
)
(
1
)
(
1
1
1
0
=
−
=
=
=
−
+
n
x
T
x
xT
x
T
x
x
T
x
T
n
n
n
3. Współczynnik przy najwyższej potędze w wielomianie
jest równy 2
)
(x
T
n
n-1
dla n=1,2,....
4.
)
(
)
1
(
)
(
x
T
x
T
n
n
n
−
=
−
5. Wielomian
ma n+1 pierwiastków w punktach
)
(
1
x
T
n
+
,....
1
,
0
,
,...,
1
,
0
,
)
1
(
2
)
1
2
(
cos
=
=
+
+
=
n
n
k
n
k
x
k
π
Wielomian będziemy nazywać znormalizowanym gdy współczynnik przy najwyższej potędze
jest w nim równy 1.
Dla funkcji f ciągłej w [a,b] rozważamy normę
)
(
max
]
,
[
]
,
[
x
f
f
b
a
x
b
a
∈
=
Twierdzenie: (Własność min-max wielomianów Czebyszewa)
Jeśli P jest znormalizowanym wielomianem stopnia n>0, to
n
n
n
T
P
−
−
−
−
=
≥
1
]
1
,
1
[
1
]
1
,
1
[
2
2
.
Dowód: (przez doprowadzenie do sprzeczności)
Przypuśćmy, że
n
P
−
−
<
1
]
1
,
1
[
2
n
x
P
x
−
<
−
∈
∀
⇔
1
2
)
(
]
1
,
1
[
. Rozważmy znormalizowany
wielomian
. Dla n+1 wartości
n
n
T
−
1
2
n
k
x
k
π
cos
=
k=0,1,…,n w przedziale [-1,1] mamy
⎩
⎨
⎧
−
=
=
⎟
⎠
⎞
⎜
⎝
⎛
=
−
−
−
−
−
k
ych
nieparzyst
dla
k
parzystych
dla
k
n
k
n
x
T
n
n
n
n
k
n
n
1
1
1
1
1
2
2
)
cos(
2
)
arccos(cos
cos
2
)
(
2
π
π
.
Wynika stąd, że różnica
zmienia znak tak, że ma co najmniej n pierwiastków w
przedziale [-1,1], co jest sprzeczne z tym, że stopień wielomianu
jest mniejszy od
n (współczynniki przy najwyższej, n-tej potędze w obu wielomianach są równe 1) ☻
P
T
n
n
−
−
1
2
P
T
n
n
−
−
1
2
Optymalny wybór węzłów interpolacji:
Resztę wzoru interpolacyjnego na przedziale [-1,1] można oszacować w następujący sposób:
]
1
,
1
[
0
]
1
,
1
[
)
1
(
]
1
,
1
[
)
(
)!
1
(
1
)
(
)
(
−
=
−
+
−
∏
−
+
≤
−
n
i
i
n
x
x
f
n
x
P
x
f
)
(
0
∏
=
−
n
i
i
x
x
jest znormalizowanym wielomianem stopnia n+1.
Zgodnie z twierdzeniem podanym wyżej dla dowolnych x
i
n
n
i
i
x
x
−
−
=
≥
−
∏
2
)
(
]
1
,
1
[
0
i norma
]
1
,
1
[
0
)
(
−
=
∏
−
n
i
i
x
x
osiąga wartość najmniejszą gdy
, to jest gdy x
)
(
2
)
(
1
0
x
T
x
x
n
n
n
i
i
+
−
=
=
−
∏
i
są
pierwiastkami wielomianu
:
)
(
2
1
x
T
n
n
+
−
n
i
n
i
x
i
,...,
1
,
0
,
)
1
(
2
)
1
2
(
cos
=
+
+
=
π
.
2
Instytut Automatyki Politechniki Łódzkiej - Metody Numeryczne
Ekstrapolacja Richardsona
Twierdzenie:
Jeśli
i zastosujemy wzór rekurencyjny:
L
+
+
+
=
2
1
2
1
0
1
)
(
p
p
h
a
h
a
a
h
F
1
)
(
)
(
)
(
)
(
1
1
1
−
−
+
=
−
−
+
m
p
m
m
m
m
q
h
F
h
q
F
h
q
F
h
F
gdzie q>1, to
L
+
+
+
=
+
+
+
+
+
+
+
2
1
)
1
(
2
)
1
(
1
0
1
)
(
m
m
p
m
m
p
m
m
m
h
a
h
a
a
h
F
Dowód: (indukcyjny)
Dla m=0 teza jest spełniona na mocy założenia.
Przypuśćmy, że
chcemy udowodnić, że
. Istotnie:
L
+
+
+
=
+
+
+
1
1
)
(
1
)
(
0
)
(
m
m
p
m
m
p
m
m
m
h
a
h
a
a
h
F
L
+
+
+
=
+
+
+
+
+
+
+
2
1
)
1
(
2
)
1
(
1
0
1
)
(
m
m
p
m
m
p
m
m
m
h
a
h
a
a
h
F
1
)
(
)
(
)
(
)
(
1
1
1
−
−
+
=
−
−
+
m
p
m
m
m
m
q
h
F
h
q
F
h
q
F
h
F
=
=
+
L
+
+
+
+
+
−
+
−
1
1
)
(
1
)
(
0
m
m
m
m
p
p
m
m
p
p
m
m
h
q
a
h
q
a
a
[
] [
]
1
1
1
1
)
(
1
)
(
0
)
(
1
)
(
0
−
+
+
+
−
+
+
+
+
+
+
+
+
−
+
−
m
m
m
m
m
m
m
p
p
m
m
p
m
m
p
p
m
m
p
p
m
m
q
h
a
h
a
a
h
q
a
h
q
a
a
L
L
=
=
L
4
4
4
4
3
4
4
4
4
2
1
4
4 3
4
4 2
1
+
⎥
⎦
⎤
⎢
⎣
⎡
−
−
+
+
⎥
⎦
⎤
⎢
⎣
⎡
−
−
+
+
+
+
+
+
+
=
−
−
+
=
−
−
1
)
1
(
1
1
1
1
1
1
1
)
(
1
0
)
(
0
m
m
m
m
m
m
m
m
m
m
p
a
p
p
p
m
m
p
p
p
p
m
m
h
q
q
q
a
h
q
q
q
a
a
=
=
☻
L
+
+
+
+
+
+
+
+
+
2
1
)
1
(
2
)
1
(
1
0
m
m
p
m
m
p
m
m
h
a
h
a
a
3