Уровень алгоритма

Алгоритм Качмажа: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 16: Строка 16:
 
Конструированию различных алгоритмов на основе итераций С. Качмажа посвящено существенное количество работ: согласно исследованию польского математика и библиографа А. Сигелски (A. Cegielski), на начало 2010 года статья С. Качмажа цитируется более чем в четырехстах реферируемых и значимых публикациях ученых из различных областей знаний. В Советской и Российской научных школах исследования итераций С. Качмажа представлены в литературе такими известными учеными как: В.Н. Ильин, Г.П. Васильченко, А.А. Светлаков и другие, например, в работах<ref>Ильин, В. П. Об итерационном методе Качмажа и его обобщениях [Текст] / В. П. Ильин // Сибирский журнал индустриальной математики. — 2006. — Т. 9, вып. 3. — С. 39–49.</ref><ref>Г. П. Васильченко, А. А. Светлаков, “Проекционный алгоритм решения систем линейных алгебраических уравнений большой размерности”, Ж. вычисл. матем. и матем. физ., 20:1 (1980), 3–10.</ref>. Общие идеи о проекционных методах так же представлены в классической работе Л. Г. Гурина, Б. Т. Поляка, Э. В. Райка<ref>Л. Г. Гурин, Б. Т. Поляк, Э. В. Райк, “Методы проекций для отыскания общей точки выпуклых множеств”, Ж. вычисл. матем. и матем. физ., 7:6 (1967), 1211–1228</ref>, где впервые предлагается и обосновывается идентичный алгоритм для решения систем линейных алгебраических неравенств и уравнений.
 
Конструированию различных алгоритмов на основе итераций С. Качмажа посвящено существенное количество работ: согласно исследованию польского математика и библиографа А. Сигелски (A. Cegielski), на начало 2010 года статья С. Качмажа цитируется более чем в четырехстах реферируемых и значимых публикациях ученых из различных областей знаний. В Советской и Российской научных школах исследования итераций С. Качмажа представлены в литературе такими известными учеными как: В.Н. Ильин, Г.П. Васильченко, А.А. Светлаков и другие, например, в работах<ref>Ильин, В. П. Об итерационном методе Качмажа и его обобщениях [Текст] / В. П. Ильин // Сибирский журнал индустриальной математики. — 2006. — Т. 9, вып. 3. — С. 39–49.</ref><ref>Г. П. Васильченко, А. А. Светлаков, “Проекционный алгоритм решения систем линейных алгебраических уравнений большой размерности”, Ж. вычисл. матем. и матем. физ., 20:1 (1980), 3–10.</ref>. Общие идеи о проекционных методах так же представлены в классической работе Л. Г. Гурина, Б. Т. Поляка, Э. В. Райка<ref>Л. Г. Гурин, Б. Т. Поляк, Э. В. Райк, “Методы проекций для отыскания общей точки выпуклых множеств”, Ж. вычисл. матем. и матем. физ., 7:6 (1967), 1211–1228</ref>, где впервые предлагается и обосновывается идентичный алгоритм для решения систем линейных алгебраических неравенств и уравнений.
  
В 2008 году американскими математиками Т. Штромером (T. Strohmer) и Р. Вершининым (R. Vershynin) в <ref>Strohmer, T. A Randomized Kaczmarz Algorithm with Exponential Convergence [Текст] / T. Strohmer, R. Vershynin // Journal of Fourier Analysis and Applications. — 2009. — Vol. 15, Issue 2. — С. 262-278.</ref> была предложена рандомизированная модификация итерационного метода, в которой последовательность приближений к решению, для совместных и переопределенных с.л.а.у. сходится с экспоненциальной скоростью.
+
В 2008 году американскими математиками Т. Штромером (T. Strohmer) и Р. Вершининым (R. Vershynin) в <ref>Strohmer, T. A Randomized Kaczmarz Algorithm with Exponential Convergence [Текст] / T. Strohmer, R. Vershynin // Journal of Fourier Analysis and Applications. — 2009. — Vol. 15, Issue 2. — С. 262-278.</ref> была предложена рандомизированная модификация итерационного метода, в которой последовательность приближений к решению для совместных и переопределенных с.л.а.у. сходится с экспоненциальной скоростью.
  
 
Множество модификаций идеи метода ортогональных проекций нашли свое практическое применение в различных областях знаний, связанных с обработкой и интерпретацией больших объемов данных: при реконструкции синограмм в медицине, биологии, геологии; при решении задач диагностики плазмы, кристаллографии<ref>Marks, L. D. A feasible set approach to the crystallographic phase problem [Текст] / L. D. Marks, W. Sinkler, E. Landree // Acta Crystallographica Section A. — 1987. — Vol. 55, Issue 4. — С. 601-612.</ref>, дефектоскопии и микроскопии, параллельных вычислений и распределенного анализа<ref>JElble, J. M. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems [Текст] / J. M. Elble, N. V. Sahinidis, P. Vouzis // Parallel Computing. — 2010. — Vol. 36, Issues 5-6. — С. 215–231.</ref> и др.
 
