ABSTRACT

An iterative method is developed for solving the solution of the general restricted linear equation. The convergence, stability, and error estimate are given. Numerical experiments are presented to demonstrate the efficiency and accuracy.

Keywords:

Linear Equation, Iterative Method, Error Estimate

1. Introduction

Let ${ℂ}_r^{m\times n}$ be the set of all $m\times n$ complex matrices with rank r. For any $A\in {ℂ}_r^{m\times n}$ , let ${\Vert A\Vert }_2\mathrm{,}\mathcal{R}\left(A\right)$ , and $\mathcal{N}\left(A\right)$ be matrix spectral norm, range space and null space, respectively. Let $\rho \left(A\right)$ be the spectral radius of the matrix A. For any $A\in C_r^{m\times n}$ , if there exists a matrix X such that $XAX=X$ , then X is called a {2}-inverse (or an outer inverse) of A [1] .

The restricted linear equation is widely applied in many practical problems [2] [3] [4] . In this paper, we consider the general restricted linear equations as

$Ax=b,x\in T,$ (1)

where $A\in {ℂ}_r^{m\times n}$ and T is a subspace of ${ℂ}^n$ . As the conclusion given in [2] , (1) has a unique solution if and only if

$b\in AT\mathrm{,}T\cap \mathcal{N}\left(A\right)=\left\{0\right\}\mathrm{.}$ (2)

In recent years, some numerical methods have been developed to solve such as problems (1). The Cramer rule method is given in [2] and then this method is developed for computing the unique solution of restricted matrix equations over the quaternion skew field in [5] . An iterative method is investigated for finding some solution of (1) in [6] . In [7] , a subproper and regular splittings iterative method is constructed. The PCR algorithm is applied for parallel computing the solution of (1) in [8] . In [4] , a new iterative method is developed and its convergence analysis is also considered. The result on condensed Cramer’s rule is given for solving the general solution to the restricted quaternion matrix equation in [9] . In [10] [11] , authors develop the determinantal representation of the generalized inverse $A_{T\mathrm{,}S}^{\left(1\right)}$ for the unique solution of (1). The non-stationary Richardson iterative method is given for solving the general restricted linear equation (1) in [4] . An iterative method is applied to computing the generalized inverse in [13] . In this paper, we develop a high order iterative method to solve the problem (1). The proposed method can be implemented with any initial $x_0\in T$ and it has higher-order accuracy. The necessary and sufficient condition of convergence analysis also is given, which is different the condition given in [14] . The stability of our scheme is also considered.

The paper is organized as follows. In Section 2, an iterative method for the general restricted linear equation is developed. The convergence analysis of our method is considered, an error estimate is also given in Section 3. In Section 4, some numerical examples are presented to test the effectiveness of our method.

2. Preliminaries and Iterative Scheme

In this section, we develop an iterative method for computing the solution of the general restricted linear Equation (1).

Lemma 1 ( [1] ) Let $A\in {ℂ}^{m\times n}$ and T and S be subspaces of ${ℂ}^n$ and ${ℂ}^m$ , respectively, with $\dim T=\dim S^{\perp }=t\le r$ . Then A has a {2}-inverse (or an outer inverse) X such that $\mathcal{R}\left(X\right)=T$ and $\mathcal{N}\left(X\right)\mathrm{<mo>\; =\; </mo>}S$ if and only if

$AT\oplus S={ℂ}^m,$

in which case X is unique ( denoted by $A_{T\mathrm{,}S}^{\left(2\right)}$ ).

Proposition 2 ( [2] ) Let $A\in {ℂ}^{m\times n}$ and T and S be subspaces of ${ℂ}^n$ and ${ℂ}^m$ , respectively. Assume that the condition (2) is satisfied, then the unique solution of (1) can be expressed by

$x=A_{T,S}^{\left(2\right)}b.$ (3)

Let L and M be complementary subspaces of ${ℂ}^m$ , i.e., $L\oplus M={ℂ}^m$ , the projection $P_L$ be a linear transformation such that $P_{L}x=x,x\in L$ and $P_{L}y=0,y\in M$ .

Lemma 3 ( [12] ) Assume that $A\in {ℂ}^{m\times n}$ and $B\in {ℂ}^{m\times n}$ with $m\le n$ . Then the n eigenvalues BA are the m eigenvalues of AB together with $n-m$ zeros.

In this paper, we construct our iterative scheme as follows:

