Wskaźnik uwarunkowania zadania obliczania wartości wielomianu interpolacyjnego Lagrange’a (zad. P2.9)
Paweł Laskoś
grupa dr Pawła Woźnego, nr indeksu 169827
10 grudnia 2005
1
Wstęp
Celem eksperymentu było sprawdzenie związku między wskaźnikiem n
X
Kn := max
|λi( x) |,
(1)
a¬x¬b i=0
gdzie
n
x − x
Y
j
λi( x) :=
(2)
x
j=0 ,j6= i
i − xj
dla parami różnych węzłów interpolacji x 0 , . . . , xn ∈ [ a, b], oraz dokładnością przybliżenia funkcji za pomocją wielomianu interpolacyjnego Lagrange’a, w zależności od różnego spo-sobu wyboru węzłów. Przyjęto liczbę węzłów n = 10, przedział [ a, b] = [ − 1 , 1], testowe funkcje
1
f 1( x) =
,
(3)
1 + 25 x 2
f 2( x) = arc tg x,
(4)
f 3( x) = max { 0 , 1 − 4 x}.
(5)
2
Opis teoretyczny
Zadanie interpolacji Lagrange’a sformułowane jest następująco (za [1, s. 2-3]): dla danych n ∈ N, parami różnych x 0 , . . . , xn ∈ R i dla danej funkcji f określonej w punktach {xi}
znaleźć wielomian Ln ∈ Π n (stopnia najwyżej n) taki, że Ln( xi) = f ( xi)
(6)
dla każdego węzła interpolacji xi.
Łatwo udowodnić jednoznaczność takiego rozwiązania (różnica dwóch wielomianów interpolacyjnych Ln − L0n jest wielomianem stopnia najwyżej n, o co najmniej n + 1 zerach xi, zatem jest równa 0), ponadto istnieje ono zawsze i jest dane wzorem n
X
Ln( x) =
f ( xi) λi( x) .
(7)
i=0
1
Dla każdej funkcji i jej wielomianu interpolacyjnego zdefiniować można funkcję błędu en := f − Ln,
(8)
i im mniejsze wartości ona osiąga, tym bardziej użyteczny jest wielomian interpolacyjny.
Spróbujmy oszacować jej wartości takim wyrażeniem, którego jeden czynnik będzie zależny tylko od interpolowanej funkcji, drugi zaś – tylko od wyboru węzłów interpolacyjnych.
|
X
en( x) | ¬ |f ( x) | + |Ln( x) | ¬ |f ( x) | +
|f ( xi) ||λi( x) | ¬
(9)
¬ |f ( x) | + max |f ( xi) | X |λi( x) | ¬ max |f ( x) |( Kn + 1) .
(10)
i
a¬x¬b
Współczynnik Kn w pewien sposób ogranicza wartość funkcji błędu, jednak powyższe szacowanie jest na tyle grube, że ograniczenie staje się niewiele warte. Mimo to można spodziewać się pewnej korelacji między wartościami funkcji błędu a wartością współczynnika Kn.
3
Wyniki doświadczenia
Wszystkie poniższe wyliczenia i wykresy zostały wykonane za pomocą programu Maple 9.5, zapisane w załączonym arkuszu inter.mw.
Rozważania przeprowadzono dla trzech wyborów węzłów interpolacyjnych: (a) węzłów równoodległych
2 i + 1
xi :=
− 1 .
(11)
11
(b) węzłów będących zerami jedenastego wielomianu Czebyszewa:
2 i + 1
xi := cos
π .
(12)
22
(c) losowo wybranych węzłów, tu (posortowane rosnąco):
x 0 := − 0 , 7662364125 ,
x 1 := − 0 , 6433701876 ,
x 2 := − 0 , 6018926488 ,
x 3 := − 0 , 3183845433 ,
x 4 := − 0 , 1968105882 ,
x 5 := 0 , 005084617 ,
x 6 := 0 , 258959741 ,
x 7 := 0 , 472901968 ,
x 8 := 0 , 590788603 ,
x 9 := 0 , 650481577 ,
x 10 := 0 , 983797135 .
(13)
Wykresy funkcji Fn( x) := P n
|
i=0 λi( x) | dla poszczególnych przypadków zamieszczone są na końcowych stronach tej pracy. Wartości współczynnika K 10, czyli maksima funkcji F 10
2
na rozważanym przedziale [ − 1 , 1], przyjmowane są na krańcach przedziału (dla losowych węzłów – nie zawsze) i wynoszą
K 10 , ( a) = 385 , 1601562 , K 10 , ( b) = 2 , 489430372 , K 10 , ( c) = 2211 , 667590 .
(14)
Zamieszczono także 9 wykresów funkcji błędu dla wszystkich badanych funkcji i zestawów węzłów interpolacji.
4
Wnioski
Korelacją, jaką zauważyć można między wykresami funkcji Fn( x) a poszczególnych funkcji błędu, jest fakt, że tam, gdzie funkcja Fn( x) przyjmuje wartości względnie duże (czyli dla x 6∈ ( x 1 , x 9) dla węzłów równoodległych, x 6∈ ( x 0 , x 9) dla węzłów losowych), tam również względnie duże wartości przyjmują funkcje błędu. Tam, gdzie Fn( x) przyjmuje wartości względnie małe (czyli dla x ∈ ( x 1 , x 9) dla węzłów równoodległych, x ∈ ( x 0 , x 9) dla węzłów losowych), tam też funkcje błędu mogą być ograniczane znacznie mniejszymi wartościami. Dla węzłów Czebyszewa funkcja Fn( x) przyjmuje na całym przedziale warto-
ści „zrównoważone”, także funkcje błędu dla węzłów Czebyszewowskich nie mają żadnych wyróżniających się ekstremów lokalnych.
Można zauważyć, że dla wyżej wymienionych przedziałów „małej zmienności” funkcji Fn( x) wielomian interpolacyjny przy węzłach równoodległych czy losowych interpoluje zadaną funkcję podobnie dobrze jak przy węzłach Czebyszewa (a przy funkcji f 2 zauwa-
żalnie lepiej). Kryterium współczynnika K 10 faworyzuje węzły Czebyszewa, gdyż dla nich funkcja Fn( x) nie posiada pików, jednak dla konkretnych zastosowań (tj. wykorzystują-
cych wartości funkcji tylko z przedziałów „małej zmienności”) mogą być lepsze inne dobory węzłów.
Wysnute wnioski skojarzyć można z twierdzeniem Rungego ([1, s. 5]), które mówi, że ciąg wielomianów interpolacyjnych funkcji f 1 dla równoodległych węzłów zbieżny jest tylko dla |x| < 0 , 726 . . . . Możnaby się spodziewać, że ciąg Fn( x) dla równoodległych węzłów będzie również zbieżny tylko w tym przedziale.
Literatura
[1] Stanisław Lewanowicz, Interpolacja wielomianowa, notatki do wykładu z analizy nu-merycznej, 20051.
1http://www.ii.uni.wroc.pl/ sle/an-inter.pdf
3
40
30
y
20
10
0
-1
-0,5
0
0,5
1
x
Rysunek 1: Wykres funkcji Fn( x) dla węzłów równoodległych 2,4
2,2
2
1,8
1,6
1,4
1,2
1
-1
-0,5
0
0,5
1
x
Rysunek 2: Wykres funkcji Fn( x) dla węzłów Czebyszewa 4
150
y 100
50
0
-1
-0,5
0
0,5
1
x
Rysunek 3: Wykres funkcji Fn( x) dla węzłów losowych 2
1
0
-1
-0,5
0
0,5
1
-1
-2
Rysunek 4: Wykres funkcji błędu dla f 1 i węzłów równoodległych 5
0,05
0
-1
-0,5
0
0,5
1
-0,05
Rysunek 5: Wykres funkcji błędu dla f 1 i węzłów Czebyszewa 4
2
0
-1
-0,5
0
0,5
1
-2
-4
Rysunek 6: Wykres funkcji błędu dla f 1 i węzłów losowych 6
0,00002
0
-1
-0,5
0
0,5
1
-0,00002
-0,00004
Rysunek 7: Wykres funkcji błędu dla f 2 i węzłów równoodległych 0,000015
0,00001
0,000005
0
-1
-0,5
0
0,5
1
-0,000005
-0,00001
-0,000015
Rysunek 8: Wykres funkcji błędu dla f 2 i węzłów Czebyszewa 7
0,00002
-1
-0,5
0
0,5
1
0
-0,00002
-0,00004
-0,00006
-0,00008
-0,0001
Rysunek 9: Wykres funkcji błędu dla f 2 i węzłów losowych 0,4
0,2
0
-1
-0,5
0
0,5
1
-0,2
-0,4
Rysunek 10: Wykres funkcji błędu dla f 3 i węzłów równoodległych 8
0,04
0,02
-1
-0,5
0
0,5
1
0
-0,02
-0,04
-0,06
-0,08
Rysunek 11: Wykres funkcji błędu dla f 3 i dla węzłów Czebyszewa 3
2
1
0
-1
-0,5
0
0,5
1
-1
Rysunek 12: Wykres funkcji błędu dla f 3 i dla węzłów losowych 9