Metody numeryczne – laboratorium 4

1. Aproksymacja, interpolacja

Celem aproksymacji jest znalezienie zależności funkcyjnej F ( x ), w przybliżeniu pokrywającej się z pewną funkcją f ( x ) , określoną w postaci ciągu punktów. Punkty te mogą pochodzić z pomiarów, albo mogą być wynikami innych obliczeń.

Interpolacja – metoda numeryczna polegająca na wyznaczaniu w danym przedziale tzw.

funkcji interpolacyjnej, która przyjmuje w nim z góry zadane wartości w ustalonych punktach, nazywanych węzłami. Stosowana jest ona często w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych do określenia zależności między wielkościami oraz w celu uproszczenia skomplikowanych funkcji, np. podczas całkowania numerycznego. Interpolacja jest szczególnym przypadkiem metod numerycznych typu aproksymacja.

1.1. Wzór interpolacyjny Lagrange'a

Jedną z najpopularniejszych i najprostszych metod interpolacyjnych jest metoda Lagrange'a. Jest to metoda, która zawsze pozwala nam na znalezienie jednoznacznie określonej funkcji interpolującej będącej wielomianem.

Mając dane n+1 węzłów wraz z ich wartościami, szukamy wielomianu Wn(x) stopnia co najwyżej n, który przyjmuje zadane wartości dla zadanych węzłów.

Oznaczając przez

ω( x) = ( x − x )( x − x )K( x − x ) (1)

0

1

n

Wzór interpolacyjny Langrange'a możemy zapisać jako:

n

( x − x )( x − x )L( x − x )( x − x )L( x − x ) W ( x) = ∑ f ( x )

0

1

k −1

k +1

n

n

k

(2)

L

L

=

−

−

−

−

−

k 0

( x

x )( x

x )

( x

x

)( x

x

) ( x

x )

k

0

k

1

k

k −1

k

k +1

k

n

n

ω( x)

W ( x) = ∑ f ( x )

n

k

(3)

=

−

ω

k 0

( x x ) '( x )

k

k

Obie zapisane powyżej postacie wzoru Lagrange'a są równoważne, stosujemy je jednak w różnych przypadkach.

Błąd metody Lagrange'a obliczamy za pomocą wzorów:

R ( )

M

x

n 1

+

≤

ω

( x)

(4)

n

(

+

n + )

n 1

1 !

gdzie

( n 1

+ )

M

= max f

( x)

n 1

+

(5)

x ≤ x≤ x

0

n

Przykład 1.:

Mając dane węzły 0, 1, 3, 8 wraz z wartościami 2, 6, -1, 8 obliczamy wielomian interpolacyjny:

1.2. Iteracyjna metoda Aitkena

Istnieje metoda obliczania wartości wielomianu Lagrange'a w zadanym punkcie, bez obliczania samego wielomianu interpolacyjnego. Służy do tego iteracyjna metoda Aitkena.

Oznaczmy przez Wi,j wielomian który w węzłach xi , xj (i≠j) przyjmuje wartości f(xj), f(xi):

y

x − x

i

i

y

x − x

j

j

(6)

Wi, j =

x − x

j

i

W ( x)

x − x

ij

j

W ( x)

x − x

(7)

W ( x)

ik

k

=

ijk

x − x

k

j

Co można uogólnić jako:

W

x − x

,

1 2,..., k − ,

1 k

k

W

x − x

,

1 2,..., − ,

1

(8)

W

( x)

k

m

m

=

,

1 2,..., k , m

x − x

m

k

Aby obliczyć wartość wielomianu interpolacyjnego opartego na n węzłach w dowolnym punkcie a różnym od węzłów, należy obliczyć wartość W1,2,…,n. Wszystkie wyniki niezbędnych obliczeń wygodnie jest umieścić w macierzy trójkątnej wraz z węzłami oraz ich wartościami (schemat taki nazywamy schematem Aitkena). Rozwiązanie takie jest dogodne zarówno podczas rachunków ręcznych, jak i maszynowych, gdyż podczas obliczania każdej wartości zawsze korzystamy z wartości położonych na lewo w tym samym rzędzie i powyższych.

Kolejność obliczania wielomianów w schemacie Aitkena:

 x

y



 1

1



 x

y

W

2

2

,

1 2



 x

y

W

W



(9)

 3

3

,

1 3

,

1 2,3



K K

K

K







 x

y

W

W

W

n

n

,

1 n

,

1 2, n

,

1 2,..., n 

Przykład 2.:

Wykorzystując wartości wraz z węzłami z przykładu 1., obliczymy wartość tej funkcji dla argumentu x = 4:

Układamy odpowiednią macierz obliczając kolejno:

,

,

,

,

,

Stąd

co jest wartością funkcji Lagrange'a w punkcie

1.3. Wzór interpolacyjny Newtona dla nierównych odstępów argumentu Kolejną metodą wyprowadzania wielomianu interpolacyjnego jest metoda Newtona.

