Vector extrapolation enhanced TSVD for linear discrete ill-posed problems

The truncated singular value decomposition (TSVD) is a popular solution method for small to moderately sized linear ill-posed problems. The truncation index can be thought of as a regularization parameter; its value affects the quality of the computed approximate solution. The choice of a suitable value of the truncation index generally is important, but can be difficult without auxiliary information about the problem being solved. This paper describes how vector extrapolation methods can be combined with TSVD, and illustrates that the determination of the proper value of the truncation index is less critical for the combined extrapolation-TSVD method than for TSVD alone. The numerical performance of the combined method suggests a new way to determine the truncation index. In memory of Gene H. Golub.     

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.     

Linear system solution by null‐space approximation and projection (SNAP)

Solutions of large sparse linear systems of equations are usually obtained iteratively by constructing a smaller dimensional subspace such as a Krylov subspace. The convergence of these methods is sometimes hampered by the presence of small eigenvalues, in which case, some form of deflation can help improve convergence. The method presented in this paper enables the solution to be approximated by focusing the attention directly on the ‘small’ eigenspace (‘singular vector’ space). It is based on embedding the solution of the linear system within the eigenvalue problem (singular value problem) in order to facilitate the direct use of methods such as implicitly restarted Arnoldi or Jacobi–Davidson for the linear system solution. The proposed method, called ‘solution by null‐space approximation and projection’ (SNAP), differs from other similar approaches in that it converts the non‐homogeneous system into a homogeneous one by constructing an annihilator of the right‐hand side. The solution then lies in the null space of the resulting matrix. We examine the construction of a sequence of approximate null spaces using a Jacobi–Davidson style singular value decomposition method, called restarted SNAP‐JD, from which an approximate solution can be obtained. Relevant theory is discussed and the method is illustrated by numerical examples where SNAP is compared with both GMRES and GMRES‐IR. Copyright © 2006 John Wiley & Sons, Ltd.     

The general a posteriori truncation method and its application to radiogenic source identification for the Helium production–diffusion equation

The purpose of the present paper is twofold: (i) to formulate the truncation method with a posteriori parameter choice rule in a uniform framework that can be adapted to solve a kind of linear inverse problems for which the solution can be represented by the eigensystem; (ii) to apply the a posteriori truncation method to the radiogenic source identification for the Helium production–diffusion equation, which is closely connected to the Helium isotopes dating as one method of the low temperature thermochronometry, the specific rate of convergence between the regularized solution and the exact solution is calculated, and numerical examples shed light on the efficiency and accuracy of the proposed 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.     

B-spline finite-element method in polar coordinates

A numerical solution method for two-dimensional electromagnetic field problems is presented using the B-spline finite-element expression based on polar coordinates. The technique has two main advantages: (1) to avoid the truncation errors at some curved boundaries and (2) to improve the accuracy of singular boundary-value problems with a sharp corner. The B-spline finite-element formulation in polar coordinates is derived and its numerical applications are illustrated by an eddy current problem and several waveguide eigenvalue problems.     

Suboptimal feedback control of linear periodic systems

A method is developed for the approximate design of an optimal state regulator for a linear periodically varying system with quadratic performance index. The periodic term is taken to be a perturbation to the system. By making use of a power-series expansion in a small parameter, associated with periodic terms, a set of matrix equations is derived for determining successively a feedback gain. Given periodic terms of a Fourier-series form, explicit solutions are obtained for those matrix equations. A sufficient condition for existence and periodicity of the solution is also shown. Further, the performance degradation resulting from a truncation of the power-series solution is investigated. The method may effectively be used in a computer-programmed computation.     

A numerical approach for solving weakly singular partial integro‐differential equations via two‐dimensional‐orthonormal Bernstein polynomials with the convergence analysis

In this paper, we develop an efficient matrix method based on two‐dimensional orthonormal Bernstein polynomials (2D‐OBPs) to provide approximate solution of linear and nonlinear weakly singular partial integro‐differential equations (PIDEs). First, we approximate all functions involved in the considerable problem via 2D‐OBPs. Then, by using the operational matrices of integration, differentiation, and product, the solution of Volterra singular PIDEs is transformed to the solution of a linear or nonlinear system of algebraic equations which can be solved via some suitable numerical methods. With a small number of bases, we can find a reasonable approximate solution. Moreover, we establish some useful theorems for discussing convergence analysis and obtaining an error estimate associated with the proposed method. Finally, we solve some illustrative examples by employing the presented method to show the validity, efficiency, high accuracy, and applicability of the proposed technique.     

Classroom note: Polynomial solutions of the Laguerre equation and other differential equations near a singular point

It can be shown that if a differential equation is analytic near a point, then it is always possible to select a forcing term along with initial conditions that will ensure the solution to the new non-homogeneous equation is a polynomial that is the finite, truncated portion of the (infinite) series solution of the original equation. It turns out that this result can be extended to expansions about a singular point. The conditions under which such a polynomial truncation can be accomplished about a singular point are presented in the Appendix. A brief algorithm is described that enables one to choose the appropriate forcing term and initial conditions. Following this, an example involving Laguerre's equation is presented.     

Convergence of the truncation error in calculating singular convolutions

We study the truncation error in the problem of calculating singular convolutions, that is, in the problem of approximating an unbounded linear operator of a certain specific form (of a singular convolution) by using discrete information about the operator. We consider the convergence of the truncation error and obtain necessary and sufficient convergence conditions as well as some effective estimates for the error. Translated fromMatematicheskie Zametki, Vol. 59, No. 6, pp. 893–908, June, 1996. In conclusion, the author wishes to express gratitude to D. A. Popov for his constant attention to the present work.     

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.     

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.     