Множество модификаций идеи метода ортогональных проекций нашли свое практическое применение в различных областях знаний, связанных с обработкой и интерпретацией больших объемов данных: при реконструкции синограмм в медицине, биологии, геологии; при решении задач диагностики плазмы, кристаллографии<ref>Marks, L. D. A feasible set approach to the crystallographic phase problem [Текст] / L. D. Marks, W. Sinkler, E. Landree // Acta Crystallographica Section A. — 1987. — Vol. 55, Issue 4. — С. 601-612.</ref>, дефектоскопии и микроскопии, параллельных вычислений и распределенного анализа<ref>JElble, J. M. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems [Текст] / J. M. Elble, N. V. Sahinidis, P. Vouzis // Parallel Computing. — 2010. — Vol. 36, Issues 5-6. — С. 215–231.</ref> и др.
Строка 27: Строка 27:
 
2
 
2
 
\end{pmatrix}</math>
 
\end{pmatrix}</math>
и несовместную переопределенную, полученную добавлением к этой системед ополнительного уравнения  <math>-u_{1}+u_{2}=1.5</math>. Каждое уравнение из с.л.а.у. можно интерпретировать как гиперплоскость в пространстве координат, а решение совместной с.л.а.у. - как точку пересечения всех этих гиперплоскостей. При использовании метода алгебраической реконструкции для решения с.л.а.у. поиск приближенного решения осуществляется в направлениях, перпендикулярных к гиперплоскостям, каждая из которых описывается отдельным уравнением решаемой системы (см. Рис.1).
+
и несовместную переопределенную, полученную добавлением к этой системе дополнительного уравнения  <math>-u_{1}+u_{2}=1.5</math>. Каждое уравнение из с.л.а.у. можно интерпретировать как гиперплоскость в пространстве координат, а решение совместной с.л.а.у. - как точку пересечения всех этих гиперплоскостей. При использовании метода алгебраической реконструкции для решения с.л.а.у. поиск приближенного решения осуществляется в направлениях, перпендикулярных к гиперплоскостям, каждая из которых описывается отдельным уравнением решаемой системы (см. Рис.1).
 
[[Файл:kz_geom_in.png|thumb|center|700px|Рисунок 1. К геометрической интерпретации метода алгебраической реконструкции: слева --- случай совместной с.л.а.у., справа --- несовместной с.л.а.у.]]
 
[[Файл:kz_geom_in.png|thumb|center|700px|Рисунок 1. К геометрической интерпретации метода алгебраической реконструкции: слева --- случай совместной с.л.а.у., справа --- несовместной с.л.а.у.]]
  

Версия 10:49, 5 июля 2016


Алгоритм Качмажа (S. Kaczmarz)


Основные авторы описания: Е.С. Козлова, А.А. Иванов.

1 Общие сведения

1.1 Автор алгоритма

Стефан Качмаж (Stefan Kaczmarz) - польский математик, родился 1895 г. в городе Самбор (Sambor) Галиция (Galicia), Австро-Венгрия (Austria-Hungary), ныне Украина. Качмаж был профессором математики на факультете машиностроения университета Яна Казимира (Jan Kazimierz University) в городе Львов (Lwów) с 1919 по 1939 год, там же сотрудничал с Стефаном Банахом. Предложенный им итерационный метод послужил основой для многих современных технологий в обработке изображений, в том числе в задачах компьютерной томографии [1].

1.2 Краткая библиография

Применение метода С. Качмажа (S. Kaczmarz) или т.н. метода алгебраической реконструкции наиболее известно в задачах реконструктивной компьютерной томографии высокого разрешения. Для интерпретации данных, полученных в результате неразрушающего сканирования некоторого объекта, с 60-70-х годов применяются различные аппаратные и программные реализации итерационного метода, разработанного польским математиком С. Качмажем (S. Kaczmarz) в 1937 году[2]; этот метод был использован Г. Хаусфилдом (G.N. Hounsfield) - конструктором первого томографа «ЭМИ-сканнер»[3] (нобелевская премия по физиологии и медицине в 1979 году).

Так же данный метод можно часто встретить под следующими названиями: Algebraic Reconstruction Technique (ART)[4][5][6], Projection onto Convex Sets (PCS)[7], Kaczmarz Algorithm [8] или метод ортогональных проекций.

