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

Чисельні ме́тоди, або Числові методи[1][2] (також числови́й ана́ліз) — методи наближеного або точного розв'язування задач чистої або прикладної математики, які ґрунтуються на побудові послідовності дій над скінченною множиною чи́сел. Дана наука вивчає алгоритми, які застосовують числову апроксимацію (на відміну від загальних символьних обчислень) для розв'язування задач математичного аналізу (чим відрізняється від дискретної математики). Основні вимоги до числових методів, щоб вони були стійкими та збіжними.

Класи задач, що розв'язують за допомогою числових методів

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

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

Розрахунок значень функцій

Інтерполяція: Ми спостерігали за тим, як змінювалася температура в приміщенні від 20 градусів за Цельсієм в 1:00 до 14 градусів в 3:00. Відповідно до лінійної інтерполяції ми можемо встановити, що о 2:00 температура становила 17 градусів, і 18.5 градусів в 1:30. Екстраполяція: Якщо валовий внутрішній продукт країни зростав в середньому на 5 % на рік і минулого року його обсяг становив 100 мільярдів доларів, ми можемо екстраполювати, що він становитиме 105 міль'ярдів доларів цього року. Пряма побудована із 20 точок Регресія: Лінійна регресія дозволяє при даних n точках розрахувати пряму, яка проходитиме настільки близько наскільки це можливо до всіх цих n точок. Скільки коштує склянка лимонаду? Оптимізація: Припустимо ви продаєте лимонад у кіоску, і підрахували, що за $1, ви можете продати 197 склянок лимонаду за день, і що піднявши ціну на кожні $0.01, ви продасте на одну склянку лимонаду на день менше. Якщо ви б виставили ціну в $1.485, ви б збільшили свій заробіток, але так як ви повинні округлити суму до цілих центів, ви можете оцінити склянку лимонаду в $1.48 або $1.49, що дасть вам максимальний прибуток в $220.52 на день. Напрям вітру показано синім, істина траєкторія чорним, результат методу Ейлера червоним. Диференціальне рівняння: Якщо ви встановите 100 вентиляторів у кімнаті, так що вони дують з одного боку кімнати у інший і кинете у цей вітер пір'ячко, що відбудеться тоді? Пірїнка буде рухатися по повітряних потоках, і рух цей може бути досить складним. Одним із методів апроксимації, є виміряти швидкість, з яким вітер дує біля місця де знаходиться пір'їнка в кожну секунду, і продовжити його рух уявним способом, так ніби воно продовжує рухатися по прямій з тією ж швидкістю протягом секунди, перед тим як швидкість вітру буде виміряно знов. Це називається Методом Ейлера для вирішення звичайного диференціального рівняння.

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

Інтерполяція, екстраполяція і регресія

Інтерполяція вирішує наступну задачу: дані значення деякої невідомої функції у вигляді набору точок, яке значення матиме функція в деякій іншій точці, між цими даними точками?

Екстраполяція дуже подібна до інтерполяції, але необхідно знайти значення невідомої функції у точці, що заходиться за межами даних точок.

Регресія також подібна до попередніх методів, але враховує те, що дані можуть бути не точними. Дані деякі точки, і вимірювання значень деякої функції в цих точках (що містять похибку), необхідно встановити невідому функцію. Популярним методом вирішення цієї задачі є метод найменших квадратів.

Розв'язання рівнянь і систем рівнянь

Іншою фундаментальною задачею є розрахунок рішення для даного рівняння. Як правило виділяють два випадки, в залежності від того чи є рівняння лінійним чи ні. Наприклад, рівняння $2x+5=3$ є лінійним рівнянням, а $2x^{2}+5=3$ не є таким.

Багато зусиль було покладено на розробку методів для вирішення систем лінійних рівнянь. До стандартних методів, які використовують розклад матриць відносяться Метод Гауса, LU-розклад матриці, Розклад Холецького для симетричних (або ермітових матриць) і додатньоозначених матриць, і QR-розклад матриці для не квадратних матриць. Ітеративні методи, такі як Метод Якобі, Метод Гауса — Зейделя, Метод релаксації і метод сполучених градієнтів як правило використовують для великих систем рівнянь. Загальні ітеративні методи можуть застосовувати розділення матриць.

Методи розв'язання нелінійних рівнянь дозволяють вирішити нелінійні рівняння і знайти їх корені (такі аргументи при яких функція дорівнює нулю). Якщо функція диференційована і її похідна відома, тоді як правило використовують метод Ньютона. Іншою технікою, яку використовують для вирішення нелінійних рівнянь є лінеаризація.

Вирішення задач власного чи сингулярного розкладу

