A class of pseudoinverse-free greedy block nonlinear Kaczmarz methods for nonlinear systems of equations

1.   Introduction

Consider the problem of finding the roots of the system of the nonlinear equations

where $\mathbf{f}:\mathcal{D} \subseteq \mathbb{R}^{n} \to \mathbb{R}^{m}$. We assume throughout that $\mathbf{f}(\mathbf{x}) = [f_{1}(\mathbf{x}), \cdots, f_{m}(\mathbf{x})]^{T}$ is a continuously differentiable vector-valued function, and $\mathbf{x} = (\mathbf{x}_{1}, \cdots, \mathbf{x}_{n})^{T}$ is an $n$-dimensional unknown vector. In this article, we exclusively study the overdetermined $(m \ge n)$ nonlinear system, where there exists a single solution $\mathbf{x}_{\ast}$ such that $\mathbf{f}(\mathbf{x}_{\ast}) = \mathbf{0}$. This kind of nonlinear problem widely exists in practical applications, such as machine learning ^[6], differential equations ^[26], convex optimization, and deep neural networks ^[15].

The Newton-Raphson (NR) method, Broyden method ^[1], and directional secant method ^[2] are some iterative methods for solving nonlinear equations. The iterative formula of the Newton-Raphson method is as follows:

where $\mathbf{f}'(\mathbf{x}_{k}) = [\nabla \mathbf{f}_{1}(\mathbf{x}_{k}), \cdots, \nabla \mathbf{f}_{m}(\mathbf{x}_{k})]^{T} \in \mathbb{R}^{m \times n}$ is the Jacobian matrix of $\mathbf{f}$ at $\mathbf{x}_{k}$. $\nabla\mathbf{f}_{i}(\mathbf{x}_{k})^{T}$ is its $i$-th row and $(\mathbf{f}'(\mathbf{x}_{k}))^{\dagger}$ is the Moore-Penrose pseudoinverse of $\mathbf{f}'(\mathbf{x}_{k})$. This approach, of course, is highly disadvantageous in the computation as it necessitates the computation of the full Jacobian matrix as well as its Moore-Penrose pseudoinverse. This leads to high calculation costs. In recent years, the nonlinear Kaczmarz method has also been developed. Wang, Li and Bao ^[28] proposed the nonlinear Kaczmarz (NK) method by generalizing the Kaczmarz method ^[14] to the nonlinear case, which still uses the core idea of the Kaczmarz method (i.e., only one row of the coefficient matrix is used in each iteration). Furthermore, for the case where the Jacobian matrix in the problem is singular, this method can be computed quickly and circumvents the shortcomings of classical methods such as the Newton method.

In contrast to the nonlinear Kaczmarz methods, the linear Kaczmarz methods are now more advanced. Next, we tried to get more efficient nonlinear Kaczmarz methods to use the optimization idea of the linear Kaczmarz methods. It is commonly known that the Kaczmarz method ^[14], whose main idea is to project the current point onto the solution space given by a row of the coefficient matrix, has drawn a lot of attention lately due to its computational simplicity and efficiency. In 2009, Strohmer and Vershynin proposed a randomized Kaczmarz (RK) ^[27] method, which selects row indexes in a random order, rather than a cyclic order, during each iteration. They proved the linear convergence of the method, which gave a great impetus to the research on the Kaczmarz methods ^{[7,8,9,10,16,18,23,35]}. Some researchers have also extended the Kaczmarz method to solve systems of inequality ^[21] and tensor equations ^[29].

Enhancing the Kaczmarz method includes two primary measures. One approach is to incorporate certain criteria to the selection of the working rows so that the larger residuals can be quickly eliminated. One of the most typical approaches is the greedy randomized Kaczmarz (GRK) method ^[4]. In addition, six typical work row selection rules are summarized in ^[3], which are the uniform, non-uniform, residual, distance, maximal residual, and maximal distance selection rules.

Another method is to select multiple working rows for each iteration, which we call the block method. By adopting the block idea ^[5,11,25], many researchers have sped up the standard Kaczmarz method's convergence. The block technique involves using a few rows of the coefficient matrix $\mathbf{A}$ for the linear system $\mathbf{Ax} = \mathbf{b}$ at each iteration. The following is a description of the block Kaczmarz technique ^[24]:

