Preconditionings and splittings for rectangular systems

Summary Recently Eiermann, Marek, and Niethammer have shown how to applysemiiterative methods to a fixed point systemx=Tx+c which isinconsistent or in whichthe powers of the fixed point operator T have no limit, to obtain iterative methods which converge to some approximate solution to the fixed point system. In view of their results we consider here stipulations on apreconditioning QAx=Qb of the systemAx=b and, separately, on asplitting A=M–N which lead to fixed point systems such that, with the aid of a semiiterative method, the iterative scheme converges to a weighted Moore-Penrose solution to the systemAx=b. We show in several ways that to obtain a meaningful limit point from a semiiterative method requires less restrictions on the splittings or the reconditionings than those which have been required in the classical Picard iterative method (see, e.g., the works of Berman and Plemmons, Berman and Neumann, and Tanabe).We pay special attention to the case when the weighted Moore-Penrose solution which is sought is the minimal norm least squares solution toAx=b.Research supported by the Deutsche ForschungsgemeinschaftPartially supported by AFOSR research grant 88-0047     

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

Scattered data fitting of Hermite type by a weighted meshless method

In many practical problems, it is often desirable to interpolate not only the function values but also the values of derivatives up to certain order, as in the Hermite interpolation. The Hermite interpolation method by radial basis functions is used widely for solving scattered Hermite data approximation problems. However, sometimes it makes more sense to approximate the solution by a least squares fit. This is particularly true when the data are contaminated with noise. In this paper, a weighted meshless method is presented to solve least squares problems with noise. The weighted meshless method by Gaussian radial basis functions is proposed to fit scattered Hermite data with noise in certain local regions of the problem’s domain. Existence and uniqueness of the solution is proved. This approach has one parameter which can adjust the accuracy according to the size of the noise. Another advantage of the weighted meshless method is that it can be used for problems in high dimensions with nonregular domains. The numerical experiments show that our weighted meshless method has better performance than the traditional least squares method in the case of noisy Hermite data.     

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.     

A weighted least squares method for scattered data fitting

In this paper, we present a weighted least squares method to fit scattered data with noise. Existence and uniqueness of a solution are proved and an error bound is derived. The numerical experiments illustrate that our weighted least squares method has better performance than the traditional least squares method in case of noisy data.     

Convergence results for an accelerated nonlinear cimmino algorithm

Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.     

A meshless local Galerkin method for the numerical solution of Hammerstein integral equations based on the moving least squares technique

In this paper, a computational scheme is proposed to estimate the solution of one- and two-dimensional Fredholm-Hammerstein integral equations of the second kind. The method approximates the solution using the discrete Galerkin method based on the moving least squares (MLS) approach as a locally weighted least squares polynomial fitting. The discrete Galerkin technique for integral equations results from the numerical integration of all integrals in the system corresponding to the Galerkin method. Since the proposed method is constructed on a set of scattered points, it does not require any background meshes and so we can call it as the meshless local discrete Galerkin method. The implication of the scheme for solving two-dimensional integral equations is independent of the geometry of the domain. The new method is simple, efficient and more flexible for most classes of nonlinear integral equations. The error analysis of the method is provided. The convergence accuracy of the new technique is tested over several Hammerstein integral equations and obtained results confirm the theoretical error estimates.     

Spectral collocation and radial basis function methods for one-dimensional interface problems

Differential equations with singular sources or discontinuous coefficients yield non-smooth or even discontinuous solutions. This problem is known as the interface problem. High-order numerical solutions suffer from the Gibbs phenomenon in that the accuracy deteriorates if the discontinuity is not properly treated. In this work, we use the spectral and radial basis function methods and present a least squares collocation method to solve the interface problem for one-dimensional elliptic equations. The domain is decomposed into multiple sub-domains; in each sub-domain, the collocation solution is sought. The solution should satisfy more conditions than the given conditions associated with the differential equations, which makes the problem over-determined. To solve the over-determined system, the least squares method is adopted. For the spectral method, the weighted norm method with different scaling factors and the mixed formulation are used. For the radial basis function method, the weighted shape parameter method is presented. Numerical results show that the least squares collocation method provides an accurate solution with high efficacy and that better accuracy is obtained with the spectral method.     

