Метод минимальных невязок (ММН)

Рассматривается СЛАУ (1) . Пусть сначала - самосопряженная положительно определенная матрица. Обозначим вектор невязки на -ой итерации

, (1)

Процесс итераций к решению строится следующим образом

, (2)

Заметим, что ошибка на -ой итерации и невязка связаны как

,

, (3)

и связь ошибок на соседних итерациях

, (4)

Из (2) получаем и связь невязок на соседних итерациях

, (5)

Ошибка в процессе вычислений неизвестна и не поддается контролю. Применяя к невязке (5) функционал (1) из 2.4.1 получаем, что минимум модуля невязки на последующей итерации наступает при

(6)

Процесс итераций в ММН строится следующим образом. Пусть найдено приближение к решению . Вычисляется невязка (1), затем параметр (6) и новое приближение к решению (2). Если норма невязки оказывается меньше заданной погрешности вычислений, то происходит выход из процесса итераций. В процессе одной итерации производится минимум два умножения матрицы на вектор (см. рис.17). Процесс умножения матрицы на вектор назовем одним тактом в составе итерации, так как это наиболее трудоемкий элемент в алгоритме итерации. Итак, ММН - двухтактовый одношаговый метод, в отличие от метода простой итерации, который является однотактовым одношаговым методом. Одношаговый, так как в процессе вычислений на одной итерации используется невязка и вектор приближений с одной и той же итерации. Общее число операций умножения в ММН приблизительно равно , где -число итераций, а - размерность матрицы. Этому же значению пропорционально время решения СЛАУ.

Доказывается [3], что для ММН всегда сходится, причем для невязки на -ой итерации справедлива оценка

(7)

где , и - наименьшее и наибольшее собственное число матрицы . Величина играет роль усредненного асимптотического знаменателя сходимости нестационарного метода.

Рис. 18. Подпрограмма метода минимальных невязок ММN

Таким образом, из оценки (7) следует, что для самосопряженной положительно определенной матрицы ММН по невязке сходится так же, как и метод оптимальной простой итерации Ричардсона МОПИ по погрешности. Заметим, что этот вывод распространяется и на некоторые типы неэрмитовых матриц. В целом же для неэрмитовых матриц сходимость методов МОПИ и ММН различная. Так, можно указать матрицы , выпуклая оболочка спектра которых содержит точку сингулярности – точку 0 (а следовательно МОПИ расходится), для которых ММН сходится быстро (№3,6,7,11 в Упражнениях ниже). И наоборот, можно указать матрицы, для которых МОПИ сходится, а ММН расходится (например, № 12). На рис. 18 приведен алгоритм ММН как подпрограмма Mathcad.

Формальные параметры п/п метода ММН:

- матрица исходной СЛАУ (1);

-вектор правой части Якоби;

Локальные параметры п/п:

- размерность матрицы и вектора ;

- число итераций, счетчик цикла; ограничение по числу итераций в случае расходимости метода - .

- вектор невязки;

- вектор предыдущей и текущей итерации.