where $\mathbf{A}_{\tau_{k}}^{\dagger}$ represents the Moore-Penrose pseudoinverse of the chosen submatrix $\mathbf{A}_{\tau_{k}}$ and $\tau_{k}$ is a subset of indicators selected according to some rule. However, the Moore-Penrose pseudoinverse must be computed for each iteration in the block Kaczmarz approach, and this is typically rather costly. Necoara ^[22] used some updated convex combinations as the new direction of the next iteration to build a unified framework for the randomized average block Kaczmarz method ^[30]. The Gaussian Kaczmarz method ^[13] can be regarded as another kind of block Kaczmarz method, that is

where $\eta$ is a Gaussian vector with mean $\mathbf{0} \in \mathbb{R}^{m}$ and the covariance matrix $\mathbf{I} \in \mathbb{R}^{m \times m}$ so that $\eta \sim N(\mathbf{0}, \mathbf{I})$.

In this paper, motivated by the above two ideas, we attempt to implement them in the nonlinear Kaczmarz method. The main contributions of this paper are as follows:

First, the common nonlinear block Kaczmarz method has the same drawback as the classical linear block Kaczmarz method in that it requires the computation of matrix pseudoinverses. The computation of the pseudoinverse of the Jacobian matrix requires a lot of computation, especially when the problem dimension is large. To solve this issue, this paper extends the averaging technique from linear to nonlinear methods.

Second, there are certain benefits for choosing the greedy criteria in this research. To avoid calculating the Frobenius norm of the entire Jacobian matrix, we used the second greedy rule in ^[33] as the criterion in the first method. In ^[32], Zhang et al. proposed a nonlinear Kaczmarz method with a greedy selection strategy, which is specified as follows:

which aims at choosing the maximum component of the residual vector. They also showed that in terms of numerical experiments and theoretical analysis, the methods with greedy rules are faster than the NK method. Therefore, we used it as the second greedy criterion in this paper.

In summary, inspired by ^[32,33], we extended the pseudoinverse-free block Kaczmarz method for solving linear equations to the nonlinear situation and incorporated greedy principles to accelerate the convergence of algorithms. We presented two kinds of pseudoinverse-free greedy block nonlinear Kaczmarz methods: the nonlinear greedy average block Kaczmarz (NGABK) method and the maximum residual nonlinear average block Kaczmarz (MRNABK) method. The convergence analyses of the two algorithms are given in detail. Numerical experiments showed that our proposed methods are more effective than the previous methods. In most cases, the MRNABK method was better than the NGABK method, and both of them were better than several state-of-the-art solvers.

The rest of this paper is organized as follows: In Section 2, the notations and preliminaries are provided. In Section 3, we provide the two pseudoinverse-free greedy block nonlinear Kaczmarz methods. We establish their convergence theorems in Section 4. The numerical experiments are given in Section 5. Finally, we make a summary of the whole work in Section 6.

2.   Notations and preliminaries

For any matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$, we use $\sigma_{max}(\mathbf{A})$, $\sigma_{min}(\mathbf{A})$, $\Vert \mathbf{A} \Vert_2$, $\Vert \mathbf{A} \Vert_F = \sqrt{\sum_{i = 1}^m \sum_{j = 1}^n \vert a_{ij} \vert^{2}}$, $\mathbf{A}^{\dagger}$, and $\mathbf{A}_{\tau}$ to denote the maximum and minimum nonzero singular values of $\mathbf{A}$, the spectral norm, the Frobenius norm, the Moore-Penrose pseudoinverse, and the row submatrix of matrix $\mathbf{A}$ indexed by the index set $\tau$. $\textbf{r}_{k}$ denotes the residual vector of the $k$-th iteration. $\mathbf{e}_{i}\in \mathbb{R}^{m}$ denotes the unit vector where the $i$-th element is 1 and the rest are 0. For an integer $m \ge 1$, let $[m]: = \{1, \dots, m\}$. At the $k$-th iteration, $\vert \tau_{k} \vert$ is the cardinal number of the set $\tau_{k}$. Set $\gamma > 0$, $\mathcal{B}(\mathbf{x}_{\ast}, \gamma)\triangleq \left\{ \mathbf{x} \in \mathbb{R}^{n} \mid \Vert \mathbf{x}-\mathbf{x}_{\ast} \Vert_2 \le \gamma \right\}$.

Definition 1 (^[28]) If for every $i \in [m]$ and $\forall \mathbf{x}_{1}, \mathbf{x}_{2} \in \mathcal{D}\subseteq \mathbb{R}^{n}$, there exists $\xi_{i} \in [0, \xi)$ satisfying $\xi = \max\limits_{i}\xi_{i} < \frac{1}{2}$ such that