Декілька важливих задач можна сформулювати і розв'язати застосовуючи власний розклад або сингулярний розклад матриць. Наприклад, алгоритм стиснення спектральних зображень[3] оснований на сингулярному розкладі. В статистиці відповідний інструмент називається методом головних компонент.

Оптимізація

Відповідно до задачі оптимізації, необхідно знайти таку точку, в який функція приймає максимальне (або мінімальне) значення. Часто, ця точка також повинна задовольняти певним обмеженням.

Далі область дослідження задач оптимізації розділяється на декілька напрямків, в залежності від форми цільової функції і заданих обмежень. Наприклад, лінійне програмування вирішує задачі в яких цільова функція і обмеження обидва є лінійними. Відомим методом із області лінійного програмування є симплекс-метод.

Метод невизначених множників Лагранжа використовують для спрощення задач оптимізації із обмеженнями до задачі оптимізації без визначених обмежень.

Числове визначення інтегралів

Чисельне інтегрування, що в деяких контекстах також відоме як чисельна квадратура, визначає значення певного заданого інтеграла. У найпопулярніших методах використовують одну із формул Ньютона-Коте (такі як правило середньої точки, правило Сімсона) або квадратури Гауса. Ці методи використовують стратегію за принципом «Розділяй та володарюй», відповідно до якої інтеграл по відносно великій множині значень розбивається на інтеграли по меншим областям. У випадках із більшою кількістю вимірів, коли ці методи стають непомірно неефективними з точки зору обчислюваних зусиль, використовують Метод Монте-Карло або методи Квазі-Монте Карло (див. Інтегрування Монте-Карло).

Диференціальні рівняння

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

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

Історія розвитку

Чисельні методи використовувалися ще за часів Ньютона (1642—1727) для розв'язання задач з астрономії, геодезії та обчислення механічних конструкцій. На той час обчислення з використовуванням чисельних методів виконувалися з доволі високою точністю (до восьми знаків після коми). Наприклад, французький математик і астроном Урбен Левер'є(1811 — 1878 рр.), уточнюючи траєкторію руху планети Уран, виявив відхилення від розрахованої траєкторії. Він припустив, що ці відхилення спричиняє інша планета, яка до того не спостерігалась астрономами. Використовуючи чисельні методи, він за півроку обчислив масу і орбіту невідомої планети, що справляє дію на Уран і виводить планету із рівноваги. Один примірник своїх розрахунків Левер'є відразу ж послав Йогану Галле з Берлінської обсерваторії, який отримавши лист 23 вересня 1846 року, негайно почав спостереження і в ту ж ніч дуже близько від місця, вказаного Левер'є, знайшов невідому планету, яку пізніше назвали Нептуном.

Основні види числових методів

Прямі і ітеративні методи

Розглянемо задачу вирішення рівняння

3x³ + 4 = 28

при не відомому значення x.

Прямий метод
	3x³ + 4 = 28.
Віднімемо 4	3x³ = 24.
Поділимо на 3	x³ = 8.
Отримаємо кубічний корінь	x = 2.

Застосуємо ітеративний метод: Метод бісекції для вирішення рівняння f(x) = 3x³ − 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 км/год). Ми можемо розрахувати повну пройдену відстань як 7001933000000000000♠93.3 км + 7002100000000000000♠100 км + 7002120000000000000♠120 км = 7002313300000000000♠313.3 км, що є прикладом численного інтегрування із використанням Суми Рімана, оскільки переміщення є інтегралом від швидкості.

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

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

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

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

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

При ітераційних методах можна віднайти розв'язок задачі, використовуючи низку формул, де кожний новий уточнений наближений розв'язок $x_{k}$ обчислюється через попередній $x_{k-1}$ , тобто $x_{k}=f(x_{k-1}$ ). Ітераційний процес пошуку наближеного розв'язку завершується тоді, коли виконається умова

$|x_{k}-x_{k-1}|\leq \varepsilon$ ,

де $k$ — номер ітерації ( $k=0,1,2,3,\dots$ ).

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

Характеристики числових методів

Для оцінки числових методів, вводять такі їх основні характеристики:

трудомісткість;
порядок методу;
збіжність;
швидкість збіжності;
стійкість до похибок обчислень;
стійкість до похибок вихідних даних.

Трудомісткість

Трудомісткість методу оцінюється кількістю та якістю обчислень, необхідних для досягнення достатньо близького наближення розв'язку задачі.

Порядок методу

Порядок методу — вимоги до знань про функції, що входять у математичне формулювання задачі (наприклад, використання в методі похідних цих функцій):

