An iterative method for solving systems of linear algebraic equations

An iterative solution process for systems of linear algebraic equations is proposed. It converges starting from any initial approximation and theoretically does not require preliminary transformation of the input data.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 55, pp. 64–68, 1985.     

Optimization of the quasi-Monte Carlo algorithm for solving systems of linear algebraic equations

An interesting conclusion about error reduction of the modified quasi-Monte Carlo method for solving systems of linear algebraic equations is suggested. The Monte Carlo method is compared with the quasi-Monte Carlo method and its modification. The optimal choice of the parameters of the Markov chain for the modified Monte Carlo method applied to solving systems of linear equations is substantiated.     

Three-layer finite difference method for solving linear differential algebraic systems of partial differential equations

A boundary value problem is examined for a linear differential algebraic system of partial differential equations with a special structure of the associate matrix pencil. The use of an appropriate transformation makes it possible to split such a system into a system of ordinary differential equations, a hyperbolic system, and a linear algebraic system. A three-layer finite difference method is applied to solve the resulting problem numerically. A theorem on the stability and the convergence of this method is proved, and some numerical results are presented.     

The focal point method for solving systems of linear equations

The Focal Point method of solving systems of linear equations is based on the linearity of matrix transformations and the fact that each equation in the system defines a hyperplane of solutions. As with Gaussian elimination the number of multiplications is a cubic polynomial inn with leading coefficientn ³/3. Some of the benefits of this new method are that it needs approximatelyn ²/4 storage registers and that the zeroes of the system are preserved. Thus for sparse systems the operation count can be significantly reduced. Numerical examples using initial segments of the Hilbert matrix demonstrate that this new method can be very accurate.

---

Zusammenfassung Die Vektor Projektions Methode zur Lösung linearer Gleichungssysteme ist darauf begründet, daß jede Gleichung eine Hyperebene definiert und daß die Berechnung der Projektionspunkte linear ist. Wie bei der Gauss'schen Eliminierung wird die Anzahl der Multiplikationen durch ein kubisches Polynom mit höchstem Koeffizientenn ³/3 beschrieben. Zwei Vorteile der neuen Methode sind, daß nur etwan ²/4 Speicherplätze benötigt werden, und daß Null-Koeffizienten im Gleichungsystem erhalten bleiben. Damit kann die Anzahl der Rechenoperationen bei dünnbesetzten Matrizen erheblich reduziert werden. Die gute Genauigkeit des neuen Verfahrens wird am Beispiel der numerischen Inversion von Hilbert-Matrizen verschiedener Größe gezeigt.

     

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.     

Multigrid method as an accelerating procedure for solving systems of linear algebraic equations with a dissipative matrix

Rostov State University. Translated from Matematicheskoe Modelirovanie, Published by Moscow University, Moscow, 1993, pp. 45–52.     

Maslov dequantization and the homotopy method for solving systems of nonlinear algebraic equations

The Maslov dequantization allows one to interpret the classical Gräffe-Lobachevski method for calculating the roots of polynomials in dimension one as a homotopy procedure for solving a certain system of tropical equations. As an extension of this analogy to systems of n algebraic equations in dimension n, we introduce a tropical system of equations whose solution defines the structure and initial iterations of the homotopy method for calculating all complex roots of a given algebraic system. This method combines the completeness and the rigor of the algebraicgeometrical analysis of roots with the simplicity and the convenience of its implementation, which is typical of local numerical algorithms.     

Polynomial of best uniform approximation in an iterative method of solving systems of linear algebraic equations

Tyumen. Translated from Sibirskii Matematicheskii Zhurnal, Vol. 33, No. 1, pp. 62–68, January–February, 1992.     

On a modification of minimal iteration methods for solving systems of linear algebraic equations

Modifications of certain minimal iteration methods for solving systems of linear algebraic equations are proposed and examined. The modified methods are shown to be superior to the original versions with respect to the round-off error accumulation, which makes them applicable to solving ill-conditioned problems. Numerical results demonstrating the efficiency of the proposed modifications are given.     

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 comparison of the monomial method and the S-system method for solving systems of algebraic equations

Two numerical methods for solving systems of equations have recently been proposed: a method based on monomial approximations (the “monomial method”) and a technique based on S-system methodology (the “S-system method”). The two methods have been shown to be fundamentally identical, that is, they are both equivalent to Newton's method operating on a transformed version of the system of equations. Yet, when applied specifically to algebraic systems of equations, they have significant computational differences that may impact the relative computational efficiency of the two methods. These computational differences are described. A combinatorial strategy for locating many, and sometimes all, solutions to a system of nonlinear equations has also been suggested previously. This paper further investigates the effectiveness of this strategy when applied to either of the two methods.     

Two-step relaxation Newton algorithm for solving nonlinear algebraic equations

We introduce a new algorithm, namely two-step relaxation Newton, for solving algebraic nonlinear equations f(x)=0. This new algorithm is derived by combining two different relaxation Newton algorithms introduced by Wu et al. (Appl. Math. Comput. 201:553–560, 2008), and therefore with special choice of the so called splitting function it can be implemented simultaneously, stably with much less memory storage and CPU time compared with the Newton–Raphson method. Global convergence of this algorithm is established and numerical experiments show that this new algorithm is feasible and effective, and outperforms the original relaxation Newton algorithm and the Newton–Raphson method in the sense of iteration number and CPU time.     

An exponential matrix method for solving systems of linear differential equations

This paper presents an exponential matrix method for the solutions of systems of high‐order linear differential equations with variable coefficients. The problem is considered with the mixed conditions. On the basis of the method, the matrix forms of exponential functions and their derivatives are constructed, and then by substituting the collocation points into the matrix forms, the fundamental matrix equation is formed. This matrix equation corresponds to a system of linear algebraic equations. By solving this system, the unknown coefficients are determined and thus the approximate solutions are obtained. Also, an error estimation based on the residual functions is presented for the method. The approximate solutions are improved by using this error estimation. To demonstrate the efficiency of the method, some numerical examples are given and the comparisons are made with the results of other methods. Copyright © 2012 John Wiley & Sons, Ltd.     

On modification of certain methods of the conjugate direction type for solving systems of linear algebraic equations

A modification of certain well-known methods of the conjugate direction type is proposed and examined. The modified methods are more stable with respect to the accumulation of round-off errors. Moreover, these methods are applicable for solving ill-conditioned systems of linear algebraic equations that, in particular, arise as approximations of ill-posed problems. Numerical results illustrating the advantages of the proposed modification are presented.     

A new look at the Lanczos algorithm for solving symmetric systems of linear equations

Simple versions of the conjugate gradient algorithm and the Lanczos method are discussed, and some merits of the latter are described. A variant of Lanczos is proposed which maintains robust linear independence of the Lanczos vectors by keeping them in secondary storage and occasionally making use of them. The main applications are to problems in which (1) the cost of the matrix-vector product dominates other costs, (2) there is a sequence of right hand sides to be processed, and (3) the eigenvalue distribution of A is not too favorable.     

Perturbation of systems of linear algebraic equations

A classical perturbation result for nonsingular systems of linear algebraic equations is extended to general consistent systems under any norm. An optimal perturbation result is also obtained for general linear least squares problems under a Euclidean norm.