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

Эта статья посвящена итерационным методам решения систем уравнений. Чтобы узнать о других значениях, см. Релаксация (значения) .

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

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

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

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

Модельная задача теории потенциала

Основная статья: Дискретное уравнение Пуассона

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

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

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

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

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

${\nabla }^{2}\varphi =f\,$

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

$\varphi ^{*}(x,y)={\tfrac {1}{4}}\left(\varphi (x{+}h,y)+\varphi (x,y{+}h)+\varphi (x{-}h,y)+\varphi (x,y{-}h)\,-\,h^{2}f(x,y)\right)\,,$

до сближения.

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

Конвергенция и ускорение

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

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

См. также

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

Ссылки

• Авраам Берман, Роберт Дж. Племмонс, Неотрицательные матрицы в математических науках , 1994, SIAM. ISBN   0-89871-321-8 .
• Ортега, Дж. М.; Рейнбольдт, WC (2000). Итерационное решение нелинейных уравнений со многими переменными . Классика прикладной математики. Том. 30 (Перепечатка изд. Academic Press 1970 г.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). стр. xxvi+572. ISBN  0-89871-461-3 . МР   1744713 .
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 18.3. Методы релаксации» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8 .
• Юсеф Саад , Итеративные методы для разреженных линейных систем , 1-е издание, PWS, 1996.
• Ричард С. Варга, , 2002 г. Матричный итеративный анализ , Второе изд. (издание Prentice Hall 1962 года), Springer-Verlag.
• Дэвид М. Янг-младший. Итеративное решение больших линейных систем , Academic Press, 1971. (перепечатано Dover, 2003).

Дальнейшее чтение

• Саутвелл, Р.В. (1940) Методы релаксации в инженерных науках . Издательство Оксфордского университета, Оксфорд.
• Саутвелл, Р.В. (1946) Методы релаксации в теоретической физике . Издательство Оксфордского университета, Оксфорд.
• Джон. Д. Джексон (1999). Классическая электродинамика . Нью-Джерси: Уайли. ISBN  0-471-30932-Х .
• МНО Садику (1992). Численные методы в электромагнетике . Бока-Ратон: президент CRC.
• П.-Б. Чжоу (1993). Численный анализ электромагнитных полей . Нью-Йорк: Спрингер.
• П. Гривет, П. В. Хоукс, А. Септье (1972). Электронная оптика, 2-е издание . Пергамон Пресс. ISBN   9781483137858 .
• ДВО Хеддл (2000). Электростатические линзовые системы, 2-е издание . ЦРК Пресс. ISBN   9781420034394 .
• Эрвин Каспер (2001). Достижения в области визуализации и электронной физики, Vol. 116, Численный расчет поля для оптики заряженных частиц . Академическая пресса. ISBN   978-0-12-014758-8 .