On a Nonlinear Fast Deterministic Block Kaczmarz Method for Solving Nonlinear Equations

doi:10.1007/s42967-024-00427-5

摘要/Abstract

摘要： For solving large-scale nonlinear equations, a nonlinear fast deterministic block Kaczmarz method based on a greedy strategy is proposed. The method is adaptive and does not need to compute the pseudoinverses of submatrices. It is proved that themethod will converge linearly to the nearest solution to the initial point under mild conditions. Numerical experiments are performed to illustrate that the method is efficient at least for the tested problems.

关键词: Greedy, Deterministic, Block, Kaczmarz, Newton, Convergence

Abstract: For solving large-scale nonlinear equations, a nonlinear fast deterministic block Kaczmarz method based on a greedy strategy is proposed. The method is adaptive and does not need to compute the pseudoinverses of submatrices. It is proved that themethod will converge linearly to the nearest solution to the initial point under mild conditions. Numerical experiments are performed to illustrate that the method is efficient at least for the tested problems.

Key words: Greedy, Deterministic, Block, Kaczmarz, Newton, Convergence

中图分类号:

65H10

Yun-Xia Tan, Zheng-Da Huang. On a Nonlinear Fast Deterministic Block Kaczmarz Method for Solving Nonlinear Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 954-969.

参考文献

