Metody numeryczne

• Podręcznik
• Spis treści
• Errata

Zdj.: Wydawnictwo Naukowe PWN

O czym jest ten podręcznik?

Metody numeryczne, matematyka obliczeniowa, analiza numeryczna, obliczenia naukowe.... Te wszystkie pojęcia odnoszą się do jednej dziedziny - oglądanej, co prawda, z różnych perspektyw - znajdującej się na styku modelowania, informatyki oraz matematyki, i której wpływ na świat, a zwłaszcza inne obszary nauki i inżynierii, okazał się ogromny.

Potrzeba obliczenia czegoś jest na dobrą sprawę tak stara jak matematyka, a konieczność obliczenia czegoś szybko stała się z jednej strony przyczyną konstruowania coraz lepszych narzędzi wspomagających liczenie (od kamyczków w starożytności, przez maszynę Leibniza i suwak logarytmiczny, aż po komputer w XX wieku), a z drugiej - spowodowała równoległy rozwój metod obliczeniowych, które współtworzyli m.in. Gauss, Euler, Newton, Lagrange, czy Courant.

Moim zasadniczym celem jest nauczenie Czytelnika umiejętności konstrukcji algorytmów rozwiązywania (klasycznych) zadań obliczeniowych, a następnie przeprowadzenia (matematycznej) analizy ich własności; przede wszystkim: kosztu i dokładności.

Przy okazji podaję też krótkie wskazówki, jak takie klasyczne zadania można rozwiązywać w popularnych językach programowania: MATLAB-ie, Octave, Julii i Pythonie. (Znacznie więcej o kwestiach związanych z implementacją piszę w innej książce: Obliczenia inżynierskie i naukowe.)

Dla kogo jest ten podręcznik?

Książkę adresuję przede wszystkim do studentów kierunków ścisłych i technicznych - od matematyki, przez informatykę, uczenie maszynowe i data science, po astronomię, chemię, ekonomię, fizykę i geologię - dysponujących podstawowym aparatem matematycznym z pierwszych dwóch-trzech semestrów studiów licencjackich, a także podstawową wiedzą informatyczną, obejmującą umiejętność konstruowania algorytmów i ich implementacji w jakimś klasycznym języku programowania.

Może być także przydatny dla inżynierów i naukowców, chcących poznać bliżej tę fascynującą gałąź nauki i jej praktyczne zastosowania.

Dzięki rozkwitowi technologii komputerowej, metody numeryczne od kilkudziesięciu lat przenikają do kolejnych gałęzi nauki i techniki, od lotów kosmicznych, po optymalizację łańcuchów produkcji, stając się podstawą niezwykłych zastosowań - takich, jak choćby tomografia komputerowa, nawigacja GPS lub format muzyki MP3. Przyczyniają się też do powstania zupełnie nowych dziedzin, w tym: uczenia maszynowego i komputerowej dynamiki płynów. Rzeczywiste procesy (fizyczne, ekonomiczne, technologiczne, biologiczne, ...) są wszak na tyle skomplikowane, że trudno gdziekolwiek osiągnąć postęp bez solidnego obliczeniowego wsparcia.

Podręcznik poświęcony jest podstawowym, klasycznym tematom; jego intencją jest wprowadzenie Czytelnika w podstawy dziedziny:

Spis treści

Możesz też pobrać spis treści w formacie PDF, zamieszczony na stronie wydawnictwa.

• Fundamenty
  1. Czym zajmują się metody numeryczne?
     1. Zadanie obliczeniowe
     2. Cel metod numerycznych
  2. Oprogramowanie dla obliczeń numerycznych
     1. MATLAB i GNU Octave
        1. Podstawy
        2. Pierwsze obliczenia
        3. Skrypty i funkcje
     2. Julia
        1. Podstawy
        2. Pierwsze obliczenia
        3. Skrypty i funkcje
     3. Python: moduły NumPy i SciPy
        1. Podstawy
        2. Pierwsze obliczenia
        3. Skrypty i funkcje
     4. Uwagi i uzupełnienia
     5. Zadania
  3. Komputer i obliczenia na liczbach rzeczywistych
     1. Zapis zmiennopozycyjny liczb rzeczywistych
     2. Standard arytmetyki zmiennopozycyjnej IEEE 754
        1. Liczby maszynowe
        2. Operacje arytmetyczne
        3. Różnice między arytmetyką dokładną a arytmetyką fl
        4. Formaty liczb maszynowych nieobjęte standardem IEEE 754
     3. Komputer
        1. Procesor
        2. Pamięć
     4. W skrócie
     5. Uwagi i uzupełnienia
     6. Zadania
     7. Sprawdźmy to w praktyce. Różnicowa aproksymacja pochodnej
  4. Błędy w zadaniach obliczeniowych
     1. Błąd bezwzględny i błąd względny
     2. Uwarunkowanie zadania
     3. Błąd i uwarunkowanie zadania po składowych
     4. Uwarunkowanie złożenia
     5. W skrócie
     6. Uwagi i uzupełnienia
     7. Zadania
     8. Sprawdźmy to w praktyce. Czułość układu elektrycznego na zmianę parametrów
  5. Jakość algorytmów numerycznych
     1. Algorytm numeryczny
     2. Błąd w przód i błąd wstecz
     3. Koszt obliczeniowy i pamięciowy algorytmu
        1. Złożoność obliczeniowa zadania
        2. Koszt algorytmów rekurencyjnych
        3. Ograniczenia używanego modelu kosztu obliczeń
     4. Zachowanie się algorytmu w arytmetyce fl
        1. Numeryczna poprawność
        2. Numeryczna stabilność
        3. Praktyczne wskazówki
     5. W skrócie
     6. Uwagi i uzupełnienia
     7. Zadania
