Metody Numeryczne, Matematyka Finansowa, rok II, st.I semestr letni 2012/2013
Wykład 3: Algorytm Neville’a. Ilorazy różnicowe. Wzór Newtona dla nierównych odstępów argumentów. I i II wzór Newtona.
Algorytm Neville’a
Algorytm Neville’a służy do wyznaczania wartości wielomianu interpolacyjnego dla pojedynczej wartości x.
Dla danego zbioru punktów węzłowych ( xi, yi), i = 0 , 1 , . . . , n oznaczamy przez Pi 0 i 1 ,...ik wielomian stopnia k o własnościach: Pi ( x ) = y , j = 0 , 1 , . . . , k. Wielomiany tego typu 0 i 1 ,...ik
ij
ij
spełniają następujący związek rekurencyjny:
Twierdzenie 1
Pi( x) = yi
(1)
( x − xi ) Pi
( x) − ( x − xi ) Pi
( x)
P
0
1 ...ik
k
0 ...ik
1
−
i
( x) =
(2)
0 i 1 ,...ik
xi − x
k
i 0
Dowód. Z określenia wielomianu P jasne jest, że Pi( x) = yi.
Oznaczamy
( x − xi ) Pi
( x) − ( x − xi ) Pi
( x)
R( x) =
0
1 ...ik
k
0 ...ik
1
−
.
xi − x
k
i 0
Stopień R nie jest oczywiście większy niż k.
Z definicji Pi
i P
wynika, że
0 ...ik
1
i 1 ...i
−
k
R( xi ) = P
( x )
0
i 0 ...ik 1
i 0
−
R( xi ) = P
( x )
k
i 1 ...ik
ik
( xi − xi ) yi − ( xi − xi ) yi R( x
j
0
j
j
k
j
i ) =
= y ,
j = 1 , . . . , k − 1 .
j
x
ij
i
− x
k
i 0
Z jednoznaczności wielomianu interpolacyjnego wynika, że R = Pi
.
0 i 1 ,...ik
W oparciu o wzory rekurencyjne (1) - (2) konstruujemy tablicę (dla przykładu k = 3): k = 0
k = 1
k = 2
k = 3
x 0
P 0( x) = y 0
P 01( x)
P 012( x)
P 0123( x)
x 1
P 1( x) = y 1
P 12( x)
P 123( x)
x 2
P 2( x) = y 2
P 23( x)
x 3
P 3( x) = y 3
gdzie
( x − x 0) P 1( x) − ( x − x 1) P 0( x) P 01( x) =
x 1 − x 0
( x − x 1) P 2( x) − ( x − x 2) P 1( x) P 12( x) =
x 2 − x 1
1
( x − x 2) P 3( x) − ( x − x 3) P 2( x) P 23( x) =
x 3 − x 2
( x − x 0) P 12( x) − ( x − x 2) P 01( x) P 012( x) =
x 2 − x 0
( x − x 1) P 23( x) − ( x − x 3) P 12( x) P 123( x) =
x 3 − x 1
( x − x 0) P 123( x) − ( x − x 3) P 012( x) P 0123( x) =
x 3 − x 0
Przykład 1 Dana jest tablica wartości funkcji x
1 2
3
4
f(x) 3 1 -1 2
Za pomocą algorytmu Neville’a wyznaczyć wartość wielomianu interpolacyjnego w punkcie x = 1 , 5.
2
Załóżmy, że dla funkcji y = f ( x) dane są punkty węzłowe ( xi, f ( xi)), i = 0 , 1 , . . . , n, przy czym przyjmujemy, że xi 6= xj, i 6= j oraz różnice xi+1 − xi, i = 0 , 1 , . . . , n − 1 nie są na ogół stałe, czyli węzły nie są rozmieszczone w równych odległościach.
Zdefiniujemy pojęcie ilorazu różnicowego:
Definicja 1 Ilorazem różnicowym rzędu zero dla węzła xi nazywamy f [ xi] := f ( xi) , i = 0 , 1 , . . . , n.
Ilorazem różnicowym rzędu pierwszego dla węzłów xi i xi+1 nazywamy f [ x
f [ x
i+1] − f [ xi]
i, xi+1] :=
,
i = 0 , 1 , . . . , n − 1 .
xi+1 − xi
Ogólnie: ilorazem różnicowym rzędu k (k-tym ilorazem różnicowym) dla węzłów xi, xi+1 , . . . , xi+ k nazywamy
f [ x
1]
f [ x
i+1 , xi+2 , . . . , xi+ k ] − f [ xi, xi+1 , . . . , xi+ k−
i, xi+1 , . . . xi+ k] :=
,
i = 0 , 1 , . . . , n − k.
xi+ k − xi
Przykładowa tablica ilorazów różnicowych, gdy znamy cztery węzły jest postaci: xi
f ( xi)
f [ xi, xi+1]
f [ xi, xi+1 , xi+2]
f [ xi, xi+1 , xi+2 , xi+3]
x 0
f [ x 0]
f [ x 0 , x 1]
f [ x 0 , x 1 , x 2]
f [ x 0 , x 1 , x 2 , x 3]
x 1
f [ x 1]
f [ x 1 , x 2]
f [ x 1 , x 2 , x 3]
x 2
f [ x 2]
f [ x 2 , x 3]
x 3
f [ x 3]
Przykład 2 Utworzyć tablicę ilorazów różnicowych dla danych x
1
3 5 6
f(x) -3 1 2 4
3
Twierdzenie 2 Wielomian interpolacyjny dla funkcji f : [ a, b] → R oraz węzłów x 0 , x 1 , . . . , xn można zapisać w postaci
Wn( x) = f [ x 0] + f [ x 0 , x 1]( x − x 0) + f [ x 0 , x 1 , x 2]( x − x 0)( x − x 1) + . . .
+ f [ x 0 , x 1 , . . . , xn]( x − x 0)( x − x 1) . . . ( x − xn 1) (3)
−
Uwaga 1 Wzór ten nosi nazwę wzoru interpolacyjnego Newtona dla nierównych od-stępów argumentów albo wzoru interpolacyjnego Newtona z ilorazami różnicowymi.
Przykład 3 Napisać wzór interpolacyjny Newtona z ilorazami różnicowymi dla funkcji danej tablicą wartości
x
1
3 5 6
f(x) -3 1 2 4
Niech dana będzie funkcja y = f ( x). Oznaczmy przez h stałą wielkość przyrostu argumentu x.
Definicja 2 Wyrażenie
∆ y = ∆ f ( x) = f ( x + h) − f ( x) , nazywamy różnicą skończoną (progresywną) rzędu pierwszego funkcji f .
Różnicę skończoną rzędu n określamy następująco:
∆ ny = ∆(∆ n 1
− y) .
Przykład 4
∆2 y =
4
Załóżmy teraz, że dane są węzły interpolacji x 0 , x 1 , . . . , xn takie, że xi+1 − xi = h,
i = 0 , 1 , . . . , n − 1
czyli
xi = x 0 + ih,
i = 0 , 1 , . . . , n − 1
Niech ponadto znane będą wartości funkcji y = f ( x) w węzłach x 0 , x 1 , . . . , xn, czyli yi = f ( xi), i = 0 , 1 , . . . , n.
Różnice skończone ciągu yi, i = 0 , 1 , . . . , n określa się następująco:
∆ yi = yi+1 − yi
∆ ny
1
1
1
i = ∆(∆ n− yi) = ∆ n− yi+1 − ∆ n− yi Przykładowa pozioma tablica różnic skończonych dla n = 3: xi
yi
∆ yi
∆2 yi
∆3 yi
x 0
y 0
∆ y 0
∆2 y 0
∆3 y 0
x 1
y 1
∆ y 1
∆2 y 1
x 2
y 2
∆ y 2
x 3
y 3
Przykład 5 Sporządzić tablicę różnic skończonych dla funkcji f ( x) = x 3 − 1 dla n = 3 z krokiem h = 1, zaczynając od x 0 = 1.
I i II wzór Newtona
Zauważmy teraz, że w przypadku węzłów interpolacji, dla których xi+1 − xi = h, i = 0 , 1 , . . . , n − 1 ilorazy różnicowe kolejnych rzędów wynoszą odpowiednio: f [ x 0] = y 0
y 1 − y 0
∆ y 0
f [ x 0 , x 1] =
=
x 1 − x 0
h
5
∆ y 1
f [ x 1 , x 2] =
=
x 2 − x 1
h
f [ x
∆ y 1
1 , x 2] − f [ x 0 , x 1]
− ∆ y 0
∆ y 1 − ∆ y 0
∆2 y 0
f [ x
h
h
0 , x 1 , x 2] =
=
=
=
x 2 − x 0
2 h
2 h 2
2! h 2
f [ x
∆ y 2
2 , x 3] − f [ x 1 , x 2]
− ∆ y 1
∆ y 2 − ∆ y 1
∆2 y 1
f [ x
h
h
1 , x 2 , x 3] =
=
=
=
x 3 − x 1
2 h
2 h 2
2! h 2
f [ x
∆2 y 1
1 , x 2 , x 3] − f [ x 0 , x 1 , x 2]
− ∆2 y 0
∆2 y 1 − ∆2 y 0
∆3 y 0
f [ x
2 h 2
2 h 2
0 , x 1 , x 2 , x 3] =
=
=
=
x 3 − x 0
3 h
6 h 3
3! h 3
Ogólnie
∆ ny 0
f [ x 0 , x 1 , . . . , xn] =
.
n! hn
Stąd wzór Newtona z ilorazami różnicowymi przyjmuje postać
∆ y 0
∆2 y 0
∆ ny 0
Wn( x) = y 0 +
( x−x 0)+
( x−x 0)( x−x 1)+ . . . +
( x−x 0)( x−x 1) . . . ( x−x 1) (4) h
2! h 2
n! hn
n−
Oznaczmy
x − x 0
q =
.
h
Wtedy
x − xi
x − ( x
( x − x
x − x
=
0 + ih) =
0) − ih =
0 − i = q − i.
h
h
h
h
Dlatego wzór (4) możemy zapisać
∆ y 0
∆2 y 0
∆ ny 0
Wn( x) = y 0 +
q +
q( q − 1) + . . . +
q( q − 1) . . . ( q − ( n − 1)) (5)
1!
2!
n!
x − x
gdzie
0
q =
h
Jest to tzw. pierwszy wzór Newtona.
Pierwszy wzór Newtona wygodnie stosować do interpolacji funkcji blisko wartości początkowej x 0.
Wzór na oszacowanie błędu interpolacji można przedstawić jako: M
|f ( x) − W
n+1
n( x) | ¬
|q( q − 1) . . . ( q − n) |hn+1
(6)
( n + 1)!
W pobliżu punktu xn stosuje się tzw. drugi wzór Newtona:
∆ y 1
∆2 y 2
∆ ny 0
W
n−
n−
n( x) = yn +
q +
q( q + 1) + . . . +
q( q + 1) . . . ( q + ( n − 1)) (7)
1!
2!
n!
x − x
gdzie q =
n
h
Wzór na oszacowanie błędu interpolacji w tym przypadku jest postaci: M
|f ( x) − W
n+1
n( x) | ¬
|q( q + 1) . . . ( q + n) |hn+1 .
(8)
( n + 1)!
6