Multigrid methods are a prime source of important advanced in algorithmic efficiency, finding a rapidly increasing number of solving problems with $N$ unknowns with $O(N)$ work and storage, not just for special cases, but for large classes of problems. In many papers, the convergence of Multigrid algorithms was proved when linear systems are positive definite system and smoother in Multigrid method is Richrdson's iteration, Jacobi iteration, and Gauss-Seidel iteration by assuming some conditions which is concerned smoothers. In Chapter 2, when the linear systems are positive definite, we show the convergence of Multigrid algorithms with general smoother which satisfy the weaker smoothing assumptions. Also, we show that these weaker smoothing assumptions are satisfied by Richardson's iteration, Jacobi iteration, Gauss-Seidel iteration, and Kaczmarz iteration.
In Chapter 3, we analyze Jacobi iteration, Gauss-Seidel iteration, and Kaczmarz iteration by using local mode analysis(Fourier modeanalysis) which is a classical method for showing the efficiency of the smoothers.
If linear systems have a unique solution but are not positive definite, we can solve only by using Richardson's iteration and Kaczmarz iteration. As a example, we analyze Multigrid algorithms for solving the linear system which are generated by discretization of the mixed type formulation of the linear Elasticity in Chapter 4. As a example of overdetermined system, we analyze Multigrid algorithm for the solution of the cell vertex finite volume method for the Cauchy-Rimann equations in Chapter 5. In this chapter, we introduce a new norm and we show that the convergence of Multigrid method with Kaczmarz smoother by using this norm.
선형방정식을 푸는 방법 중 다중격자법은 어떤 특별한 문제 뿐만 아니라 매우 많은 문제에서 미지수 $N$이 커짐에 따라 계산 횟수와 기억용량이 $N$에 비례하여 커지므로 미지수 $N$이 매우 큰 경우에 매우 유용한 방법이다. 많은 논문에서 다중격자법의 수렴성은 선형방정식이 일양인 경우에 Richadson 밥복법, Jacobi 반복법, Gauss-Seidel 반복법을 Smoother로 사용한 다중격자법에 대하여 만 증명되었었다. 2장에서는 일반화된 Smoothing 조건을 만족하는 반복법을 Smoother로 가지는 다중격자법의 수렴성을 보이고 Richadson 반복법, Jacobi 반복법, Gauss-Seidel 반복법, Kaczmarz 반복법이 이 일반화 된 Smoothing 조건을 만족함을 보였다.
3장에서는 Smppther의 유용성을 보이는 고전적인 방법인 국소적 해석방법(푸리에 국소 해석방법)을 가지고 Jacobi 반복법, Gauss-Seidel 반복법, Kaczmarz 반복법을 해석하였다. 선형방정식이 유일한 해를 가지고 대칭이지만 일양이 아닌 경우에는 오직 Richardson 반복법이나 Kaczmarz 반복법을 사용하여 해를 구할 수 있다. 위와 같은 경우의 예로써, 4 장에서는 선형 탄성문제의 혼합 유한 요소법을 이용하여 만든 유한차원 선형방정식의 해를 구하는 다중격자법의 수렴성을 보였다. 5장에서는 선형방정식에서 미지수의 개수와 식의 다른 경우의 예로서 Cauchy-Rimann 연립 편미분방정식을 Cell Vertex 유한체적법을 이용하여 만든 유한차원 선형방정식의 해를 구하는 다중격자법의 수렴성을 보였다. 이 장에서는 새로운 척도(norm)을 도입하고, 이 새로운 척도를 이용하여 Kaczmarz 반복법을 Smoother로 이용한 다중격자법이 수렴함을 보였다.
