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