Обчислювальна математика

Вавилонська глиняна табличка приблизно 1800—1600 років до нашої ери з сучасними анотаціями. Надписи на табличці дають наближене значення квадратного кореня з 2 як суми чотирьох шістдесяткових чисел: ${\sqrt {2}}=1+24/60+$
$\ 51/60^{2}+10/60^{3}=$
$1.41421296\ldots$

Обчи́слювальна матема́тика — розділ математики, до якого входить коло питань, зв'язаних з виконанням наближених обчислень. У вужчому розумінні, обчислювальна математика — теорія числових методів розв'язування типових математичних задач. Сучасна обчислювальна математика уводить до кола своїх проблем вивчення особливостей обчислень із використанням комп'ютерів.

Обчислювальна математика має широке коло прикладних використань для проведення наукових та інженерних розрахунків. На її основі в останні десятиліття розвинулися нові області обчислювальних наук, наприклад, обчислювальна хімія, обчислювальна біологія тощо.

Історія

Обчислювальна математика виникла дуже давно, ще в стародавньому Межиріччі були розроблені методи добування квадратного кореня. В епоху першої наукової революції 16-17 ст. обчислювальна математика швидко розвивалася, виходячи з практичних потреб, паралельно з математичним аналізом. Зокрема, наближені обчислення широко використовувалися в небесній механіці для передбачення руху небесних тіл, що привело до встановлення геліоцентричної системи, законів Кеплера, законів Ньютона. XVII та XVIII століттях стали свідками розроблення значної кількості чисельних методів та алгоритмів.

Виконання великої кількості інженерних обчислень у XIX та XX століттях вимагало створення відповідних засобів. Одним із таких засобів стала логарифмічна лінійка, іншим — таблиці функцій. Таблиці трансцендентних функцій друкувалися з великою точністю — до 16 знаків після коми, й значно допомагали проводити розрахунки. Існували механічні пристрої для виконання математичних операцій — арифмометри. У першій половині 20 століття для розв'язку диференціальних рівнянь використовувалися аналогові електричні схеми.

Винахід комп'ютера в середині 20 століття означав створення універсального інструмента для математичних розрахунків. Поряд із мейнфреймами до широкого розповсюдження персональних комп'ютерів у розпорядженні інженерів та науковців для виконання ручних операцій були калькулятори.

Проблема чотирьох фарб стала першою чисто математичною теоремою доведеною, за допомогою комп'ютера в 1976 році. Це доведення зводиться до вичерпного перебору кількох тисяч варіантів, чого людина зробити не може. Відтоді чисельні обчислення за допомогою комп'ютера увійшли в арсенал засобів математика.

Задачі обчислювальної математики

До задач обчислювальної математики належать:

• розв'язування систем лінійних рівнянь
• пошук власних значень і векторів матриці
• пошук сингулярних значень і векторів матриці
• розв'язування нелінійних (в тому числі алгебраїчних та трансцендентних) рівнянь
• розв'язування систем нелінійних алгебраїчних рівнянь
• розв'язування диференціальних рівнянь (як звичайних диференціальних рівнянь, так і рівнянь з частинними похідними)
• розв'язування систем диференціальних рівнянь
• розв'язування інтегральних рівнянь
• задачі апроксимації
• задачі інтерполяції
• задачі екстраполяції
• задачі оптимізації
• задачі регресії
• обернені задачі.

Окремим класом задач обчислювальної математики є задачі з використанням послідовностей випадкових чисел, різноманітні методи Монте-Карло, що широко застосувуються в багатьох галузях як власне математики, так і суміжних наук. Для розв'язання цього класу задач необхідна розробка й вдосконалення методів генерації псевдовипадкових чисел із різноманітними розподілами.

Обмеження представлення чисел у комп'ютері

Основна відмінність обчислювальної математики з використанням комп'ютерів полягає в тому, що при розв'язуванні обчислювальних задач комп'ютер оперує машинними числами, що є дискретною проекцією дійсних чисел на конкретну архітектуру комп'ютера. Так, наприклад, якщо взяти машинне число завдовжки 8 байтів, у ньому можна запам'ятати тільки 2⁶⁴ різних чисел, тому важливу роль в обчислювальній математиці відіграють оцінки точності алгоритмів та їхня стійкість до представлень машинних чисел у комп'ютері. Саме тому, наприклад, для розв'язування лінійної системи алгебричних рівнянь дуже рідко використовується обчислення оберненої матриці, тому що цей метод може привести до помилкового розв'язку у випадку з сингулярною матрицею, а дуже розповсюджений у лінійній алгебрі метод заснований на обчисленні визначника матриці і її доповнення вимагає набагато більше арифметичних операцій, ніж будь-який стійкий метод розв'язування лінійної системи рівнянь.