• Algebra liniowa
  1. Metody bezpośrednie dla układów równań liniowych
     1. Jak tego nie robić?
     2. Proste układy równań liniowych
        1. Układ z macierzą trójkątną
        2. Układ z macierzą ortogonalną
     3. Rozkłady macierzy
        1. Rozkład LU
        2. Rozkład LU z osiowaniem
        3. Rozkład QR
     4. Rozkłady macierzy specjalnych
        1. Macierz trójdiagonalna
        2. Macierz symetryczna i dodatnio określona
     5. Uwarunkowanie układu równań liniowych
     6. Reszta, a błąd rozwiązania
     7. Numeryczna poprawność algorytmów opartych na rozkładach
        1. Rozkład QR
        2. Rozkład LU
     8. W skrócie
     9. Software
     10. Uwagi i uzupełnienia
     11. Zadania
     12. Sprawdźmy to w praktyce. Po awarii nad rzeką
  2. Liniowe zadanie najmniejszych kwadratów
     1. Proste zadanie najmniejszych kwadratów
     2. Rozwiązywanie LZNK przez rozkład QR
     3. Metoda Householdera
        1. Wyznaczenie rozkładu QR metodą Householdera
        2. Koszt rozkładu QR metodą Householdera
     4. Sprowadzenie LZNK do układu równań normalnych
     5. Uwarunkowanie LZNK
     6. Reszta, a błąd rozwiązania
     7. W skrócie
     8. Software
     9. Uwagi i uzupełnienia
     10. Zadania
     11. Sprawdźmy to w praktyce. Panorama
  3. Symetryczne zagadnienie własne
     1. Wyznaczanie pojedynczej pary własnej
        1. Metoda potęgowa
        2. Iloraz Rayleigha
        3. Transformacje widma
        4. Odwrotna metoda potęgowa
        5. Odwrotna metoda potęgowa z przesunięciem
     2. Uwarunkowanie wartości własnych
     3. Reszta, a błąd wstecz
     4. Kryteria stopu
     5. Pełne zagadnienie własne
        1. Sprowadzenie macierzy do prostszej postaci
        2. Metoda dziel i rządź dla trójdiagonalnej macierzy symetrycznej
        3. Wyznaczanie wektorów i wartości własnych modyfikacji rzędu jeden macierzy diagonalnej
        4. Metoda QR
     6. Lokalizacja wartości własnych
     7. W skrócie
     8. Software
     9. Uwagi i uzupełnienia
     10. Zadania
     11. Sprawdźmy to w praktyce. Jak zmienił się cały świat
  4. Rozkład SVD
     1. Własności
     2. Przykłady zastosowań
        1. Nieregularne liniowe zadanie najmniejszych kwadratów
     3. Wyznaczanie rozkładu SVD
        1. Sprowadzenie do postaci dwudiagonalnej
        2. Metoda dziel i rządź dla macierzy dwudiagonalnej
     4. W skrócie
     5. Software
     6. Uwagi i uzupełnienia
     7. Zadania
     8. Sprawdźmy to w praktyce. PCA na przykładzie LSA
  5. Metody iteracyjne dla układów równań liniowych
     1. Macierze rozrzedzone
        1. Reprezentacja macierzy rozrzedzonych
     2. Metody iteracyjne oparte na rozszczepieniu macierzy
        1. Klasyczne metody rozszczepienia
     3. Metody przestrzeni Kryłowa
        1. Metoda CG (sprzężonych gradientów)
        2. Metoda GMRES
     4. Ściskanie macierzy
        1. Proste operatory ściskające
        2. Ściskanie dla CG: metoda PCG
     5. Kryteria stopu metod iteracyjnych
     6. W skrócie
     7. Software
     8. Uwagi i uzupełnienia
     9. Zadania
     10. Sprawdźmy to w praktyce. Miejska sieć gazowa
