Metody numeryczne
skrót wykładu
dr inż. Anna Barcz
Zakład Matematyki Stosowanej
kontakt: pokój 28
[e-mail]
konsultacje: środa 12.15 - 14.00
1
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Zagadnienia
Zadanie aproksymacji.
Twierdzenie Weierstrassa.
Aproksymacja ciągła.
Aproksymacja dyskretna.
Wielomiany ortogonalne.
Wielomiany trygonometryczne.
Ekstrapolacja.
2
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji  ZADANIE APROKSYMACJI
Funkcję f(x), znaną lub określoną tablicą wartości, będziemy
aproksymować (zastępować) inną funkcją F(x), zwaną
funkcją aproksymującą lub przybliżeniem funkcji f(x).
Przybliżenie powoduje pojawienie się błędów i problem
oszacowania tych błędów oraz ich wielkość mają istotny
wpływ na wybór metody aproksymacyjnej.
3
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji  ZADANIE APROKSYMACJI
Zadanie aproksymacji:
dla danej funkcji f spośród funkcji ustalonej klasy
poszukujemy takiej funkcji g, która w określonym sensie
najlepiej przybliża f,
wyznaczanie, możliwie niskim kosztem, przybliżenia g
funkcji f z zadaną dokładnością,
wyznaczanie klas funkcji przybliżających inne klasy
funkcji.
4
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji  ZADANIE APROKSYMACJI
Aproksymacja funkcji f(x) polega na wyznaczeniu takich
współczynników a0, a1, ... ,am funkcji
F śąxźą=a0ÔÄ…0śąxźąƒÄ…a1ÔÄ…1śą xźąƒÄ…‹Ä…ƒÄ…amÔÄ…mśą xźą
gdzie sÄ… funkcjami bazowymi m+1 wymiarowej
ÔÄ…0 ,ÔÄ…1 ,‹Ä… ,ÔÄ…m
podprzestrzeni liniowej Xm+1, aby funkcja F(x) spełniała pewne
warunki, np. minimalizowała normę różnicy
f śą xźą-F śą xźą
%" %"
f(x)  pewna funkcja, którą chcemy aproksymować,
X  pewna przestrzeń liniowa unormowana,
Xm  m-wymiarowa podprzestrzeń liniowa przestrzeni X.
5
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji
Jak określić i dobrać współczynniki ak (k=0,1,...,m)?
F śąxźą=a0ÔÄ…0śąxźąƒÄ…a1ÔÄ…1śą xźąƒÄ…‹Ä…ƒÄ…amÔÄ…mśą xźą
Zadanie najlepszej aproksymacji przy wybranych funkcjach
bazowych sprowadza się do znalezienia wartości współczynników
ak takich, aby otrzymać minimum wyrażenia
f śą xźą-śąa0ÔÄ…0śąxźąƒÄ…a1ÔÄ…1śą xźąƒÄ…‹Ä…ƒÄ…amÔÄ…mśą xźąźą
%" %"
i aby istniało jedyne możliwe rozwiązanie tego zagadnienia ze
względu na ak.
6
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa
dla funkcji f(x) określonej na przedziale poszukujemy
minimum całki
b
F śą xźą- f śą xźą = w śąxźą F śą xźą- f śąxźą dx
%" %" [ ]2
+"
a
dla funkcji f(x) danej na dyskretnym zbiorze argumentów
poszukujemy minimum sumy (metoda najmniejszych kwadratów)
n
2
F śą xźą- f śą xźą = w śąxiźą śą xiźą- f śą xiźą
%" %"
"
[F ]
i=0
wśą xiźą‡Ä…0 dla i=0,1 ,‹Ä…,n
7
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja jednostajna
dla funkcji f(x) określonej na przedziale poszukujemy funkcji
F(x) dającej najmniejsze maksimum różnicy między F(x) a f(x) na
całym przedziale
F śą xźą- f śą xźą =sup#"F śą xźą- f śąxźą#"
%" %"
)#a , b*#
8
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Twierdzenia Weierstrassa
Jeżeli funkcja f(x) jest ciągła na skończonym przedziale , to dla
każdego µ dodatniego można dobrać takie n, że jest możliwe
utworzenie wielomianu Pn(x) stopnia n, który spełnia nierówność
#" f śą xźą-Pnśąxźą#""Ä…ÏÄ…
na całym przedziale .
Jeżeli funkcja f(x) jest ciągła na R i okresową o okresie 2Ą, to dla
każdego µ dodatniego istnieje wielomian trygonometryczny
n
Snśą xźą=a0ƒÄ… śąak cos kxƒÄ…bk sin kxźą
"
k=1
spełniający dla wszystkich x nierówność
#" f śą xźą-Snśą xźą#""Ä…ÏÄ…
9
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa
ÔÄ…jśą xźą
Niech , j=0,1,...,m, będzie układem funkcji bazowych
podprzestrzeni Xn.
Poszukujemy wielomianu uogólnionego F(x), będącego najlepszym
przybliżeniem średniokwadratowym funkcji f(x) na zbiorze X=(xj)
m
F śąxźą= ai ÔÄ…iśą xźą
"
i=0
przy czym współczynniki ai są tak określone, aby
n
2
F śą xźą- f śą xźą = w śąxiźą śą xiźą- f śą xiźą Śą min
%" %"
"
[F ]
i=0
10
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa - wielomianowa
baza  ciąg jednomianów xi, i=0,1,...,m
n m
f śą x źą- ai xij xkj=0
" "
j
[ ]
j=0 i=0
zmieniamy kolejność sumowania
n m n
f śą x źą xk= ai xijƒÄ…k
" " "
j j
śą źą
j=0 i=0 j=0
k=0,1 ,‹Ä…,m
11
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa - wielomianowa
m n n
ai xijƒÄ…k = f śą x źą xkj k=0,1 ,‹Ä…,m
" " "
j
śą źą
i=0 j=0 j=0
n n n n
k=0
a0 x0ƒÄ…0ƒÄ…a1 x0ƒÄ…1ƒÄ…‹Ä…ƒÄ…am x0ƒÄ…m= f śą x źą x0
" " " "
j j j j j
j=0 j=0 j=0 j=0
n n n n
a0 x1ƒÄ…0ƒÄ…a1 x1ƒÄ…1ƒÄ…‹Ä…ƒÄ…am x1ƒÄ…m= f śąx źą x1
k=1
" " " "
j j j j j
j=0 j=0 j=0 j=0
‹Ä…
n n n n
{
a0 xmƒÄ…0ƒÄ…a1 xmƒÄ…1ƒÄ…‹Ä…ƒÄ…am xmƒÄ…m= f śą x źą xm
k=m
" " " "
j j j j j
j=0 j=0 j=0 j=0
m+1 równań, m+1 niewiadomych
12
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa - wielomianowa
Jeżeli x0,x1,...,xn są różne i md"n, to wyznacznik jest różny od zera,
a więc układ ma jednoznaczne rozwiązanie.
Jeżeli m = n to aproksymacja = interpolacji.
Jeżeli m = n to aproksymacja = interpolacji.
W praktyce stopień wielomianu jest i powinien być znacznie
mniejszy od liczby punktów, korzystamy wtedy z dużej ilości
informacji uzyskujÄ…c proste (niskiego stopnia) funkcje
aproksymujÄ…ce.
13
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa  wielomiany ortogonalne
Funkcje f(x) i g(x) nazywamy ortogonalnymi na dyskretnym
zbiorze punktów x0,x1,...,xn jeśli
n
f śą xiźą g śąxiźą=0
"
i=0
przy czym
n n
[ f śąxiźą]2ą0 [ g śą xiźą]2ą0
" "
i=0 i=0
14
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa  wielomiany ortogonalne
CiÄ…g funkcyjny
ÔÄ…mśą xźąa"ÔÄ…0śą xźą ,ÔÄ…1śą xźą ,‹Ä…,ÔÄ…mśą xźą ,‹Ä…
nazywamy ortogonalnym na zbiorze punktów x0,x1,...,xn, jeśli
n
ÔÄ… śąxiźąÔÄ…k śą xiźą=0, dla j`"k
"
j
i=0
n
ÔÄ…2śąxiźąą0
"
j
i=0
(nie wszystkie punkty xi sÄ… miejscami zerowymi rozpatrywanych funkcji)
15
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa  wielomiany ortogonalne
mamy n+1 równoodległych punktów xi, xi=x0+ih, i=0,1,...,n
dokonujemy przekształcenia liniowego, które przeprowadzi
punkty odpowiednio w kolejne liczby całkowite od 0 do n
x-x0
t=
h
poszukujemy ciągu wielomianów spełniających na zbiorze
punktów t=0,1,...,n warunek ortogonalności
n
ÔÄ… śątiźąÔÄ…k śątiźą=0, dla j`"k
"
j
i=0
16
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa  wielomiany ortogonalne
dowolny wielomian Q stopnia co najwyżej m może być
przedstawiony jako liniowa kombinacja wielomianów
ortogonalnych Pj
Qmśątźą=b0 P0śątźąƒÄ…b1 P1śątźąƒÄ…‹Ä…ƒÄ…bm Pmśątźą
Jak znalez
ć współczynniki bm?
17
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Aproksymacja średniokwadratowa  wielomiany trygonometryczne
dla funkcji okresowych o okresie 2Ä„
n
a0
Qnśąxźą= ƒÄ… śąak cos kxƒÄ…bk sin kxźą
"
2
k =1
ai, bi  współczynniki trygonometryczne Fouriera funkcji f(x)
względem ortogonalnego układu funkcji bazowych
1,sinśą xźą ,cosśą xźą ,sin śą2 xźą ,cosśą2 xźą ,‹Ä…,sinśąk xźą , cosśąk xźą
18
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Ekstrapolacja
Ekstrapolacja jest przybliżaniem funkcji f(x) poza zadanym
przedziałem [x1, xn].
Ekstrapolacja liniowa
śąx-x1źąśą y2- y1źą
F śąxźą= y1ƒÄ… , dla x"Ä…x1
h
śąx-xnźąśą yn- yn-1źą
F śąxźą= ynƒÄ… , dla xÄ…xn
h
19
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Ekstrapolacja
Ekstrapolacja kwadratowa
śąx-x1źąśą4 y2- y3-3 y1źą
F śąxźą= y1ƒÄ… , dla x"Ä…x1
2 h
śąx-xnźąśą3 ynƒÄ… yn-2-4 yn-1źą
F śąxźą= ynƒÄ… , dla xÄ…xn
2 h
20
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08