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
Document Outline
Wyszukiwarka
Podobne podstrony:
geometria i garsc dowodow id 18 Nieznany
kilka modeli id 234791 Nieznany
Abolicja podatkowa id 50334 Nieznany (2)
4 LIDER MENEDZER id 37733 Nieznany (2)
katechezy MB id 233498 Nieznany
metro sciaga id 296943 Nieznany
perf id 354744 Nieznany
interbase id 92028 Nieznany
Mbaku id 289860 Nieznany
Probiotyki antybiotyki id 66316 Nieznany
miedziowanie cz 2 id 113259 Nieznany
LTC1729 id 273494 Nieznany
D11B7AOver0400 id 130434 Nieznany
analiza ryzyka bio id 61320 Nieznany
pedagogika ogolna id 353595 Nieznany
Misc3 id 302777 Nieznany
cw med 5 id 122239 Nieznany
więcej podobnych podstron