부산대학교 응용수치해석 kaczmarz method

1. Basic knowledge

Kaczmarz 방법은 선형 방정식의 집합을 푸는 데 사용되는 반복적인 알고리즘으로, 주로 대규모 문제를 해결하는 데 효과적이다. 이 방법은 폴란드의 수학자인 Stefan Kaczmarz에 의해 처음 소개되었으며, 그 학문적 기초는 막대 그래프와 관련된 실제 문제들을 해결하는 데서 출발하였다. Kaczmarz 방법의 핵심 아이디어는 여러 개의 선형 방정식으로 구성된 시스템을 해결하는 데 있어, 각 방정식을 순차적으로 사용하여 해를 점진적으로 수정해 나가는 것이다. Kaczmarz 방법은 ’순차적’인 성격을 가지며, 각 반복 단계에서 하나의 방정식만을 고려하므로, 대규모 문제에서 메모리 사용량이 적고 계산이 간단하다는 장점이 있다. 선형 방정식 시스템이 Ax = b 형태일 때, 이 시스템의 방정식들은 각각의 고유한 하이퍼플레인으로 나타낼 수 있으며, 이 하이퍼플레인의 교차점에서 해가 존재하게 된다. Kaczmarz 방법에서는 하나의 방정식을 선택하고, 그 방정식이 정의하는 하이퍼플레인 위에서 현재의 해를 수정하는 방식으로 진행된다. 이 과정은 주어진 방정식의 해를 점진적으로 개선하므로, 수렴성과 효율성이 측정되는 중요한 요소로 작용한…