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

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

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

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

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

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

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

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

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

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

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

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

Схождение и ускорение [ править ]

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ а б Ортега, JM; Райнбольдт, WC (2000). Итерационное решение нелинейных уравнений нескольких переменных . Классика прикладной математики. 30 (Перепечатка изд. Изд. Academic Press 1970 г.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). С. xxvi + 572. ISBN 0-89871-461-3. Руководство по ремонту  1744713 .
  2. ^ a b c d Ричард С. Варга 2002 Матричный итерационный анализ , второе изд. (из издания Prentice Hall 1962 г.), Springer-Verlag.
  3. ^ a b c d Дэвид М. Янг младший Итерационное решение больших линейных систем , Academic Press, 1971 г. (перепечатано Dover, 2003 г.)
  4. ^ a b Абрахам Берман, Роберт Дж. Племмонс , Неотрицательные матрицы в математических науках , 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. Руководство по ремонту  0720547 . CS1 maint: discouraged parameter (link)
  6. ^ Гоффин, Ж.-Л. (1980). «Релаксационный метод решения систем линейных неравенств». Математика. Опер. Res . 5 (3): 388–414. DOI : 10.1287 / moor.5.3.388 . JSTOR 3689446 . Руководство по ремонту 0594854 .  
  7. ^ a b Минукс, М. (1986). Математическое программирование: теория и алгоритмы . Эгон Балас (предисловие) (Перевод Стивена Вайды из французского изд. (1983 Paris: Dunod)). Чичестер: публикация Wiley-Interscience. John Wiley & Sons, Ltd., стр. Xxviii + 489. ISBN 0-471-90170-9. Руководство по ремонту  0868279 . (Второе изд., 2008 г., на французском языке: Математическое программирование: Теория и алгоритмы . Издания Tec & Doc, Париж, 2008 г. xxx + 711 стр.). CS1 maint: discouraged parameter (link)
  8. ^ a b Юсеф Саад , Итерационные методы для разреженных линейных систем , 1-е издание, PWS, 1996.
  9. ^ Уильям Л. Бриггс, Ван Эмден Henson, и Стив Ф. McCormick (2000), многосеточным Учебник архивации 2006-10-06 в Wayback Machine (2е изд.), Филадельфия: Общество промышленной и прикладной математики , ISBN 0- 89871-462-1 . 

Ссылки [ править ]

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