The row-oriented form of the regularized Kaczmarz’s method

Full Text

Введение. Итерационные методы являются эффективным средством решения систем линейных алгебраических уравнений (СЛАУ), возникающих в различных прикладных задачах. При большой размерности и разреженности СЛАУ итерационные алгоритмы порой являются единственным доступным инструментом их решения [1]. В последние годы вновь возник интерес к проекционному алгоритму Качмажа [2]. Впервые данный алгоритм был успешно применён в компьютерной томографии для реконструкции изображений [3]. Алгоритм Качмажа имеет очень простую структуру, но из-за низкой скорости сходимости не нашел широкого применения в других прикладных областях. В работе [4] на основе процедуры рандомизации был предложен способ ускорения скорости сходимости алгоритма Качмажа. Данная статья позволила расширить область применения алгоритма Качмажа [5-10]. Для решения стандартной задачи регуляризации А. Н. Тихонова в статье [11] предложена столбцово-ориентированная форма регуляризованного алгоритма Качмажа и показана эффективность регуляризованного алгоритма при решении определенного класса прикладных задач. Однако итерационный алгоритм [11] не позволяет решать задачи, данные в которых поступают последовательно (построчно). Подобные задачи возникают, например, при обработке изображений. В предлагаемом сообщении рассматривается строчно-ориентированная форма регуляризованного алгоритма Качмажа. 1. Постановка задачи. Рассмотрим стандартную задачу регуляризации А. Н. Тихонова: minn Au - f 2 + α u , (1) u∈R Rm×n , Rm , где A ∈ f ∈ α > 0 - параметр регуляризации, · = · 2 - евклидова векторная норма. Как известно, все итерационные алгоритмы решения задачи (1) основаны на решении уравнений Эйлера (регуляризованных нормальных уравнений) A A + αEn u = A f. (2) Главный недостаток использования системы (2) для решения задачи (1) - спектральное число обусловленности задачи (2) равно квадрату спектрального числа обусловленности матрицы A в задаче (1). В работе [12] для решения задачи (1) предложена расширенная регуляризованная нормальная система уравнений: ωEm A A -ωEn y u = f 0 ⇔ Bw θ = q, (3) где Bw = b1 , . . . , bm+n ∈ R(m+n)×(m+n) , θ = y , u ∈ Rm+n , q = = (f , 0, . . . , 0) = (q1 , . . . , qm+n ) ∈ Rm+n ; qi = fi , i = 1, . . . , m; qi = 0, 547 Ж д а н о в А. И., С и д о р о в Ю. В. √ i = m + 1, . . . , m + n; ω = α; Em , En - единичные матрицы соответствующих порядков. Матрица Bw системы (3) при α > 0 невырождена и система (3) имеет единственное решение θ∗ = (y∗ , u∗ ) , где u∗ - решение задачи (2), а y∗ = = ω -1 (f - Au∗ ) [12]. Одним из преимуществ расширенной регуляризованной нормальной системы уравнений (3) является существенно меньшее спектральное число обусловленности матрицы Bw по сравнению со спектральным числом обусловленности матрицы A задачи (1) [12], т. е. κ2 (Bw ) = κ2 (A A + αEn ). Так как матрица Bw системы (3) при α > 0 является невырожденной квадратной матрицей, сама система (3) является совместной и, следовательно, как показано в работе [13], имеет единственное решение θ∗ , которое может быть получено применением итерационного метода Качмажа к расширенной системе (3). Алгоритм Качмажа для расширенной системы (3) можно записать в следующем виде, используя «микроитерации» [14]: θk+1 = θk + (qs - bs θk ) bs , bs 2 (4) где k = 0, 1, 2, . . . ; s = s(k) = (k mod (m + n)) + 1, т. е. {s (k)}∞ k=0 - периодическая последовательность вида 1, 2, . . . , m + n, . . . 1, 2, . . . , m + n, . . . . Так как система (3) совместная, то при любом начальном значении θ0 = = (y0 , u0 ) итерационная последовательность {θk }∞ k=0 , формируемая рекуррентным выражением (4), сходится к вектору θ∗ : lim θk - θ∗ = 0, k→∞ где θ∗ = (y∗ , u∗ ) , u∗ = (A A + αEn )-1 A f , y∗ = ω -1 (f - Au∗ ). Покажем, что за счет использования условий согласования, по аналогии со столбцово-ориентированной формой регуляризованного алгоритма Качмажа [11], для системы (3) можно получить сокращенный вариант строчноориентированной формы регуляризованного алгоритма. 2. Строчно-ориентированная форма регуляризованного алгоритма Качмажа. Запишем систему (3) в виде системы матричных уравнений: y + Au = f, (5) A y - ωu = 0. (6) Если в качестве условий согласования начальных значений u0 , y0 пользовать уравнение (5): исy0 = ω -1 (f - Au0 ) , то применив алгоритм Качмажа к уравнению (6), как показано в [11], получаем столбцово-ориентированную регуляризованную форму алгоритма Качмажа. 548 Строчно-ориентированная форма регуляризованного метода Качмажа Пусть начальные значения y0 , u0 будут удовлетворять условию согласования u0 = ω -1 A y0 , (7) которые получены на основании уравнения (6), и применим алгоритм Качмажа к уравнению (5). Ниже будет показано, что из условия согласования (7) следует выполнение условия uk = ω -1 A yk (8) для всех k 0. Тогда рекуррентные выражения строчно-ориентированной формы алгоритма можно записать в виде yk+1 = yk + ω k ej , uk+1 = uk + k aj ; k = fj - ωej yk - aj uk aj 2 + ω2 . (9) Здесь A = (a1 , . . . , am ) ∈ Rm×n , f = (f1 , . . . , fm ) ∈ Rm , Em = (e1 e2 . . . em ); k = 0, 1, 2, . . . ; j = j(k) = (k mod m) + 1; {j (k)}∞ k=0 - периодическая последовательность вида 1, 2, . . . , m, 1, 2, . . . m, . . . ; начальные условия u0 и y0 удовлетворяют (7). Таким образом, рекуррентные выражения (9) соответствуют алгоритму Качмажа (4), примененным к (5) при s = s (k) = 1, 2, . . . , m. Теорема 1. Пусть в (9) начальные значения θ0 = (y0 , u0 ) удовлетворяют условию согласования (7). Тогда θk → θ∗ при k → ∞, где θk = (yk , uk ) определяются из рекуррентных выражений (9), а θ∗ = (y∗ , u∗ ) . Д о к а з а т е л ь с т в о. Докажем по индукции, что из условия согласованности (7) начальных значений y0 , u0 следует выполнение условия согласованности (8) при любых k 0, где yk и uk вычисляются из рекуррентных выражений (9). При k = 0 на основании условий теоремы имеем u0 = ω -1 A y0 . При k = 1 из (9) получаем ω -1 A y1 = ω -1 A (y0 + ω 0 e1 ) = ω -1 A y0 + u0 0A e1 = u0 + 0 a1 = u1 . (10) a1 Таким образом, из (10) следует, что ω -1 A y1 = u1 . Пусть (8) выполняется для некоторого произвольного k = ν > 1. uν = ω -1 A yν . (11) Покажем тогда, что из справедливости (11) для k = ν следует справедливость (8) при k = ν + 1. Из рекуррентных выражений (9) получаем ω -1 A yν+1 = ω -1 A yν + ω ν ej(ν+1) = ω -1 A yν + νA = ej(ν+1) = uν + ν aj(ν+1) = uν+1 . (12) 549 Ж д а н о в А. И., С и д о р о в Ю. В. Из выражения (12) следует, что ω -1 A yν+1 = uν+1 , и как следствие этого - справедливость (8) для любых k ∈ N. Следовательно, если u0 и y0 удовлетворяют условию согласования (7), то алгоритм Качмажа (4) достаточно применить только для матричной системы уравнений (5), так как для выражения (4) из справедливости (8) следует, что θk+1 = θk для всех s = s(k) = m + 1, . . . , m + n. Докажем справедливость этого факта. Для всех s = s(k) = 1, . . . , m имеем алгоритм (4), а для всех s = s(k) = = m + 1, . . . , m + n получим θk+1 = θk - βk где βk = (qs ,-ω˜ es )θk , qs 2 +ω 2 qs -ω˜ es , а A = (q1 q2 . . . qn ), En = (˜ e1 e˜2 . . . e˜n ). Из условия (8) следует, что bs θk = qs , -ω˜ es θk = qs yk - ω˜ es uk = qs yk - e˜s A yk = 0. qs Таким образом для всех s = s(k) = m + 1, . . . , m + n βk = 0 и, следовательно, θk+1 = θk . Из теоремы 1 непосредственно следует, что при нулевых начальных условиях u0 = 0 и y0 = 0 алгоритм (9) будет сходиться, т. е. θk → θ∗ при k → ∞, так как эти начальные условия удовлетворяют условию согласования (7). 3. Тестовые исследования. Проведем сравнение столбцово-ориентированной [11] и строчно-ориентированной, полученной в данном сообщении, форм регуляризованного алгоритма Качмажа на двух тестовых задачах с матрицей A полного столбцового и не полного столбцового рангов. Тестовая задача 1. Рассмотрим матрицу A= 1 2 3 4 , rank(A) = 2 и правую часть f = (1, 2) . При заданном параметре регуляризации α = 0.1 вычислялось точное регуляризованное решение u∗ = (A A + αEn )-1 A f. В табл. 1 приведены общее число внутренних и внешних итераций, а также общее число k «микроитераций», необходимые для получения регуляризованного решения u∗ для столбцово-ориентированной и строчно-ориентированной форм регуляризованного алгоритма Качмажа с условием остановки uk - uk-1 < 10-8 . Из табл. 1 видно, что алгоритму Качмажа в строчно-ориентированной форме для нахождения решения тестовой задачи 1 с заданной точностью требуется в 1.7 раз меньше внешних итераций, чем алгоритму в столбцовоориентированной форме [11], при одинаковом числе внутренних итераций. Тестовая задача 2. Рассмотрим матрицу   1 2 3 A =  . . . . . . . . .  ∈ R15×3 , rank(A) = 2 43 44 45 550 Строчно-ориентированная форма регуляризованного метода Качмажа Таблица 1 Число итераций для тестовой задачи 1 [The number of iterations for the test problem 1] The algorithm form column-oriented [11] row-oriented The number of The number of The number k of internal iterations external iterations micro iterations 2 2 422 237 844 474 u∗ - uk 2.71 · 10-7 1.66 · 10-7 и правую часть f = (1, . . . , 15) ∈ R15 . При заданном параметре регуляризации α = 0.1 вычислялось точное ре-1 гуляризованное решение u∗ = A A + αEn A f с условием остановки итераций uk - uk-1 < 10-8 . Отметим, что для нахождения решения тестовой задачи 2 строчно-ориентированная форма алгоритма Качмажа требует в 5 раз больше внутренних итераций, чем столбцово-ориентированная форма алгоритма [11]. В табл. 2 приведены данные по числу итераций, необходимых для получения регуляризованного решения u∗ с заданной точностью по обеим формам регуляризованного алгоритма Качмажа. Таблица 2 Число итераций для тестовой задачи 2 [The number of iterations for the test problem 2] The algorithm form column-oriented [11] row-oriented The number of The number of The number k of internal iterations external iterations micro iterations 3 15 297 751 44 049 893 253 660 735 u∗ - uk 5.21 · 10-4 6.85 · 10-5 Из табл. 2 видно, что несмотря на то, что предложенная строчно-ориентированная форма алгоритма Качмажа требует большего числа внутренних итераций, она по сравнению со столбцово-ориентированной формой позволяет существенно снизить число внешних итераций, при этом уменьшается и общее число «микроитераций». При решении тестовой задачи 2 с заданной точностью эти «снижения» составляют 6.7 и 1.3 раз, соответственно. Заключение. В данном сообщении предлагается строчно-ориентированная форма регуляризованного алгоритма Качмажа, которая позволяет проводить последовательную (построчную) обработку данных, аналогично классическому алгоритму Качмажа. Преимуществом рассматриваемой формы регуляризованного алгоритма (9), в отличие от столбцово-ориентированной формы алгоритма, полученного в работе [11], является последовательный доступ к поступающим данным, что может быть эффективно использовано для решения прикладных задач, возникающих в компьютерной томографии и обработки изображений. Как показано в тестовых исследованиях, представленная строчно-ориентированная форма регуляризованного алгоритма (9) позволяет уменьшить число итераций для нахождения решений определенного класса задач по сравнению со столбцово-ориентированной формой алгоритма, полученного в [11]. Следует отметить, что для столбцово-ориентированной формы регуля551 Ж д а н о в А. И., С и д о р о в Ю. В. ризованного алгоритма Качмажа существует параллельная реализация для многоядерных (многопроцессорных) систем [15], а для получения параллельной версии строчно-ориентированной формы алгоритма можно использовать результаты работы [16]. Исследованию регуляризованных вариантов алгоритма Качмажа, основанных на расширенных системах (предложенных в работе [12]), также посвящена недавно опубликованная работа [17]. Конкурирующие интересы. Мы не имеем конкурирующих интересов. Авторский вклад и ответственность. Все авторы принимали участие в разработке концепции статьи и в написании рукописи. Авторы несут полную ответственность за предоставление окончательной рукописи в печать. Окончательная версия рукописи была одобрена всеми авторами. Финансирование. Исследование выполнялось без финансирования.

About the authors

Alexander I Zhdanov

Samara State Technical University

Email: zhdanovaleksan@yandex.ru
Dr. Phys. & Math. Sci., Professor; Head of Department; Dept. of Higher Mathematics & Applied Computer Science 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

Yuri V Sidorov

Samara State Technical University

Email: linuxboy2007@gmail.com
Senior Lecturer; Dept. of Higher Mathematics & Applied Computer Science 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

References

Supplementary files