Метод релаксації

У числовій математиці методи релаксації — ітераційні методи для вирішення систем рівнянь, включаючи нелінійні системи.

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

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

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

Синоніми ред.

Ітеративна релаксація розчинів зазвичай називається згладжуванням, оскільки релаксація деяких рівнянь (наприклад, рівняння Лапласа) нагадує повторне застосування локального згладжувального фільтра до вектора розчину. Інша назва — стаціонарний лінійний ітераційний метод.

Модельна проблема теорії потенціалу ред.

Нехай $\phi$ — гладка дійснозначна функція на дійсних чисел, її другу похідну можна апроксимувати за допомогою:

${\frac {d^{2}\phi \left(x\right)}{dx^{2}}}={\frac {\phi \left(x-h\right)-2\phi \left(x\right)+\psi \left(x+h\right)}{n^{2}}}+\theta (h^{2})$

Використовуючи це в обох вимірах для функції $\phi$ двох аргументів у точці $\left(x,y\right)$ та розв'язання для $\phi \left(x,y\right)$ , виникає результат:

$\phi \left(x,y\right)={\frac {\phi \left(x+h\right)i}{4}}+\phi \left(x-h\_3y\right)+\phi \left(x\right)y-h-h^{2}\nabla ^{2}\phi \left(x,y\right)+\mathrm {O} \left(h^{4}\right)$

Щоб наблизити рішення рівняння Пуассона:

$\nabla ^{2\phi }=f$

Чисельно на двовимірні сітки з відстані сітки $h$ , метод релаксації привласнює задані значення функції $\phi$ до точок сітки поблизу граничних та довільних значень до внутрішніх точок сітки, а потім кілька разів виконує призначення $\phi :=\phi ^{*}$ на внутрішні точки, де $\phi ^{*}$ визначається:

$\phi ^{*}\left(x,y\right)={\frac {\phi \left(x+h,y\right)+\phi \left(x,y+h\right)+\phi \left(x-h,y\right)+\phi \left(x,y-h\right)-h^{2}*f\left(x,y\right)}{4}}$ , до зближення.

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

Збіжність та прискорення ред.

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

Багатогранні методи можуть бути використані для прискорення методів. Спочатку можна обчислити наближення на грубій сітці — зазвичай подвійний двогодинний інтервал — і використовувати це рішення з інтерпольованими значеннями для інших точок сітки як початкове призначення. Тоді це також можна зробити рекурсивно для менш точного обчислення.

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

Джерела ред.

Ortega, J. M.; Rheinboldt, W. C. (2000). Iterative solution of nonlinear equations in several variables. Classics in Applied Mathematics. 30 (Reprint of the 1970 Academic Press ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xxvi+572. ISBN 0-89871-461-3. MR 1744713.
Richard S. Varga 2002 Matrix Iterative Analysis, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
David M. Young, Jr. Iterative Solution of Large Linear Systems, Academic Press, 1971. (reprinted by Dover, 2003)
Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8.
Murty, Katta G. (1983). «16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)». Linear programming. New York: John Wiley & Sons Inc. pp. 453—464. ISBN 0-471-09725-X. MR 0720547.
Goffin, J.-L. (1980). «The relaxation method for solving systems of linear inequalities». Math. Oper. Res. 5 (3): 388—414. doi:10.1287/moor.5.3.388. JSTOR 3689446. MR 0594854.
Minoux, M. (1986). Mathematical programming: Theory and algorithms. Egon Balas (foreword) (Translated by Steven Vajda from the (1983 Paris: Dunod) French ed.). Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed., in French: Programmation mathématique: Théorie et algorithmes. Editions Tec & Doc, Paris, 2008. xxx+711 pp. ISBN 978-2-7430-1000-3. MR2571910).
Yousef Saad, Iterative Methods for Sparse Linear Systems, 1st edition, PWS, 1996.
William L. Briggs, Van Emden Henson, and Steve F. McCormick (2000), A Multigrid Tutorial (2nd ed.), Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-462-1.
Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8.
Richard S. Varga 2002 Matrix Iterative Analysis, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
David M. Young, Jr. Iterative Solution of Large Linear Systems, Academic Press, 1971. (reprinted by Dover, 2003).