Wielomian utworzony za jej pomocą, jest tożsamy z wielomianem Lagrange'a.

Wprowadźmy pojęcie ilorazu różnicowego. Wyrażenie:

f ( x ; x

;K, x

)− f ( x ; x ;K, x

)

f ( x ; x ;K, x

)

i +1

i+2

i + n

i

i+1

i+ n

=

−1

i

i+1

i+ n

(10)

x

− x

i + n

i

nazywamy ilorazem różnicowym rzędu n.

Podczas dalszych obliczeń, niezbędne staną się wartości kolejnych ilorazów różnicowych: f(x1;x2), f(x1;x2,x3), …, f(x1;x2;…;xn)

Aby je obliczyć, wygodnie jest utworzyć następującą tabelkę:

 x

y



 0

0

x

y

f ( x ; x )



 1

1

1

2



 x

y

f ( x ; x )

f ( x ; x ; x )



(11)

 2

2

1

3

1

2

3



K K

K

K



 x

y

f ( x ; x )

f ( x ; x ; x ) K

f ( x ; x ;K; x )

n

n

1

n

1

2

n

1

2

n 

Tak jak poprzednio, przyjmując oznaczenie

ω( x) = ( x − x )( x − x )L( x − x ) (11)

0

1

n

wielomian interpolacyjny który przyjmuje postać:

W ( x) = f ( x ) + f ( x ; x )ω ( x) + f ( x ; x ; x )ω ( x) + K + f ( x ; x ;K; x )ω

( x)

(12)

n

0

0

1

0

0

1

2

1

0

1

n

n 1

−

jest nazywany wzorem interpolacyjnym Newtona z ilorazami różnicowymi. Błąd podczas stosowania powyższej metody jest identyczny jak ten w przypadku interpolacji Lagrange'a.

2. Aproksymacja w Octave (Matlab)

Uzyskiwanie wielomianu aproksymacyjnego:

w1 = polyfit(x0, y0, N)

x0, y0 – współrzędne punktów,

N – zadany stopień wielomianu,

Wynikiem wywołania tej funkcji są współczynniki wielomianu.

Obliczanie wartości wielomianu:

f1 = polyval(w1, x)

w1 – obliczony wielomian,

x – zadany wektor argumentów.

Wynikiem wywołania są wartości wielomianu w1 dla argumentu x.

Przykład 3.:

x0 = [ 0 2 3 4] ;

y0 = [ -1 0 3 8] ;

x=-2:0.1:5

hold on;

plot(x0,y0,'g*');

%aproksymacja wielomianem 2 stopnia

w2=polyfit(x0,y0,2);

f2=polyval(w2,x);

plot(x,f2,'r')

%aproksymacja wielomianem 3 stopnia

w3=polyfit(x0,y0,3);

f3=polyval(w3,x);

plot(x,f3,'b');

hold off;

3. Ćwiczenia

3.1. Utwórz skrypt main.m, w którym zdefiniuj współrzędne punktów: x0 = [1 2 4 6 8 10];

y0 = [6 6 4 2 0 0];

3.2. Narysuj te punkty na wykresie używając np. *

3.3. Wyznacz wbudowanymi funkcjami wielomiany aproksymacyjne 2 i 3 stopnia oraz narysuj na tym samym wykresie ich funkcje wielomianowe.

3.4. Napisz funkcję

function [y] = f_lagrange(x0,y0, x)

która będzie implementacją interpolacji Lagrange’a (wzór 2, 3) gdzie:

x0, y0 – współrzędne punktów,

x – wektor argumentów, dla którego funkcja będzie poszukiwać rozwiązań, y – wektor wartości wielomianu dla x.

3.5. W pliku main.m wywołaj funkcję oraz narysuj ją na tym samym wykresie co poprzednie.

3.6. Napisz funkcję

function [y] = f_aitken(x0,y0, x)

która będzie implementacją iteracyjnej metody Aitkena (wzór 6 - 8) gdzie:

x0, y0 – współrzędne punktów,

x – wektor argumentów, dla którego funkcja będzie poszukiwać rozwiązań, y – wektor wartości wielomianu dla x.

3.7. W pliku main.m wywołaj funkcję oraz narysuj ją na tym samym wykresie co poprzednie odróżniającymi symbolami.

3.8. Napisz funkcję

function [y] = f_newton(x0,y0, x)

która będzie implementacją iteracyjnej metody Newtona dla nierównych odstępów argumentu (wzór 10 – 12)

gdzie:

x0, y0 – współrzędne punktów,

x – wektor argumentów, dla którego funkcja będzie poszukiwać rozwiązań, y – wektor wartości wielomianu dla x.

3.9. W pliku main.m wywołaj funkcję oraz narysuj ją na tym samym wykresie co poprzednie odróżniającymi symbolami.

3.10. Dla zaawansowanych:

Zaproponuj zastosowanie funkcji interp1.