Расслабление (итерационный метод) - Relaxation (iterative method)

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

Были разработаны методы релаксации для решения больших редкий линейные системы, возникшие как конечно-разностный дискретизации из дифференциальные уравнения.^[2][3] Они также используются для решения линейных уравнений для линейный метод наименьших квадратов проблемы^[4] а также для систем линейных неравенств, например возникающих в линейное программирование.^[5][6][7] Они также были разработаны для решения нелинейных систем уравнений.^[1]

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

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

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

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

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

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

${ displaystyle 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}) ,.}$

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

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

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

${ displaystyle 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) ,,}$

до схождения.^[3][2]

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

Схождение и ускорение

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

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

Смотрите также

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

Примечания

Рекомендации

• Авраам Берман, Роберт Дж. Племмонс, Неотрицательные матрицы в математических науках, 1994, SIAM. ISBN  0-89871-321-8.
• Ортега, Дж. М .; Райнбольдт, В. К. (2000). Итерационное решение нелинейных уравнений с несколькими переменными. Классика прикладной математики. 30 (Перепечатка изд. Academic Press 1970 г.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). С. xxvi + 572. ISBN  0-89871-461-3. МИСТЕР  1744713.CS1 maint: ref = harv (связь)
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (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-X.
• M.N.O. Садику (1992). Численные методы в электромагнетизме. Бока-Ратон: CRC Pres.
• П.-Б. Чжоу (1993). Численный анализ электромагнитных полей.. Нью-Йорк: Спрингер.