Релаксация (итерационный метод)

В вычислительной математике, методы релаксации - это итерационные методы для решения систем уравнений, в том числе нелинейных.

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

Методы релаксации важны, особенно при решении линейных систем, используемых для моделирования эллиптических уравнений в частных производных, таких как уравнение Лапласа и его обобщение, уравнение Пуассона. Эти уравнения описывают краевые задачи, в которых значения функции решения задаются на границе области; проблема состоит в том, чтобы вычислить решение также и для его внутренней части. Методы релаксации используются для решения линейных уравнений, возникающих в результате дискретизации дифференциального уравнения, например, с помощью конечных разностей.

Итеративная релаксация решений обычно называется сглаживанием, потому что с некоторыми уравнениями такие как и уравнение Лапласа, оно напоминает многократное применение локального сглаживающего фильтра к вектору решения. Их не следует путать с методами релаксации в математической оптимизации, которые аппроксимируют сложную проблему более простой задачей, «расслабленное» решение которой предоставляет информацию о решении. исходной задачи.

• 1 Модельная задача теории потенциала
• 2 Сходимость и ускорение
• 3 См. также
• 4 Примечания
• 5 Ссылки
• 6 Дополнительная литература

Когда φ - гладкая вещественнозначная функция на действительных числах, ее вторая производная может быть аппроксимирована следующим образом:

$d\; 2\; \phi \; (x)\; dx\; 2\; =\; \phi \; (x\; -\; h)\; -\; 2\; \phi \; (x)\; +\; \phi \; (x\; +\; h)\; h\; 2\; +\; O\; (h\; 2).\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{d\; ^\; \{2\}\; \backslash \; varphi\; (x)\}\; \{\{dx\}\; ^\; \{2\}\}\}\; =\; \{\backslash \; frac\; \{\backslash \; varphi\; (x\; \{-\}\; h)\; -2\; \backslash \; varphi\; (x)\; +\; \backslash \; varphi\; (x\; \{+\}\; h)\}\; \{h\; ^\; \{2\}\}\}\; \backslash ,\; +\; \backslash ,\; \{\backslash \; mathcal\; \{O\}\}\; (h\; ^\; \{2\})\; \backslash ,.\}$

Использование этого в обоих измерениях для функция φ двух аргументов в точке (x, y) и решение для φ (x, y) приводит к:

$\phi \; (x,\; y)\; =\; 1\; 4\; (\phi \; (x\; +\; h,\; y)\; +\; \phi \; (x,\; y\; +\; h)\; +\; \phi \; (x\; -\; h,\; y)\; +\; \phi \; (x,\; y\; -\; h)\; -\; h\; 2\; \nabla \; 2\; \phi \; (x,\; y))\; +\; O\; (h\; 4).\; \{\backslash \; displaystyle\; \backslash \; varphi\; (x,\; y)\; =\; \{\backslash \; tfrac\; \{1\}\; \{4\}\}\; \backslash \; left\; (\backslash \; varphi\; (x\; \{+\}\; h,\; y)\; +\; \backslash \; varphi\; (x,\; y\; \{+\}\; h)\; +\; \backslash \; varphi\; (x\; \{-\}\; h,\; y)\; +\; \backslash \; varphi\; (x,\; y\; \{-\}\; h)\; \backslash ,\; -\; \backslash ,\; h\; ^\; \{2\}\; \{\backslash \; nabla\}\; ^\; \{2\}\; \backslash \; varphi\; (x,\; y)\; \backslash \; right)\; \backslash ,\; +\; \backslash ,\; \{\backslash \; mathcal\; \{O\}\}\; (h\; ^\; \{4\})\; \backslash ,.\}$

Чтобы приблизить решение уравнения Пуассона:

$\nabla \; 2\; \phi \; =\; f\; \{\backslash \; displaystyle\; \{\backslash \; nabla\}\; ^\; \{2\}\; \backslash \; varphi\; =\; f\; \backslash ,\}$

численно на двумерной сетке с шагом сетки h метод релаксации присваивает заданные значения функции φ точкам сетки вблизи границы и произвольные значения внутренним точкам сетки., а затем многократно выполняет присвоение φ: = φ * для внутренних точек, где φ * определяется как:

$\phi \; \ast \; (x,\; y)\; =\; 1\; 4\; (\phi \; (x\; +\; h,\; y)\; +\; \phi \; (x,\; y\; +\; час)\; +\; \phi \; (Икс\; -\; час,\; Y)\; +\; \phi \; (x,\; y\; -\; h)\; -\; час\; 2\; f\; (x,\; y)),\; \{\backslash \; displaystyle\; \backslash \; varphi\; ^\; \{*\}\; (x,\; y)\; =\; \{\; \backslash \; tfrac\; \{1\}\; \{4\}\}\; \backslash \; left\; (\backslash \; varphi\; (x\; \{+\}\; h,\; y)\; +\; \backslash \; varphi\; (x,\; y\; \{+\}\; h)\; +\; \backslash \; varphi\; (x\; \{-\}\; h,\; y)\; +\; \backslash \; varphi\; (x,\; y\; \{-\}\; h)\; \backslash ,\; -\; \backslash ,\; h\; ^\; \{2\}\; f\; (x,\; y)\; \backslash \; right)\; \backslash ,,\}$

до сходимости.

Метод, описанный здесь для два измерения, легко обобщается на другие е количество измерений.