метод нульового порядку — використовує тільки значення цих функцій;
метод першого порядку — використовує значення функцій і їх перших похідних;
метод другого порядку — використовує значення і функцій та їх перших і других похідних і т. д.

Збіжність методу

Числовий метод називається таким, що збігається, якщо наближення $x_{k}$ прямує до розв'язку $x_{*}$ зі збільшенням $k$ .

Основні швидкості збіжності методів:

1. Лінійна збіжність. Послідовність ${x_{k}}(k=0,1,2,\dots )$ збігається до розв'язку $x_{*}$ лінійно (або із швидкістю геометричної прогресії), якщо існують числа $q\in (0,1)$ і $k_{0}>0$ такі, що

|x^{k+1}-x^{*}|\leq q|x^{k}-x^{*}|

для всіх

k\geq k_{0}

.

Тут норма $|x-y|$ означає відстань між $x$ і $y$ .

2. Надлінійна збіжність. Послідовність ${x_{k}}(k=0,1,2,\dots )$ збігається до розв'язку $x_{*}$ надлінійно, якщо існує послідовність ${q_{k}}(k=0,1,2,\dots ),q_{k}\in (0,1)$ для всіх $k$ , така, що

|x^{k+1}-x^{*}|\leq q_{k}|x^{k}-x^{*}|

і

q_{k}\to 0

при

k\to \infty

.

3. Квадратична збіжність. Послідовність ${x_{k}}(k=0,1,2,\dots )$ збігається до розв'язку $x_{*}$ квадратично, якщо існують числа $C>0$ і $k_{0}>0$ такі, що

|x^{k+1}-x^{*}|\leq C|x^{k}-x^{*}|^{2}

для всіх

k\geq k_{0}

.

Стійкі та збіжні чисельні методи

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

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

Основне питання теорії числових методів: створення методів, які задовольняють вимоги високої точності, стійкості та економічності. Розробка чисельних методів, що задовольняють ці вимоги, є складною задачею оптимізації цих методів.

Стійкість до похибок обчислень

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

Стійкість до похибок вихідних даних

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

Утворення та поширення похибок

Вивчення природи помилок є важливою частиною числових методів. Існує декілька основних шляхів, через які можуть виникати помилки при вирішені задач.

Округлення

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

Помилка відсікання та дискретизації

Похибка відсікання виникає коли ітеративний метод завершує свій розрахунок або математична процедура є наближеною, і наближене рішення відрізняється від точного рішення. Аналогічним чином, процедура дискретизації вносить похибку дискретизації, оскільки рішення дискретної задачі не співпадатиме точно із рішенням неперервної задачі. Наприклад, якщо ми розрахуємо рішення рівняння $3x^{3}+4=28$ ітеративним способом, то після 10 ітерацій ми матимемо рішення, що корінь дорівнюватиме близько 1,99 (наприклад). Таким чином похибка відсікання становить 0,01.