1. Alam, S.M.S., Natarajan, B., Pahwa, A.: Distribution grid state estimation from compressed measurements. IEEE Trans. Smart Grid 5, 1631–1642 (2014)
2. An, H.-B., Bai, Z.-Z.: NGLM: a globally convergent Newton-GMRES method (in Chinese). Math. Numer. Sin. 27, 151–174 (2005)
3. An, H.-B., Bai, Z.-Z.: A globally convergent Newton-GMRES method for large sparse systems of nonlinear equations. Appl. Numer. Math. 57, 235–252 (2007)
4. Bai, Z.-Z., An, H.-B.: On efficient variants and global convergence of the Newton-GMRES method (in Chinese). J. Numer. Methods Comput. Appl. 26, 291–300 (2005)
5. Bai, Z.-Z., Guo, X.-P.: On Newton-HSS methods for systems of nonlinear equations with positive-definite Jacobian matrices. J. Comput. Math. 28, 235–260 (2010)
6. Bai, Z.-Z., Wang, L.: On convergence rates of Kaczmarz-type methods with different selection rules of working rows. Appl. Numer. Math. 186, 289–319 (2023)
7. Bai, Z.-Z., Wu, W.-T.: On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput. 40, A592–A606 (2018)
8. Bai, Z.-Z., Wu, W.-T.: On convergence rate of the randomized Kaczmarz method. Linear Algebra Appl. 553, 252–269 (2018)
9. Bao, J.-F., Yu, C.K.W., Wang, J.-H., Hu, Y.-H., Yao, J.-C.: Modified inexact Levenberg-Marquardt methods for solving nonlinear least squares problems. Comput. Optim. Appl. 74, 547–582 (2019)
10. Bellavia, S., Morini, B.: A globally convergent Newton-GMRES subspace method for systems of nonlinear equations. SIAM J. Sci. Comput. 23, 940–960 (2001)
11. Ben-Israel, A.: A Newton-Raphson method for the solution of systems of equations. J. Math. Anal. Appl. 15, 243–252 (1966)
12. Brown, K.M.: A quadratically convergent Newton-like method based upon Gaussian elimination. SIAM J. Numer. Anal. 6, 560–569 (1969)
13. Byrne, C.: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20, 103–120 (2004)
14. Censor, Y.: Row-action methods for huge and sparse systems and their applications. SIAM Rev. 23, 444–466 (1981)
15. Censor, Y.: Parallel application of block-iterative methods in medical imaging and radiation therapy. Math. Progr. 42, 307–325 (1988)
16. Chen, J.-Q., Huang, Z.-D.: On a fast deterministic block Kaczmarz method for solving large-scale linear systems. Numer. Algorithms 89, 1007–1029 (2022)
17. Chen, Q.-P., Hao, W.-R.: Randomized Newton’s method for solving differential equations based on the neural network discretization. J. Sci. Comput. 92, 49 (2022)
18. Chen, X.-J., Womersley, R.S.: Existence of solutions to systems of underdetermined equations and spherical designs. SIAM J. Numer. Anal. 44, 2326–2341 (2006)
19. Du, K., Gao, H.: A new theoretical estimate for the convergence rate of the maximal weighted residual Kaczmarz algorithm. Numer. Math. Theory Methods Appl. 12, 627–639 (2019)
20. Eggermont, P.P.B., Herman, G.T., Lent, A.: Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl. 40, 37–67 (1981)
21. Elble, J.M., Sahinidis, N.V., Vouzis, P.: GPU computing with Kaczmarz’s and other iterative algorithms for linear systems. Parall. Comput. 36, 215–231 (2010)
22. Gordon, R., Bender, R., Herman, G.T.: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol. 29, 471–481 (1970)
23. Gower, R.M., Richtárik, P.: Randomized iterative methods for linear systems. SIAM J. Matrix Anal. Appl. 36, 1660–1690 (2015)
24. Haltmeier, M., Leitao, A., Scherzer, O.: Kaczmarz methods for regularizing nonlinear ill-posed equations I: convergence analysis. Inverse Probl. Imaging 1, 289–298 (2007)
25. Hanke, M., Neubauer, A., Scherzer, O.: A convergence analysis of the Landweber iteration for nonlinear ill-posed problems. Numer. Math. 72, 21–37 (1995)
26. Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient. IEEE Trans. Med. Imaging 12, 600–609 (1993)
27. Hounsfield, G.N.: Computerized transverse axial scanning (tomography). Part I. Description of system (Reprinted from British-Journal-of-Radiology. 46, 1016–1022, 1973). Br. J. Radiol. 68, 166–172 (1995)
28. Kaczmarz, S.: Angenäherte auflösung von systemen linearer gleichungen. Bull. Int. Acad. Polon. Sci. Lett. A 35, 355–357 (1937)
29. Kak, A.C., Slaney, M.: Principles of Computerized Tomographic Imaging. IEEE Press, New York (1988)
30. Kaltenbacher, B., Neubauer, A., Scherzer, O.: Iterative Regularization Methods for Nonlinear Ill-Posed Problems. Walter de Gruyter, Berlin (2008)
31. Kelley, C.T.: Solving Nonlinear Equations with Newton’s Method. SIAM, Philadelphia (2003)
32. Kuegler, P.: A sparse update method for solving underdetermined systems of nonlinear equations applied to the manipulation of biological signaling pathways. SIAM J. Appl. Math. 72, 982–1001 (2012)
33. Li, L., Li, W.-G., Xing, L.-L., Bao, W.-D.: Nonlinear greedy relaxed randomized Kaczmarz method. Results Appl. Math. 16, 100340 (2022)
34. Liu, C.-W.: An acceleration scheme for row projection methods. J. Comput. Appl. Math. 57, 363–391 (1995)
35. Martínez, J.M.: The projection method for solving nonlinear systems of equations under the “most violated constraint” control. Comput. Math. Appl. 11, 987–993 (1985)
36. McCormick, S.F.: The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space. Indiana Univ. Math. J. 26, 1137–1150 (1977)
37. Meyn, K.H.: Solution of underdetermined nonlinear equations by stationary iteration methods. Numer. Math. 42, 161–172 (1983)
38. Moré, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981)
39. Needell, D., Srebro, N., Ward, R.: Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Math. Program. 155, 549–573 (2016)
40. Needell, D., Tropp, J.A.: Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl. 441, 199–221 (2014)
41. Niu, Y.-Q., Zheng, B.: A greedy block Kaczmarz algorithm for solving large-scale linear systems. Appl. Math. Lett. 104, 106294 (2020)
42. Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970)
43. Pasqualetti, F., Carli, R., Bullo, F.: Distributed estimation via iterative projections with application to power network monitoring. Autom. J. IFAC 48, 747–758 (2012)
44. Romero, L.A., Mason, J.: Geolocation using TOA, FOA, and altitude information at singular geometries. IEEE Trans. Aerosp. Electron. Syst. 51, 1069–1078 (2015)
45. Shao, C.-P.: A deterministic Kaczmarz algorithm for solving linear systems. SIAM J. Matrix Anal. Appl. 44, 212–239 (2023)
46. Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009)
47. Tompkins, C.: Projection methods in calculation. In: Proceedings of the Second Symposium in Linear Programming, Washington, D.C., 1955, pp. 425–448. National Bureau of Standards, Washington, DC (1955)
48. Wang, Q.-F., Li, W.-G., Bao, W.-D., Gao, X.-Q.: Nonlinear Kaczmarz algorithms and their convergence. J. Comput. Appl. Math. 399, 113720 (2022)
49. Ye, W.-N., Zhang, M., Zhu, Y., Wang, L.-J., Hu, J.-C., Li, X., Hu, C.-X.: Real-time displacement calculation and offline geometric calibration of the grating interferometer system for ultra-precision wafer stage measurement. Precis. Eng. 60, 413–420 (2019)
50. Yuan, R., Lazaric, A., Gower, R.M.: Sketched Newton-Raphson. SIAM J. Optim. 32, 1555–1583 (2022)
51. Zhang, F.-Y., Bao, W.-D., Li, W.-G., Wang, Q.: On sampling Kaczmarz-Motzkin methods for solving large-scale nonlinear systems. Comput. Appl. Math. 42, 126 (2023)
52. Zhang, J.-H., Wang, Y.-Q., Zhao, J.: On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations. J. Comput. Appl. Math. 425, 115065 (2023)