Конструированию различных алгоритмов на основе итераций С. Качмажа посвящено существенное количество работ: согласно исследованию польского математика и библиографа А. Сигелски (A. Cegielski), на начало 2010 года статья С. Качмажа цитируется более чем в четырехстах реферируемых и значимых публикациях ученых из различных областей знаний. В Советской и Российской научных школах исследования итераций С. Качмажа представлены в литературе такими известными учеными как: В.Н. Ильин, Г.П. Васильченко, А.А. Светлаков и другие, например, в работах[9][10]. Общие идеи о проекционных методах так же представлены в классической работе Л. Г. Гурина, Б. Т. Поляка, Э. В. Райка[11], где впервые предлагается и обосновывается идентичный алгоритм для решения систем линейных алгебраических неравенств и уравнений.

В 2008 году американскими математиками Т. Штромером (T. Strohmer) и Р. Вершининым (R. Vershynin) в [12] была предложена рандомизированная модификация итерационного метода, в которой последовательность приближений к решению для совместных и переопределенных с.л.а.у. сходится с экспоненциальной скоростью.

Множество модификаций идеи метода ортогональных проекций нашли свое практическое применение в различных областях знаний, связанных с обработкой и интерпретацией больших объемов данных: при реконструкции синограмм в медицине, биологии, геологии; при решении задач диагностики плазмы, кристаллографии[13], дефектоскопии и микроскопии, параллельных вычислений и распределенного анализа[14] и др.

1.3 Геометрическая интерпретация

Метод алгебраической реконструкции достаточно просто формулируется с использованием его геометрической интерпретации. Рассмотрим совместную с.л.а.у. с двумя неизвестными

[math]A=\begin{pmatrix}3 & 2\\
2 & 3
\end{pmatrix},\text{ }f=\begin{pmatrix}1\\
2
\end{pmatrix}[/math]

и несовместную переопределенную, полученную добавлением к этой системе дополнительного уравнения [math]-u_{1}+u_{2}=1.5[/math]. Каждое уравнение из с.л.а.у. можно интерпретировать как гиперплоскость в пространстве координат, а решение совместной с.л.а.у. - как точку пересечения всех этих гиперплоскостей. При использовании метода алгебраической реконструкции для решения с.л.а.у. поиск приближенного решения осуществляется в направлениях, перпендикулярных к гиперплоскостям, каждая из которых описывается отдельным уравнением решаемой системы (см. Рис.1).

Рисунок 1. К геометрической интерпретации метода алгебраической реконструкции: слева --- случай совместной с.л.а.у., справа --- несовместной с.л.а.у.

Интерактивная диаграмма для совместного случая подготовлена авторами статьи здесь (Notes about S. Kaczmarz algorithm - consistent case), а для несовместного случая здесь (Notes about S. Kaczmarz algorithm - inconsistent case). Данные диаграммы позволяют регулировать параметры с.л.а.у. и начальное приближение, что позволяет наглядно демонстрировать сходимость итерационной последовательности.

Описанные результаты наводят на очевидную идею - проекционная последовательность влияет на скорость сходимости метода ортогональных проекций. Обратите внимание на Рис.2.

Рисунок 2. Выбор последовательности проектирования в алгоритме С. Качмажа: К выбору последовательности ортогональных проекций: слева - последовательность проектирования начинается от первого к последнему уравнению и в обратном порядке - от последнего к предпоследнему (symART[15][16][17]), а справа - последовательность строится циклическим способом (от последнего к первому уравнению и т.д.)

Как показано на Рис. 2 - итерационная последовательность, в случае Рис. 2 (справа) сходится вообще за конечное число итераций.

1.4 Математическая запись алгоритма

Запишем совместную (в общем случае - переопределенную) с.л.а.у.

[math]Au=f,\, A\in R^{m\times n},\, u\in R^{n},\, f\in R^{m},[/math]

тогда итерации согласно алгоритму определяются последовательностью

[math]u^{k+1}=u^{k}+\lambda_{k}\frac{f_{j\left(k\right)}-\left(a_{j\left(k\right)},u^{k}\right)}{\Vert a_{j\left(k\right)}\Vert^{2}}a_{j\left(k\right)},[/math]

где

[math]A=\left(a_{1},\, a_{2},\,\ldots\,,\, a_{m}\right)^{T}\in R^{m\times n},\, u\in R^{n},\, f=\left(f_{1},\, f_{2},\,\ldots\,,\, f_{m}\right)\in R^{m},[/math]

а последовательность проектирования в классическом варианте алгоритма определяется как

[math]j\left(k\right)=\left(k\ \bmod\ m\right)+1,\, k=\overline{0,\infty},[/math]

