Двухшаговые алгоритмы ДММН и ДМСС

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

(1)

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

Рис. 20. П/п двухшагового метода минимальных невязок DMMN

На рис. 20 представлен алгоритм такого двухшагового метода на основе ММН. Назовем его двухшаговый метод минимальных невязок (ДММН). В этом алгоритме параметр , в отличие от алгоритма ММН, вычисляется на основе невязки, найденной на предыдущей итерации. Аналогично составляется двухшаговый метод скорейшего спуска (ДМСС). Изменение алгоритма не влияет на его трудоемкость по сравнению с ММН, оставляя его двухтактовым. Двухшаговость и двухтактовость при этом делают алгоритмы ДММН и ДМСС одними из наиболее экономичных среди нестационарных вариационных алгоритмов для решения как эрмитовых, так и, что более важно, неэрмитовых СЛАУ.

В случае хорошей сходимости ММН и МСС методы ДММН и ДМСС сходятся примерно за такое же число итераций, быть может лишь немного лучше. Однако в случае плохой сходимости они становятся мощным альтернативным вычислительным инструментом и могут сходиться быстро даже в случаях, когда у ММН и МСС практически сходимости нет, например, когда матрица СЛАУ очень близка к сингулярной.

а) б)

в) г)

Рис.21. Поведение параметра ДММН и ММН для обычной (a) и близкой к сингулярной матрице (б), (в), (г)

Так, на рис. 21 представлено поведение модуля параметра ДММН и ММН для обычной (a) и близкой к сингулярной матрице (б) большой размерности . В первом случае значения концов отрезка области локализации спектра матрицы перехода , во втором (близость к точке сингулярности - точке 1). На рис. 21(а) число итераций ДММН и ММН для достижения заданной точности решения составляет соответственно и , на рис. 21(б) сходимость обоих методов хуже и число итераций и . Матрица еще далека от сингулярной. Число обусловленности в норме 2 равно . Таким образом, сходимость ДММН в этом случае быстрее в 5 раз, чем у классического ММН. Интересно, что параметр ММН в случае (а) почти точно устанавливается на значении ОП МОПИ , а в случае (б) его величина выполняет небольшие колебания вокруг значения ОП МОПИ . В то же время параметр ДММН ведет самостоятельный колебательный поиск и заканчивает его намного раньше. Здесь выводится на график значение параметра , которое в стационарном случае (ОП МОПИ) связано этой формулой с параметром ((14) из 2).

Hа рис. 21 (в) и (г) матрица становится все более сингулярной. Параметр спектра и число обусловленности соответственно равны , и , . Соотношение числа итераций ММН и ДММН для достижения заданной точности соответственно и . То есть с ростом сингулярности матрицы выигрыш ДММН по отношению к ММН и к МОПИ становится все более существенным. Максимальный выигрыш ДММН в трудоемкости по сравнению с прямым методом Гаусса имеет место, конечно же для обычной, несингулярной матрицы, в рассматриваемых случаях на рис. 21 (а) при . При нашем требовании к точности решения выигрыш составляет порядка . Стандартный прямой библиотечный метод, как правило, хорошо обусловлен, ориентирован на минимальную погрешность порядка машинной константы и его погрешность почти не зависит от сингулярности матрицы.