then the function $\mathbf{f}:\mathcal{D} \subseteq \mathbb{R}^{n} \to \mathbb{R}^{m}$ is referred to satisfy the local tangential cone condition.

Lemma 1 (^[34]). If the function $\mathbf{f}$ satisfies the local tangential cone condition, then for $\forall \mathbf{x}_{1}, \mathbf{x}_{2} \in \mathcal{D}\subseteq \mathbb{R}^{n}$ and an index subset $\tau \subseteq [m]$, we have

Lemma 2 (^[19]). Let $\rho_{1}\ge \dots\ge \rho_{n}$ and $\zeta_{1}\ge\dots\ge\zeta_{n}$ be the singular values of the matrices $\mathbf{A}$ and $\mathbf{B}$ respectively. Then

Lemma 3. Suppose $\mathbf{f}'(x)$ is a full column rank matrix for $\forall \mathbf{x}\in \mathcal{D} \subseteq \mathbb{R}^{n}$. Then there exist $\underline{\sigma}$ and $\overline{\sigma}$ such that

Proof. For any $\mathbf{x} \in \mathcal{D}$, $\mathbf{f}'(\mathbf{x})$ is full column rank, then we have $\sigma_{max}(\mathbf{f}'(\mathbf{x})) = \sigma_{1}(\mathbf{f}'(\mathbf{x})) \ge \dots \ge \sigma_{n}(\mathbf{f}'(\mathbf{x})) = \sigma_{min}(\mathbf{f}'(\mathbf{x})) > 0$. By Lemma 2, $\sigma_{i}(\mathbf{f}'(\mathbf{x}))(i = 1, \dots, n)$ is a continuous function of $\mathbf{f}'(\mathbf{x})$. In addition, $\mathbf{f}'(\mathbf{x})$ continuously depends on $\mathbf{x}$. Then, $\sigma_{i}(\mathbf{x})(i = 1, \dots, n)$ is a continuous function of $\mathbf{x}$.

Since $\mathcal{D}$ is bounded closed and $\sigma_{min}(\mathbf{x})$ is a continuous function of $\mathbf{x}$, there exists a point $\underline{\mathbf{x}} \in \mathcal{D}$ such that $\underline{\sigma} = \sigma_{min}(\underline{\mathbf{x}}) = \inf\limits_{\mathbf{x}\in\mathcal{D}}\sigma_{min}(\mathbf{x}) > 0$. Then, we have

Similarly, since $\mathcal{D}$ is bounded closed and $\sigma_{max}(\mathbf{x})$ is a continuous function of $\mathbf{x}$, there exists a point $\overline{\mathbf{x}} \in \mathcal{D}$ such that $\overline{\sigma} = \sigma_{max}(\overline{\mathbf{x}}) = \sup\limits_{\mathbf{x}\in\mathcal{D}}\sigma_{max}(\mathbf{x}) < \infty$. Then, we have

□

3.   Pseudoinverse-free greedy block nonlinear Kaczmarz methods

Yuan et al. developed a randomized NR method based on the sketch-and-project technique ^[31], which is called the sketched Newton-Raphson (SNR) method. The formula of the SNR method is written as follows,

When $\mathbf{S}_{k} = \eta_{k} = \sum_{i \in \tau_{k}}(-f_{i}(\mathbf{x}_{k}))\mathbf{e}_{i}$ in Eq (3.1), we get an iterative formula as follows:

Based on the greedy randomized Kaczmarz method ^[4], the block indices $\mathcal{I}_{k}$ in distance-residual capped nonlinear Kaczmarz (DR-CNK) method ^[33] is chosen by

with

that is, the information of the entire Jacobian matrix is required. This will result in a large amount of computation. Now, by choosing the $\tau_{k}$ by

with

we get a nonlinear greedy average block Kaczmarz (NGABK) method which is described in case 1 of Algorithm 1. At the $k$-th iteration, a random vector $\eta_{k}$ is drawn and a search direction is formed by $\mathbf{f}'(\mathbf{x}_{k})^{T}\eta_{k}$. When $\mathbf{f}'(\mathbf{x}_{k})^{T}\eta_{k} = 0$, no line search is performed.

Remark 1. The computational complexity of the iterative formula of our proposed method is $O(\vert \tau_{k} \vert n)$ much smaller than that of the Newton-Raphson method $O(n^2)$ at each iteration. Here, in conjunction with the numerical experiments later, the size of $\tau_{k}$ is usually $m$/3.