[1]	Yujian Cao, Jianguo Huang, Haoqin Wang. A Hybrid Iterative Method for Elliptic Variational Inequalities of the Second Kind[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 910-928.
[2]	Gang Bao, Peijun Li, Xiaokai Yuan. Convergence of the PML Method for the Biharmonic Wave Scattering Problem in Periodic Structures[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 1122-1145.
[3]	Shipeng Mao, Jiaao Sun. Error Estimates of Finite Element Method for the Incompressible Ferrohydrodynamics Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 485-535.
[4]	Gui-Lin Yan, Yu-Jiang Wu, Bo Deng. Improvement of Convergence of One- and Two-Step MSM Iteration Methods for Nondifferentiable Nonlinear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 733-758.
[5]	Mengfei Wang, Yan Xu. Superconvergence of UWLDG Method for One-Dimensional Linear Sixth-Order Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 771-795.
[6]	Ren Liu, Lifei Wu. Numerical Approach for Solving Two-Dimensional Time-Fractional Fisher Equation via HABC-N Method[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 315-346.
[7]	Pavel Bakhvalov, Mikhail Surnachev. On the Order of Accuracy of Edge-Based Schemes: a Peterson-Type Counter-Example[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 372-391.
[8]	Jieying Zhang, Caixia Ou, Zhibo Wang, Seakweng Vong. An Order Reduction Method for the Nonlinear Caputo-Hadamard Fractional Diffusion-Wave Model[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 392-408.
[9]	Mária Lukáčová-Medvid'ová, Yuhuan Yuan. Convergence of a Generalized Riemann Problem Scheme for the Burgers Equation[J]. Communications on Applied Mathematics and Computation, 2024, 6(4): 2215-2238.
[10]	Michel Bergmann, Afaf Bouharguane, Angelo Iollo, Alexis Tardieu. High Order ADER-IPDG Methods for the Unsteady Advection-Diffusion Equation[J]. Communications on Applied Mathematics and Computation, 2024, 6(3): 1954-1977.
[11]	Yifan Chen, Thomas Y. Hou, Yixuan Wang. Exponentially Convergent Multiscale Finite Element Method[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 862-878.
[12]	Wes Whiting, Bao Wang, Jack Xin. Convergence of Hyperbolic Neural Networks Under Riemannian Stochastic Gradient Descent[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1175-1188.
[13]	Daniil Bochkov, Frederic Gibou. A Non-parametric Gradient-Based Shape Optimization Approach for Solving Inverse Problems in Directed Self-Assembly of Block Copolymers[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1472-1489.
[14]	Xuechun Liu, Haijin Wang, Jue Yan, Xinghui Zhong. Superconvergence of Direct Discontinuous Galerkin Methods: Eigen-structure Analysis Based on Fourier Approach[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 257-278.
[15]	Changpin Li, Dongxia Li, Zhen Wang. L1/LDG Method for the Generalized Time-Fractional Burgers Equation in Two Spatial Dimensions[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1299-1322.