A numerical solution of singular integrodifferential equations with variable coefficients

A method for the numerical solution of singular integrodifferential equations is presented where the integrals are discretized by using a convenient quadrature rule. Then the problem is reduced to a system of linear algebraic equations by applying the discretized functional equation to appropriately selected collocation points. This technique constitutes an extension of an analogous method convenient for solving singular integral equations which was proposed by the authors.     

Matrix displacement mappings in the numerical solution of functional and nonlinear differential equations with the tau method

The use of matrix displacement mappings reduces most matrix operations required in the construction of an approximate solution of a functional or differential equation by means of Ortiz' formulation of the Tau method to index shifts. The coefficient vector of the approximate solution is defined implicitly by a very sparse system of linear algebraic equations. The contributions of the differential or functional operator, and of the supplementary conditions of the problem (initial, boundary, or multipoint conditions) are treated with a single and versatile procedure of remarkable simplicity, which can be easily implemented in a computer. We give two nontrivial examples on the application of this approach: the first is a nonlinear boundary value problem with a continuous locus of singular points and multiple solutions, where stiffness is present, the second is a functional differential equation arising in analytic number theory. In both cases we obtain results of nigh accuracy.     

含奇线(奇面)二阶线性偏微分方程的解在奇线(奇面)附近的性质

本文的第一部分研究了含奇线方程的解在奇线附近的性质;引进了“指数”的概念,从而给出了关于这类方程的“奇型郭西问题”的正确提法;并且通过一种特殊的积分-征分方程的研究,证明了这种“奇型郭西问题”的解的存在性,并且给出其近似解法;最后,就一般的情形,给出了方程一般解的表达式,从而说明了在β+β′<0时,郭西问题的多解性。本文的第二部分研究了空间含奇面方程(?)其中 A_σ是任一祇与变元σ=(σ_1…,σ_n)有关的算子,并且关于(15.5)的奇型郭西问题的解可以用关于方程(不合奇面)(?)(15.6)的郭西问题的解表示出来。同样的方法可用来解决空间却普里金方程(17.1)的郭西问题。     

A semi-iterative method for real spectrum singular linear systems with an arbitrary index

In this paper we develop a semi-iterative method for computing the Drazin-inverse solution of a singular linear system Ax = b, where the spectrum of A is real, but its index (i.e., the size of its largest Jordan block corresponding to the eigenvalue zero) is arbitrary. The method employs a set of polynomials that satisfy certain normalization conditions and minimize some well-defined least-squares norm. We develop an efficient recursive algorithm for implementing this method that has a fixed length independent of the index of A. Following that, we give a complete theory of convergence, in which we provide rates of convergence as well. We conclude with a numerical application to determine eigenprojections onto generalized eigenspaces. Our treatment extends the work of Hanke and Hochbruck (1993) that considers the case in which the index of A is 1.     

ON THE SINGULAR ONE DIMENSIONAL P-LAPLACIAN-LIKE EQUATION WITH NEUMANN BOUNDARY CONDITIONS

1IntroductionInthispaper,weconsiderthesolvabilityofsingularonedimensionalpLaplacian-likeequationwithNeumannboundaryconditionswhereA(()ispositivefor(>0,h(t)EL'([0,1]),gisacontinuousfunctiondefinedon(--co,0)U(0, co)suchthatg(f)-0asf'l-cojg(()- coas(-0 ,g(()---coas(-0--,andg(')(>0for'/0.Afunctionu(t)issaidtobeasolutionof(1.1),ifthefollowingconditionsaresatisfied:Itiseasytoseethatthenecessaryconditionfortheexistenceofthesolutionof(1.1)isInfact,fromtheassumptionsong,weknowthatu(t)/0foralltE(0,1)…     

A New Scheme for the Tensor Representation

The paper presents a new scheme for the representation of tensors which is well-suited for high-order tensors. The construction is based on a hierarchy of tensor product subspaces spanned by orthonormal bases. The underlying binary tree structure makes it possible to apply standard Linear Algebra tools for performing arithmetical operations and for the computation of data-sparse approximations. In particular, a truncation algorithm can be implemented which is based on the standard matrix singular value decomposition (SVD) method.     

Right preconditioned MINRES for singular systems†

We consider solving large sparse symmetric singular linear systems. We first introduce an algorithm for right preconditioned minimum residual (MINRES) and prove that its iterates converge to the preconditioner weighted least squares solution without breakdown for an arbitrary right‐hand‐side vector and an arbitrary initial vector even if the linear system is singular and inconsistent. For the special case when the system is consistent, we prove that the iterates converge to a min‐norm solution with respect to the preconditioner if the initial vector is in the range space of the right preconditioned coefficient matrix. Furthermore, we propose a right preconditioned MINRES using symmetric successive over‐relaxation (SSOR) with Eisenstat's trick. Some numerical experiments on semidefinite systems in electromagnetic analysis and so forth indicate that the method is efficient and robust. Finally, we show that the residual norm can be further reduced by restarting the iterations.     

Classical solutions of two-dimensional stokes problems on non-smooth domains. Part 2: Collocation method for the radon equation

The non-uniquely solvable Radon boundary integral equation for the two-dimensional Stokes-Dirichlet problem on a non-smooth domain is transformed into a well posed one by a suitable compact perturbation of the velocity double-layer potential operator. The solution to the modified equation is decomposed into a regular part and a finite linear combination of intrinsic singular functions whose coefficients are computed from explicit formulae. Using these formulae, the classical collocation method, defined by continuous piecewise linear vector-valued basis functions, which converges slowly because of the lack of regularity of the solution, is improved into a collocation dual singular function method with optimal rates of convergence for the solution and for the coefficients of singularities.