Metody numeryczne
Interpolacja, cz˛e´s´c I
Janusz Szwabi´nski
szwabin@ift.uni.wroc.pl
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.1/55
Literatura (uzupełnienie)
1. K. A. Ross, Ch. R. B. Wright, “Matematyka dyskretna”
2. P. Wróblewski, “Algorytmy, struktury danych i techniki
programowania”
3. Z. Fortuna, B. Macukow, J. W ˛
asowski, “Metody
numeryczne”
4. G. M. Fichtenholz, “Rachunek ró˙zniczkowy i całkowy”
5. A. Mostowski, M. Stark, “Elementy algebry wy˙zszej”
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.2/55
Interpolacja, cz˛e´s´c I
1. Zagadnienie interpolacyjne
2. Interpolacja wielomianowa
Wzór interpolacyjny Lagrange’a
Metoda Aitkena
Metoda Neville’a
Oszacowanie bł˛edu wzoru interpolacyjnego
Wzór interpolacyjny Newtona
Zbie˙zno´s´c procesów interpolacyjnych
3. Interpolacja wymierna
Sformułowanie zagadnienia
Odwrotno´sci ilorazów ró˙znicowych
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.3/55
Zagadnienie interpolacyjne (1)
-
w˛ezły interpolacji
-
warto´sci funkcji interpolowanej
-
funkcja interpoluj ˛
aca
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.4/55
Zagadnienie interpolacyjne (2)
−1
0
1
x
0
0,5
1
y
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.5/55
Interpolacja wielomianowa (1)
Definicja Wyznacznikiem Vandermonde’a stopnia
nazywa si˛e
wyznacznik
..
.
Twierdzenie 1
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.6/55
Interpolacja wielomianowa (2)
Definicja Układ
równa ´n liniowych o
niewiadomych
..
.
nazywamy układem Cramera, je´sli
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.7/55
Interpolacja wielomianowa (3)
Twierdzenie 2 Układ Cramera ma dokładnie jedno
rozwi ˛
azanie:
gdzie macierz
powstaje z macierzy
przez zast ˛
apienie –tej
kolumny przez
,
,
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.8/55
Interpolacja wielomianowa (4)
-
zbiór wielomianów stopnia
Twierdzenie 3 Dla dowolnych
punktów w˛ezłowych
dla
istnieje dokładnie jeden wielomian
taki, ˙ze
interpolacja wielomianowa jest zagadnieniem
jednoznacznym.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.9/55
Interpolacja wielomianowa (5)
Dowód Mamy
punktów w˛ezłowych
. Szukamy
wielomianu interpoluj ˛
acego w postaci
przy czym
St ˛
ad
..
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.10/55
Interpolacja wielomianowa (6)
Dowód (ci ˛
ag dalszy) Macierz tego układu (niewiadomymi s ˛
a
współczynniki
!) ma posta´c
..
.
jest wyznacznikiem Vandermonde’a
Poniewa˙z
dla
,
układ równa´n jest układem Cramera
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.11/55
Interpolacja wielomianowa (7)
Dowód (ci ˛
ag dalszy)
istnieje dokładnie jedno rozwi ˛
azanie
gdzie
s ˛
a kolejnymi dopełnieniami algebraicznymi
elementów
–tej kolumny macierzy
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.12/55
Wzór interpolacyjny Lagrange’a (1)
-
wielomiany stopnia
Poniewa˙z
gdy
,
gdy
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.13/55
Wzór interpolacyjny Lagrange’a (2)
Z warunku
otrzymujemy
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.14/55
Wzór interpolacyjny Lagrange’a (3)
gdzie
Twierdzenie o jednoznaczno´sci
wielomian Lagrange’a jest jedynym wielomianem
interpolacyjnym stopnia
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.15/55
Wzór interpolacyjny Lagrange’a (4)
Przykład Szukamy wielomianu interpolacyjnego, który
przechodzi przez nast˛epuj ˛
ace punkty w˛ezłowe:
-2
1
2
4
3
1
-3
8
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.16/55
Wzór interpolacyjny Lagrange’a (5)
Przykład
FUNCTION LAGRANGE(x,xa,ya) RESULT (wnx)
implicit
none
double precision,dimension(:) :: xa,ya !punkty wezlowe
double precision
:: x,wnx,om,w
integer :: i,j
wnx=0.0
om=1.0
do i=1,size(xa)
om=om*(x-xa(i))
w=1.0
do j=1, size(xa)
if(i .ne. j) w=w*(xa(i)-xa(j))
end do
wnx=wnx+ya(i)/(w*(x-xa(i)))
end do
wnx=wnx*om
END FUNCTION
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.17/55
Metoda Aitkena (1)
-
wielomian stopnia pierwszego
przechodz ˛
acy przez
,
-
wielomian stopnia drugiego przechodz ˛
acy
przez
,
,
-
wielomian stopnia
przechodz ˛
acy
przez
,
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.18/55
Metoda Aitkena (2)
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.19/55
Metoda Aitkena (3)
Schemat Aitkena:
..
.
..
.
..
.
..
.
..
.
..
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.20/55
Metoda Aitkena (4)
Przykład Obliczy´c metod ˛
a Aitkena warto´s´c wielomianu
interpolacyjnego
dla punktu
, je´sli wielomian ten
przechodzi przez nast˛epuj ˛
ace punkty w˛ezłowe:
0
1
3
1
3
2
Schemat Aitkena dla tego zadania ma posta´c:
0
1
1
3
3
2
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.21/55
Metoda Neville’a (1)
-
wielomian stopnia
przechodz ˛
acy
przez
,
Twierdzenie 4 Wielomian
daje si˛e przedstawi´c
wzorem rekurencyjnym
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.22/55
Metoda Neville’a (2)
Dowód Niech
b˛edzie praw ˛
a stron ˛
a powy˙zszego równania.
Poka˙zemy, ˙ze
ma własno´sci wielomianu
.
Widzimy, ˙ze stopie ´n
jest
. Ponadto, zgodnie z definicj ˛
a
wielomianów
i
mamy
a dla
Zatem
rzeczywi´scie ma cechy
, co na mocy
twierdzenia o jednoznaczno´sci ko´nczy dowód.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.23/55
Metoda Neville’a (3)
Schemat Neville’a:
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.24/55
Metoda Neville’a (4)
Przykład Zastosowa´c metod˛e Neville’a do poprzedniego
przykładu:
0
1
3
1
3
2
Schemat Neville’a dla
ma posta´c:
0
1
1
3
3
2
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.25/55
Oszacowanie bł˛edu wzoru interpolacyjnego (1)
Niech
b˛edzie funkcj ˛
a
razy ró˙zniczkowaln ˛
a oraz
Twierdzenie 5
gdzie
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.26/55
Oszacowanie bł˛edu wzoru interpolacyjnego (2)
Twierdzenie 6 (Rolle’a) Niech 1) funkcja b˛edzie okre´slona na
przedziale domkni˛etym
; 2) istnieje pochodna sko´nczona
przynajmniej w przedziale otwartym
; 3) na ko´ncach
przedziału funkcja przyjmuje warto´sci
. Wówczas
mi˛edzy
i
mo˙zna znale´z´c taki punkt
(
), ˙ze
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.27/55
Oszacowanie bł˛edu wzoru interpolacyjnego (3)
Dowód (twierdzenia 5)
Wprowad´zmy funkcj˛e pomocnicz ˛
a (
- pewna stała)
Współczynnik
dobieramy tak, aby pierwiastkiem funkcji
był równie˙z punkt
, ró˙zny od w˛ezłów interpolacji. St ˛
ad
Mianownik w ostatnim wzorze jest ró˙zny od zera dla wszystkich
(
).
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.28/55
Oszacowanie bł˛edu wzoru interpolacyjnego (4)
Dowód (ci ˛
ag dalszy)
ma w sumie
miejsc zerowych
,
,
,
,
.
Twierdzenia Rolle’a
ma w ka˙zdym z podprzedziałów poło˙zonych mi˛edzy
pierwiastkami co najmniej jedno miejsce zerowe
w przedziale
jest co najmniej
miejsc zerowych
co najmniej
miejsc zerowych drugiej pochodnej
..
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.29/55
Oszacowanie bł˛edu wzoru interpolacyjnego (5)
Dowód (ci ˛
ag dalszy)
istnieje co najmniej jeden punkt
w przedziale
taki, ˙ze
Poniewa˙z
wi˛ec
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.30/55
Oszacowanie bł˛edu wzoru interpolacyjnego (6)
Dowód (ci ˛
ag dalszy)
St ˛
ad wynika
zatem
gdzie
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.31/55
Oszacowanie bł˛edu wzoru interpolacyjnego (7)
Przykład Niech
. Załó˙zmy, ˙ze znamy warto´sci
dokładne naszej funkcji w punktach
Wówczas
St ˛
ad np. dla
mamy
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.32/55
Wzór interpolacyjny Newtona
Metody Aitkena i Neville’a:
wyznaczanie warto´sci wielomianu interpolacyjnego w danym
punkcie
niepraktyczne, je´sli punktów jest du˙zo
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.33/55
Ilorazy ró˙znicowe (1)
Definicja Ilorazami ró˙znicowymi pierwszego rz˛edu nazywamy
wyra˙zenia
..
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.34/55
Ilorazy ró˙znicowe (2)
Definicja Ilorazami ró˙znicowymi drugiego rz˛edu nazywamy
wyra˙zenia
..
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.35/55
Ilorazy ró˙znicowe (3)
Definicja Ilorazem ró˙znicowym rz˛edu
nazywamy
dla
oraz
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.36/55
Ilorazy ró˙znicowe (4)
Ilorazy ró˙znicowe
rz˛edu 1
rz˛edu 2
rz˛edu 3
rz˛edu 4
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.37/55
Wzór Newtona (1)
Twierdzenie 7
przy czym
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.38/55
Wzór Newtona (2)
Dowód Dla
mamy
zatem twierdzenie jest prawdziwe. Załó˙zmy teraz, ˙ze jest ono
prawdziwe dla pewnego
. Aby pokaza´c prawdziwo´s´c
dla
zauwa˙zmy najpierw, ˙ze ró˙znica
jest
wielomianem, który mo˙zna przedstawi´c w postaci
gdzie
jest najwy˙zszym współczynnikiem (czyli
współczynnikiem przy najwy˙zszej pot˛edze ) wielomianu
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.39/55
Wzór Newtona (3)
Dowód (ci ˛
ag dalszy)
Według zało˙zenia indukcyjnego, najwy˙zszymi współczynnikami
wielomianów
oraz
s ˛
a odpowiednio
i
. Ze wzoru Neville’a wynika
zatem
Na mocy zasady indukcji matematycznej twierdzenie jest wi˛ec
udowodnione.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.40/55
Wzór Newtona (4)
Przykład Szukamy wielomianu interpolacyjnego dla funkcji
okre´slonej tablic ˛
a warto´sci:
0
2
3
4
6
1
3
2
5
7
Tworzymy tablic˛e ilorazów ró˙znicowych dla tej funkcji:
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.41/55
Wzór Newtona (5)
Przykład (ci ˛
ag dalszy)
0
1
1
2
3
-1
3
2
2
3
4
5
1
6
7
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.42/55
Wzór Newtona (6)
Przykład (ci ˛
ag dalszy)
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.43/55
Zbie˙zno´s´c procesów interpolacyjnych (1)
Definicja Mówimy, ˙ze metoda interpolacyjna jest zbie˙zna do
funkcji
w punkcie
, gdy
gdzie
to funkcja interpoluj ˛
aca (niekoniecznie wielomian).
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.44/55
Zbie˙zno´s´c procesów interpolacyjnych (2)
−1
0
1
x
0
0,5
1
y
y=|x|
W
2
(x)
W
4
(x)
W
6
(x)
W
10
(x)
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.45/55
Interpolacja wymierna (1)
Mamy
punktów w˛ezłowych
Warto´s´c funkcji
przybli˙zamy funkcj ˛
a wymiern ˛
a
spełniaj ˛
ac ˛
a warunek
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.46/55
Interpolacja wymierna (2)
Uwaga, pułapka!
Z
mo˙zna wnioskowa´c, ˙ze
okre´sla współczynniki
,
.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.47/55
Interpolacja wymierna (3)
Przykład Niech
oraz
0
1
2
1
2
2
Zakładaj ˛
ac, ˙ze
jest parametrem, oraz ˙ze
, otrzymamy
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.48/55
Interpolacja wymierna (4)
Przykład (ci ˛
ag dalszy)
czyli
Dla
mamy
, a po uproszczeniu otrzymujemy
A zatem funkcja
nie rozwi ˛
azuje zadania interpolacji.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.49/55
Odwrotno´sci ró˙znic ilorazowych (1)
Definicja Odwrotno´sciami ilorazów ró˙znicowych nazywamy
wielko´sci
przy czym niektóre z nich mog ˛
a by´c niesko´nczone ze wzgl˛edu
na zerowanie si˛e mianowników.
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.50/55
Odwrotno´sci ró˙znic ilorazowych (2)
Spełniona jest nast˛epuj ˛
aca własno´s´c:
St ˛
ad wynika
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.51/55
Odwrotno´sci ró˙znic ilorazowych (3)
a zatem
co prowadzi do
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.52/55
Odwrotno´sci ró˙znic ilorazowych (4)
Ostatecznie, dla naszego wyra˙zenia wymiernego otrzymujemy
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.53/55
Odwrotno´sci ró˙znic ilorazowych (5)
mo˙zna wi˛ec przedstawi´c w postaci nast˛epuj ˛
acego
ułamka ła´ncuchowego:
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.54/55
Odwrotno´sci ró˙znic ilorazowych (6)
Przykład Mamy dan ˛
a tabel˛e odwrotno´sci ilorazów
ró˙znicowych:
0
0
1
-1
2
-3
3
9
nm_slides-2.tex – Metody numeryczne – Janusz Szwabi ´nski – 8/10/2002 – 22:40 – p.55/55
Document Outline
- small Literatura (uzupe³nienie)
- small Interpolacja, czêœæ I
- small Zagadnienie interpolacyjne (1)
- small Zagadnienie interpolacyjne (2)
- small Interpolacja wielomianowa (1)
- small Interpolacja wielomianowa (2)
- small Interpolacja wielomianowa (3)
- small Interpolacja wielomianowa (4)
- small Interpolacja wielomianowa (5)
- small Interpolacja wielomianowa (6)
- small Interpolacja wielomianowa (7)
- small Wzór interpolacyjny Lagrange'a (1)
- small Wzór interpolacyjny Lagrange'a (2)
- small Wzór interpolacyjny Lagrange'a (3)
- small Wzór interpolacyjny Lagrange'a (4)
- small Wzór interpolacyjny Lagrange'a (5)
- small Metoda Aitkena (1)
- small Metoda Aitkena (2)
- small Metoda Aitkena (3)
- small Metoda Aitkena (4)
- small Metoda Neville'a (1)
- small Metoda Neville'a (2)
- small Metoda Neville'a (3)
- small Metoda Neville'a (4)
- small Oszacowanie b³êdu wzoru interpolacyjnego (1)
- small Oszacowanie b³êdu wzoru interpolacyjnego (2)
- small Oszacowanie b³êdu wzoru interpolacyjnego (3)
- small Oszacowanie b³êdu wzoru interpolacyjnego (4)
- small Oszacowanie b³êdu wzoru interpolacyjnego (5)
- small Oszacowanie b³êdu wzoru interpolacyjnego (6)
- small Oszacowanie b³êdu wzoru interpolacyjnego (7)
- small Wzór interpolacyjny Newtona
- small Ilorazy ró¿nicowe (1)
- small Ilorazy ró¿nicowe (2)
- small Ilorazy ró¿nicowe (3)
- small Ilorazy ró¿nicowe (4)
- small Wzór Newtona (1)
- small Wzór Newtona (2)
- small Wzór Newtona (3)
- small Wzór Newtona (4)
- small Wzór Newtona (5)
- small Wzór Newtona (6)
- small Zbie¿noœæ procesów interpolacyjnych (1)
- small Zbie¿noœæ procesów interpolacyjnych (2)
- small Interpolacja wymierna (1)
- small Interpolacja wymierna (2)
- small Interpolacja wymierna (3)
- small Interpolacja wymierna (4)
- small Odwrotnoœci ró¿nic ilorazowych (1)
- small Odwrotnoœci ró¿nic ilorazowych (2)
- small Odwrotnoœci ró¿nic ilorazowych (3)
- small Odwrotnoœci ró¿nic ilorazowych (4)
- small Odwrotnoœci ró¿nic ilorazowych (5)
- small Odwrotnoœci ró¿nic ilorazowych (6)
Wyszukiwarka
Podobne podstrony:
met num rown rozniczkowe wyklad
Wykład 2a
Met num cz1, METODY NUMERYCZNE W ELEKTROTECHNICE
MET-NUM Lab1 mathcad
met num wejs2
MMK MNU, gik, gik, I sem, mat stos i met numer, wyklad
wykład 2a
wykład 2a (3 ) IIIr wymagania stawiane ściekom oczyszczonym 20010
met num dla inform (2)
wykład 2a (3 ) -IIIr, wymagania stawiane ściekom oczyszczonym 20010
Macierze - teoria, Politechnika Radomska, 1 stopień, przed 5 semestrem, metody numeryczne, Wysyłka M
Wykład 8 (2a), szkoła, Projektowanie Aplikacji Internetowych
SSF do wykładu 2a
Zadanie 2 Met Num TM 2010, Politechnika Radomska, 1 stopień, przed 5 semestrem, metody numeryczne,
Ekonomia Wykład 2a, Transport ZUT, rok 1, Ekonomia
więcej podobnych podstron