• Aproksymacja funkcji i zadania pokrewne
  1. Aproksymacja wielomianami
     1. Istnienie elementu najlepszej aproksymacji
     2. Najlepsza aproksymacja średniokwadratowa
        1. Uwarunkowanie zadania najlepszej aproksymacji średniokwadratowej
        2. Wyznaczanie wielomianu najlepszej aproksymacji średniokwadratowej
        3. Wielomiany ortogonalne
        4. Przypadek dyskretnej aproksymacji średniokwadratowej
     3. Najlepsza aproksymacja jednostajna
        1. Charakteryzacja wielomianu najlepszej aproksymacji jednostajnej przez alternans
        2. Wyznaczenie wielomianu aproksymacji jednostajnej
        3. Wielomiany Czebyszewa i ich własności
     4. Interpolacja Lagrange'a
        1. Algorytm różnic dzielonych
        2. Błąd interpolacji
        3. Najlepsza aproksymacja jednostajna, a interpolacja
        4. Uwarunkowanie zadania interpolacji
     5. W skrócie
     6. Software
     7. Uwagi i uzupełnienia
     8. Zadania
     9. Sprawdźmy to w praktyce. Wielomianowy wytrych
  2. Aproksymacja splajnami
     1. Splajn, czyli funkcja sklejana z wielomianów
        1. Reprezentacja splajnu w postaci PP
     2. Reprezentacja splajnu w B-bazie
        1. Własności B-splajnów
        2. Algorytm de Boora
     3. Interpolacja splajnowa
        1. Interpolacja splajnem liniowym
        2. Interpolacja splajnem kubicznym
        3. Optymalność splajnów interpolacyjnych
     4. Splajnowa aproksymacja średniokwadratowa
        1. Przypadek dyskretnej aproksymacji średniokwadratowej
     5. W skrócie
     6. Software
     7. Uwagi i uzupełnienia
     8. Zadania
     9. Sprawdźmy to w praktyce. Galeria aproksymacji
  3. Całkowanie
     1. Proste kwadratury interpolacyjne
        1. Błąd kwadratur interpolacyjnych
        2. Kwadratury Gaussa
     2. Kwadratury złożone
        1. Błąd kwadratur złożonych
        2. Kwadratury Romberga
     3. Uwarunkowanie zadania całkowania
     4. W skrócie
     5. Software
     6. Uwagi i uzupełnienia
     7. Zadania
     8. Sprawdźmy to w praktyce. Jak często brać tabletkę?
  4. Równania nieliniowe
     1. Metoda bisekcji dla równania skalarnego
     2. Metoda Newtona
        1. Modyfikacje nieużywające pochodnej
     3. Wielowymiarowa metoda Newtona
        1. Implementacja
        2. Modyfikacje obniżające koszt iteracji
        3. Modyfikacje nieużywające pochodnej
     4. Zadanie punktu stałego, a równanie nieliniowe
        1. Metoda Banacha (iteracja prosta)
     5. Uwarunkowanie równania nieliniowego
     6. Kryteria stopu. Reszta, a błąd
     7. W skrócie
     8. Software
     9. Uwagi i uzupełnienia
     10. Zadania
     11. Sprawdźmy to w praktyce. Dializator
  5. Optymalizacja
     1. Metoda Newtona
        1. Implementacja
        2. Modyfikacje obniżające koszt iteracji
        3. Modyfikacje ograniczające użycie pochodnych
     2. Metoda spadku po gradiencie
        1. Wybór długości kroku
     3. Uwarunkowanie zadania minimalizacji
     4. Kryteria stopu. Norma gradientu, a błąd
     5. Nieliniowe zadanie najmniejszych kwadratów
        1. Metoda Gaussa-Newtona
     6. W skrócie
     7. Software
     8. Uwagi i uzupełnienia
     9. Zadania
     10. Sprawdźmy to w praktyce. Gdzie ja jestem?

Zobacz fragment książki zamieszczony na stronie wydawnictwa.

Errata

Zauważone w tekście błędy proszę zgłaszać na adres p.krzyzanowski@mimuw.edu.pl.

Strona 76 linia 4, do końca zdania