A dynamic meshless method for the least squares problem with some noisy subdomains

The interpolation method by radial basis functions is used widely for solving scattered data approximation. However, sometimes it makes more sense to approximate the solution by least squares fit. This is especially true when the data are contaminated with noise. A meshfree method namely, meshless dynamic weighted least squares (MDWLS) method, is presented in this paper to solve least squares problems with noise. The MDWLS method by Gaussian radial basis function is proposed to fit scattered data with some noisy areas in the problem’s domain. Existence and uniqueness of a solution is proved. This method has one parameter which can adjusts the accuracy according to the size of noises. Another advantage of the developed method is that it can be applied to problems with nonregular geometrical domains. The new approach is applied for some problems in two dimensions and the obtained results confirm the accuracy and efficiency of the proposed method. The numerical experiments illustrate that our MDWLS method has better performance than the traditional least squares method in case of noisy data.     

Error estimation for a weighted minimum-norm least squares solution with positive definite weights

The weighted least squares problem is considered. Given a generally inconsistent system of linear algebraic equations, error estimates are obtained for its weighted minimum-norm least squares solution under perturbations of the matrix and the right-hand side, including the case of rank modifications of the perturbed matrix.     

ON THE SPLITTINGS FOR RECTANGULAR SYSTEMS

1.IntroductionItiswellknownthatthemostprevaJentapproachforobtainingaAsedpoilltsystem'ofthefollowingsystemAx=b,AECm"(1.1)isviaasplittingofthecoefficientmatrirAintoA=U-V(1.2)Ifm=nandUisnonsingular,wepresenttheequivalentformulationof(1.1)byx=U-1Vx+U-1b-(1.3)Ifm/norifUisnotinvertible,wecan,bytakingagenerallzedinverseU-ofU(insteadofU-'),extend(l.3)byconsideringthefixedpointsystemx=U-Vx+U-b.(1.4)GeneraJizedinversesofmatricesplayakeyroleinourpreselitwork.Itisinstructiveforourpurposestothin…     

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.     

Perturbation theory for generalized and constrained linear least squares

The perturbation analysis of weighted and constrained rank‐deficient linear least squares is difficult without the use of the augmented system of equations. In this paper a general form of the augmented system is used to get simple perturbation identities and perturbation bounds for the general linear least squares problem both for the full‐rank and rank‐deficient problem. Perturbation identities for the rank‐deficient weighted and constrained case are found as a special case. Interesting perturbation bounds and condition numbers are derived that may be useful when considering the stability of a solution of the rank‐deficient general least squares problem. Copyright © 2000 John Wiley & Sons, Ltd.     

Local Weighted Composite Quantile Estimating for Varying Coefficient Models

A generalization of classical linear models is varying coefficient models, which offer a flexible approach to modeling nonlinearity between covariates. A method of local weighted composite quantile regression is suggested to estimate the coefficient functions. The local Bahadur representation of the local estimator is derived and the asymptotic normality of the resulting estimator is established. Comparing to the local least squares estimator, the asymptotic relative efficiency is examined for the local weighted composite quantile estimator. Both theoretical analysis and numerical simulations reveal that the local weighted composite quantile estimator can obtain more efficient than the local least squares estimator for various non-normal errors. In the normal error case, the local weighted composite quantile estimator is almost as efficient as the local least squares estimator. Monte Carlo results are consistent with our theoretical findings. An empirical application demonstrates the potential of the proposed method.     

Sparse Linear Least Squares Problems in Optimization

