矩阵奇异值分解问题重分析的摄动法

本文提出了一般实矩阵奇异值分解问题重分析的摄动法.这是一种简捷、高效的快速重分析方法,对于提高各种需要反复进行矩阵奇异值分解的迭代分析问题的计算效率具有较重要的实用价值.文中导出了奇异值和左、右奇异向量的直到二阶摄动量的渐近估计算式.文末指出了将这种振动分析方法直接推广到一般复矩阵情况的途径.     

An iterative method based on equation decomposition for the fourth‐order singular perturbation problem

In this article, we propose an iterative method based on the equation decomposition technique ( 1 ) for the numerical solution of a singular perturbation problem of fourth‐order elliptic equation. At each step of the given method, we only need to solve a boundary value problem of second‐order elliptic equation and a second‐order singular perturbation problem. We prove that our approximate solution converges to the exact solution when the domain is a disc. Our numerical examples show the efficiency and accuracy of our method. Our iterative method works very well for singular perturbation problems, that is, the case of 0 < ε ? 1, and the convergence rate is very fast. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

On the numerical solution of singular two‐point boundary value problems: A domain decomposition homotopy perturbation approach

This paper reports a modified homotopy perturbation algorithm, called the domain decomposition homotopy perturbation method (DDHPM), for solving two‐point singular boundary value problems arising in science and engineering. The essence of the approach is to split the domain of the problem into a number of nonoverlapping subdomains. In each subdomain, a method based on a combination of HPM and integral equation formalism is implemented. The boundary condition at the right endpoint of each inner subdomain is established before deriving an iterative scheme for the components of the solution series. The accuracy and efficiency of the DDHPM are demonstrated by 4 examples (2 nonlinear and 2 linear). In comparison with the traditional HPM, the proposed domain decomposition HPM is highly accurate.     

矩阵奇异值分解问题重分析的直接摄动法

矩阵奇异值分解的摄动重分析技术具有广泛的应用前景,作者继在文[2]中提出了一种间接摄动分析方法之后,在本文中又进一步提出了直接摄动法,建立了一般实矩阵的非重奇异值及其左、古奇异向量的二阶摄动计算公式.这可满足大多数实际应用问题的一般需要.文中以算例说明了直接摄动法的有效性.     

On the computation of a truncated SVD of a large linear discrete ill-posed problem

The singular value decomposition is commonly used to solve linear discrete ill-posed problems of small to moderate size. This decomposition not only can be applied to determine an approximate solution but also provides insight into properties of the problem. However, large-scale problems generally are not solved with the aid of the singular value decomposition, because its computation is considered too expensive. This paper shows that a truncated singular value decomposition, made up of a few of the largest singular values and associated right and left singular vectors, of the matrix of a large-scale linear discrete ill-posed problems can be computed quite inexpensively by an implicitly restarted Golub–Kahan bidiagonalization method. Similarly, for large symmetric discrete ill-posed problems a truncated eigendecomposition can be computed inexpensively by an implicitly restarted symmetric Lanczos method.     

Method for solving nonlinear initial value problems by combining homotopy perturbation and reproducing kernel Hilbert space methods

The nonlinear singular initial value problems including generalized Lane–Emden-type equations are investigated by combining homotopy perturbation method (HPM) and reproducing kernel Hilbert space method (RKHSM). He’s HPM is based on the use of traditional perturbation method and homotopy technique and can reduce a nonlinear problem to some linear problems and generate a rapid convergent series solution in most cases. RKHSM is also an analytical technique, which can overcome the difficulty at the singular point of non-homogeneous, linear singular initial value problems; especially when the singularity appears on the right-hand side of this type of equations, so it can solve powerfully linear singular initial value problems. Therefore, using advantages of these two methods, more general nonlinear singular initial value problems can be solved powerfully. Some numerical examples are presented to illustrate the strength of the method.     

Estimation of optimal backward perturbation bounds for the linear least squares problem

In this paper a method of estimating the optimal backward perturbation bound for the linear least squares problem is presented. In contrast with the optimal bound, which requires a singular value decomposition, this method is better suited for practical use on large problems since it requiresO(mn) operations. The method presented involves the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm which gives a gap in which the optimal bounds for the spectral and the Frobenius norm must be. Numerical tests are performed showing that this method produces an efficient estimate of the optimal backward perturbation bound.     

A truncated projected SVD method for linear discrete ill-posed problems

Truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. However, since the singular value decomposition of the matrix is independent of the right-hand side, there are linear discrete ill-posed problems for which this method fails to yield an accurate approximate solution. This paper describes a new approach to incorporating knowledge about properties of the desired solution into the solution process through an initial projection of the linear discrete ill-posed problem. The projected problem is solved by truncated singular value decomposition. Computed examples illustrate that suitably chosen projections can enhance the accuracy of the computed solution.     

Combining approximate solutions for linear discrete ill-posed problems

Linear discrete ill-posed problems of small to medium size are commonly solved by first computing the singular value decomposition of the matrix and then determining an approximate solution by one of several available numerical methods, such as the truncated singular value decomposition or Tikhonov regularization. The determination of an approximate solution is relatively inexpensive once the singular value decomposition is available. This paper proposes to compute several approximate solutions by standard methods and then extract a new candidate solution from the linear subspace spanned by the available approximate solutions. We also describe how the method may be used for large-scale problems.     

Modifying the generalized singular value decomposition with application with application in direction-of-arrival finding

