Block regularization Kaczmarz method

Full Text

Введение. Некорректные и плохо обусловленные задачи возникают в различных приложениях при решении интегральных уравнений первого рода Блочный регуляризованный метод Качмажа Для решения некорректных задач существует ряд подходов, одним из которых является метод А. Н. Тихонова [1], основанный на решении задачи min { Au - f u∈Rn 2 + α u 2 }, (1) где A ∈ Rm×n , f ∈ Rm , α > 0 - параметр регуляризации, · = · 2 - евклидова норма. Итерационные алгоритмы для решения задачи (1) основаны на решении уравнения Эйлера (регуляризованные нормальные уравнения) (A A + αEn )u = A f, (2) где En - единичная матрица порядка n. Важной характеристикой итерационных методов является скорость сходимости, которая зависит от числа обусловленности исходной задачи. Плохая обусловленность приводит к снижению скорости сходимости итерационных методов. Спектральное число обусловленности задачи (2) равно квадрату числа обусловленности исходной задачи (1), поэтому у данной задачи (2) медленная скорость сходимости. Кроме этого, итерационные методы для решения поставленной задачи расходятся, и поэтому практически невозможно с помощью них решить задачу (1). Так как итерационные алгоритмы могут иметь крайне медленную сходимость, существуют различные подходы для ее увеличения, одним из которых является предобуславливатель [2-6], позволяющий снизить число обусловленности системы уравнений. Для итерационного метода типа проекционного алгоритма последнее время используется рандомизированый подход [7-9]. Однако эти два способа не решают проблему повышения скорости решения задачи. Не для всех задач найдены предобуславлеватели. При условии, что они найдены, их использование приводит к сильному увеличению вычислительной сложности алгоритма, от чего снижается эффект от итерационного метода. Одним из самых наиболее эффективных итерационных методов решения задачи является разработка блочного варианта [10]. Для решения системы (2) рассмотрим блочную форму метода Качмажа [11-13], которая основана на проекционном итерационном алгоритме, предложенном в работе [14] польским математиком С. Качмажем. Применив блочный метод Качмажа к расширенной системе (1), предложим оригинальную модификацию данного метода, полученную по аналогии с работой [10]. Целью данной работы является получение эффективной вычислительной модификации блочного метода Качмажа для задачи регуляризации, что позволит снизить его вычислительную сложность и тем самым повысить скорость сходимости алгоритма. Предполагается, что параметр регуляризации α известен, поэтому в данной статье не рассматривается его выбор. В настоящее время существует много подходов по его определению, одним из которых является метод, предложенный В. А. Морозовым и С. Ф. Гилязовым [15], когда система совместна. Также предлагается множество устойчивых правил выбора параметра регуляризации [16, 17], которые являются стабильными с точки зрения оценки 545 Б о г д а н о в а Е. Ю. уровня производительности. Существуют различные правила отбора параметров регуляризации, не требующие априорной информации [18]. В заключение приведем доказательство сходимости предлагаемого блочного варианта метода Качмажа для задачи регуляризации. Постановка задачи. Регуляризованная нормальная система уравнений (2) может быть представлена в виде матричного уравнения ωEm A A -ωEn y u f 0 = ⇐⇒ Aω z = f , (3) √ где ω = α, Em ∈ Rm×m , En ∈ Rn×n . Матрица Aω системы (3) не сингулярная для α > 0 и имеет единственное решение - вектор z∗ = y∗ u∗ , где u∗ = (A A + αEn )-1 A f , y∗ = ω -1 r∗ , r∗ = f - Au∗ . Модификация блочного метода Качмажа для задачи регуляризации. Представим решение системы (3) в виде системы уравнений (ωEm |A)z = f, (4) (A | - ωEn )z = 0. Воспользуемся блочным методом Качмажа: z1p = z0p + (ωEm |A)+ (f - (ωEm |A)z0p ), (5) ztp (6) p zt+1 = - Btp , p-1 , t = 1, 2, . . ., где Btp = (Ap | - ωEtp )+ (Ap | - ωEtp )ztp , p = 1,2, . . . , s, z0p = zn+1 p n ×n 1 2 p Et ∈ R - p блок единичной матрицы En , т.е. En = (En , En , . . . , Ens ), A = = (A1 , A2 , . . . , As ), Ap ∈ Rm×np , количество блоков зависит от размерности матрицы A и количества строк в блоках, sp=1 np = n, A+ - псевдообратная матрица к A. Уравнение (6) представим в виде рекуррентных уравнений p yt+1 = ytp - Ap Btp , (7) p,t p p up,t t+1 = ut + ω(En ) Bt , (8) где Btp = (Gp Gp )-1 Gp (ytp |upt ) , Gp = (Ap | - ωEnp ). Поскольку y = ω -1 r, где r = f - Au, рекуррентные уравнения (7), (8) могут быть преобразованы следующим образом: p rt+1 = rtp - Ap Ctp , (9) p,t p p up,t t+1 = ut + (En ) Ct , где Ctp = (Dp Dp )-1 Dp (ytp |upt ) , Dp = (Ap | - αEnp ). Покажем, что можно не использовать первое рекуррентное уравнение (5) в процессе итерации, если выполнены дополнительные условия - совпадают с 546 Блочный регуляризованный метод Качмажа начальными условиями u0 = u10 и r0 = r01 . Уравнение (4) используется только для согласования c начальными условиями u0 и r0 : rk+1 = rk - Aj(k) Ck , (10) uk+1 = uk + (Enj(k) ) Ck , (11) j(k) где Ck = (Dj(k) Dj(k) )-1 Dj(k) (yk |uk ) , Dj(k) = (Aj(k) | - αEn ), k = 0, 1, 2, . . ., j(k) = k mod(l) + 1, l - количество блоков, следовательно, {j(k)}∞ k=0 - периодическая последовательность вида {1, 2, . . . , l, 1, 2, . . .}. Введем вектор θk = (rk , uk ) , с помощью которого рекуррентные уравнения (10), (11) можно записать в виде одного рекуррентного уравнения: θk+1 = θk + (Aj(k) | - Enj(k) ) Ck , (12) j(k) где Ck = (Dj(k) Dj(k) )-1 Dj(k) θk , Dj(k) = (Aj(k) | - αEn ), k = 0, 1, 2, . . ., θ0 - вектор начальных значений. Теорема. Пусть вектор начальных условий θ0 = (r0 , u0 ) удовлетворяет условию согласования r0 = f -Au0 . Тогда последовательность θk , формируемая рекуррентным уравнением (12), сходится к θ∗ : θk → θ∗ при k → ∞, θ∗ = (r∗ , u∗ ) . Д о к а з а т е л ь с т в о. Доказательство проведем методом математической индукции. Из условия согласования начальных значений r0 = f -Au0 следует, что условие согласования выполняется при любом k 0: rk = f - Auk , (13) где rk и uk рассчитываются из рекуррентных уравнений (8), (9). Для k = 1 из (8), (9) получаем f - Au1 = f - A(u0 + (En1 ) C0 ) = = (f - Au0 ) - A(En1 ) C0 = r0 - A1 C0 = r1 . Предположим, что (13) выполняется для некоторого произвольного k = ν. Покажем, что (13) выполняется для k = ν + 1: f - Auν+1 = f - A(uν+1 + (Enν+1 ) Cν ) = = (f - Auν ) - Aν (Enν+1 ) Cν = rν - Aν+1 Cν = rν+1 . Из этого следует, что (13) выполняется для любого k > 0. Таким образом, по методу математической индукции для произвольного начального вектора u0 , θk → θ∗ , при k → ∞, θ∗ = (r∗ , u∗ ). В работе [19] показано, что при выполнении теоремы нет необходимости использовать в алгоритме итерационное уравнение (5). Таким образом, блочный алгоритм Качмажа для задачи регуляризации сходится. Выводы. В данной статье предложен эффективный итерационный вариант блочного алгоритма Качмажа для решения задачи регуляризации. Данная оригинальная модификация метода позволяет уменьшить вычислительную сложность и повысить скорость сходимости алгоритма для решения 547 Б о г д а н о в а Е. Ю. некорректных и плохо обусловленных задач, которые возникают в различных приложениях при решении интегральных уравнений первого рода, частных производных, а так же в задачах математической физики. Декларация о финансовых и других взаимоотношениях. Исследование не имело спонсорской поддержки. Автор несет полную ответственность за предоставление окончательной версии рукописи в печать. Окончательная версия рукописи была одобрена автором. Автор не получал гонорар за статью.

About the authors

Ekaterina Yu Bogdanova

Samara State Technical University

Email: fwinter@yandex.ru
Postgraduate Student, Dept. of Higher Mathematics & Applied Computer Science 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

References

Supplementary files