Це обмеження не є принциповим. Комп'ютер може виконувати обчислення з довільною точністю, використовуючи звичайне символічне представлення чисел так, як це робила б людина, але, відповідно, це призводить до збільшення часу розрахунків. Зокрема, можливість обчислень з довільною точністю дають популярні програмні продукти: Mathematica, Sage, Maple, MATLAB.

Чисельні методи

Основним об'єктом вивчення обчислювальної математики є чисельні методи розв'язування різноманітних математичних задач та алгоритмізація цих методів. Серед найважливіших характеристик чисельних методів — збіжність, стійкість, ефективність.

Збіжність методу визначається його спроможністю знайти наближений розв'язок задачі з достатнью точністю за скінченне число кроків. Особливої уваги вимагають ітераційні методи. Збіжність ітераційних методів часто залежить від тих значень, з яких починається ітераційний процес. Чисельний метод повинен будуватися так, щоб бажаний розв'язок був атрактором ітераційної процедури. Дуже часто побудова або вибір методу залежать від уміння математика, не як ремесла, а як мистецтва.

Стійкість чисельного методу з одного боку зумовлена математичною проблемою. Ітераційний процес, наприклад, у залежності від початкових значень, може збігатися до різних атракторів математичної задачі. Результат застосування стійких методів не повинен залежати від зміни почакових значень принаймні в межах деякої області.

Крім математичної стійкості, що визначається початковими умовами, існує також проблема чисельної нестійкості. Кожне обчислення виконується з певною похибкою, зумовленою представленням чисел, округленнями тощо. Накопичення похибок може призвести до виходу стану системи з басейну притягання атрактора, і результат не буде знайдено.

Ефективність методу визначається числом операцій, необхідних для знаходження розв'язку, а також об'ємом пам'яті, потрібної для збереження проміжних результатів. Як число операцій, так і небхідна комп'ютерна пам'ять часто зростають дуже швидко із ростом розмірів системи. Так, наприклад, розв'язок диференціального рівняння з частинними похідними часто зводиться до розв'язку системи лінійних алгебраїчних рівнянь розміності $N^{2}$, де N — число точок, для яких треба знайти розв'язок. Це число точок пропорційне $L^{d}$, де L — число точок в одному вимірі, d — розмірність системи. Для тривимірної системи, розмірність матриці повинна бути порядку $L^{6}$. Наприклад, для 100 точок в кожному вимірі потрібно зберігати принаймні 10¹² чисел, а для 1000 точок 10¹⁸ чисел. Відповідно збільшується час розрахунків.

Програмне забезпечення

Алгоритми розв'язування багатьох стандартних задач обчислювальної математики реалізовані на багатьох мовах програмування. Найчастіше для цих цілей використовуються мови ФОРТРАН і C. Ці алгоритми скомпоновані в бібліотеки, які можна знайти, наприклад, в репозиторії Netlib. Популярні комерційні бібліотеки — IMSL, NAG, Intel MKL, чи вільна альтернатива GNU Scientific Library.

MATLAB, Mathematica, Maple, S-PLUS, LabVIEW та IDL, а також їх вільні альтернативи Sage, FreeMat, Scilab, GNU Octave (схожа на Matlab), IT++ (бібліотека C++), R (подібна до S-PLUS), Python (з NumPy та SciPy) мають у своєму розпорядженні різноманітні чисельні методи, а також засоби для візуалізації та відображення результатів.

Джерела

• К. И. Бабенко. Основы численного анализа. Москва. Наука. 1986.
• Канторович Л. В., Крылов В. И. Приближенные методы высшего анализа. Москва — Ленинград. ГИИТЛ. 1949.
• Hildebrand, F. B. (1974). Introduction to Numerical Analysis (2nd edition ed.). McGraw-Hill. ISBN 0-07-028761-9.
• Leader, Jeffery J. (2004). Numerical Analysis and Scientific Computation. Addison Wesley. ISBN 0-201-73499-0.
• Trefethen, Lloyd N. (2006). «Numerical analysis», 20 pages. In: Timothy Gowers and June Barrow-Green (editors), Princeton Companion of Mathematics, Princeton University Press.
• Higham, Nicholas J. (1966). Accuracy and Stability of Numerical Algorithms (Society for Industrial and Applied Mathematics, ISBN 0-89871-355-2).