The standard forms and convergence theory of the Kaczmarz-Tanabe type methods for solving linear systems. (English) Zbl 1517.65022
Summary: In this paper, we consider the standard forms of two kinds of Kaczmarz-Tanabe type methods, one is derived from the Kaczmarz method and the other is derived from the symmetric Kaczmarz method. As a famous image reconstruction method in computerized tomography, the Kaczmarz method is simple and easy to implement, but its convergence speed is slow, so is the symmetric Kaczmarz method. When the standard forms of the Kaczmarz-Tanabe type methods are obtained, their iteration matrices can be used continuously in the subsequent iterations. Moreover, the iteration matrices can be stored in the image reconstruction devices, which enables the Kaczmarz method and the symmetric Kaczmarz method to be used like the simultaneous iterative reconstructive techniques (SIRT). Meanwhile, theoretical analysis shows that the convergence rate of the symmetric Kaczmarz-Tanabe method is better than that of the Kaczmarz-Tanabe method but is slightly worse than that of two-step Kaczmarz-Tanabe method, which is verified numerically. Numerical experiments also show that the convergence rates of the Kaczmarz-Tanabe method and the symmetric Kaczmarz-Tanabe method are better than those of the SIRT methods.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
| 65J20 | Numerical solutions of ill-posed problems in abstract spaces; regularization |
Keywords:
Kaczmarz method; symmetric Kaczmarz method; Kaczmarz-Tanabe method; convergence rate; image reconstruction; computerized tomographySoftware:
AIR toolsReferences:
| [1] | Ledley, R. S.; Ayers, W. R., Computerized medical imaging and graphics evolves from computerized tomography, Comput. Med. Imag. Grap., 12, 1, v-xviii (1988) |
| [2] | Herman, G. T., Fundamentals of Computerized Tomography (2010), Academic Press |
| [3] | Natterer, F., The Mathematics of Computerized Tomography (2001), SIAM · Zbl 0973.92020 |
| [4] | Engl, H. W.; Hanke, M.; Neubauer, A., Regularization of Inverse Problems (1996), Kluwer Academic · Zbl 0859.65054 |
| [5] | Wang, F.; Li, W.; Bao, W.; Lv, Z., Gauss-Seidel method with oblique direction, Results Appl. Math., 12, Article 100180 pp. (2021) · Zbl 1480.65077 |
| [6] | Radon, J., Uber die bestimmung von funktionen durch ihre integralwerte langs gewisser mannigfaltigkeiten, Ber. Verh. Sächs. Akad. Wiss. Leipzig, 69, 262-267 (1917) · JFM 46.0436.02 |
| [7] | Herman, G. T., Image reconstruction from projections, Real-Time Imag., 1, 3-18 (1995) |
| [8] | Gordon, R.; Bender, R.; Herman, G. T., Algebraic reconstrction techniques (ART) for three dimensional electron microscopy and X-ray photography, J. Theoret. Biol., 29, 3, 471-481 (1970) |
| [9] | Kaczmarz, S., Angenäherte auflösung von systemen linearer Gleichungen, Bull. Int. Acad. Pol. Sci. Lett. A, 35, 355-357 (1937) · Zbl 0017.31703 |
| [10] | Björck, A.; Elfving, T., Accelerated projection methods for computing pseudoinverse solutions of systems of lienar equations, BIT, 19, 2, 145-163 (1979) · Zbl 0409.65022 |
| [11] | Huang, W., The convergence of the multigrid method using the symmetric Kaczmarz iteration as its smoothing method, Acta Math. Appl. Sin., 16, 1, 100-106 (1993) · Zbl 0778.65082 |
| [12] | Wei, K., Solving systems of phaseless equations via Kaczmarz methods: A proof of concept study, Inverse Problems, 31, 12, Article 125008 pp. (2015) · Zbl 1332.65045 |
| [13] | Kang, C., Convergence rates of the Kaczmarz-Tanabe method for linear system, J. Comput. Appl. Math., 394, Article 113577 pp. (2021) · Zbl 1472.65039 |
| [14] | Popa, C., Convergence rates for Kaczmarz-type algorithms, Numer. Algorithms, 79, 1-17 (2018) · Zbl 1398.65049 |
| [15] | Tanabe, K., Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17, 3, 203-214 (1971) · Zbl 0228.65032 |
| [16] | Hansen, P. C.; Jorgensen, J. S., AIR Tools II: Algebraic iterative reconstruction method, improved implementation, Numer. Algorithms, 79, 1, 107-137 (2018) · Zbl 1397.65007 |
| [17] | Elfving, T.; Nikazad, T.; Hansen, P. C., Semi-convergence and relaxation parameters for a class of SIRT algorithms, Electron. T. Numer. Ana., 37, 321-336 (2010) · Zbl 1205.65148 |
| [18] | Landweber, L., An iteration formula for Fredholm integral equations of the first kind, Am. J. Math., 73, 3, 615-624 (1951) · Zbl 0043.10602 |
| [19] | Cimmino, G., Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica, Series II, 9, 326-333 (1938) · JFM 64.1244.02 |
| [20] | Censor, Y.; Dan, G.; Gordon, R., Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel Comput., 27, 6, 777-808 (2001) · Zbl 0972.68189 |
| [21] | Censor, Y.; Elfving, T.; Herman, G. T.; Nikazad, T., On diagonally-relaxed orthogonal projection methods, SIAM J. Sci. Comput., 30, 1, 473-504 (2008) · Zbl 1159.65317 |
| [22] | Jiang, M.; Wang, G., Convergence of the simultaneous algebraic reconstruction technique (SART), IEEE T. Image. Process., 12, 8, 957-961 (2003) · Zbl 1279.94022 |
| [23] | Andersen, A. H.; Kak, A. C., Simultaneous algebraic reconstruction technique (SART): A superior implementation of the ART algorithm, Ultrason. Imaging, 6, 1, 81-94 (1984) |
| [24] | Wan, X.; Zhang, F.; Chu, Q.; Zhang, K.; Fei, S.; Yuan, B.; Liu, Z., Three-dimensional reconstruction using an adaptive simultaneous algebraic reconstruction technique in electron tomography, J. Struct. Biol., 175, 3, 277-287 (2011) |
| [25] | David, C. L., Linear Algebra and its Applications (2012), Pearson Education, Inc |
| [26] | Needell, D.; Tropp, J. A., Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441, 1, 199-221 (2014) · Zbl 1282.65042 |
| [27] | Ma, A.; Needell, D.; Ramdas, A., Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36, 4, 1590-1604 (2015) · Zbl 1327.65112 |
| [28] | Elfving, T., Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35, 1, 1-12 (1980) · Zbl 0416.65031 |
| [29] | Censor, Y.; Elfving, T., Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem, SIAM J. Matrix Anal. Appl., 24, 1, 40-58 (2002) · Zbl 1028.90034 |
| [30] | Needell, D.; Zhao, R.; Zouzias, A., Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra Appl., 484, 322-343 (2015) · Zbl 1330.65056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
