Слайд 1ЛІТЕРАТУРА
Гловацкая А.П. Методы и алгоритмы вычислительной математики. М.: Радио и
связь. – 1999. – 408с.
Данилина Н.И., Дубровская Н.С., Кваша О.П.
Численные методы. - М.: Высшая школа, 1976.
Демидович Б.П., Марон И.А. Основы вычислительной математики. - М.: Наука, 1970 - 664 с.
Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. М.: Наука. – 1972. – 366с.
Лященко М.Я., Головань М.С. Чисельні методи. – Київ: Либідь. – 1996. – 288 с.
Ортега Д., Пул У. Введение в численные методы решения дифференциальных равнений. -М.: Наука, 1986. - 288 с.
Самарский А.А. Введение в численные методы.- М.:Наука, 1982 - 272 с.
Турчак Л.И. Основы численных методов. М.: Наука. – 1987. – 318с.
Фельдман Л.П., Петренко А.І., Дмитрієва О.А. Чисельні методи в інформатиці. - Київ: Видавнича група BHV.- 2006. – 480 с.
Слайд 2ОБЧИСЛЮВАЛЬНИЙ ЕКСПЕРИМЕНТ ТА ЙОГО ЕТАПИ
Обчислювальний експеримент — це метод дослідження
складних процесів, об'єктів чи систем шляхом побудови , реалізації та
аналізу їх математичних моделей засобами обчислювальної техніки.
Під математичною моделлю фізичної системи, об'єкта або процесу розуміють сукупність математичних співвідношень (формул, рівнянь, логічних виразів), які визначають характеристики стану і властивості системи, об'єкта і процесу та їх функціонування залежно від параметрів їх компонентів, початкових умов, вхідних збуджень і часу.
Чисельні методи — це математичний інструментарій, за допомогою якого математична задача формулюється так, щоб вона могла бути розв’язана за допомогою простих арифметичних і логічних операцій, таких звичних для комп'ютера. В цьому випадку говорять про перетворення математичної задачі в обчислювальну задачу. При цьому послідовність виконання необхідних арифметичних і логічних операцій визначається алгоритмом її розв’язку.
Слайд 3ОБЧИСЛЮВАЛЬНИЙ ЕКСПЕРИМЕНТ ТА ЙОГО ЕТАПИ
Об’єкт дослідження
(процес, система)
Модель
математична
(ММ)
Модель
дискретна
(МД)
Результати
обчислень
Модель
програмна
(МП)
(x,t) Þ
(Δx, Δt) Þ (xi, ti)
y = FM(x)
Слайд 4ВЛАСТИВОСТІ ЧИСЕЛЬНИХ МЕТОДІВ
Передбачають проведення великої кількості арифметичних обчислень за допомогою
рекурсивних співвідношень, що використовуються для організації ітерацій, тобто повторюваних циклів
обчислень із зміненими початковими умовами для поліпшення розв’язку.
Направлені на локальне спрощення задачі, коли, наприклад, нелінійні залежності чи функції лінеаризуються за допомогою своїх обчислених похідних або похідні замінюються різницевими апроксимаціями (наприклад, ряд Тейлора чи поліноміальні апроксимації).
Залежать від вибору початкового значення (або декількох), необхідного для початку обчислень, від властивостей нелінійних функцій, що використовуються в математичних моделях.
Слайд 5ВЛАСТИВОСТІ ЧИСЕЛЬНИХ МЕТОДІВ
Чисельні методи характеризуються різною:
швидкістю збіжності, тобто числом
ітерацій, виконання яких необхідне для отримання заданої точності розв’язку;
стійкістю, тобто збереженням достовірності розв’язку при подальших ітераціях;
точністю отримуваного розв’язку при виконанні однакового числа ітерацій або циклів обчислень.
Чисельні методи розрізняються за рівнем:
універсальності для розв’язування різних математичних задач;
складності їх програмування;
чутливості до погано обумовлених (або некоректних) математичних задач.
Слайд 6ОСНОВНІ ЗАДАЧІ ЧИСЕЛЬНИХ МЕТОДІВ
Розв’язування системи лінійних (в загальному випадку, лінеаризованих)
рівнянь.
Розв’язування систем нелінійних рівнянь.
Проблема власних значень матриці.
Наближення масиву даних або
складної функції набором стандартних, більш простих функцій.
Чисельне інтегрування і диференціювання.
Розв’язування систем звичайних диференціальних рівнянь та диференціальних рівнянь в частинних похідних.
Розв’язування інтегральних рівнянь.
Чисельна оптимізація.
Слайд 7ВИМОГИ ДО ЧИСЕЛЬНИХ МЕТОДІВ
Вимоги до засобів реалізації чисельних методів:
швидкодія;
об’єм пам’яті;
можливість тестування;
аналіз критичних ситуацій;
документованість;
супроводження;
можливість
перенесення на інші комп’ютерні платформи.
Вимоги до адекватності обчислювальної задачі:
збіжність;
стійкість;
коректність.
Слайд 8ВИМОГИ ДО ЧИСЕЛЬНИХ МЕТОДІВ
Метод є збіжним, якщо виконується умова:
Розв’язок є
стійким стосовно вхідних даних, якщо він неперервно залежить від вхідних
даних, тобто для задачі
маємо
Обчислювальна задача y = A(x) називається коректною, якщо для будь-яких вхідних даних, що належать певному класу, існує розв’язок задачі , який є єдиним і стійким стосовно вхідних даних, де A(x) – оператор (алгоритм), що реалізує метод обчислень.
Застосовувати ЧМ безпосередньо до некоректних задач не можна.
Слайд 9ПОХИБКИ ОБЧИСЛЕНЬ
Поліном Уілкінсона:
Якщо внести незначну помилку в коефіцієнт
а19 =
210 (210 + 2 - 23) = 210, 000 000
119,
то серед коренів, знайдених по коефіцієнтах полінома, з'являться комплексні корені
xi,i + 1 = 16,730737400 ± j 2,812624894.
Слайд 10ПОХИБКИ ОБЧИСЛЕНЬ
Існують декілька джерел похибок обчислень:
Похибки вхідних даних і спрощення
моделей компонентів.
Округлення під час обчислень, локальні відсікання.
Похибки представлення чисел в
комп'ютері.
Нехай а — точне значення величини; — наближене значення цієї величини, тоді
— абсолютна похибка;
— відносна похибка.
Слайд 11ПОХИБКИ ОБЧИСЛЕНЬ
При виконанні арифметичних операцій похибки обчислень тільки накопичуються, незалежно
від типу виконуваної операції:
Слайд 12ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ І ОБЧИСЛЕНЬ
Складність обчислень,
передбачених алгоритмом, оцінюється за допомогою сигнальних функцій fA(n), які визначають
обчислювальні витрати на роботу алгоритму через кількість необхідних операцій, що використовується алгоритмом в процесі обчислень, де fA (n) — верхня межа кількості операцій;
n — розмірність задачі.
Слайд 13ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ І ОБЧИСЛЕНЬ
Поліноміальний алгоритм, сигнальна функція якого fA
(n) росте від n не швидше, ніж деякий поліном g(n).
При цьому розрізняють оцінки двох типів:
fA (n) = O [g(n)]
і
fA (n) = о [g(n)]
Комбінаторний алгоритм, коли сигнальна функція fA(n) змінюється як експоненціальна функція або містить в собі оцінки операцій перебору, сполучень, визначення факторіалу n!
Для виконання n! = 20! (24 329 *1017) операцій для комп’ютера з середнім часом виконання операції 10-7 сек необхідно близько 77 століть.