Remark 2. The index set $\tau_{k}$ is always nonempty. Because

and then

implies $i_{k} \in \tau_{k}$. Therefore, the method is well-defined.

According to the maximum residual rule, we establish the maximum residual nonlinear average block Kaczmarz (MRNABK) method in case 2 of Algorithm 1. In this method, $\varrho \in [0, 1]$ is the relaxation parameter, which can be determined in numerical experiments. It is obvious that in the $k$-th iteration of the MRNABK Algorithm, the set $\tau_{k}$ is also non-empty. This is because

That is to say, the largest residual component $i_{k}$ is always in the set $\tau_{k}$.

From the MRNABK method, we can see that the larger components of the residual are eliminated preferentially, which greatly improves the efficiency of the algorithm. We establish its convergence theorem in Section 4.

4.   Convergence analysis

Lemma 4. If the function $\mathbf{f}$ satisfies the local tangential cone condition, then for $i \in \left[m \right]$, $\xi = \max\limits_{i\in [m]} \xi_{i} < \dfrac{1}{2}$, $\forall \mathbf{x}_{1}, \mathbf{x}_{2} \in \mathcal{B}(\mathbf{x}^{\ast}, \gamma) \subseteq \mathcal{D}$ and the updating formula (3.2), we have

Proof. From the updating formula (3.2), we have

According to the definition of $\eta_{k}$ and $f_{i}(\mathbf{x}_{\ast}) = 0$, we have

From Definition 1, we have

□

Remark 3. It follows from Lemma 4 that $\mathbf{x}_{k+1} \in \mathcal{B}(\mathbf{x}^{\ast}, \gamma) \subseteq \mathcal{D}$ when $\mathbf{x}_{k} \in \mathcal{B}(\mathbf{x}^{\ast}, \gamma) \subseteq \mathcal{D}$. So, if $\mathbf{f}'(\mathbf{x})$ is a full column rank matrix, the iterative sequence $\left\{\mathbf{x}_{k}\right\}$ generated by the algorithm is well-defined.

Theorem 1. Consider that the nonlinear system of equations $\mathbf{f}(\mathbf{x}) = 0$, $\mathbf{f}:\mathcal{D}\subseteq\mathbb{R}^{n} \to \mathbb{R}^{m}$ on a bounded closed set $\mathcal{D}$, and there exists $\mathbf{x}_{\ast}$ such that $\mathbf{f}(\mathbf{x}_{\ast}) = \mathbf{0}$. For $\forall \mathbf{x} \in \mathcal{D}$, the nonlinear function $\mathbf{f}$ satisfies the local tangential cone condition given in Definition 1, $\xi = \max\limits_{i\in [m]} \xi_{i} < \dfrac{1}{2}$ and $\mathbf{f}'(\mathbf{x})$ is a full column rank matrix. Assume that $\mathbf{x}_{0}\in \mathcal{B}(\mathbf{x}^{\ast}, \gamma) \subseteq \mathcal{D}\subseteq \mathbb{R}^{n}$, then the iterations of the NGABK method in case 1 of Algorithm 1 satisfy

Proof. Let $\mathbf{E}_{k} \in \mathbb{R}^{m \times \vert \tau_{k} \vert}$ be the matrix whose columns consist of all the vectors $\mathbf{e}_{i} \in \mathbb{R}^{m}$ with $i \in \tau_{k}$. Denote $\mathbf{f}'_{\tau_{k}}(\mathbf{x}_{k}) = \mathbf{E}_{k}^{T}\mathbf{f}'(\mathbf{x}_{k})$, $\hat{\eta}_{k} = \mathbf{E}_{k}^{T}\eta_{k}$, then

and

Therefore, we have

