У обчислювальній математиці ітераційний метод — це математична процедура, яка використовує початкове значення для генерації послідовності дедалі точніших наближених розв'язків для певного класу задач, при цьому -те наближення (яке називається «ітерацією») отримується на основі попередніх.
Конкретна реалізація з критеріями зупинки для заданого ітераційного методу, такого як градієнтний спуск, підйом на вершину (hill climbing), метод Ньютона або квазі-ньютонівські методи на кшталт BFGS, є алгоритмом ітераційного методу або методом послідовних наближень. Ітераційний метод називається збіжним, якщо відповідна послідовність збігається для заданих початкових наближень. Зазвичай виконується математично строгий аналіз збіжності ітераційного методу; однак також поширені евристичні ітераційні методи.
На противагу цьому, прямі методи намагаються розв'язати задачу за допомогою скінченної послідовності операцій. За відсутності похибок округлення прямі методи забезпечували б точний розв'язок (наприклад, розв'язання системи лінійних рівнянь за допомогою методу Гаусса). Ітераційні методи часто є єдиним вибором для нелінійних рівнянь. Проте ітераційні методи також часто корисні навіть для лінійних задач із великою кількістю змінних (іноді порядку мільйонів), де прямі методи були б надто дорогими (а в деяких випадках і неможливими) навіть за наявності найпотужніших обчислювальних ресурсів.
Притягуючи нерухомі точки Якщо рівняння можна подати у вигляді , і розв'язок є притягуючою нерухомою точкою функції , тоді можна почати з точки у басейні притягання точки і задати для , і послідовність збігатиметься до розв'язку . Тут — це -те наближення або ітерація для , а — наступна, тобто -ша ітерація для . Альтернативно, у чисельних методах часто використовують показники степеня в дужках, щоб не плутати їх з індексами іншого значення (наприклад, ). Якщо функція є неперервно диференційовною, достатньою умовою збіжності є те, що похідної строго обмежений одиницею в околі нерухомої точки. Якщо ця умова виконується в самій нерухомій точці, то обов'язково існує достатньо малий окіл (басейн притягання).
Лінійні системи У випадку системи лінійних рівнянь розрізняють два основні класи ітераційних методів: стаціонарні ітераційні методи та більш загальні методи підпросторів Крилова.
Стаціонарні ітераційні методи
Вступ Стаціонарні ітераційні методи розв'язують лінійну систему за допомогою оператора, який наближує початковий оператор, і на основі вимірювання похибки результату () формують «рівняння поправки», для якого цей процес повторюється. Хоча ці методи прості у виведенні, реалізації й аналізі, їх збіжність гарантується лише для обмеженого класу матриць.
Означення Ітераційний метод задається як
,
а для заданої системи лінійних рівнянь з точним розв'язком похибка визначається як
Ітераційний метод називається лінійним, якщо існує матриця , така що
,
і цю матрицю називають ітераційною матрицею. Ітераційний метод з ітераційною матрицею називається збіжним, якщо виконується
Важлива теорема стверджує, що ітераційний метод є збіжним тоді й лише тоді, коли його менший за одиницю, тобто
Основні ітераційні методи базуються на розкладенні матриці в
де матриця повинна легко обертатися. Тоді ітераційний процес визначається як
або, еквівалентно,
Звідси випливає, що ітераційна матриця має вигляд
Приклади Базові приклади стаціонарних ітераційних методів використовують розклад матриці як
де — це лише діагональна частина матриці , — строго нижньотрикутна частина матриці , а — строго верхньотрикутна частина матриці .
Метод Якобі:
Затухаючий метод Якобі:
Метод Гауса–Зейделя:
Метод послідовної верхньої релаксації (SOR):
(SSOR):
Лінійні стаціонарні ітераційні методи також називають .
Методи підпросторів Крилова Методи підпросторів КриловаCharles George Broyden and Maria Terasa Vespucci: Krylov Solvers for Linear Algebraic Systems: Krylov Solvers, Elsevier, ISBN 0-444-51474-0, (2004). працюють шляхом побудови базису послідовності послідовних степенів матриці, помножених на початкову нев'язку (послідовності Крилова). Далі наближення до розв'язку формуються шляхом мінімізації нев'язки в утвореному підпросторі. Типовим представником цього класу є метод спряжених градієнтів (CG), який передбачає, що матриця системи є симетричною додатно визначеною. Для симетричної (можливо, невизначеної) матриці використовується (MINRES). У випадку несиметричних матриць застосовують такі методи, як (GMRES) та (BiCG).
Збіжність методів підпросторів Крилова Оскільки ці методи будують базис, очевидно, що вони збігаються за ітерацій, де — розмір системи. Проте за наявності похибок округлення це твердження не виконується; крім того, на практиці може бути дуже великим, і ітераційний процес досягає достатньої точності набагато раніше. Аналіз цих методів є складним, оскільки він залежить від складної функції спектра оператора.
Передумови Наближений оператор, який використовується у стаціонарних ітераційних методах, може бути також включений у методи підпросторів Крилова, такі як (або ж методи Крилова можна розглядати як прискорені варіанти стаціонарних ітераційних методів). У такому разі вони перетворюють початковий оператор на оператор з кращою обумовленістю. Побудова передумов є окремою великою галуззю наукових досліджень.
Методи послідовних наближень До математичних методів, пов'язаних із послідовними наближеннями, належать:
— для знаходження квадратних коренів Метод простої ітерації Методи знаходження нулів функцій: метод Галлея метод Ньютона
Розв'язування диференціальних рівнянь: теорема Пікара–Ліндельофа про існування розв'язків диференціальних рівнянь методи Рунге–Кутти для чисельного розв'язування диференціальних рівнянь
Історія Джамшід аль-Каші використовував ітераційні методи для обчислення синуса 1° та числа з високою точністю у своїй праці «Трактат про хорду і синус». Один із перших ітераційних методів для розв'язування системи лінійних рівнянь з'явився в листі Гауса до одного зі своїх учнів. Він запропонував розв'язувати систему з чотирьох рівнянь шляхом багаторазового розв'язування тієї складової, для якої нев'язка була найбільшою.
Теорія стаціонарних ітераційних методів набула чіткої і завершеної форми завдяки працям , починаючи з 1950-х років. Метод спряжених градієнтів також було створено в 1950-х роках незалежно , і , однак тоді його суть і сфера застосування були неправильно зрозумілі. Лише у 1970-х роках усвідомили, що методи, засновані на спряженості, дуже ефективно працюють для рівнянь у частинних похідних, особливо еліптичного типу.
Див. також
Вираз замкненої форми
Чисельні методи Методи розв'язання нелінійних рівнянь
Примітки