Block regularization Kaczmarz method

Abstract


This article focuses on the modification of the iterative version of Kaczmarz block algorithm for solving the problem of regularization, which is a fairly effective method for large-scale problems. An important characteristic of iterative methods is the speed of convergence, which depends on the condition number of the original problem. The main drawback of many iterative methods is the large condition number, while methods based on normal equations have the condition number of the system equal to the square of the condition number of the original problem. At the present time to increase the speed of convergence of iterative methods different types of preconditioners are used reducing the condition number of the system. The disadvantages of this approach is manifested in high computational complexity and the lack of universal preconditioner, which could be applied to any iterative method. One of the most effective approaches for improving the convergence rate of the method is to use a block variant of the method used. In this regard, in this paper we propose a modification of the original block Kaczmarz method for the regularization of the problem, which will reduce the computational complexity, and thus increase the rate of convergence of the algorithm. The article provides a detailed derivation of the proposed modification of the method and the proof of the convergence of the proposed variant of the block 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
244, Molodogvardeyskaya st., Samara, 443100, Russian Federation
Postgraduate Student, Dept. of Higher Mathematics & Applied Computer Science

References

  1. Тихонов А. Н., Арсений В. Я. Методы решения некорректных задач. М.: Наука, 1979. 284 с.
  2. Gill P. E., Murray W., Saunders M. A. Preconditioners for indefinite systems arising in optimization // SIAM. J. Matrix Anal. Appl., 1992. vol. 13, no. 1. pp. 292-311. doi: 10.1137/0613022.
  3. Benzi M. Preconditioning Techniques for Large Linear Systems: A Survey // J. Comput. Phys., 2002. vol. 182, no. 2. pp. 418-477. doi: 10.1006/jcph.2002.7176.
  4. Benzi M., Tuma M. A comparative study of sparse approximate inverse preconditioners // Appl. Numer. Math., 1999. vol. 30, no. 1-2. pp. 305-340. doi: 10.1016/S0168-9274(98)00118-4.
  5. Bergamaschi L., Pini G., Sartoretto F. Aproximate inverse preconditioning in the parallel solution of sparse eigenproblems // Numer. Linear Algebra Appl., 2000. vol. 7, no. 3. pp. 99-116. doi: 10.1002/(SICI)1099-1506(200004/05)7:3<99::AID-NLA188>3.0.CO;2-5.
  6. Benzi M., Joubert W. D., Mateescu G. Numerical experiments with parallel orderings for ILU preconditioners // ETNA. Electronic Transactions on Numerical Analysis, 1999. vol. 8. pp. 88-114, http://eudml.org/doc/119978.
  7. Bocs˛an Gh. Convergence of iterative methods for solving random operator equations // J. Nonlinear Sci. Appl., 2013. vol. 6, no. 1. pp. 2-6, http://www.tjnsa.com/includes/files/articles/Vol6_Iss1_2--6_Convergence_of_iterative_methods_fo.pdf.
  8. Gower R. M., Richtárik P. Randomized Iterative Methods for Linear Systems // SIAM. J. Matrix Anal. & Appl., 2015. vol. 36, no. 4. pp. 1660-1690, arXiv: 1506.03296 [math.NA].
  9. Жданов А. И., Сидоров Ю. В. Параллельная реализация рандомизированного регуляризованного алгоритма Качмажа // Компьютерная оптика, 2015. Т. 39, № 4. С. 536-541. doi: 10.18287/0134-2452-2015-39-4-536-541.
  10. Ivanov A. A., Zhdanov A. I. Kaczmarz algorithm for Tikhonov regularization problem // Applied Mathematics E-Notes, 2013. vol. 13. pp. 270-276, http://www.math.nthu.edu.tw/~amen/2013/1302252(final).pdf.
  11. Васильченко Г. П., Светлаков А. А. Проекционный алгоритм решения систем линейных алгебраических уравнений большой размерности // Ж. вычисл. матем. и матем. Физ., 1980. № 1. С. 3-10.
  12. Tanabe K. Projection method for solving a singular system of linear equation and its applications // Numer. Math., 1971. vol. 17, no. 3. pp. 203-214. doi: 10.1007/BF01436376.
  13. Strohmer T. A., Vershynin R. A randomized Kaczmarz algorithm for linear systems with exponential convergence // J. Fourier Anal. Appl., 2009. vol. 15. pp. 262-278. doi: doi: 10.1007/s00041-008-9030-4.
  14. Kaczmarz S. Angenäherte Auflösung von Systemen linearer Gleichungen // Bull. Int. Acad. Polon. Sci. A, 1937. vol. 35. pp. 335-357, http://jasonstockmann.com/Jason_Stockmann/Welcome_files/kaczmarz_english_translation_1937.pdf.
  15. Morozov V. A. Methods of Solving Incorrectly Posed Problems. New York: Springer Verlag, 1984. xviii+257 pp. doi: 10.1007/978-1-4612-5280-1.
  16. Hämarik U., Palm R., Raus T. A family of rules for parameter choice in Tikhonov regularization of ill-posed problems with inexact noise level // Comput. Appl. Math., 2012. vol. 236, no. 8. pp. 2146-2157. doi: 10.1016/j.cam.2011.09.037.
  17. Долишний В. В., Жданов А. И. Вычисление параметра регуляризации методом перекрестной значимости на основе эквивалентных нормальных расширенных систем / Труды седьмой Всероссийской научной конференции с международным участием: Информационные технологии в математическом моделировании. Часть 4 (3-6 июня 2010 г.) / Матем. моделирование и краев. задачи. Самара: СамГТУ, 2010. С. 52-55.
  18. Жданов А. И. Оптимальная регуляризация решений приближенных стохастических систем линейных алгебраических уравнений // Ж. вычисл. матем. и матем. физ., 1990. Т. 30, № 10. С. 1588-1593.
  19. Жданов А. И. Метод расширенных регуляризованных нормальных уравнений // Ж. вычисл. матем. и матем. физ., 2012. Т. 52, № 2. С. 205-208.
  20. Жданов А. И. Об одной модификации итерационного алгоритма Качмажа / Труды седьмой Всероссийской научной конференции с международным участием: Информационные технологии в математическом моделировании. Часть 4 (3-6 июня 2010 г.) / Матем. моделирование и краев. задачи. Самара: СамГТУ, 2010. С. 75-77.

Statistics

Views

Abstract - 28

PDF (Russian) - 11

Cited-By


PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2016 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies