Ускорение сходимости итерационных методов

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

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

Процедуры ускорения связаны с построением очередного вектора по одному или нескольким его значениям на предыдущих итерационных циклах. Фактически речь идет о построении на каждом шаге итераций  интерполирующей функции с векторным аргументом, по которой вычисляют очередной вектор для подстановки. Для вычисления вектора  на (k+1)-ом шаге итераций необходимо сначала получить величину  и единичный вектор направления   и просуммировать предыдущий вектор  с добавочным вектором:

 .

Подстановка последнего в уравнение  () образует вектор  из покомпонентных невязок. Для задания структурной взаимосвязи каждой невязки с соответствующей компонентой вектора  и образования функционала (скалярной функции от вектора невязок) возмем скалярное произведение вектора невязки на вектор-строку  :

 .

После подстановки  очередного вектора функционал получит новое значение, которое будет зависеть от некоторого скаляра :

 .

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

Из последнего равенства для (k+1)-й итерации величина шага  в направлении вектора   должна быть вычислена так:

  .

Если единичные векторы направления последовательно выбирать равными координатным, т.е. , то будет реализован метод Гаусса-Зейделя (метод покоординатного спуска в задачах оптимизации).

Выбирая направление изменения очередного вектора в сторону локального убывания, т.е. в сторону, противоположную вектору градиента функционала, получается метод быстрого спуска. В этом случае