где [math]k[/math] - номер итерации, [math]u^{0}[/math] - начальное приближение, а [math]\lambda_{k}[/math] - параметр релаксации (Рис. 2 построен для случая, когда [math]\lambda_{k}=1,\,\forall k[/math]).

2 Рандомизированная версия алгоритма и скорость сходимости

3 Программная реализация

4 Параллельные реализации

5 Классификация проекционных последовательностей

Рисунок 3. Классификация правил для задания проекционной последовательности в алгоритме C. Качмажа

5.1 Алгоритм с четной перестановкой

6 Алгоритм Качмажа как метод максимального уменьшения ошибки на каждой итерации

7 References

  1. Natterer, Frank (2001), "V.3 Kaczmarz's method", The Mathematics of Computerized Tomography, Classics in Applied Mathematics 32, SIAM, p. 128, ISBN 9780898714937.
  2. Kaczmarz, S. Angenäherte Auflösung von Systemen linearer Gleichungen [Текст] / S. Kaczmarz // Bulletin International de l'Académie Polonaise des Sciences et des Lettres / Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques. — 1937. — Vol. 35. — С. 355-357.
  3. Hounsfield, G. N. A Discussion on Recent Developments in Medical Endoscopy and Related Fields [Текст] / G. N. Hounsfield // Proceedings of the Royal Society of London. Series B, Biological Sciences. — 1977. — Vol. 195, N. 1119. — С. 281-289.
  4. Gordon, R. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography [Текст] / R. Gordon, R. Bender, G. T. Herman // Journal of theoretical biology. — 1970. — Vol. 29, Issue 3. — С. 471–481.
  5. Micke, A. The Mathematics of Computerized Tomography [Текст] / A. Micke, F. Natterer // ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik (Journal of Applied Mathematics and Mechanics). — 1987. — Vol. 67, Issue 11. — С. 580. —ISBN 3-519-02103-X and 0-471-90959-9.
  6. Herman, G. T. Fundamentals of computerized tomography: Image reconstruction from projection [Текст] : 2nd ed. / G. T. Herman. — Springer, 2009. — 300 с.
  7. Sezan, K. M. Applications of convex projection theory to image recovery in tomography and related areas [Текст] / K. M. Sezan, H. Stark // Image Recovery: Theory and Application / H. Stark, editor. — Academic Press, 1987. — С. 415-462.
  8. Cegielski, A. Bibliography on the Kaczmarz method [Электронный ресурс] : Faculty of Mathematics, Computer Science and Econometrics University of Zielona Gora ; Poland, March, 28th, 2010 / Режим доступа: http://www.uz.zgora.pl/~acegiels/Publikacje-Kaczmarz.pdf
  9. Ильин, В. П. Об итерационном методе Качмажа и его обобщениях [Текст] / В. П. Ильин // Сибирский журнал индустриальной математики. — 2006. — Т. 9, вып. 3. — С. 39–49.
  10. Г. П. Васильченко, А. А. Светлаков, “Проекционный алгоритм решения систем линейных алгебраических уравнений большой размерности”, Ж. вычисл. матем. и матем. физ., 20:1 (1980), 3–10.
  11. Л. Г. Гурин, Б. Т. Поляк, Э. В. Райк, “Методы проекций для отыскания общей точки выпуклых множеств”, Ж. вычисл. матем. и матем. физ., 7:6 (1967), 1211–1228
  12. Strohmer, T. A Randomized Kaczmarz Algorithm with Exponential Convergence [Текст] / T. Strohmer, R. Vershynin // Journal of Fourier Analysis and Applications. — 2009. — Vol. 15, Issue 2. — С. 262-278.
  13. Marks, L. D. A feasible set approach to the crystallographic phase problem [Текст] / L. D. Marks, W. Sinkler, E. Landree // Acta Crystallographica Section A. — 1987. — Vol. 55, Issue 4. — С. 601-612.
  14. JElble, J. M. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems [Текст] / J. M. Elble, N. V. Sahinidis, P. Vouzis // Parallel Computing. — 2010. — Vol. 36, Issues 5-6. — С. 215–231.
  15. Bjorck, A. Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations [Текст] / A. Bjorck, T. Elfving // BIT Numerical Mathematics. — 1979. — Vol. 19, Issue 2. — С.145-163.
  16. Nikazad, T. Algebraic Reconstruction Methods [Текст] : PhD. Thesis, Linköping University / T. Nikazad. — Linköping, 2008.
  17. Kamath, G. Component-Average Based Distributed Seismic Tomography in Sensor Networks [Текст] / G. Kamath, L. Shi, W.-Z. Song // IEEE International Conference on Distributed Computing in Sensor Systems. — 2013. — С. 88-95.