$\{\begin{array}{l}{Z}_k=\left[tI-C_t^2{Z}_{k-1}A+\cdots +{\left(-1\right)}^{t-1}{\left(Z_{k-1}A\right)}^{t-1}\right]Z_{k-1},\\ x_k=x_{k-1}+Z_k\left(b-A{x}_{k-1}\right),\end{array}$ (4)

where $k=1,2,3,\cdots$ , $t\in \mathbb{N}$ , and $t\ge 2$ . Here, we take the initial value $Z_0=\beta Y$ in our scheme (4), where $\beta$ is a relaxation factor. Thus, if $t=2$ , then (4) degenerates to the non-stationary Richardson iterative method given in [4] .

Lemma 4 Let $A\in {ℂ}^{m\times n}$ , T and S be subspaces of ${ℂ}^n$ and ${ℂ}^m$ , respectively. Assume that $Z_0=\beta Y$ and $\mathcal{R}\left(Y\right)\subseteq T$ , where $\beta$ is a nonzero constant and $Y\in {ℂ}^{n\times m}$ . For any initial $x_0\in T$ , the iterative scheme (4) converges to some solution of (1) if and only if

$\rho \left(P_T-Z_{0}A\right)<1,$

where a projection $P_T$ from ${ℂ}^m$ onto T.

Proof. The proof can be given as following the line of in [4] . □

3. Convergence Analysis

Now, we consider the convergence analysis of our iterative method (4).

Theorem 5 Let $A\in {ℂ}^{m\times n}$ , T and S be subspaces of ${ℂ}^n$ and ${ℂ}^m$ , respectively. Assume that $AT\oplus S={ℂ}^m$ and $Y\in {ℂ}^{nm}$ satisfies $\mathcal{R}\left(Y\right)\subseteq T$ and $\mathcal{N}\left(Y\right)\subseteq S$ , where $\dim T=\dim S^{\perp }$ . If $b\in AT$ , for the given initial value $Z_0=\beta Y,\beta \ne 0$ and $x_0\in T$ , then the sequence $\left\{x_k\right\}$ generated by iteration (4) converges to the unique solution of (1) if and only if $\rho \left(P_T-Z_{0}A\right)<1$ , where $P_T$ is a projection. In this case, we have

$\underset{k\to \infty }{\lim }{x}_k={\left(I-P_T+Z_{0}A\right)}^{-1}{Z}_{0}b.$ (5)

Further, we have

$\Vert x_k-x_{\infty }\Vert \le {\Vert q\Vert }^{\frac{t\left(t^k-1\right)}{t-1}}\left(\Vert x_0-Z_{0}b\Vert +\frac{\Vert q\Vert }{1-\Vert q\Vert }\Vert Z_{0}b\Vert \right).$ (6)

where $q=P_T-A{Z}_0$ .

Proof. For any $x\in T\cap N\left(A\right)$ , we have $Ax=0$ . By $AT\oplus S={ℂ}^m$ and Lemma 1, there exists a matrix X such that $\mathcal{R}\left(X\right)=T$ and $XAX=X$ . Now, assume that $y\in {ℂ}^m$ satisfies $x=Xy$ , we have

$x=Xy=XAXy=XAx=0,T\cap N\left(A\right)=\left\{0\right\}.$

If $b\in AT$ , then (2) is satisfied. Therefore, by ( [4] , Lemma 1.1), the scheme (4) converges to the unique solution of (1).

Since $\mathcal{R}\left(Y\right)\subseteq T$ , $P_T{Z}_0=Z_0$ , and then by (4), we obtain $P_T{Z}_k=Z_k$ . Since $x_0\in T$ , $P_T{x}_k=x_k$ by (4b), and therefore

$x_k=x_{k-1}+Z_k\left(b-A{x}_{k-1}\right)=Z_{k}b+\left(P_T-Z_{k}A\right)x_{k-1}.$ (7)

If $P_{T}W=W$ , then

$\left(I-Z_{k-1}A\right)W=\left(P_T-Z_{k-1}A\right)W.$ (8)

By (4) and (8), we obtain

$Z_{k}A={\displaystyle \sum _{i=1}^t{\left(-1\right)}^{i-1}{C}_t^i{\left(Z_{k-1}A\right)}^i}={\displaystyle \sum _{i=0}^{t-1}{\left(P_T-Z_{k-1}A\right)}^i{Z}_{k-1}A},$

$\left(P_T-Z_{k}A\right)W={\left(P_T-Z_{k-1}A\right)}^{t}W={\left(P_T-Z_{0}A\right)}^{t^k}W.$ (9)

By induction on k, it leads to

$\begin{array}{l}{Z}_{k}A={\displaystyle \sum _{i=0}^{t-1}{\left(P_T-Z_{0}A\right)}^{i{t}^{k-1}}{Z}_{k-1}A}\\ ={\displaystyle \sum _{i_1=0}^{t-1}{\left(P_T-Z_{0}A\right)}^{i_1{t}^{k-1}}}{\displaystyle \sum _{i_2=0}^{t-1}{\left(P_T-Z_{0}A\right)}^{i_2{t}^{k-2}}{Z}_{k-2}A}\\ =S_k{Z}_{0}A,\end{array}$ (10)

where $S_k:={\displaystyle \sum _{i=0}^{t^k-1}}{\left(P_T-Z_{0}A\right)}^i.$ From $b\in AT$ , $w\in T$ , we have $b=Aw$ and it implies that $Z_{k}b=Z_{k}Aw=S_k{Z}_{0}Aw=S_k{Z}_{0}b$ . By (9), we have

$\begin{array}{c}{x}_k=S_k{Z}_{0}b+{\left(P_T-Z_{0}A\right)}^{t^k}{x}_{k-1}\\ =S_k{Z}_{0}b+{\displaystyle \sum _{i=0}^{k-1}{\displaystyle \prod _{j=0}^i{\left(P_T-Z_{0}A\right)}^{t^{k-j}}{S}_{k-1-i}{Z}_{0}b}}+{\displaystyle \prod _{i=0}^{k-1}{\left(P_T-Z_{0}A\right)}^{t^{k-i}}{x}_0}\\ ={\displaystyle \sum _{i=0}^k{\left(P_T-Z_{0}A\right)}^{\frac{t^{k+1}-t^{k+1-i}}{t-1}}{S}_{k-i}{Z}_{0}b}+{\left(P_T-Z_{0}A\right)}^{\frac{t^{k+1}-t}{t-1}}{x}_0.\end{array}$ (11)

Note that $\left(P_T-Z_{0}A\right)S_k=S_k\left(P_T-Z_{0}A\right)$ , $\left[I-\left(P_T-Z_{0}A\right)\right]S_k=I-{\left(P_T-Z_{0}A\right)}^{t^k}\mathrm{.}$ From (11), we obtain

$\begin{array}{l}\left[I-\left(P_T-Z_{0}A\right)\right]x_k\\ =\left[I-{\left(P_T-Z_{0}A\right)}^{\frac{t^{k+1}-t}{t-1}}\right]Z_{0}b+\left[I-\left(P_T-Z_{0}A\right)\right]{\left(P_T-Z_{0}A\right)}^{\frac{t^{k+1}-t}{t-1}}{x}_0.\end{array}$ (12)

If $\rho \left(P_T-Z_{0}A\right)<1$ , then $I-\left(P_T-Z_{0}A\right)$ is invertible and it implies that $x_k$ converges as $k\to \infty$ . For convenience, let its limit denote by $x_{\infty }$ . Thus, we have $\left[I-\left(P_T-Z_{0}A\right)\right]x_{\infty }=Z_{0}b$ . Since T is closed and $x_k\in T$ , we have $x_{\infty }\in T$ and $P_T{x}_{\infty }=x_{\infty }$ . Thus, $Z_0\left(A{x}_{\infty }-b\right)=0$ and $A{x}_{\infty }-b\in \mathcal{N}\left(Z_0\right)\cap AT=\mathcal{N}\left(Y\right)\cap AT\subseteq S\cap AT=\left\{0\right\}$ . Note that $x_{\infty }$ is the unique solution of (1) and $x_{\infty }={\left[I-\left(P_T-Z_{0}A\right)\right]}^{-1}{Z}_{0}b$ . From (4), it follows that

$x_{k+1}-x_{\infty }=\left(P_T-Z_{k+1}A\right)\left(x_0-x_{\infty }\right)={\left(P_T-Z_{0}A\right)}^{\frac{t\left(t^{k+1}-1\right)}{t-1}}\left(x_0-x_{\infty }\right).$ (13)

From Lemma 4, we have $\rho \left(P_T-Z_{0}A\right)<1$ and

$x_k-x_{\infty }={\left(P_T-Z_{0}A\right)}^{\frac{t\left(t^k-1\right)}{t-1}}\left(\left(x_0-Z_{0}b\right)-\left(I-{\left(I-P_T+Z_{0}A\right)}^{-1}\right)Z_{0}b\right).$

Therefore,

$\begin{array}{c}\Vert x_k-x_{\infty }\Vert \le {\Vert q\Vert }^{\frac{t\left(t^k-1\right)}{t-1}}\left(\Vert x_0-Z_{0}b\Vert +\Vert I-{\left(I-q\right)}^{-1}\Vert \Vert Z_{0}b\Vert \right)\\ \le {\Vert q\Vert }^{\frac{t\left(t^k-1\right)}{t-1}}\left(x_0-Z_{0}b+\frac{\Vert q\Vert }{1-\Vert q\Vert }{Z}_{0}b\right),\end{array}$

where $q=P_T-A{Z}_0$ . □

Remark If $\mathcal{N}\left(Y\right)\subseteq S$ in Theorem 5 is removed and $t=2$ , then the result degenerates into that given in ( [4] , Theorem 3.2). However, the sequence $\left\{x_k\right\}$ given in (4) does not converse to $A_{T\mathrm{,}S}^{\left(2\right)}b$ , the unique solution of (1) is given by Proposition 2. Here, it can be tested by the following example:

Let A and b of the general restricted linear Equation (1) be

$A=\left[\begin{array}{ccccc}2& 2.5& 0.2& 0.3& 0\\ 0& 1.5& 0& 0& 0\\ 0& 0& 0.2& 0.2& 0\\ 0& 0& 0& 0.25& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]\in {ℂ}_4^{6\times 5},b=\left[\begin{array}{c}7\\ 3\\ 0.2\\ 0.2\\ 0\\ 0\end{array}\right].$ (14)

The matrix Y is

$Y=\left[\begin{array}{cccccc}1.2& 2& 0.2& -2& 1& 0\\ 0& 2& 5& -2& 0& 0\\ 0& 0& 0.25& 0.1& 0& 0\\ 0& -0.1& 0& 1.3& 0& 0\\ 1& 0& 0& 0& 0& 0\end{array}\right]$

Note that $R\left(Y\right)\subset T$ , but $\mathcal{N}\left(Y\right)\cancel{\subseteq }S$ . If take $\beta =0.16$ , then $\rho \left(P_T-Z_{0}A\right)<1$ . Here, we choose $t=2$ in (4). Thus, it can be seen as the method given in [4] . The errors, , and of (4) with and are presented in Table 1. Numerical results given in Table 1 show that, but. Thus, the limit of is not the solution of (1) presented by Proposition 2.

Theorem 6 Under the same conditions as in Theorem 5. The iterative scheme (4) is stable for solving (1), where.

Proof. Let and be numerical perturbations of and given in (4), respectively. Thus, we can express as,. If , , then,. Here, we formally neglect quadratic terms containing,. Since, we get

By (4), we derive

(15)

From (9) and (4), we have and

Therefore, we obtain

(16)

By (4), we have. Similarly, we have

(17)

By (17) and (16), we derive

(18)

Thus, by, we have

(19)

If, then and for any k,

where. It follows that the iterative method (4) is asymptotically stable. □

4. Numerical Examples

In the section, we give an example to test the accuracy of our scheme (4), which is implemented by our main code given in Appendix, and make a comparison with the method given in [4] . We also apply our scheme to solve the restricted linear system (1) with taking different t and intial value.

Example 1 Consider the restricted linear system (1) with a coefficient matrix being random of order, where, 900, 1000, 2000 of index one and random vectors. Let be a random matrix. Take, , and a random vector. Here, we make a comparison the mean CPU time(MCT) and error bounds of our scheme (4) with those given by the method of [4] . The stopping criteria used is given as in [4] by

Numerical results given in Table 2 and Figure 1 show that the accuracy of our method is similar to those given in [4] and our method cost less time (MCT) than the method of [4] . We can see that, to obtain the similar accuracy, the MCT of our scheme is similar to those given in [4] from Figure 2.

Example 2 Consider the general restricted linear Equation (1), where A and b is given as in (14). Here, we use the scheme (4) to solve the example. Let,. Take

Obviously, , , , , and. To verify the accuracy of our method, we present the generalized inverse as

To ensure, we take parameter in Table 3 and in Table 4, respectively. We present the errors , , and in 2-norm as in Table 3 and in Table 4, respectively.

From the numerical results given in Table 3 and Table 4, we can see that the scheme (4) has high order accuracy and these results given with are better than those obtained by, respectively.

5. Conclusion

The high order iterative method has been derived for solving the general restricted linear equation. The convergence and stability of our method also have derived. Numerical experiments have presented to demonstrate the efficiency and accuracy.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 11061005, 11701119, 11761024), the Natural Science Foundation of Guangxi (No. 2017GXNSFBA198053), the Ministry of Education Science and Technology Key Project (210164), and the open fund of Guangxi Key laboratory of hybrid computation and IC design analysis (HCIC201607).

Cite this paper

Liu, X.J., Du, W.R., Yu, Y.M. and Qin, Y.H. (2018) Efficient Iterative Method for Solving the General Restricted Linear Equation. Journal of Applied Mathematics and Physics, 6, 418-428. https://doi.org/10.4236/jamp.2018.62039

References

Appendix

function hocigrlscm()

;;

fprintf(' )

fprintf('------------------------BEGING----------------------------)

;;

for,

tic;;;;

for

;

; % compute

end

;

;

clear;

itm = toc;

if,; break, end

end % END it