Przedmiotem naszego zainteresowania będą metody rozwiązywania czterech podstawowych zadań obliczeniowych, bardzo często spotykanych w rozmaitych działach matematyki stosowanej:

Układ równań liniowych

Dla danej macierzy rzeczywistej A rozmiaru N×N i wektora b∈RN znaleźć x∈RN taki, że

A⁢x=b.

Układ równań nieliniowych

Dla danej funkcji F:RN⊃D→RN i wektora b∈RN znaleźć x∈D taki, że

F⁢x=b.

Zagadnienie własne

Dla danej macierzy rzeczywistej A rozmiaru N×N znaleźć λ∈C i niezerowy wektor x∈CN takie, że

A⁢x=λ⁢x.

Całkowanie

Mając daną f:RN⊃D→R, obliczyć

I=∫Df⁢x⁢⁢d⁢x.

Bez wielkiej przesady można powiedzieć, że w każdej poważniejszej symulacji wykonywanej na użytek inżynierski, bankowy, naukowy, itp., któreś (lub kilka) z powyższych zadań występuje jako jądro obliczeniowe, nierzadko o krytycznym znaczeniu. Dlatego jest tak ważne, by potrafić takie zadania rozwiązywać szybko i dokładnie.

Wymienione zadania mają w zastosowaniach jeszcze jedną wspólną cechę: jest nią duży (lub bardzo duży) rozmiar zadania N. Przykładowo, układy równań liniowych spotykane w symulacjach układów elektronicznych mogą mieć kilka milionów niewiadomych. W finansach konieczne jest obliczanie całek z bardzo skomplikowanych funkcji, po kostce 360-wymiarowej. Algorytm stosowany w wyszukiwarce Google musi wyznaczyć wektor własny odpowiadający dominującej wartości własnej macierzy o miliardowym rozmiarze. Dyskretyzacje nieliniowych układów równań różniczkowych (na przykład, równania Naviera–Stokesa), bardzo szybko mogą doprowadzić do nieliniowych układów równań o milionie niewiadomych, a ludzie prowadzący symulacje turbulentnego przepływu cieczy z radością uścisnęliby nas, gdybyśmy tylko dali im szansę wykonana obliczeń z 1012 (lub więcej!) niewiadomych.

Zadania obliczeniowe o tak wielkim rozmiarze wymagają specjalnych algorytmów numerycznych. Przykładowo, naiwnie obliczając całkę

jako całkę iterowaną

i stosując do wyznaczenia każdej z całek jednowymiarowych na przykład złożoną kwadraturę trapezów opartą na n≥2 węzłach, musielibyśmy obliczyć aż nN samych tylko wartości funkcji! (Gdy N=360, jak w finansach, a za n weźmiemy skromnie n=10, należałoby wyznaczyć 10360 samych tylko wartości funkcji — co nie rokuje zbyt dobrze, zważywszy, że współczesne komputery osobiste w ciągu jednego roku mogą w najlepszym razie wykonać ,,zaledwie” 1015 operacji arytmetycznych, a najszybsze na świecie superkomputery mogą teoretycznie wykonać 1020 takich operacji rocznie…)

W naszych rozważaniach o sposobach rozwiązywania Wielkiej Czwórki Zadań będziemy stąpać po solidnym gruncie, omawiając metody klasyczne: sprawdzone w praktyce i teoretycznie dobrze zbadane. Co ciekawe, do ich zrozumienia i analizy będzie nam potrzebna jedynie podstawowa wiedza z Analizy i GALu, a także nieco elementarnych wiadomości z Rachunku Prawdopodobieństwa. W wykładzie bardzo mało będziemy odwoływać się wprost do materiału z Matematyki Obliczeniowej I: jego treść jest w znacznej mierze ortogonalna do tego przedmiotu — ale oczywiście pewna wiedza o metodach numerycznych może nam pomóc lepiej umieścić omawiane kwestie na tle szerszego spektrum zagadnień matematyki obliczeniowej.

Wraz z możliwościami obliczeniowymi komputerów rosną także nasze potrzeby i wymagania, a zjawiska, jakie chcemy symulować numerycznie stają się coraz bardziej złożone, wykraczając poza podstawowe zadania omawiane w skrypcie. Mamy nadzieję, że zdobyta na niniejszym wykładzie wiedza i doświadczenie pozwolą Państwu świadomie korzystać z gotowych pakietów obliczeniowych (więcej na ten temat w wykładzie z Obliczeń naukowych) i w przyszłości zmierzyć się także z nowymi, trudniejszymi wyzwaniami.