Optimal Backward Error Bounds For Two-sided Invariant Subspaces And Two-sided Krylov Subspaces

The optimal backward perturbation error bounds of the approximate solution are the criteria to judge the stability of an algorithm and the important measure to evaluate the quality of computed solution.Therefore,it is a very important subject to study the best backward perturbation error bounds of approximate subspace problems in numer-ical linear algebra and large-scale scientific and engineering calculations.Given the matrix A and its two approximate invariant subspaces X and y,the backward perturbation problem of the two-sided invariant subspaces is to find the per-turbation matrix E with the smallest norm,so that X and y are invariant subspaces of A+E and(A+E)H,respectively.The famous Kahan-Parlett-Jiang theorem gives the optimal backward perturbation error bound of this problem under certain conditions.In essence,it presents an a posteriori error bound on approximate solutions to eigen-problems,which provides a powerful tool to evaluate the quality of the computation-al solutions of two-sided invariant subspaces of large-scale non-Hermitian matrices.However,the perturbation error bound determined by the theorem is only local optimal rather than global optimal.For two-sided Krylov subspaces of large-scale non-Hermitian matrices,let X and y be two approximately Krylov subspaces of matrix A.Wu et al.considered how to determine a backward perturbation matrix E whose norm is as small as possible,such that X and y are Krylov subspaces of A+E and(A+E)H,respectively.However,as the two bases used are biorthonormal,and the problem are transformed into a quasi optimal problem,their results are not optimal.Recently,an upper bound on the number of distinct eigenvalues of a low-rank updated matrix was established by Farrell.Xu improved Farrell's result by using the inequality of rank.The results can be applied to estimate the number of Krylov iter-ations required for solving a perturbed linear system.However,we find that in many cases they exceed the size of the matrix.Therefore,it is interesting to seeking some new upper bounds.We will reconsider the above three questions.The main results of this paper are as follows:Firstly,the global optimal backward perturbation error bound of the two-sided invariant subspaces problem is obtained.The main idea is to use derivative to seek the minimum.We establish a new matrix differential formula,which effectively avoids the differentiation of a complex matrix variables function which is not analytical.Chosen basis matrices Xm and Ym of X and y,we obtain the optimal backward perturbed solution E by using the matrix differential formula.And we show that the Frobenius norm of the optimal backward perturbed solution E is independent of the choices of the orthonormal basis matrices Xm and Ym.That is to say,our result is the global optimal backward perturbation error bound.However,Kahan-Parlett-Jiang theorem is only the local optimal.Therefore,our result improves Kahan-Parlett-Jiang theorem.The numerical results agree well with our global optimality.Secondly,we consider the two-sided Krylov subspace problem of large-scale non-Hermitian matrices,the key technique is that we use the differentiation of function in matrix variable,too.Since the perturbation error matrix of the two-sided Krylovs sub-spaces problem involves some rectangular matrices,we propose two new strategies.One is to choose optimal orthonormal basis matrices to replace the biorthonormal ba-sis of Wu et al..The other is to use Lagrange multiplier method to find the optimal backward perturbation solution.To do this,we establish a new differential formula in matrix.Numerical experiments show that our bounds improve the existing one sub-stantially.Thirdly,a refined upper bounds on the number of distinct eigenvalues of a matrix after low-rank update is established.Some prior upper bounds that only rely on the information of the matrix in question and the low-rank update are provided.Examples show the superiority of our theoretical results over the ones of Farrell and Xu.Upper bounds on the number of distinct singular values of a matrix after perturbation is also investigated.