Хотя метод сходится в общих условиях, он обычно прогрессирует медленнее, чем конкурирующие методы. Тем не менее, изучение методов релаксации остается основной частью линейной алгебры, поскольку преобразования теории релаксации обеспечивают отличные предварительные условия для новых методов. Действительно, выбор предобуславливателя часто более важен, чем выбор итерационного метода.

Многосеточные методы могут использоваться для ускорения работы методов. Сначала можно вычислить приближение на более грубой сетке - обычно с двойным интервалом 2h - и использовать это решение с интерполированными значениями для других точек сетки в качестве начального назначения. Затем это также можно сделать рекурсивно для более грубых вычислений.

• В линейных системах двумя основными классами методов релаксации являются стационарные итерационные методы и более общий Методы подпространства Крылова.
• Метод Якоби - это простой метод релаксации.
• Метод Гаусса – Зейделя является усовершенствованием метода Якоби.
• Последовательная избыточная релаксация может применяться к любому из методов Якоби и Гаусса – Зейделя для ускорения сходимости.
• Многосеточные методы

1. ^ Ортега, JM; Райнбольдт, В. К. (2000). Итерационное решение нелинейных уравнений нескольких переменных. Классика прикладной математики. 30 (Перепечатка изд. 1970 Academic Press). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). С. xxvi + 572. ISBN 0-89871-461-3. MR 1744713. CS1 maint: ref = harv (ссылка )
2. ^ Ричард С. Варга 2002 Матричный итерационный анализ, второе издание (изд. Прентис Холл, 1962 г.), Springer-Verlag.
3. ^ Дэвид М. Янг, младший Итерационное решение больших линейных систем, Academic Press, 1971. (перепечатано Dover, 2003 г.))
4. ^ Авраам Берман, Роберт Дж. Племмонс, Неотрицательные матрицы в математических науках, 1994, SIAM. ISBN 0-89871-321-8.
5. ^(1983). «16 итерационных методов для линейных неравенств и линейных программ (особенно 16.2 методов релаксации и 16.4 сохраняющих разреженность итерационных алгоритмов SOR для линейного программирования)». Линейное программирование. Нью-Йорк: John Wiley Sons Inc., стр. 453–464. ISBN 0-471-09725-X. MR 0720547. CS1 maint: ref = harv (link )
6. ^Goffin, J. -L. (1980). "Релаксационный метод решения систем линейных неравенств". Math. Oper. Res. 5 (3): 388–414. doi : 10.1287 / moor.5.3.388. JS ТОР 3689446. MR 0594854. CS1 maint: ref = harv (ссылка )
7. ^ (1986). Математическое программирование: теория и алгоритмы. Эгон Балас (предисловие) (Перевод Стивена Вайды из французского изд. (1983 Paris: Dunod)). Чичестер: публикация Wiley-Interscience. John Wiley Sons, Ltd., стр. Xxviii + 489. ISBN 0-471-90170-9. MR 0868279. (Второе издание, 2008 г., на французском языке: Programmation mathématique: Théorie et algorithmes. Editions Tec Doc, Paris, 2008. xxx + 711 с. ISBN 978-2-7430-1000 -3. MR 2571910 ). CS1 maint: ref = harv (ссылка )
8. ^ Юсеф Саад, Итерационные методы для разреженных линейных систем, 1-е издание, PWS, 1996.
9. ^Уильям Л. Бриггс, Ван Эмден Хенсон и Стив Ф. Маккормик (2000), A Multigrid Tutorial Архивировано 06.10.2006 на Wayback Machine (2-е изд.), Филадельфия: Общество промышленной и прикладной математики, ISBN 0-89871-462-1.

• Abraham Berman, Роберт Дж. Племмонс, Неотрицательные матрицы в математических науках, 1994, SIAM. ISBN 0-89871-321-8.
• Ортега, JM; Rheinboldt, WC (2000). Итерационное решение нелинейных уравнений с несколькими переменными. Classics in Applied Mathematics. 30 (Reprint of the 1970 Academic Press ed.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. тики (SIAM). С. xxvi + 572. ISBN 0-89871-461-3. MR 1744713. CS1 maint: ref = harv (ссылка )
• Press, WH; Teukolsky, SA; Веттерлинг, В. Т.; Фланнери, Б. П. (2007). «Раздел 18.3. Методы релаксации». Численные рецепты: Искусство научных вычислений (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8.
• Юсеф Саад, Итерационные методы для разреженных линейных систем, 1-е издание, PWS, 1996.
• Ричард С. Варга 2002 Матричный итерационный анализ, второе издание (издание Прентис Холл, 1962 г.), Springer-Verlag.
• Дэвид М. Янг, младший Итерационное решение больших линейных систем, Academic Press, 1971. ( перепечатано Dover, 2003)

• Саутвелл Р.В. (1940) Методы релаксации в технических науках. Издательство Оксфордского университета, Оксфорд.
• Саутвелл Р.В. (1946) Методы релаксации в теоретической физике. Oxford University Press, Oxford.
• John. D. Jackson (1999). Classical Electrodynamics. New Jersey: Wiley. ISBN 0-471- 30932-X.
• M.N.O. Садику (1992). Численные методы в электромагнетизме. Бока-Ратон: CRC Pres.
• P.-B. Чжоу (1993). Численный анализ электромагнитных полей. Нью-Йорк: Springer.