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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Історія розвинення[ред.ред. код]

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

Основні види чисельних методів[ред.ред. код]

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

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

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

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

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

|x_k - x_{k-1}| \le \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^*| \le q|x^k - x^*| для всіх k \ge 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^*| \le q_k|x^k - x^*| і q_k\to0 при k\to\infty.

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

|x^{k+1} - x^*| \le C|x^k - x^*|^2 для всіх k \ge k_0.

Стійкість до погрішностей обчислень[ред.ред. код]

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

Стійкість до погрішностей у відправних даних[ред.ред. код]

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

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

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

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

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

Див. також[ред.ред. код]

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

Посилання[ред.ред. код]

Література[ред.ред. код]

  • Фельдман Л. П., Петренко А. І., Дмитрієва О. А. Чисельні методи в інформатиці. — К.: Видавнича група BHV, 2006. — 480 c.
  • Волков Е. А. Численные методы: Учеб. пособие для вузов. — М.: Наука, 1987. — 248с.
  • Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы: Учеб. пособие. — М.: Наука, 1987. — 600с.
  • Гулин И. А., Самарский А. А. Численные методы. М.: Наука, 1989. — 432 с.
  • Бахвалов Н. С., Лапин А. В., Чижонков Е. В. Численные методы в задачах и упражнениях. М.: Высшая школа, 2000. — 190 с.
  • Иванов В. В. Методы вычислений на ЭВМ: Справочное пособие / В. В. Иванов — К.: Наукова думка, 1986. — 564 с.


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.