We consider updating and downdating problems for the generalized singular value decomposition (GSVD) of matrix pairs when new rows are added to one of the matrices or old rows are deleted. Two classes of algorithms are developed, one based on the CS decomposition formulation of the GSVD and the other based on the generalized eigenvalue decomposition formulation. In both cases we show that the updating and downdating problems can be reduced to a rank-one SVD updating problem. We also provide perturbation analysis for the cases when the added or deleted rows are subject to errors. Numerical experiments on direction-of-arrival (DOA) finding with colored noises are carried out to demonstrate the tracking ability of the algorithms. The work of the first author was supported in part by NSF grants CCR-9308399 and CCR-9619452. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

矩阵广义逆新的扰动上界

利用矩阵的奇异值分解方法,研究了矩阵广义逆的扰动上界,得到了在F-范数下矩阵广义逆的扰动上界定理,所得定理推广并彻底改进了近期的相关结果.相应的数值算例验证了定理的有效性.     

A new Tikhonov regularization method

The numerical solution of linear discrete ill-posed problems typically requires regularization, i.e., replacement of the available ill-conditioned problem by a nearby better conditioned one. The most popular regularization methods for problems of small to moderate size, which allow evaluation of the singular value decomposition of the matrix defining the problem, are the truncated singular value decomposition and Tikhonov regularization. The present paper proposes a novel choice of regularization matrix for Tikhonov regularization that bridges the gap between Tikhonov regularization and truncated singular value decomposition. Computed examples illustrate the benefit of the proposed method.     

Randomized algorithms for distributed computation of principal component analysis and singular value decomposition

Randomized algorithms provide solutions to two ubiquitous problems: (1) the distributed calculation of a principal component analysis or singular value decomposition of a highly rectangular matrix, and (2) the distributed calculation of a low-rank approximation (in the form of a singular value decomposition) to an arbitrary matrix. Carefully honed algorithms yield results that are uniformly superior to those of the stock, deterministic implementations in Spark (the popular platform for distributed computation); in particular, whereas the stock software will without warning return left singular vectors that are far from numerically orthonormal, a significantly burnished randomized implementation generates left singular vectors that are numerically orthonormal to nearly the machine precision.     

Stability theorems for singular perturbation of eigenvalues

Two stability, i.e., convergence in multiplicity, theorems for eigenvalues of non-self-adjoint singular perturbation problems are proved in this paper. Use is made of quadratic interpolation between Hubert spaces to obtain an extension of the notion of a holomorphic family of type (B). Applications to singular perturbation problems for non-self-adjoint elliptic partial differential operators, and to singular potential perturbation problems with complex coupling constants, are presented.This research was partially supported by NSF Grant 02 MCS-7902663     

Perturbation analysis of generalized singular subspaces

This paper, as a continuation of the paper [20] in Numerische Mathematik, studies the subspaces associated with the generalized singular value decomposition. Second order perturbation expansions, Fréchet derivatives and condition numbers, and perturbation bounds for the subspaces are derived. Received January 26, 1996 / Revised version received May 14, 1997     

Coercive singular perturbations II: Reduction and convergence

An algebra of pseudodifferential singular perturbations is introduced. It provides a constructive machinery in order to reduce an elliptic singularly perturbed operator (in $\text{R}$ⁿ or on a smooth manifold without border) to a regular perturbation. The technique developed is applied to some singularly perturbed boundary value problems as well. Special attention is given to a singular perturbation appearing in the linear theory of thin elastic plates. A Wiener-Hopf-type operator containing the small parameter reduces this singular perturbation to a regular one. It also gives rise to a natural recurrence process for the construction of high-order asymptotic formulae for the solution of the perturbed problem. The method presented can be extended to the general coercive singular perturbations.     

Subspace-restricted singular value decompositions for linear discrete ill-posed problems

The truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. These problems are numerically underdetermined. Therefore, it can be beneficial to incorporate information about the desired solution into the solution process. This paper describes a modification of the singular value decomposition that permits a specified linear subspace to be contained in the solution subspace for all truncations. Modifications that allow the range to contain a specified subspace, or that allow both the solution subspace and the range to contain specified subspaces also are described.     

Combined perturbation bounds: Ⅱ. Polar decompositions

In this paper, we study the perturbation bounds for the polar decomposition A= QH where Q is unitary and H is Hermitian. The optimal (asymptotic) bounds obtained in previous works for the unitary factor, the Hermitian factor and singular values of A are σ2r||△Q||2F ≤ ||△A||2F,1/2||△H||2F ≤ ||△A||2F and ||△∑||2F ≤ ||△A||2F, respectively, where ∑ = diag(σ1, σ2,..., σr, 0,..., 0) is the singular value matrix of A and σr denotes the smallest nonzero singular value. Here we present some new combined (asymptotic)perturbation bounds σ2r ||△Q||2F+1/2||△H||2F≤ ||△A||2F and σ2r||△Q||2F+||△∑ ||2F ≤||△A||2F which are optimal for each factor. Some corresponding absolute perturbation bounds are also given.     

Wave Propagation in Dissipative or Dispersive Non-linear Media

A singular perturbation method is developed to investigate onedimensional weak nonlinear waves in dissipative or dispersivemedia. Utilizing this method a boundary value problem for asystem of partial differential equations characterizing wavepropagation in homogeneous dissipative or dispersive media isstudied. In order to obtain a first-order uniformly valid solution,the problem is reduced to an initial value problem for scalarnon-linear partial differential equation. Some special casesarising from the structure of coefficient matrices are examinedand the method is extended to these cases. As an applicationof the perturbation method, various problems of wave propagationin a finite linear viscoelastic half-space are studied.