where $\sigma_{max}(\mathbf{f}'_{\tau_{k}}(\mathbf{x}_{k}))$ is the largest singular value of submatrix $\mathbf{f}'_{\tau_{k}}(\mathbf{x}_{k})$ of the Jacobian matrix $\mathbf{f}'(\mathbf{x}_{k})$. From the definition of $\eta_{k}$, we have

From the definition of $\tau_{k}$, we have

Further, using Lemma 4, we can obtain

In addition, we have $\sigma_{max}^{2}(\mathbf{f}'_{\tau_{k}}(\mathbf{x}_{k})) = \Vert \mathbf{f}'_{\tau_{k}}(\mathbf{x}_{k}) \Vert_2^{2} \le \Vert \mathbf{f}'(\mathbf{x}_{k}) \Vert_2^{2}\le\overline{\sigma}^2$ and $\delta_{k} = \frac{1}{2}(\frac{\max\limits_{i\in m}\lvert f_{i}(\mathbf{x}_{k}) \rvert^{2}}{\Vert \mathbf{f}(\mathbf{x}_{k}) \Vert_2^{2}}+\frac{1}{m}) \ge \frac{1}{m}$ and use Lemma 3, so

So, the convergence of the NGABK method is proved. □

Remark 4. Since $1-2\xi < 1 < 1+\xi^{2}$ and $\underline{\sigma}^2 < m\overline{\sigma}^2$, we have

This shows that the convergence factor of our method is strictly smaller than 1.

Now, we give the convergence theorem of the MRNABK method.

Theorem 2. Consider that the nonlinear system of equations $\mathbf{f}(\mathbf{x}) = 0$, $\mathbf{f}:\mathcal{D}\subseteq\mathbb{R}^{n} \to \mathbb{R}^{m}$ on a bounded closed set $\mathcal{D}$, and there exists $\mathbf{x}_{\ast}$ such that $\mathbf{f}(\mathbf{x}_{\ast}) = \mathbf{0}$. For $\forall \mathbf{x} \in \mathcal{D}$, the nonlinear function $\mathbf{f}$ satisfies the local tangential cone condition given in Definition 1, $\xi = \max\limits_{i\in [m]} \xi_{i} < \dfrac{1}{2}$ and $\mathbf{f}'(\mathbf{x})$ is a full column rank matrix. Assume that $\mathbf{x}_{0}\in \mathcal{B}(\mathbf{x}^{\ast}, \gamma) \subseteq \mathcal{D}\subseteq \mathbb{R}^{n}$, then the iterations of the MRNABK method in case 2 of Algorithm 1 satisfy

Proof. Following an analogous proof process to the NGABK method, we get the following formula:

The second inequality follows from the definition of $\tau_{k}$. Using $\max \limits_{1\le i \le m}\vert f_{i}(\mathbf{x}_{k}) \vert^{2} \ge \frac{1}{m}\Vert \mathbf{f}(\mathbf{x}_{k})\Vert_2^{2}$, we can get the third inequality.

From Lemma 1, it follows that

Further, using Lemmas 4 and 3, we obtain

So, the convergence of the MRNABK method is proved. □

Remark 5. Similarly, we have

This shows that the convergence factor of our method is strictly smaller than 1.

5.   Numerical examples

In this section, we primarily compare the efficiency of our new methods with the Broyden method ^[1], the NRK method ^[28], the residual-distance capped nonlinear Kaczmarz (RD-CNK) method, and the residual-based block capped nonlinear Kaczmarz (RB-CNK) method ^[33] for solving the nonlinear systems of equations in the iteration steps (denoted as 'IT') and computing time in seconds (denoted as 'CPU'). The RD-CNK method and the NRK method are based on a single sample. The RB-CNK method is based on multi-sampling and uses the following iteration scheme:

where $\mathcal{I}_{k}$ is the selected index subset. The target block in the MRNABK method is calculated by

where $\varrho \in (0, 1]$. However, the choice of $\varrho$ is only for the experiments in this paper.

In the numerical experiment, IT and CPU are the average of the results of 10 times repeated runs of the corresponding method. All experiments are terminated when the number of iterations exceeds 200, 000 or $\Vert \mathbf{f}(\mathbf{x}_{k}) \Vert_2^{2} < 10^{-6}$. All of the tables below show the number of IT and CPU required for several algorithms to reach the stop preparation (''–'' indicates that the convergence cannot be achieved under the stop criterion). Additionally, the logarithm diagram of the norm of the nonlinear residual and the number of IT, as well as the connection diagram between the number of CPU or IT and the number of equations, are provided for each experiment. Our experiment is implemented on MATLAB (version R2018b).

Example 1. In this example, we consider the following equations:

The system of equations is called H-equation, which is usually used to solve the problem of outlet distribution in radiation transmission ^[28]. In this problem, $N$ represents the number of equations and $\mu_{i} = (i-\frac{1}{2})/N$. When $c\in(0, 1)$, the discrete problem has solutions. We set $\mathbf{x}_{0}$ be the zero vector and $c = 0.9$. In the Broyden method, we set the approximate matrix for the Jacobian matrix to be the identity matrix. First of all, we tested the value of parameter $\varrho$. In Table 1, we observed that in most cases, the MRNABK method required relatively less computing time, when $\varrho = 0.1, 0.2, 0.3$. When the number of equations was fixed, we found that the larger $\varrho$ was, the longer the calculation time of the MRNABK method was. So, in this example, we set $\varrho = 0.1$. Next, we tested the performance of our methods and other methods. The results of the numerical experiments are listed in Tables 2 and 3. The results show that the NGABK method and the RB-CNK method based on multiple sampling were substantially faster than the RD-CNK method and the NRK method based on single sampling, as shown in Figure 1. Figure 2 plots the running time (CPU) and iteration steps (IT) of different methods for different $N$. According to Figure 2, the NGABK method outperformed the RB-CNK method in terms of CPU. From Table 4, the MRNABK method converged faster than the NGABK method in terms of computing time and iteration steps. For H-equation with $\mathbf{f}:\mathbb{R}^{n} \to \mathbb{R}^{n}$, the Broyden method had a better numerical result.

Example 2. In this example, we consider the Brown almost linear function ^[20],

In this experiment, we set the initial value $\mathbf{x}_{0} = 0.5 \ast ones(n, 1)$. The solution of this problem is $\mathbf{x}_{\ast} = (1, 1, ..., 1)^{T}$. The number of equations and the number of unknowns is set to $50\times50$, $100\times100$, $150\times150$, $200\times200$, $250\times250$, $300\times300$, $350\times350$, and $400\times400$. We list the computing time and iteration numbers of these methods, respectively, in Tables 5 and 6. The outcomes demonstrate how much better our new approaches perform than the NRK method. Table 6 shows that the NGABK method and the MRNABK method have almost identical iteration times, yet they are both superior to the RB-CNK method.

Example 3. In this example, we consider the Singular Broyden problem ^[12],

In this experiment, we set the initial value $\mathbf{x}_{0} = -0.5 \ast ones(n, 1)$ and $n$ is the number of the equations. The Singular Broyden problem ^[12] is a square nonlinear system of equations, and its Jacobian matrix is singular at the solution. First, we conducted an experiment on the values of parameter $\varrho$. From Table 7, we can see that for a fixed number of equations, the CPU of the MRNABK method was better when $\varrho \in [0.1, 0.3]$. So, we set $\varrho = 0.2$ in this example. Tables 8 and 9 demonstrate that, in terms of both computation time and iteration steps, the NGABK approach converged more quickly than the other three methods. The MRNABK method's residuals fell the fastest, whereas the NRK method's residuals declined the slowest, as seen in Figure 3. It is evident from Figure 4 that all five approaches may get the approximate results.

Example 4. Consider the following problem, which is a chained serpentine overdetermined problem ^[17],

where $m$ represents the number of equations. In this experiment, we set the initial value $\mathbf{x}_{0} = 0.5 \ast ones(n, 1)$, and $n =$ 100, 300, 500, 1000, 2000, respectively. From Table 10, we set $\varrho = 0.2$. As we can see, when compared to the other four approaches, the NGABK method produced better numerical results from Tables 11 and 12. Furthermore, we note that the NGABK method and the MRNABK method required fewer iterations as the dimension of overdetermined issues grew, and the NRK method's iteration time was nearly equal to that of the NGABK method. The Broyden method took too long when the problem's dimension grew. The Broyden method took more than 10 minutes to iterate when there were 1998 equations.

6.   Conclusion

Based on the Gaussian Kaczmarz method and the RD-CNK method, we introduced a new class of nonlinear Kaczmarz block approaches to solve nonlinear equations and investigated their convergence theories. By employing an averaging technique, these methods avoid computing the Moore–Penrose pseudoinverse of the Jacobian matrix at each iteration, significantly reducing the computational cost. Experimental results demonstrated that the NGABK and MRNABK methods performed better in terms of CPU and IT than the NRK method (and other methods) for the singular Jacobian matrix issue and the overdetermined problem. For problems like the H-equation, several traditional methods, including the Broyden method, and the Newton method perform well, but our proposed methods also worked better than the other Kaczmarz methods. Additionally, selecting the ideal parameter $\varrho$ was a crucial matter. We plan to keep working on the more significant research of the pseudoinverse-free approach and the more effective greedy rules in the future.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare that there are no conflicts of interest.