wyklad.pdf
(
1739 KB
)
Pobierz
Matematykastosowana
Matematyka
obliczeniowa II
PiotrKrzy»anowski
http://www.mimuw.edu.pl/~przykry
LeszekPlaskota
http://www.mimuw.edu.pl/~leszekp
Uniwersytet Warszawski, 2012
Streszczenie.
W skrypcie omawiamy - w zakresie szerszym ni» w semestral-
nym wykładzie - zaawansowane metody rozwi¡zywania podstawowych zagad-
nie« obliczeniowych spotykanych w praktycznej matematyce stosowanej: wiel-
kich układów równa« liniowych i nieliniowych, zagadnienia własnego i jemu
pokrewnych oraz obliczaniu całek wielowymiarowych. S¡ to kanoniczne zagad-
nienia matematyki obliczeniowej, których wspólnym mianownikiem we współ-
czesnym ±wiecie jest to, »e dotycz¡ obiektów bardzo du»ego rozmiaru. Kurs
wymaga podstawowej wiedzy z Analizy i z Algebry Liniowej i b¦dzie przydat-
ny wszystkim, którzy licz¡ si¦ z tym, »e b¦d¡ musieli w przyszło±ci policzy¢ co±
bardziej skomplikowanego ni» współczynniki wielomianu interpolacyjnego...
Wersja internetowa wykładu:
http://mst.mimuw.edu.pl/lecture.php?lecture=mo2
(mo»e zawiera¢ dodatkowe materiały)
Niniejsze materiały s¡ dost¦pne na
licencji Creative Commons 3.0 Polska
:
Uznanie autorstwa — U»ycie niekomercyjne — Bez utworów zale»nych
.
Copyright c
P.Krzy»anowski, L.Plaskota, Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mecha-
niki, 2012. Niniejszy plik PDF został utworzony 28 wrze±nia 2012.
Projekt współfinansowany przez Uni¦ Europejsk¡ w ramach
Europejskiego Funduszu Społecznego
.
Skład w systemie L
A
T
E
X, z wykorzystaniem m.in. pakietów
beamer
oraz
listings
. Szablony podr¦cznika i prezentacji:
Piotr Krzy»anowski; koncept: Robert D¡browski.
Spis tre±ci
Wprowadzenie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1. Zagadnienie własne I
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.1.
Podstawy teoretyczne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.
Teoria zaburze« dla macierzy niesymetrycznych
. . . . . . . . . . . . . . . . . . . . . . .
9
1.2.1.
Wst¦pny przykład
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2.2.
Wra»liwo±¢ warto±ci własnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.2.3.
Wra»liwo±¢ wektorów własnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.3.
Teoria zaburze« dla macierzy symetrycznych
. . . . . . . . . . . . . . . . . . . . . . . . .
13
1.3.1.
Wra»liwo±¢ warto±ci własnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.3.2.
Wra»liwo±¢ wektorów własnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2. Zagadnienie własne II
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.1.
Uwagi wst¦pne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.1.1.
Sprowadzanie macierzy do postaci Hessenberga
. . . . . . . . . . . . . . . . . . .
18
2.2.
Metoda Hymana
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.3.
Metoda pot¦gowa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.1.
Definicja metody
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.2.
Analiza zbie»no±ci
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.4.
Odwrotna metoda pot¦gowa i deflacja
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3. Zagadnienie własne III
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.1.
Iteracje podprzestrzeni
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.1.1.
Algorytm ogólny
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.1.2.
Iteracje ortogonalne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.2.
Metoda QR
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.1.
Wyprowadzenie metody
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.2.
QR a iteracje ortogonalne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.2.3.
Analiza zbie»no±ci
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.3.
QR z przesuni¦ciami i deflacja
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4. Zagadnienie własne IV
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.1.
Obroty Givensa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.1.1.
Definicja obrotu
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.1.2.
Algorytm Gentlemana
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.2.
Metoda Jacobiego
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.3.
QR dla macierzy trójdiagonalnej
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.4.
Rozkład według warto±ci szczególnych (SVD)
. . . . . . . . . . . . . . . . . . . . . . . . .
39
4.4.1.
Twierdzenie o rozkładzie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
Dlaczego nie pomno»y¢
A
T
A
?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2.
40
4.4.3.
SVD dla macierzy dwudiagonalnych
. . . . . . . . . . . . . . . . . . . . . . . . . .
41
5. Proste metody iteracyjne rozwi¡zywania układów równa« liniowych
. . . . . . . . . .
44
5.1.
Macierze rozrzedzone
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
5.1.1.
Przykłady macierzy rozrzedzonych
. . . . . . . . . . . . . . . . . . . . . . . . . . .
45
5.2.
Macierze rozrzedzone: implementacja
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5.3.
Metody stacjonarne rozwi¡zywania układów równa« liniowych
. . . . . . . . . . . . . . .
53
5.3.1.
Metoda Jacobiego
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
5.3.2.
Metoda Gaussa–Seidela
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
5.3.3.
Metoda SOR
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
Matematyka obliczeniowa II c P.Krzy»anowski, L.Plaskota, Uniwersytet Warszawski, 2012.
5.4. Metody blokowe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.5. Metody projekcji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.5.1. Metoda najszybszego spadku
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.5.2. Metoda najmniejszego residuum
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6. Metody iteracyjne Kryłowa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.1. Metoda gradientów sprz¦»onych (CG)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.1.1. Implementacja
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.2. Metoda GMRES
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2.1. Implementacja
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2.2. Wersja z restartem: GMRES(
m
)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7. ciskanie macierzy (preconditioning)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.1. Proste operatory ±ciskaj¡ce
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.2. Macierze spektralnie równowa»ne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.3. Metoda PCG
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.4. ciskanie dla GMRES
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.5. Kryteria stopu metod iteracyjnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.5.1. Kryterium bł¦du
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.5.2. Kryterium residualne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.5.3. Kryterium post¦pu
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8. Przegl¡d innych metod rozwi¡zywania wielkich układów równa« liniowych
. . . . . 95
8.1. Inne metody Kryłowa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.1.1. Uogólnienia metody CG
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.1.2. Metody nie oparte na minimalizacji
. . . . . . . . . . . . . . . . . . . . . . . . . . 98
8.2. Metody strukturalne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
8.3. Metody wielosiatkowe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9. Układy równa« nieliniowych. Metoda Newtona
. . . . . . . . . . . . . . . . . . . . . . . 103
9.1. Szybko±¢ zbie»no±ci
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9.2. Metoda Banacha
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
9.3. Metoda Newtona
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.3.1. Analiza zbie»no±ci metody Newtona
. . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.3.2. Implementacja metody Newtona
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.Wariacje na temat metody Newtona
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.1. Twierdzenie o istnieniu rozwi¡za«
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.2. Obni»anie kosztu iteracji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.2.1. Uproszczona metoda Newtona
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
10.2.2. Wpływ niedokładno±ci wyznaczenia pochodnej lub funkcji na zbie»no±¢ metody
Newtona
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
10.2.3. Metoda z przybli»on¡ pochodn¡
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
10.2.4. Niedokładna metoda Newtona
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
11.Metoda Broydena
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.1. Realizacja metody Broydena
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.2. Zbie»no±¢ metody Broydena
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
12.Globalizacja zbie»no±ci
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
12.1. Metoda nawrotów
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
12.1.1. Prosta metoda nawrotów
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
12.1.2. Wielomianowe nawroty
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
12.2. Metody kontynuacji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
12.2.1. Wyznaczanie dobrego przybli»enia pocz¡tkowego dla metody typu Newtona
. . . 130
12.2.2. Metoda homotopii
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
13.Kwadratury interpolacyjne w wielu wymiarach
. . . . . . . . . . . . . . . . . . . . . . . 132
13.1. Sformułowanie zadania
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5
13.2. Interpolacja na siatkach regularnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
13.2.1. Posta¢ wielomianu interpolacyjnego
. . . . . . . . . . . . . . . . . . . . . . . . . . 133
13.2.2. Bł¡d interpolacji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
13.3. Kwadratury interpolacyjne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
13.3.1. Kwadratury proste
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
13.3.2. Kwadratury zło»one
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
13.4. Przekle«stwo wymiaru
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
14.Metody Monte Carlo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
14.1. Wst¦p, metody niedeterministyczne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
14.2. Klasyczna metoda Monte Carlo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
14.2.1. Definicja i bł¡d
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
14.2.2. Całkowanie z wag¡
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
14.3. Redukcja wariancji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
14.3.1. Losowanie warstwowe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
14.3.2. Funkcje kontrolne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
14.4. Generowanie liczb (pseudo-)losowych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
14.4.1. Liniowy generator kongruencyjny
. . . . . . . . . . . . . . . . . . . . . . . . . . . 147
14.4.2. Odwracanie dystrybuanty i „akceptuj albo odrzu¢”
. . . . . . . . . . . . . . . . . 147
14.4.3. Metoda Box-Muller dla rozkładu gaussowskiego
. . . . . . . . . . . . . . . . . . . 148
15.Metody quasi-Monte Carlo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
15.1. Co to s¡ metody quasi-Monte Carlo?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
15.2. Dyskrepancja
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
15.3. Bł¡d quasi-Monte Carlo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
15.3.1. Formuła Zaremby
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
15.3.2. Nierówno±¢ Koksmy-Hlawki
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
15.4. Ci¡gi o niskiej dyskrepancji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
15.4.1. Ci¡g Van der Corputa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
15.4.2. Konstrukcje Haltona i Sobol’a
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
15.4.3. Sieci (
t,m,d
) i ci¡gi (
t,d
)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Literatura
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Plik z chomika:
xyzgeo
Inne pliki z tego folderu:
wyklad.pdf
(1739 KB)
Inne foldery tego chomika:
0
algebra
algebra liniowa
algorytmy
analiza funkcjonalna
Zgłoś jeśli
naruszono regulamin