Введение
Метод Качмарца или алгоритм Качмарца — это итеративный алгоритм для решения систем линейных уравнений. Он был впервые открыт польским математиком Стефаном Качмарцем, а в 1970 году повторно открыт Ричардом Гордоном, Робертом Бендером и Габором Германом в области реконструкции изображений по проекциям, где он известен как метод алгебраической реконструкции (ART). ART включает в себя ограничение неотрицательности, что делает его нелинейным. Метод Качмарца применим к любой системе линейных уравнений, но его вычислительное преимущество перед другими методами зависит от разреженности системы. В некоторых приложениях биомедицинской визуализации он показал себя лучше, чем другие методы, такие как метод фильтрованной обратной проекции. Он находит применение в самых разных областях, от компьютерной томографии (КТ) до обработки сигналов. Его также можно получить, применяя метод последовательных проекций на выпуклые множества (POCS) к гиперплоскостям, описывающим линейную систему.
The Kaczmarz method or Kaczmarz's algorithm is an iterative algorithm for solving linear equation systems It was first discovered by the Polish mathematician Stefan Kaczmarz, and was rediscovered in the field of image reconstruction from projections by Richard Gordon, Robert Bender, and Gabor Herman in 1970, where it is called the Algebraic Reconstruction Technique (ART). ART includes the positivity constraint, making it nonlinear. The Kaczmarz method is applicable to any linear system of equations, but its computational advantage relative to other methods depends on the system being sparse. It has been demonstrated to be superior, in some biomedical imaging applications, to other methods such as the filtered backprojection method. It has many applications ranging from computed tomography (CT) to signal processing. It can be obtained also by applying to the hyperplanes, described by the linear system, the method of successive projections onto convex sets (POCS).
Алгоритм 3: алгоритм Говера-Рихтарика
В 2015 году Роберт М. Говер и Питер Рихтхарик разработали универсальный рандомизированный итеративный метод для решения системы линейных уравнений, имеющей решение, который включает в себя рандомизированный алгоритм Качмарца как частный случай. Другими частными случаями являются рандомизированный метод координатными спусками, рандомизированный градиентный спуск и рандомизированный метод Ньютона. Блочные варианты и варианты с использованием важностной выборки для всех этих методов также являются частными случаями. Показано, что метод демонстрирует экспоненциальную скорость убывания (в среднем), также известную как линейная сходимость, при весьма общих условиях на способ введения случайности в алгоритм. Метод Говера — Рихтхарика стал первым алгоритмом, выявившим родственную связь между этими методами, некоторые из которых были предложены независимо, а многие – являются новыми.