Interpolacja.pdf

(83 KB) Pobierz
Interpolacja
Zakładamy,
że
mamy dane
n+1
punktów:
x
0
, x
1
,…,x
n
oraz wartości pewnej funkcji
f
w tych
punktach:
y
0
=f(x
0
), y
1
= f(x
1
),…, y
n
= f(x
n
).
Punkty
x
0
, x
1
,…, x
n
nazywamy węzłami interpolacji.
Zadaniem interpolacji jest wyznaczenie przybliżonych wartości funkcji
f
w punktach nie
będących węzłami interpolacji. W tym celu należy znaleźć funkcję
F(x),
która w węzłach
interpolacji przyjmie takie same wartości, jak funkcja
f(x)[1].
Funkcja interpolująca
F
może
przyjmować różne postaci: funkcji liniowych, wielomianu, funkcji trygonometrycznych, czy
funkcji sklejanych. Rysunek 1 przedstawia ideę interpolacji.
Rys. 1.
Idea interpolacji
[1].
Interpolacja Lagrange’a
Zadanie interpolacji Lagrange’a polega na znalezieniu dla danej funkcji
f
wielomianu
L
n
stopnia nie większego niż
n,
którego wartości w
n+1
punktach
x
0
, x
1
, …, x
n
są takie same jak
wartości interpolowanej funkcji, tzn.:
L
n
(x
j
)=f(x
j
),
dla
j = 0, 1, …, n,
przy czym
x
i
≠
x
j
dla
i
≠
j.
Zadanie interpolacji Lagrange’a ma jednoznaczne rozwiązanie, dane wzorem [2]:
L
n
(
x
)
=
∑
f
(
x
j
)
l
j
(
x
)
=
∑
f
(
x
j
)
∏
j
=
0
j
=
0
i
=
0
i
≠
j
n
n
n
x
−
x
i
.
x
j
−
x
i
Pseudokod programu rozwiązującego zadanie interpolacji Lagrange’a jest następujący:
Start
Wczytaj A – tablicę węzłów
Wczytaj W – tablicę wartości w węzłach
Wczytaj x – dany punkt
Dla j=0,1,…,n-1
Dla i=0,1,…,n-1
Jeżeli i!=j
w1=w1*(x-A[i])
w2=w2*(A[j]-A[i])
s+=W[j]*w1/w2
w1=1;
w2=1;
Koniec
Interpolacja Hermite’a
Zakładamy,
że
dane jest
k+1
węzłów interpolacji
x
0
, x
1
, …, x
k
oraz liczby naturalne
m
0
, m
1
, …, m
k
k
takie,
że
∑
m
i
=
0
i
=
n
+
1
. Dla danej funkcji
f
należy znaleźć wielomian
H
n
stopnia nie większego niż
n,
dla którego:
H
n(j)
(x
i
) = f
(j)
(x
i
),
dla
i = 0, 1, …, k, j = 0, 1, …, m
i
– 1.
Wielomian interpolacyjny jest w tym przypadku postaci:
H
n
(
x
)
=
∑
a
i
∏
(
x
−
x
j
)
.
n
i
=
0
j
=
0
i
−
1
Współczynniki
a
i
wielomianu interpolacyjnego obliczamy według następującego algorytmu:
1. Tworzymy tabelę o ilości wierszy równej n+1.
2. W pierwszej kolumnie wpisujemy węzły interpolacji. Każdy węzeł wpisujemy tyle razy, ile
wynosi jego krotność -
m
i
.
3. W kolejnej kolumnie wpisujemy wartości funkcji interpolowanej w poszczególnych węzłach.
4. Kolejne kolumny to odpowiednie różnice dzielone.
Różnice dzielone obliczamy według wzoru:
f
[
x
i
]
=
f
(
x
i
)
f
[
x
i
,...,
x
i
+
j
+
1
]
=
f
[
x
i
+
1
,...,
x
i
+
j
+
1
]
−
f
[
x
i
,...,
x
i
+
j
]
x
i
+
j
+
1
−
x
i
.
5. Współczynniki
a
i
to elementy na przekątnej utworzonej tabeli:
x
0
x
1
f(x
0
)
f(x
1
)
f
[
x
0
,
x
1
]
=
f
[
x
1
,
x
2
]
=
…
f
(
x
1
)
−
f
(
x
0
)
x
1
−
x
0
f
(
x
2
)
−
f
(
x
1
)
x
2
−
x
1
O
x
2
…
f(x
2
)
…
x
n
f(x
n
)
f
[
x
n
−
1
,
x
n
]
=
f
(
x
n
)
−
f
(
x
n
−
1
)
…
x
n
−
x
n
−
1
f
[
x
0
,...,
x
n
]
=
f
[
x
1
,...,
x
n
]
−
f
[
x
0
,...,
x
n
−
1
]
x
n
−
x
0
Przykład:
Znajdź wielomian interpolacyjny Hermite’a wiedząc,
że:
f(2)=1, f ’(2)=2, f ’’(2)=0, f(3)=1, f ’(3)=2.
Rozwiązanie:
Mamy dwa węzły:
x
0
=2, x
1
=3.
Pierwszy węzeł jest trzykrotny:
m
0
=3,
drugi dwukrotny
m
1
=2.
n+1=m
1
+m
2
= 5 => n=4,
więc szukamy wielomianu rzędu 4. Tworzymy tabelę:
x
i
f(x
i
)
f[x
i-1
,x
i
]
f[x
i-2
,x
i-1
,x
i
]
f[x
i-3
,x
i-2
,x
i-1
,x
i
] f[x
i-4
,x
i-3
,x
i-2
,x
i-1
,x
i
]
x
0
f(x
0
)
x
0
f(x
0
) f[x
0
, x
0
] = f ‘ (x
0
)
x
0
f(x
0
) f[x
0
, x
0
] = f ‘ (x
0
) f[x
0
, x
0
,x
0
] = f ‘‘(x
0
)
x
1
f(x
0
) f[x
0
, x
1
]
f[x
0
, x
0
,x
1
]
f[x
0
, x
0
,x
0
,x
1
]
x
1
f(x
0
) f[x
1
, x
1
] = f ‘ (x
1
) f[x
0
, x
1
,x
1
]
Czyli:
f[x
0
, x
0
,x
1
,x
1
]
f[x
0
, x
0
,x
0
,x
1
,x
1
]
x
i
f(x
i
) f[x
i-1
,x
i
] f[x
i-2
,x
i-1
,x
i
] f[x
i-3
,x
i-2
,x
i-1
,x
i
] f[x
i-4
,x
i-3
,x
i-2
,x
i-1
,x
i
]
2
2
2
3
3
1
1
1
1
1
2
2
0
2
0
-2
2
-2
4
6
Zatem wielomian interpolacyjny Hermite’a to:
H
n
(x)=1+2(x-2)+0(x-2)
2
-2(x-2)
3
+6(x-2)
3
(x-3).
Sprawdzenie:
H
n
(2)=1, H
n
(3)=1,
H’
n
(x)=2-6(x-2)
2
+18(x-2)
2
(x-3)+6(x-2)
3
,
H’
n
(2)=2, H’
n
(3)=2,
H’’
n
(x)=-12(x-2)+36(x-2)(x-3)+18(x-2)
2
+18(x-2)
2
,
H’’
n
(2)=0.
1.
Fortuna Z., Macukow B., Wąsowski J.
Metody Numeryczne.
Warszawa : Wydawnictwa Naukowo
Techniczne, 1993.
2.
Jankowscy, Janina i Michał.
Przegląd metod i algorytmów numerycznych, cz.1.
Warszawa :
Wydawnictwa Naukowo-Techniczne, 1981.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin