Строчно-ориентированная форма регуляризованного метода Качмажа


Цитировать

Полный текст

Аннотация

Предложен новый итерационный метод решения стандартной задачи регуляризации А. Н. Тихонова. Данный метод основан на применении проекционного алгоритма Качмажа к расширенной регуляризованной нормальной системе уравнений. Использование расширенной регуляризованной нормальной системы уравнений, в отличие от системы регуляризованных нормальных уравнений, позволяет значительно снизить спектральное число обусловленности исходной задачи. Получена строчно-ориентированная форма регуляризованного алгоритма Качмажа. Такая форма регуляризованного алгоритма Качмажа позволяет решать задачи, в которых данные поступают последовательно (построчно), и эффективно вычислять решения задач с разреженными матрицами больших и сверхбольших размерностей. Приведены результаты сравнения предложенной строчно-ориентированной формы алгоритма со столбцово-ориентированной формой этого алгоритма. Показано, что для определенных классов задач предложенная форма регуляризованного алгоритма позволяет уменьшить число итераций по сравнению со столбцово-ориентированной формой алгоритма.

Об авторах

Александр Иванович Жданов

Самарский государственный технический университет

Email: zhdanovaleksan@yandex.ru
доктор физико-математических наук, профессор; заведующий кафедрой; каф. высшей математики и прикладной информатики Россия, 443100, Самара, ул. Молодогвардейская, 244

Юрий Вячеславович Сидоров

Самарский государственный технический университет

Email: linuxboy2007@gmail.com
старший преподаватель; каф. высшей математики и прикладной информатики Россия, 443100, Самара, ул. Молодогвардейская, 244

Список литературы

  1. Saad Y. Iterative Methods for Sparse Linear Systems. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2003. xviii+528 pp. doi: 10.1137/1.9780898718003.
  2. Kaczmarz S. Angenäherte Auflösung von Systemen linearer Gleichungen // Bull. Int. Acad. Polon. Sci. A, 1937. no. 35. pp. 355-357 ; Kaczmarz S. Approximate solution of systems of linear equations // Int. J. Control, 1993. vol. 57, no. 6. pp. 1269-1271. doi: 10.1080/00207179308934446.
  3. Gordon R., Bender R., Herman G. T. Algebraic Reconstruction Techniques (ART) for threedimensional electron microscopy and X-ray photography // J. Theor. Biol., 1970. vol. 29, no. 3. pp. 477-481. doi: 10.1016/0022-5193(70)90109-8.
  4. Strohmer T., Vershynin R. A Randomized Kaczmarz Algorithm with Exponential Convergence // J. Fourier Anal. Appl., 2009. vol. 15. pp. 262-278, arXiv: math/0702226 [math.NA]. doi: 10.1007/s00041-008-9030-4.
  5. Needell D. Randomized Kaczmarz solver for noisy linear systems // BIT Numer. Math., 2010. vol. 50, no. 2. pp. 395-403, arXiv: 0902.0958 [math.NA]. doi: 10.1007/s10543-010-0265-5.
  6. Needell D., Tropp J. A. Paved with good intentions: Analysis of randomized block Kaczmarz method // Linear Alg. Appl., 2014. vol. 441. pp. 199-221, arXiv: 1208.3805 [math.NA]. doi: 10.1016/j.laa.2012.12.022.
  7. Needell D., Zhao R., Zouzias A. Randomized block Kaczmarz method with projection for solving least squares // Linear Alg. Appl., 2015. vol. 484. pp. 322-343, arXiv: 1403.4192 [math.NA]. doi: 10.1016/j.laa.2015.06.027.
  8. Gower R., Richtarik 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]. doi: 10.1137/15M1025487.
  9. Wei K. Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study // Inverse Problems, 2015. vol. 31, no. 12, 125008, arXiv: 1502.01822 [math.NA]. doi: 10.1088/0266-5611/31/12/125008.
  10. Shin Y., Xiu D. A Randomized Algorithm for Multivariate Function Approximation // SIAM J. Sci. Comput., 2017. vol. 39, no. 3. pp. A983-A1002. doi: 10.1137/16M1075193.
  11. Ivanov A., Zhdanov A. Kaczmarz algorithm for Tikhonov regularization problem // Appl. Math. E-Notes, 2013. vol. 13. pp. 270-276.
  12. Жданов А. И. Метод расширенных регуляризованных нормальных уравнений // Ж. вычисл. матем. и матем. физ., 2012. Т. 52, № 2. С. 205-208.
  13. Tanabe K. Projection Method for Solving a Singular System of Linear Equations and its Applications // Numer. Math., 1971. vol. 17, no. 3. pp. 203-214. doi: 10.1007/BF01436376.
  14. Ильин В. П. Об итерационном методе Качмажа и его обобщениях // Сиб. журн. индустр. матем., 2006. Т. 9, № 3. С. 39-49.
  15. Жданов А. И., Сидоров Ю. В. Параллельная реализация рандомизированного регуляризованного алгоритма Качмажа // Комп. оптика, 2015. Т. 39, № 4. С. 536-541. doi: 10.18287/0134-2452-2015-39-4-536-541.
  16. Liu Ji, Wright S. J., Sridhar S. An Asynchronous Parallel Randomized Kaczmarz Algorithm, 2014, arXiv: 1401.4780 [math.NA].
  17. Hefny A., Needell D., Ramdas A. Rows versus Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression // SIAM J. Sci. Comput., 2017. vol. 39, no. 5. pp. S528-S542, arXiv: 1507.05844 [math.NA]. doi: 10.1137/16M1077891.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Самарский государственный технический университет, 2017

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).