The solution of linear systems by using the Sherman-Morrison formula (Q860990): Difference between revisions

The paper presents the solution of the linear system \(Ax=b\) (LS) by using the Sherman-Morrison formula (SH), where \(A\) is the nonsingular matrix, \(b\) is the known vector, and \(x\) is the vector to be determined. Consider the matrix \(A=A_o+u_1v_1^T+\dots u_Mv_M^T\), where \(A, A_o\in \mathbb{R}^{N\times N}\), and \(u_j, v_j\in \mathbb{R}^N, j=1,\dots,M\). Suppose \(x=x_l\) solves \(A_lx=b\) and for \(k=l+1,\dots,M\) \(y\in \mathbb{R}^N.\) \(x_l\) solves the LS for \(l=M\). Given \(x_o\) and a nonsingular \(A_o\) results in \(A_l=A_{l-1}+u_lv_l^T\) for \(l>0\). The repeated application of the SH on \(A_l\) leads to the solution \(x=x_M\). The convergence analysis and the computational costs are considered. When some \(A_l\) is singular, the partial pivoting technique of the Gauss elimination method is applied to compute the approximate solution \(x=x_M\). The numerical comparison tests of this method with the restarted generalized minimum residual method and the Gaussian elimination method with partial pivoting are supplied for randomly generated matrices as well as for the LS with Pascal, Cauchy, and Vandermonde matrices. The method is also applied in the preconditioning of large sparse nonsymmetric LS.