Як тільки була отримана похибка, вона як правило буде поширюватися на усі наступні розрахунки. Наприклад, ми вже відмічали що виконання операції + на калькуляторі (або комп'ютері) не буде точною. Звідси випливає, що виконання розрахунку виду $a+b+c+d+e$ буде ще більш неточним.

Що означає, коли говорять що похибка відсікання виникає у разі коли математична процедура є наближеною? Ми знаємо, що при точному інтегруванні функції необхідно знайти суму нескінченної кількості трапецій. Але на практиці можливо розрахувати суму тільки скінченної кількості трапецій, і таким чином застосувати наближену математичну процедуру. Аналогічно, при диференціюванні функції, елемент диференціювання наближається до нуля, але на практиці ми можемо застосувати лише обмежене значення величини елементу диференціювання.

Розрахункова стійкість і добре обумовлені задачі

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

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

Таким чином алгоритм який вирішує добре обумовлену задачу може бути або розрахунково стійким або нестійким. Задачею числового аналізу є знайти стійкий алгоритм вирішення добре обумовленої математичної задачі. Наприклад, розрахунок квадратного кореня числа 2 (наближене значення якого становить 1.41421) це добре обумовлена задача. Більшість алгоритмів вирішують цю задачу починаючи із початкового наближеного значення x₀ для ${\sqrt {2}}$ , наприклад x₀ = 1.4, і потім розраховують покращені оцінки x₁, x₂, і так далі. Одним із відомих методів є Вавилонський метод, який задається як послідовність розрахунків x_k+1 = x_k/2 + 1/x_k. Інший метод, назвемо його Метод X, виглядатиме як x_k+1 = (x_k² − 2)² + x_k. (Це метод простої ітерації для розв'язання рівняння $x=(x^{2}-2)^{2}+x=f(x)$ , рішенням якого є ${\sqrt {2}}$ . Ітеративний метод завжди збігається до правого кореня, оскільки $f(x)\geq x$ . Оскільки $x_{1}=1.4<{\sqrt {2}}$ збігається, а $x_{1}=1.42>{\sqrt {2}}$ є розбіжним.) Розрахуємо декілька ітерацій за цими методами, вони наведені у таблиці, при чому початковими значеннями x₀ = 1.4 і x₀ = 1.42.

Вавилонський метод	Вавилонський метод	Метод X	Метод X
x₀ = 1.4	x₀ = 1.42	x₀ = 1.4	x₀ = 1.42
x₁ = 1.4142857...	x₁ = 1.41422535...	x₁ = 1.4016	x₁ = 1.42026896
x₂ = 1.414213564...	x₂ = 1.41421356242...	x₂ = 1.4028614...	x₂ = 1.42056...
		...	...
		x_1000000 = 1.41421...	x₂₇ = 7280.2284...

Зауважте, що Вавилонський метод наближається до рішення дуже швидко завдяки вибраному початковому значенню, в той час як Метод X наближається дуже повільно при початковому значенні в x₀ = 1.4 і є розбіжним при початковому значенні x₀ = 1.42. Оскільки Вавилонський метод є розрахунково стійким, в той час як Метод X є розрахунково не стійким.

Див. також

Примітки

Російсько-український словник наукової термінології: Математика. Фізика. Техніка. Науки про Землю та Космос / НАН України. Комітет наукової термінології; Інститут мовознавства ім. О. О. Потебні / Гейченко В. В., Завірюхіна В. М., Зеленюк О. О., Коломієць В. Г., Кратко М. І. Ред. Митропольський Ю. О. — К.: Наук. думка, 1998. — 888 с., C. 330. — ISBN 5-12-004273-2.
Вступ до числових методів: Навч. посіб. для вищ. закл. освіти / П. І. Каленюк, В. А. Бакалець, І. І. Бакалець, Н. В. Горбачова, П. Л. Сохан; Держ. ун-т «Львів. політехніка». — Л., 2000. — 145 c. — (Математика для інженерів). — Бібліогр.: 20 назв.
The Singular Value Decomposition and Its Applications in Image Compression Архівовано 4 жовтня 2006 у Wayback Machine.

Посилання

Література

Вступ до числових методів: Навч. посіб. для вищ. закл. освіти / П. І. Каленюк, В. А. Бакалець, І. І. Бакалець, Н. В. Горбачова, П. Л. Сохан; Держ. ун-т «Львів. політехніка». — Л., 2000. — 145 c. — (Математика для інженерів). — Бібліогр.: 20 назв.
Чисельні методи: [навч. посіб.] / М. В. Кутнів. — Л. : Вид-во «Растр-7», 2010. — 288 с. — Бібліогр.: с. 285—286 (23 назви). — ISBN 978-966-2004-44-1
Чисельні методи: Підруч. для студ. вищ. навч. закл. / Г. Г. Цегелик; Львів. нац. ун-т ім. І.Франка. — Л., 2004. — 407 c. — Бібліогр.: 32 назв.
Фельдман Л. П., Петренко А. І., Дмитрієва О. А. Чисельні методи в інформатиці. — К.: Видавнича група BHV, 2006. — 480 c.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы: Учеб. пособие. — М.: Наука, 1987. — 600с.
Гулин И. А., Самарский А. А. Численные методы. М.: Наука, 1989. — 432 с.
Иванов В. В. Методы вычислений на ЭВМ: Справочное пособие / В. В. Иванов — К.: Наукова думка, 1986. — 564 с.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Російсько-український словник наукової термінології: Математика. Фізика. Техніка. Науки про Землю та Космос / НАН України. Комітет наукової термінології; Інститут мовознавства ім. О. О. Потебні / Гейченко В. В., Завірюхіна В. М., Зеленюк О. О., Коломієць В. Г., Кратко М. І. Ред. Митропольський Ю. О. — К.: Наук. думка, 1998. — 888 с., C. 330. — ISBN 5-12-004273-2.

[2] Вступ до числових методів: Навч. посіб. для вищ. закл. освіти / П. І. Каленюк, В. А. Бакалець, І. І. Бакалець, Н. В. Горбачова, П. Л. Сохан; Держ. ун-т «Львів. політехніка». — Л., 2000. — 145 c. — (Математика для інженерів). — Бібліогр.: 20 назв.

[3] The Singular Value Decomposition and Its Applications in Image Compression Архівовано 4 жовтня 2006 у Wayback Machine.