Стационарные и релаксационные методы

Стационарные итерационные методы решают линейную систему путем расщепления матрицы и многократного применения фиксированного правила обновления; классические схемы Якоби, Гаусса-Зейделя и последовательной верхней релаксации являются основополагающими примерами.

Definition

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

Scope

Эта тема охватывает структуру расщепления матрицы, итерации Якоби и Гаусса-Зейделя, последовательную верхнюю релаксацию и выбор оптимального параметра релаксации, критерий сходимости по спектральному радиусу, а также роль, которую эти простые итерации играют сегодня в качестве сглаживателей в мультисеточных методах и в качестве предобуславливателей.

Core questions

• Как расщепление матрицы приводит к итерации с фиксированной точкой для линейной системы?
• В чем различие между методами Якоби и Гаусса-Зейделя, и почему Гаусс-Зейдель обычно быстрее?
• Как верхняя релаксация ускоряет сходимость, и как выбирается оптимальный параметр?
• При каких условиях на матрицу эти итерации сходятся?

Key theories

Расщепление матрицы и критерий спектрального радиуса

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

Последовательная верхняя релаксация

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

Mechanisms

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

Clinical relevance

Хотя стационарные методы обычно слишком медленны, чтобы быть конкурентоспособными автономными решателями для больших систем, они остаются важными в качестве сглаживателей в основе мультисеточных методов, как простые предобуславливатели для методов Крылова и как легко распараллеливаемые строительные блоки; в частности, Гаусс-Зейдель и взвешенный Якоби повсеместно используются в современных многоуровневых решателях.

History

Итерации Якоби и Гаусса-Зейделя датируются девятнадцатым веком, в то время как последовательная верхняя релаксация и ее строгая теория сходимости были разработаны Дэвидом Янгом и Ричардом Варгой в 1950-х годах; хотя позже они были вытеснены методами Крылова и мультисеточными методами в качестве основных решателей, эти итерации были возрождены как важные компоненты многоуровневых и предобусловленных схем.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

Почему Гаусс-Зейдель обычно быстрее Якоби?

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

Если эти методы медленные, почему их все еще изучают?

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