Чисельні ме́тоди, або Числові методиРосійсько-український словник наукової термінології: Математика. Фізика. Техніка. Науки про Землю та Космос / НАН України. Комітет наукової термінології; Інститут мовознавства ім. О. О. Потебні / Гейченко В. В., Завірюхіна В. М., Зеленюк О. О., Коломієць В. Г., Кратко М. І. Ред. Митропольський Ю. О. — К.: Наук. думка, 1998. — 888 с., C. 330. — ISBN 5-12-004273-2.Вступ до числових методів: Навч. посіб. для вищ. закл. освіти / П. І. Каленюк, В. А. Бакалець, І. І. Бакалець, Н. В. Горбачова, П. Л. Сохан; Держ. ун-т «Львів. політехніка». — Л., 2000. — 145 c. — (Математика для інженерів). — Бібліогр.: 20 назв. (також числови́й ана́ліз) — методи наближеного або точного розв'язування задач чистої або прикладної математики, які ґрунтуються на побудові послідовності дій над скінченною множиною чи́сел. Дана наука вивчає алгоритми, які застосовують числову апроксимацію (на відміну від загальних символьних обчислень) для розв'язування задач математичного аналізу (чим відрізняється від дискретної математики). Основні вимоги до числових методів, щоб вони були стійкими та збіжними.
Класи задач, що розв'язують за допомогою числових методів
За допомогою чисельних методів можливо розв'язати багато різних класів задач, які є під-дисциплінами цієї області. Деякими з них є : розв'язок лінійних та нелінійних рівнянь та їх систем інтерполяція та апроксимація функцій числове інтегрування та обчислення похідної числовий розв'язок диференціальних рівнянь та систем числовий розв'язок диференціальних рівнянь в частинних похідних та їх систем числовий розв'язок інтегральних рівнянь задачі оптимізації
Розрахунок значень функцій
Інтерполяція: Ми спостерігали за тим, як змінювалася температура в приміщенні від 20 градусів за Цельсієм в 1:00 до 14 градусів в 3:00. Відповідно до лінійної інтерполяції ми можемо встановити, що о 2:00 температура становила 17 градусів, і 18.5 градусів в 1:30.
Екстраполяція: Якщо валовий внутрішній продукт країни зростав в середньому на 5 % на рік і минулого року його обсяг становив 100 мільярдів доларів, ми можемо екстраполювати, що він становитиме 105 міль'ярдів доларів цього року.
Регресія: Лінійна регресія дозволяє при даних n точках розрахувати пряму, яка проходитиме настільки близько наскільки це можливо до всіх цих n точок.
Оптимізація: Припустимо ви продаєте лимонад у кіоску, і підрахували, що за $1, ви можете продати 197 склянок лимонаду за день, і що піднявши ціну на кожні $0.01, ви продасте на одну склянку лимонаду на день менше. Якщо ви б виставили ціну $1.485, ви б збільшили свій заробіток, але так як ви повинні округлити суму до цілих центів, ви можете оцінити склянку лимонаду в $1.48 або $1.49, що дасть вам максимальний прибуток $220.52 на день.
Диференціальне рівняння: Якщо ви встановите 100 вентиляторів у кімнаті, так що вони дмуть з одного боку кімнати в інший, і кинете у цей вітер пір'ячко, що відбудеться тоді? Пір'їнка рухатиметься повітряними потоками, і рух цей може бути досить складним. Одним із методів апроксимації є виміряти швидкість, з яким вітер дме біля місця, де перебуває пір'їнка в кожну секунду, і продовжити його рух уявним способом, так ніби воно продовжує рухатися по прямій з тією ж швидкістю протягом секунди, перед тим як швидкість вітру буде виміряно знов. Це називається Методом Ейлера для роз'язання звичайного диференціального рівняння.
Однією із найпростіших задач є розрахунок значення функції в заданій точці. Найбільш прямолінійний підхід — просто підставити значення в формулу — може бути не найефективнішим способом. Для поліномів краще використовувати схему Горнера, позаяк вона дозволяє зменшити необхідну кількість операцій множення і додавання. Як правило, важливо враховувати і контролювати похибку округлення, яка виникає при виконанні арифметики чисел із рухомою комою.
Інтерполяція, екстраполяція і регресія
Інтерполяція вирішує наступну задачу: дані значення деякої невідомої функції у вигляді набору точок, яке значення матиме функція в деякій іншій точці, між цими даними точками?
Екстраполяція дуже подібна до інтерполяції, але необхідно знайти значення невідомої функції у точці, що заходиться за межами даних точок.
Регресія також подібна до попередніх методів, але враховує те, що дані можуть бути не точними. Дані деякі точки, і вимірювання значень деякої функції в цих точках (що містять похибку), необхідно встановити невідому функцію. Популярним методом розв'язування цієї задачі є метод найменших квадратів.
Розв'язання рівнянь і систем рівнянь
Іншою фундаментальною задачею є розрахунок розв'язку для даного рівняння. Як правило виділяють два випадки, в залежності від того чи є рівняння лінійним чи ні. Наприклад, рівняння є лінійним рівнянням, а не є таким.
Багато зусиль покладено на розробку методів розв'язуваннч систем лінійних рівнянь. До стандартних методів, які використовують розклад матриць відносяться Метод Гауса, LU-розклад матриці, Розклад Холецького для симетричних (або ермітових матриць) і додатньоозначених матриць, і QR-розклад матриці для не квадратних матриць. Ітеративні методи, такі як Метод Якобі, Метод Гауса — Зейделя, Метод релаксації і метод сполучених градієнтів як правило використовують для великих систем рівнянь. Загальні ітеративні методи можуть застосовувати розділення матриць.
Методи розв'язання нелінійних рівнянь дозволяють вирішити нелінійні рівняння і знайти їх корені (такі аргументи при яких функція дорівнює нулю). Якщо функція диференційована і її похідна відома, тоді як правило використовують метод Ньютона. Іншою технікою, яку використовують для розв'язування нелінійних рівнянь є лінеаризація.
Розв'язування задач власного чи сингулярного розкладу Декілька важливих задач можна сформулювати і розв'язати застосовуючи власний розклад або сингулярний розклад матриць. Наприклад, алгоритм стиснення спектральних зображеньThe Singular Value Decomposition and Its Applications in Image Compression оснований на сингулярному розкладі. В статистиці відповідний інструмент називається методом головних компонент.
Оптимізація
Відповідно до задачі оптимізації, необхідно знайти таку точку, в який функція приймає максимальне (або мінімальне) значення. Часто, ця точка також повинна задовольняти певним обмеженням.
Далі область дослідження задач оптимізації розділяється на декілька напрямків, в залежності від форми цільової функції і заданих обмежень. Наприклад, лінійне програмування вирішує задачі в яких цільова функція і обмеження обидва є лінійними. Відомим методом із області лінійного програмування є симплекс-метод.
Метод невизначених множників Лагранжа використовують для спрощення задач оптимізації із обмеженнями до задачі оптимізації без визначених обмежень.
Числове визначення інтегралів
Чисельне інтегрування, що в деяких контекстах також відоме як чисельна квадратура, визначає значення певного заданого інтеграла. У найпопулярніших методах використовують одну із формул Ньютона — Котса (такі як правило середньої точки, правило Сімсона) або квадратури Гауса. Ці методи використовують стратегію за принципом «Розділяй та володарюй», відповідно до якої інтеграл по відносно великій множині значень розбивається на інтеграли по меншим областям. У випадках із більшою кількістю вимірів, коли ці методи стають непомірно неефективними з точки зору обчислюваних зусиль, використовують Метод Монте-Карло або методи Квазі-Монте Карло (див. ).
Диференціальні рівняння
Чисельні методи також використовуються для розрахунку (наближеного) розв'язку диференціальних рівнянь, як для звичайних диференціальних рівнянь, так і для диференціальних рівнянь із частинними похідними.
Диференціальні рівняння із частинними похідними розв'язують шляхом дискретизації рівняння, що приводить їх до скінченномірного підпростору. Це можна здійснити за допомогою методу скінченних елементів, методу скінченних різниць, або методу скінченних об'ємів. Теоретичне обґрунтування цих методів часто використовують теореми функціонального аналізу. Ці методи зводять задачу до розв'язання алгебраїчних рівнянь.
Історія розвитку
Чисельні методи використовувалися ще за часів Ньютона (1642—1727) для розв'язання задач з астрономії, геодезії та обчислення механічних конструкцій. На той час обчислення з використовуванням чисельних методів виконувалися з доволі високою точністю (до восьми знаків після коми). Наприклад, французький математик і астроном Урбен Левер'є(1811 — 1878 рр.), уточнюючи траєкторію руху планети Уран, виявив відхилення від розрахованої траєкторії. Він припустив, що ці відхилення спричиняє інша планета, яка до того не спостерігалась астрономами. Використовуючи чисельні методи, він за півроку обчислив масу і орбіту невідомої планети, що справляє дію на Уран і виводить планету із рівноваги. Один примірник своїх розрахунків Левер'є відразу ж послав Йогану Галле з Берлінської обсерваторії, який отримавши лист 23 вересня 1846 року, негайно почав спостереження і в ту ж ніч дуже близько від місця, вказаного Левер'є, знайшов невідому планету, яку пізніше назвали Нептуном.
Основні види числових методів Прямі й ітеративні методи
Розглянемо задачу розв'язування рівняння
3x3 + 4 = 28
при не відомому значення x.
+ Прямий метод 3x3 + 4 = 28. Віднімемо 4 3x3 = 24. Поділимо на 3 x3 = 8. Отримаємо кубічний корінь x = 2.
Застосуємо ітеративний метод: Метод бісекції для розв'язування рівняння f(x) = 3x3 − 24. Початковими значеннями будуть a = 0, b = 3, f(a) = −24, f(b) = 57.
+ Ітеративний метод a b сер. f(сер.) 0 3 1.5 −13.875 1.5 3 2.25 10.17... 1.5 2.25 1.875 −4.22... 1.875 2.25 2.0625 2.32...
Із цієї таблиці розрахунків ми отримали, що розв'язок лежить між числами 1.875 і 2.0625. Алгоритм може повернути будь-яке значення між цими числами, з похибкою, що становить менше ніж 0.2.
Дискретизація та числове інтегрування
Під час двогодинних автомобільних перегонів, ми виміряли швидкість авто три рази і записали їх у таблицю.
Час 0:20 1:00 1:40 км/год. 140 150 180
Застосувавши дискретизацію ми б прийняти, що швидкість автомобіля була постійною на відрізку часу від 0:00 до 0:40, потім від 0:40 до 1:20 і зрештою від 1:20 до 2:00. Наприклад, загальна відстань пройдена за перші 40 хвилин, тоді б становила приблизно (2/3 год × 140 км/год). Ми можемо розрахувати повну пройдену відстань як + + = , що є прикладом численного інтегрування із використанням Суми Рімана, оскільки переміщення є інтегралом від швидкості.
Статистична обробка експериментальних даних зазвичай ґрунтується на граничних теоремах теорії ймовірностей та вимагає обчислення оцінок в порівнянні з простими формулами. Однак для підвищення якості оцінок необхідна велика кількість даних, і обсяг обчислень може виявитися дуже великим. Тому чисельні методи тут націлені на скорочення обсягу обчислень при збереженні якості результатів. Найефективнішими числовими методами в цій галузі є методи, які застосовують швидке перетворення Фур'є.
Для розв'язання задач апроксимації та обчислення функцій різних класів застосовують чисельні методи інтерполювання, найменших квадратів, ортогоналізації, врівноваження значень, умовної мінімізації та ін. Найактуальнішими є методи кусково-многочленної та раціональної сплайнової апроксимації, а також адаптивної апроксимації та нелінійної за параметром апроксимації.
Числове інтегрування та диференціювання здійснюється на основі означення відповідних операцій, однак через необхідність економії обсягу обчислень та некоректність задачі диференціювання розроблено велику кількість чисельних методів для різних класів функцій та різного роду вихідних даних.
Основою числових методів розв'язання багатьох класів рівнянь є дискретизація задачі з наступним зведенням отриманих, загалом кажучи, нелінійних рівнянь до послідовності систем алгебраїчних рівнянь. У зв'язку з цим чисельні методи можна поділити за способом дискретизації на проєкційні, скінченно-різницеві та проєкційно-різницеві, а за способом розв'язання лінійної системи — на прямі, ітераційні та комбіновані методи.