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

Expand
  • School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, Zhejiang, China

Received date: 2023-11-28

  Revised date: 2024-05-01

  Accepted date: 2024-05-03

  Online published: 2025-05-23

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.

Cite this article

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 . DOI: 10.1007/s42967-024-00427-5

References

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)
Options
Outlines

/