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]	Fei Li, Sha Li, Liuqiang Zhong, Wanwan Zhu. Modified Adaptive Two-Grid FEMs for Nonsymmetric or Indefinite Elliptic Problems[J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 831-850.
[2]	Hongying Man, Shangyou Zhang. On the Superconvergence of a Conforming Mixed Finite Element for Linear Elasticity on Uniform n-Square Grids[J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 851-867.
[3]	Reetika Chawla, Devendra Kumar, Haitao Qi. A Numerical Technique to Solve Time-Fractional Delay Diffusion Wave Equation via Trigonometric Collocation Approach[J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 909-929.
[4]	B. Yu. Irgashev. Robin Type Problem for a Degenerate Equation of Even Order with Caputo Fractional Derivative[J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 930-952.
[5]	Zhengge Huang. New Gradient-Based Iterative-Like Algorithms for Solving a Class of Sylvester Tensor Equations[J]. Communications on Applied Mathematics and Computation, 2026, 8(3): 1005-1049.
[6]	Bei-Bei Li, Jing-Jing Cui, Zheng-Ge Huang, Xiao-Feng Xie. Two Quasi-combining Real and Imaginary Parts Iteration Methods for Solving Complex Symmetric System of Linear Equations[J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 427-455.
[7]	Lisha Chen, Zhibo Wang. A Second-Order Scheme with Nonuniform Time Grids for the Two-Dimensional Time-Fractional Zakharov-Kuznetsov Equation[J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 456-471.
[8]	Yongjun Chen, Liping Zhang. Linear Convergence of the Collatz Method for Computing the Perron Eigenpair of a Primitive Dual Number Matrix[J]. Communications on Applied Mathematics and Computation, 2026, 8(1): 232-247.
[9]	Chunxiu Liu, Junying Cao, Tong Lyu, Xingyang Ye. Numerical Analysis of a High-Order Scheme with Nonuniform Time Grids for Caputo-Hadamard Fractional Reaction Sub-diffusion Equations[J]. Communications on Applied Mathematics and Computation, 2026, 8(1): 338-365.
[10]	Qin-Qin Shen, Geng-Chen Yang, Chen-Can Zhou. Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1617-1638.
[11]	Fang Chen, Shu-Ru He. Practical Restrictively Preconditioned Conjugate Gradient Methods for a Class of Block Two-by-Two Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1639-1651.
[12]	Xu Li, Jian-Sheng Feng. Parameterized QHSS Iteration Method and Its Variants for Non-Hermitian Positive Definite Linear Systems of Strong Skew-Hermitian Parts[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1665-1683.
[13]	Jin-Feng Mao, Fang Chen. On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1724-1743.
[14]	Lu-Xin Wang, Yang Cao, Qin-Qin Shen. Two Variants of Robust Two-Step Modulus-Based Matrix Splitting Iteration Methods for Mixed-Cell-Height Circuit Legalization Problem[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1769-1790.
[15]	Yan-Xia Dai, Ren-Yi Yan, Ai-Li Yang. Minimum Residual BAS Iteration Method for Solving the System of Absolute Value Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1815-1825.