|
Nie obrażaj więc mojej inteligencji poprzez czynione na pokaz zaniżanie własnej.
Z2007/8
str 1 W3 Interpolacja Sformułowanie zadania interpolacyjnego Danych jest n+1 róŜnych punktów x 0 , x 1 , ... , x n z przedziału [a,b], które nazywamy w ę złami interpolacji , oraz wartości pewnej funkcji y = f(x) w tych punktach y 0 = f(x 0 ) , y 1 = f(x 1 ) , .... , y n = f(x n ). Zadanie interpolacji polega na znalezieniu funkcji F, zwanej funkcj ą interpoluj ą c ą, która w węzłach x i , i = 0, 1, ... ,n , pokrywa się z funkcją f F(x i ) = f(x i ) dla i = 0, 1, ... , n . RozwaŜamy zadanie interpolacji liniowej , tj. zadanie w którym funkcja interpolująca przedstawiana jest w postaci kombinacji liniowej n ∑ = F ( ) = a j × f j ( ) j 0 gdzie f j , j = 0,1, ... ,n są funkcjami określonymi na przedziale [a,b]. Poszukiwanymi są tutaj współczynniki kombinacji liniowej a j , j = 0, 1, ... ,n. Pytania o istnienie i jednoznaczność funkcji interpolującej sprowadzają się do tego, czy układ równań liniowych n ∑ = ( ) dla i = 0,1, .... , n (*) a j × f j x i = y i j 0 ma rozwiązanie oraz, czy to rozwiązanie jest jedyne. ( ) f 0 x 1 ( ) ( ) f 0 x 0 f 1 x 0 . . f n x 0 ( ) ( ) ( ) f 1 x 1 . . f n x 1 Oznaczymy A = . f 0 x n . f 1 x n . . . . . f n x n ( ) ( ) ( ) Odpowiedź na powyŜsze pytania zaleŜy od wyznacznika macierzy A. JeŜeli det A , to układ (*) ( ) ¹ 0 ma jednoznaczne rozwiązanie. Znalezienie tego rozwiązania daje funkcję interpolującą. Interpolacja Lagrange'a Zadanie intepolacyjne Lagrange'a polega na znalezieniu wielomianu L n , stopnia nie wyŜszego niŜ n, spełniającego warunki interpolacji L n (x i ) = f(x i ) dla i = 0,1, ... ,n . Wielomian L n nazywamy wielomianem interpolacyjnym Lagrange'a funkcji f opartym na w ę złach x 0 , x 1 , ... , x n . str 2 W3 Z2007/8 TWIERDZENIE . Zadanie interpolacyjne Lagrange'a na jednoznaczne rozwiązanie. Wielomian interpolacyjny L n moŜna przedstawić w postaci n ∑ = L n , ( ) = a j × f j ( ) j 0 gdzie układ funkcji f 0 , f 1 , ... , f n stanowi bazę przestrzeni W n (przestrzeni wielomianów stopnia nie wyŜszego niŜ n). Rozpatrzymy (a) bazę naturalną : 1, x , x 2 , ... , x n j - 1 = ( ) (b) bazę wielomianów Newtona : p 0 ( ) , p j ( ) , j = 1, ... , n = 1 = x - x k k 0 W przypadku (a) mamy do czynienia z postaci ą naturaln ą wielomianu interpolacyjnego n ∑ = x j L n ( ) = a j × j 0 W przypadku (b) współczynniki a 0 = y 0 oraz a j = f 0,1, ... ,j , j = 1, ... ,n są ilorazami ró Ŝ nicowymi określonymi poniŜej. WyraŜenia y 1 - y 0 y n - y n - 1 f 0 1 , . . . . , f n = = , - 1 , n x 1 - x 0 x n - x n - 1 nazywamy ilorazami ró Ŝ nicowymi 1 -go rz ę du . Analogicznie definiujemy ilorazy ró Ŝ nicowe 2 -go rz ę du f 1 2 - f 0 1 f n - f n 2 , , - 1 , n - , n - 1 f 0 1 , . . . . f n = = , , 2 - 2 , n 1 - , n x 2 - x 0 x n - x n 2 - Ogólnie iloraz ró Ŝ nicowy rz ę du k tworzymy z ilorazów róŜnicowych rzędu k-1 za pomoca wzoru rekurencyjnego f i - f i .... + 1 , .... , i + k , , i + k - 1 f i i = , + 1 , .... , i + k x i - x i + k Wobec tego L n (x) = y 0 + f 0, 1 p 1 (x) + f 0, 1, 2 p 2 (x) + .... + f 0,1, ... , n p n (x) Jest to tzw. posta ć Newtona wielomianu interpolacyjnego. Z2007/8 str 3 W3 ( ) Dla n =1 (2 węzły) L 1 ( ) = y 0 + f 0 1 × x - x 0 , ( ) ( ) ( ) Dla n =2 (3 węzły) L 2 ( ) = y 0 + f 0 1 × x - x 0 + f 0 1 × x - x 0 × x - x 1 , , , 2 Algorytm obliczania n-tego ilorazu róŜnicowego moŜna zapisać w postaci tablicy trójkątnej x 0 x 1 x 2 . . x n y 0 y 1 y 2 . . y n f 0 1 , f 1 2 f 0 1 , , , 2 . . f n 2 . . . . . . . . . f n 3 . - x n 1 - y n 1 - , n - 1 - , n - 2 , n - 1 f n f n . . . . f 0 1 - 1 , n - 2 , n - 1 , n , , .. , n W celu oszacowania bł ę du interpolacji moŜemy posłuŜyć się twierdzeniem TWIERDZENIE . JeŜeli funkcja f jest klasy C (n+1) ([a,b]), to dla a £ x £ b M n + 1 ( ) ( ) ( ) f ( ) - L n ( ) £ × x - x 0 × x - x 1 × .... × x - x n ( n + 1 ) ! | f (n+1) (x)|. gdzie M n+1 = max a x £ £ b W sformułowanym zadaniu interpolacyjnym wyznaczamy wielomian w oparciu o dane wartości funkcji f w (n+1) róŜnych węzłach. Powstaje pytanie, czy wielomian ten będzie coraz lepiej przybliŜał funkcję f wraz ze zwiększeniem liczby węzłów ? Oczywiście, większa liczba zmierzonych wartości funkcji zawiera w sobie dokładniejszą informację o tej funkcji. W przypadku stosowania wielomianów jako funkcji interpolujących, często występuje zjawisko pogarszania się przybliŜenia przy zwiększaniu się liczby węzłów interpolacyjnych. Dokładniej oznacza to, Ŝe ciąg ( L n ) wielomianów interpolacyjnych nie będzie zbieŜny do funkcji f na przedziale [a,b]. Problemy te nie występują, gdy do interpolacji będziemy stosować funkcje kawałkami "sklejane" z wielomianów niskich stopni. |
Menu
|