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


Цитировать

Полный текст

Аннотация

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

Об авторах

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

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

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.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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