Extrapolation vs. projection methods for linear systems of equations

It is shown that the four vector extrapolation methods, minimal polynomial extrapolation, reduced rank extrapolation, modified minimal polynomial extrapolation, and topological epsilon algorithm, when applied to linearly generated vector sequences, are Krylov subspace methods, and are equivalent to some well known conjugate gradient type methods. A unified recursive method that includes the conjugate gradient, conjugate residual, and generalized conjugate gradient methods is developed. Finally, the error analyses for these methods are unified, and some known and some new error bounds for them are given.     

Approximate pseudoinverse solutions to ill-conditioned linear systems

A new method for the numerical solution to ill-conditioned systems of linear equations based on the matrix pseudoinverse is presented. Some illustrative numerical results are provided.     

Krylov projection methods for linear Hamiltonian systems

Numerical Algorithms - In this paper, we are concerned with the numerical treatment of a recent diffuse interface model for two-phase flow of electrolyte solutions (Campillo-Funollet et al., SIAM...     

Preconditioning projection methods for solving algebraic linear systems

Numerical experiments have shown that projection methods are robust for solving the problem of finding a point satisfying a linear system of n variables and m equations; however, their qualities of convergence depend on certain parameters: an n × n symmetric positive definite matrix M, and a vector u with m components. We are concerned here with the choice of M. Through a link with Conjugate Gradient methods we determine an expedient M. Preliminary numerical results on a hard 3D partial differential equation are highly promising. We solve a discretized system that could not be solved by conventional methods. We also give hints on how to adapt our findings to the solution of a linear system of inequalities. This is the first stage of a forthcoming research. This revised version was published online in June 2006 with corrections to the Cover Date.     

A general projection algorithm for solving systems of linear equations

In this paper, we give a general projection algorithm for implementing some known extrapolation methods such as the MPE, the RRE, the MMPE and others. We apply this algorithm to vectors generated linearly and derive new algorithms for solving systems of linear equations. We will show that these algorithms allow us to obtain known projection methods such as the Orthodir or the GCR.     

Accelerated PMHSS iteration methods for complex symmetric linear systems

In this paper, we introduce and analyze an accelerated preconditioning modification of the Hermitian and skew-Hermitian splitting (APMHSS) iteration method for solving a broad class of complex symmetric linear systems. This accelerated PMHSS algorithm involves two iteration parameters α,β and two preconditioned matrices whose special choices can recover the known PMHSS (preconditioned modification of the Hermitian and skew-Hermitian splitting) iteration method which includes the MHSS method, as well as yield new ones. The convergence theory of this class of APMHSS iteration methods is established under suitable conditions. Each iteration of this method requires the solution of two linear systems with real symmetric positive definite coefficient matrices. Theoretical analyses show that the upper bound σ₁(α,β) of the asymptotic convergence rate of the APMHSS method is smaller than that of the PMHSS iteration method. This implies that the APMHSS method may converge faster than the PMHSS method. Numerical experiments on a few model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of the new method.     

Accelerated iterative methods for finding solutions of a system of nonlinear equations

In this paper, we present a technique to construct iterative methods to approximate the zeros of a nonlinear equation F(x)=0, where F is a function of several variables. This technique is based on the approximation of the inverse function of F and on the use of a fixed point iteration. Depending on the number of steps considered in the fixed point iteration, or in other words, the number of evaluations of the function F, we obtain some variants of classical iterative processes to solve nonlinear equations. These variants improve the order of convergence of classical methods. Finally, we show some numerical examples, where we use adaptive multi-precision arithmetic in the computation that show a smaller cost.     

Conjugate direction methods for solving systems of linear equations

A generalization of the notion of a set of directions conjugate to a matrix is shown to lead to a variety of finitely terminating iterations for solving systems of linear equations. The errors in the iterates are characterized in terms of projectors constructable from the conjugate directions. The natural relations of the algorithms to well known matrix decompositions are pointed out. Some of the algorithms can be used to solve linear least squares problems.This work was supported by the Office of Naval Research under contract number N 00014-67-A-0126.     

A projection method for least-squares solutions to overdetermined systems of linear inequalities

An algorithm previously introduced by the author for finding a feasible point of a system of linear inequalities is further investigated. For inconsistent systems, it is shown to generate a sequence converging at a linear rate to the set of least-squares solutions. The algorithm is a projection-type method, and is a manifestation of the proximal-point algorithm.     

On hybrid iterative methods for nonsymmetric systems of linear equations

Summary. Hybrid methods for the solution of systems of linear equations consist of a first phase where some information about the associated coefficient matrix is acquired, and a second phase in which a polynomial iteration designed with respect to this information is used. Most of the hybrid algorithms proposed recently for the solution of nonsymmetric systems rely on the direct use of eigenvalue estimates constructed by the Arnoldi process in Phase I. We will show the limitations of this approach and propose an alternative, also based on the Arnoldi process, which approximates the field of values of the coefficient matrix and of its inverse in the Krylov subspace. We also report on numerical experiments comparing the resulting new method with other hybrid algorithms. Received May 27, 1993 / Revised version received November 14, 1994     

Two composition methods for solving certain systems of linear equations

Summary This note is concerned with the following problem: Given a systemA·x=b of linear equations and knowing that certains of its subsystemsA ¹·x ¹=b ¹, ...,A ^m ·x ^m =b ^m can be solved uniquely what can be said about the regularity ofA and how to find the solutionx fromx ¹, ...,x ^m ? This question is of particular interest for establishing methods computing certain linear or quasilinear sequence transformations recursively [7, 13, 15].Work performed under NATO Research Grant 027-81     

Superconvergence results of iterated projection methods for linear Volterra integral equations of second kind

In this paper, we develop the iteration techniques for Galerkin and collocation methods for linear Volterra integral equations of the second kind with a smooth kernel, using piecewise constant functions. We prove that the convergence rates for every step of iteration improve by order \({\mathcal {O}}(h^{2})\) for Galerkin method, whereas in collocation method, it is improved by \({\mathcal {O}}(h)\) in infinity norm. We also show that the system to be inverted remains same for every iteration as in the original projection methods. We illustrate our results by numerical examples.     

Enclosing solutions of complex linear systems of equations iteratively

We consider the interval iteration [x ]^{k +1} = [A ][x ]^k + [b ] in different interval arithmetics with the aim to enclose solutions of x = Ax +b in the case that A and b are only known to be contained in some given intervals. We give necessary and sufficient criteria for the convergence of the interval iteration for every initial interval vector [x ]⁰ to some [x ]* = [x ]*([x ]⁰) with respect to the considered interval arithmetic. Such a limit is a solution of the interval system [x ] = [A ][x ] + [b ]. If we compare the interval arithmetics with respect to the behavior of [x ]^{k +1} = [A ][x ]^k + [b ] we come to the conclusion, that the special choice of the arithmetic has a sensitive influence on the convergence of the sequence. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Symmetric linear multistep methods for second-order differential equations with periodic solutions

Special symmetric linear multistep methods for second-order differential equations without first derivatives are proposed. The methods can be tuned to a possibly a priori knowledge of the user on the location of the frequencies, that are dominant in the exact solution. On the basis of such extra information the truncation error can considerably be reduced in magnitude. Numerical results are compared with results produced by the symmetric methods of Lambert and Watson and the method of Gautschi.     

A study of semiiterative methods for nonsymmetric systems of linear equations

Summary Given a nonsingular linear systemA x=b, a splittingA=M–N leads to the one-step iteration (1)x _m =T X _m–1 +c withT:=M ^–1N andc:=M ^–1 b. We investigate semiiterative methods (SIM's) with respect to (1), under the assumption that the eigenvalues ofT are contained in some compact set of , with 1. There exist SIM's which are optimal with respect to , but, except for some special sets , such optimal methods are not explicitly known in general. Using results about maximal convergence of polynomials and uniformly distributed nodes from approximation and function theory, we describe here SIM's which are asymptotically optimal with respect to . It is shown that Euler methods, extensively studied by Niethammer-Varga [NV], are special SIM's. Various algorithms for SIM's are also derived here. A 1-1 correspondence between Euler methods and SIM's, generated by generalized Faber polynomials, is further established here. This correspondence gives that asymptotically optimal Euler methods are quite near the optimal SIM's.Dedicated to Professor Karl Zeller (Universität Tübingen) on the occasion of his sixtieth birthday (December 28, 1984)     

Application of homotopy perturbation methods for solving systems of linear equations

In this paper, homotopy perturbation methods (HPMs) are applied to obtain the solution of linear systems, and conditions are deduced to check the convergence of the homotopy series. Moreover, we have adapted the Richardson method, the Jacobi method, and the Gauss-Seidel method to choose the splitting matrix. The numerical results indicate that the homotopy series converges much more rapidly than the direct methods for large sparse linear systems with a small spectrum radius.