Powinno być “… 96 albo 128 bitów (w kompilatorze GCC domyślnie wybierane są takie, które lepiej odpowiadają ABI, tzn. 96 bitów dla IA-32 oraz 128 bitów dla IA-64).”

Strona 106, tw. 4.4.2, linia -6

Powinno być: $D\subset R^N$

Strona 107, tw. 4.4.3, linia 2

Powinno być: $F:D\to R^N$, gdzie $D\subset R^N\times R^M$

Strona 123, ramka, linia 4

Zamiast $\text{O}(N^p)$ powinno być: $\text{Const}\cdot N^p$

Strona 128, ramka, linia 2

Zamiast $\text{O}(N^3)$ powinno być: $N^3$

Strona 154 linia 12

Zamiast “$r=\sqrt{s}$” powinno być “$r=\sqrt{d}$”.

Strona 173 linie -8..-6

Zdanie “W poniższej wersji jedynek z diagonali (…) bo przecież i tak wiemy, gdzie muszą być” odnosi się do alg. 6.3.2.

Strona 179 linia 2

Przed rozpoczęciem pętli “for $k$…”, należy inicjalizować wektor permutacji: $\sigma =[1,\dots ,N]$.

Strona 179 linia 7

powinno być: ${\sigma }_k=p$, ${\sigma }_p=k$ (…zapamiętanie permutacji).

Strona 215 linia -3

Powinno być: “wymaga – przy założeniu, że wyznaczając $v$, zapamiętaliśmy także mnożnik $2/v^{T}v$ (zob. ramkę powyżej) – obliczenia”

Strona 233

Macierz w drugiej kolumnie tekstu prawidłowo powinna wyglądać tak: $$\left[\begin{array}{cccc}-\frac{a_2}{a_1}& -\frac{a_3}{a_1}& \cdots & -\frac{a_{N+1}}{a_1}\\ 1& & & \\ & \ddots & & \\ & & 1& \end{array}\right]$$

Strona 239

w równaniu poprzedzającym równanie (8.1), czynnik ${\lambda }_1^{2k}$ jest zbędny.

Strona 239

w równaniu (8.1) i w kończącej dowód nierówności, zamiast ${\alpha }_1$ powinno być $|{\alpha }_1|$.

Strona 247

Tw. 8.2.3 powinno brzmieć: Niech $v_1,\dots ,v_N$ stanowią bazę ortogonalną złożoną z wektorów własnych macierzy symetrycznej $A$, odpowiadających wartościom własnym ${\lambda }_1\ge \dots \ge {\lambda }_N$. Analogicznie, niech ${\tilde{v}}_1,\dots ,{\tilde{v}}_N$ stanowią bazę ortogonalną złożoną z wektorów własnych macierzy symetrycznej $A+\mathrm{\Delta }$, odpowiadających wartościom własnym ${\tilde{\lambda }}_1\ge \dots \ge {\tilde{\lambda }}_N$. Wtedy dla każdego $i=1,\dots ,N$ zachodzi $$\sin {\theta }_i\le \frac{2}{\underset{j\ne i}{min}|{\lambda }_j-{\lambda }_i|}||\mathrm{\Delta }|{|}_2,$$ gdzie ${\theta }_i$ oznacza kąt (ostry) pomiędzy $v_i$ oraz ${\tilde{v}}_i$. (Gdy ${\lambda }_i$ jest wielokrotną wartością własną, po prawej stronie nierówności kładziemy $\mathrm{\infty }$.)

Strona 247 linia -8

Po słowie Dowód należy dodać zdanie: “Ustalmy $i$ oraz oznaczmy dla uproszczenia notacji $\lambda :={\tilde{\lambda }}_i$ oraz $v:={\tilde{v}}_i$.”

Strona 247 linia -5

Zamiast “$u\perp v_i$” powinno być “$u_i\perp v_i$”. Zamiast “$v_{,}$” powinno być “$v_j$”.

Strona 259 linia -2

Powinno być: “przeplatają się z wartościami z diagonali $D$. W szczególności, gdy $\beta >0$, zachodzi:”

Strona 277 linia 4

Powinno być: $${\hat{U}}^{T}A\hat{V}={\hat{\mathrm{\Sigma }}}^{-1}{\hat{V}}^T\underset{=B}{\underbrace{A^{T}A}}\hat{V}={\hat{\mathrm{\Sigma }}}^{-1}{\hat{\mathrm{\Sigma }}}^2=\hat{\mathrm{\Sigma }}.$$

Strona 324 linia -5

Zamiast “$r_k$” powinno być “$M{r}_k$”.

Strona 501 linia -13

Powinno być “dostatecznie blisko”.