Стабилизированный метод бисопряженных градиентов

К сожалению, описанный алгоритм BiCG зачастую обнаруживает в экспериментах неустойчивость и осциллирующее поведение нормы невязки. Более того, итерационный процесс может полностью оборваться, без возможности его дальнейшего продления. Это происходит если коэффициент b _j =0. К тому же метод BiCG плохо поддается реализации на многопроцессорных вычислительных системах с распределенной памятью за счет использования операций с транспонированной матрицей. Эти возникающие проблемы привели к разработке целого класса методов, в которых операция с транспонированной матрицей не используется.

Алгебраически это может быть достигнуто за счет изменения специальным образом полинома p _m, которому удовлетворяет последовательность невязок в методах, использующих подпространства Крылова. Из числа методов, свободных от транспонирования, в настоящее время широко применяется стабилизированный метод бисопряженных градиентов (BiCGStab), использующий соотношение r _m =p _m (A)q _m (A) r ⁽⁰⁾, где q _m – специальным образом строящийся полином, такой, что произведение p _m q _m не содержит нечетных степеней.

Далее приведен алгоритм стабилизированного метода бисопряженных градиентов.

Алгоритм метода BiCGStab

Если необходимо построить матрицу предобусловливателя M

Выбрать начальное приближение x⁽⁰⁾

r⁽⁰⁾ = b – A x⁽⁰⁾

Выбрать вектор , удовлетворяющий условию (r⁽⁰⁾, ) ¹ 0 (например, = r⁽⁰⁾)

Для i = 1, 2, … до сходимости или до N_it^max

r _{i – 1}= (, r^{( i –1)})

Если r _{i –1}= 0

то метод не может решить данную систему

Если i = 1

p⁽ⁱ⁾ = r^{(i –1)}

Иначе

b _{i –1} = (r _{i –1} / r _{i –2}) (a _{i –1} / w _{i –1})

p⁽ⁱ⁾ = r^{(i –1)} + b _{i –1}(p^{( i –1)} – w _{i –1} v^{( i –1)})

Найти p^*из системы M = p^{( i )}

v^{( i )} = A

a _i = r _{i –1} / (, v^{( i )})

s = r^{(i –1)} – a _i v^{( i )}

Если ||s||₂/ ||r⁽⁰⁾||₂£ tol

то КОНЕЦ(x^{( i )} = x^{( i– 1)} +a _i – полученное решение)

Найти из системы M = s

t = A

w _i = (t, s) / (t, t)

x⁽ⁱ⁾ =x^{( i –1)} +a _i +w _i

r⁽ⁱ⁾ =s – w _i t

Если ||r||₂/ ||r⁽⁰⁾||₂£ tol

то КОНЕЦ(x^{( i )} – полученное решение)

увеличить i

Параметры метода полностью совпадают с параметрами метода BiCG.

Пример использования метода BiCGStab в системе TALGAT:

- действительный случай: SET "solve" BICGSTAB_r real_m right_r 0. 1.e-8 150 10 5.e-4;

- комплексный случай: SET "solve" BICGSTAB complex_m right_c 0. 1.e-8 150 10 5.e-4.

Дата добавления: 2014-12-27