§ 7. Метод Зейделя

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

Систему (1) можно представить в виде

где

Отсюда получаем

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

собственные значения матрицы являются корнями уравнения .

Таким образом, необходимое и достаточное условие сходимости метода Зейделя можно сформулировать следующим образом: все корни уравнения

должны быть по модулю меньше 1.

Часто можно предложить более удобные для применения достаточные условия сходимости метода Зейделя.

Задача 1. Пусть при всех

Получить оценку

Рис. 6.7.1

Рис. 6.7.2

Рис. 6.7.3

Проблема решения систем линейных уравнений является модельной относительно более сложных задач решения систем нелинейных уравнений и минимизации функций многих переменных. Для перенесения метода на более сложные задачи важно понять его наиболее «грубые» качественные свойства, обеспечивающие сходимость. С этой целью наиболее желательно получить геометрическую интерпретацию метода. Обозначим через плоскость . При получении приближения , из приближения происходит перемещение приближения параллельно оси до пересечения с плоскостью . Таким образом, геометрически метод Зейделя состоит в циклическом перемещении точек, соответствующих последовательно получаемым приближениям, параллельно координатным осям до пересечения с плоскостями . Рис. иллюстрируют при случаи, когда метод Зейделя сходится, расходится, имеет цикл (как говорят, «зацикливается»). Сравнение первых двух рисунков показывает, что сходимость метода Зейделя может изменить характер при перестановке уравнений.

Особенно интересная геометрическая картина возникает в случае, когда матрица А симметричная.

Теорема. Пусть А — вещественная симметричная положительно определенная матрица. Тогда метод Зейделя сходится.

Доказательство. При симметричной А имеем

Если то при , поэтому функция имеет минимум, и притом единственный, при .

Таким образом, задача отыскания решения системы оказалась равносильной задаче отыскания единственного минимума функции .

Одним из методов минимизации функции многих переменных является метод покоординатного спуска.

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

Рис. 6.7.4

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

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

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

поэтому

при . Вследствие (3) имеем равенство , где . Соотношение (6) можно переписать в виде

при . На сфере величина непрерывна, поэтому она достигает своего наибольшего значения . Так как , то всегда и поэтому . Положим . Вследствие (7) имеем . Очевидно, при любом , поэтому при любом . Отсюда получаем неравенство

и, таким образом,

Из (3.8), (3.9) следуют неравенства

Отсюда получаем оценку скорости сходимости

Теорема доказана.

Из рис. 6.7.5 можно усмотреть, что метод Зейделя сходится быстрее, если направление осей эллипсоидов близко к направлению координатных осей, т. е. матрица А близка к диагональной.

Рис. 6.7.5

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

— диагональная матрица с элементами по диагонали. Как показала практика вычислений, при целесообразно брать показатель релаксации р в пределах в случае метод релаксации обычно называют методом сверхрелаксации (или методом верхней релаксации). На рис. 6.7.4 изображены символами о приближения метода Зейделя, * — метода верхней релаксации при . Например, для уменьшения погрешности в раз при решении системы (6.28) методом Зейделя требуется порядка итераций. Если применить метод верхней релаксации при , то потребуется порядка итераций. Подбор параметра в этой задаче требует детального рассмотрения. В частности, во многих случаях оптимальное значение параметра релаксации р определяется экспериментально. Иногда параметр релаксации р выбирают зависящим от и .

Для случая еще раз обратимся к геометрической картине (см. рис. 6.7.4). После уточнения компоненты по методу релаксации при мы попадаем в точку, лежащую внутри или на границе эллипсоида . Рассуждая так же, как при обосновании сходимости метода Зейделя, заключаем, что при всегда , если .

Задача 2. Доказать, что при условии метод релаксации сходится со скоростью геометрической прогрессии.