Numerical and computational aspects of direct methods for largeand sparseleast squares problems are considered. After a brief survey of the most oftenused methods, we summarize the important conclusions made from anumerical comparison in matlab. Significantly improved algorithms haveduring the last 10-15 years made sparse QR factorization attractive, andcompetitive to previously recommended alternatives. Of particular importanceis the multifrontal approach, characterized by low fill-in, dense subproblemsand naturally implemented parallelism. We describe a Householder multifrontalscheme and its implementation on sequential and parallel computers. Availablesoftware has in practice a great influence on the choice of numericalalgorithms. Less appropriate algorithms are thus often used solely because ofexisting software packages. We briefly survey softwarepackages for the solution of sparse linear least squares problems. Finally,we focus on various applications from optimization, leading to the solution oflarge and sparse linear least squares problems. In particular, we concentrateon the important case where the coefficient matrix is a fixed general sparsematrix with a variable diagonal matrix below. Inner point methods forconstrained linear least squares problems give, for example, rise to suchsubproblems. Important gains can be made by taking advantage of structure.Closely related is also the choice of numerical method for these subproblems.We discuss why the less accurate normal equations tend to be sufficient inmany applications.     

Some observations on local least squares

In previous work we introduced a construction to produce biorthogonal multiresolutions from given subdivisions. The approach involved estimating the solution to a least squares problem by means of a number of smaller least squares approximations on local portions of the data. In this work we use a result by Dahlquist, et al. on the method of averages to make observational comparisons between this local least squares estimation and full least squares approximation. We have explored examples in two problem domains: data reduction and data approximation. We observe that, particularly for design matrices with a repetitive pattern of column entries, the least squares solution is often well estimated by local least squares, that the estimation rapidly improves with the size of the local least squares problems, and that the quality of the estimate is largely independent of the size of the full problem. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 93E24     

A condition analysis of the weighted linear least squares problem using dual norms

In this paper, based on the theory of adjoint operators and dual norms, we define condition numbers for a linear solution function of the weighted linear least squares problem. The explicit expressions of the normwise and componentwise condition numbers derived in this paper can be computed at low cost when the dimension of the linear function is low due to dual operator theory. Moreover, we use the augmented system to perform a componentwise perturbation analysis of the solution and residual of the weighted linear least squares problems. We also propose two efficient condition number estimators. Our numerical experiments demonstrate that our condition numbers give accurate perturbation bounds and can reveal the conditioning of individual components of the solution. Our condition number estimators are accurate as well as efficient.     

Direct Implementation of Tikhonov Regularization for the First Kind Integral Equation

A common way to handle the Tikhonov regularization method for the first kind Fredholm integral equations, is first to discretize and then to work with the final linear system. This unavoidably inflicts discretization errors which may lead to disastrous results, especially when a quadrature rule is used. We propose to regularize directly the integral equation resulting in a continuous Tikhonov problem. The Tikhonov problem is reduced to a simple least squares problem by applying the Golub-Kahan bidiagonalization (GKB) directly to the integral operator. The regularization parameter and the iteration index are determined by the discrepancy principle approach. Moreover, we study the discrete version of the proposed method resulted from numerical evaluating the needed integrals. Focusing on the nodal values of the solution results in a weighted version of GKB-Tikhonov method for linear systems arisen from the Nyström discretization. Finally, we use numerical experiments on a few test problems to illustrate the performance of our algorithms.     

A weighted pseudoinverse,generalized singular values,and constrained least squares problems

The weighted pseudoinverse providing the minimum semi-norm solution of the weighted linear least squares problem is studied. It is shown that it has properties analogous to those of the Moore-Penrose pseudoinverse. The relation between the weighted pseudoinverse and generalized singular values is explained. The weighted pseudoinverse theory is used to analyse least squares problems with linear and quadratic constraints. A numerical algorithm for the computation of the weighted pseudoinverse is briefly described.This work was supported in part by the Swedish Institute for Applied Mathematics.