The Solution of Large Sparse Unsymmetric Systems of Linear Equations

We describe in moderate detail an algorithm for the solutionof a general sparse set of linear equations. It aims to maintainboth stability and sparseness, and allows further systems withthe same matrix, or another matrix having the same sparsitypattern, to be solved economically. It is compared, in testson several non-trivial problems, with two earlier algorithmsfrom which it was derived, and appears to combine the best featuresof both.     

Numerical Solution of Matrix Polynomial Equations by Newton's Method

Let P(X) = _v=1ⁿ A_vX^v with A_v, X C^m?m (v = 1, ..., n) be a matrixpolynomial. We present a Newton method to solve the equationP(X) = B, and we prove that the algorithm converges quadraticallynear simple solvents. We need the inverse of the Fr?chet-derivativeP' of P. This leads to linear equations for the correctionsH of type In the second part, we turn to the case of scalar coefficients, i.e. A_v = _vI, with_v C (v = 1, ..., n). The derivative P' and the usual algebraicderivative P' are compared and we show that the use of P' leadsto difficulties. In particular, those algorithms based on P'are not self-correcting, while our proposed method is self-correcting.Numerical examples are included. In the Appendix, an existencetheorem is proved by using a modified Newton method.     

Direct Solution of Sets of Linear Equations whose Matrix is Sparse, Symmetric and Indefinite

We consider the use of 1?1 and 2?2 pivots for direct solutionof sets of linear equations whose matrix is sparse and symmetric.Inclusion of 2?2 pivots permits a stable decomposition to beobtained in the indefinite case and we demonstrate that in practicethere is little loss of speed even in positive definite cases.A pivotal strategy suitable for the sparse case is proposedand compared experimentally with alternatives. We present ananalysis of error, explain how the stability may be monitoredcheaply, discuss automatic scaling and consider implementationdetails.     

一类特殊模糊矩阵方程的简便求解

给出了一类特殊模糊矩阵方程的简便且实用的求解方法.     

Solution of Band Matrix Equations by Projection-Recurrence

The solution space of the matrix equation Hx=u is decomposed by a projection which leads to a recurrence for H^-1. For tridiagonal H it is shown that the elements of H^-1 can always be completely factorized. An explicit expression is obtained for H^-1 when H is tridiagonal with constant interior elements and arbitrary boundary elements. This result reduces to a particularly simple form when H is Toeplitz. For general N×N tridiagonal H, the maximum number of arithmetic operations to obtain any element of H^-1 is asymptotic to 6N, and to obtain H^-1 it is N²+14N. To obtain the vector x the number of operations ranges from 8N to 11N.     

Lagrange and the Solution of Numerical Equations

In 1798 J.-L. Lagrange published an extensive book on the solution of numerical equations. Lagrange had developed four versions of a general systematic algorithm for detecting, isolating, and approximating, with arbitrary precision, all real and complex roots of a polynomial equation with real coefficients. In contrast to Newton's method, Lagrange's algorithm is guaranteed to converge. Some of his powerful ideas and techniques foreshadowed methods developed much later in geometry and abstract algebra. For instance, in order to make a more efficient algorithm for isolating roots, Lagrange essentially worked in a quotient ring of a polynomial ring. And to accelerate both the convergence and calculation of his continued fraction expansions of the roots, he employed nonsimple continued fractions and Möbius transformations. Copyright 2001 Academic Press.En 1798 J.-L. Lagrange publié un important traité sur la résolution d'équations numériques. Dans ce traité, Lagrange développe quatre versions d'un algorithme général qui systématiquement détecte, isole, et approxime, avec toute la précision voulue, toutes les racines réelles et complexes d'une équation polynomiale à coefficients réels. Contrairement à la méthode de Newton, l'algorithme de Lagrange converge toujours. Certaines de ses idées et techniques les plus brillantes ont ouvert la voie à des méthodes en géométrie et en algèbre développées beaucoup plus tard. Par exemple, pour augmenter l'efficacité de son algorithme afin d'isoler les racines, Lagrange travaille essentiellement dans un anneau quotient d'un anneau de polynômes. De plus, dans le but d'accélérer à la fois la convergence et les calculs de l'expansion des racines via des fractions continues, il emploie des fractions continues non-simples ainsi que des transformations de Möbius. Copyright 2001 Academic Press.1798 veröffentlichte J.-L. Lagrange ein ausführliches Buch über die Lösung von numerischen Gleichungen. Lagrange entwickelte vier Versionen eines allgemeinen systematischen Algorithmus für die Identifizierung, Isolation, und beliebig genaue Approximation, aller reellen und imaginären Wurzeln einer Polynomgleichung mit reellen Koeffizienten. Im Gegensatz zu Newtons Methode konvergiert Lagranges Algorithmus immer. Einige seiner machtvollen Ideen und Techniken waren Vorläufer von Methoden in der Geometrie und Algebra die erst viel später entwickelt wurden. Zum Beispiel arbeitete Lagrange im Grunde in einem Quotientenring eines Polynomringes um seinen Algorithmus für die Isolation von Wurzeln effizienter zu machen. Und um sowohl die Konvergenz wie auch die Berechnung seiner Kettenbruchexpansion der Wurzeln zu beschleunigen benützte er nichteinfache Kettenbrüche und Möbiustransformationen. Copyright 2001 Academic Press.MSC subject classifications: 01A50; 65-03; 65H05; 65B66; 00A30.     

基于样条的高阶矩阵微分方程近似解

矩阵微分方程经常出现在许多物理模型和工程技术模型中.利用矩阵样条构造形如{y（p）（x）=Ap-1（x）y（p-1）（x）＋Ap-2（x）y（p-2）（x）＋…＋A1（x）y（1）（x）＋A0（x）y（x）＋B0（x）,y（a）=ya,…,y（p-1）（a）=y（p-1）a,x∈[a,b];Ai（x）,B0（x）∈C4[a,b],0≤i≤p-烅烄烆1的高阶矩阵线性微分方程初值问题的数值解.给出实现算法和数值解的近似误差估计以及数值实例.先将高阶矩阵微分方程转化为一阶矩阵微分方程,然后利用三次矩阵样条求出一阶矩阵线性微分方程的数值解,从而解决高阶微分方程问题.     

Efficient Algorithms for Large‐Scale Quadratic Matrix Equations

Quadratic matrix equations and in particular symmetric algebraic Riccati equations play a fundamental role in systems and control theory. Classically, they are solved via methods using their connection to Hamiltonian eigenproblems. Due to the ever‐increasing complexity of the models describing the underlying control problems, new methods are needed that can be used for large‐scale problems. In particular, sparsity of the coefficient matrices, obtained, e.g., from semi‐discretizing partial differential equations to describe the physical process to be controlled, need to be addressed. We briefly review recent approaches based on Krylov subspace methods and discuss a new approach employing a sparse implementation of Newton's method for algebraic Riccati equations.     

J-中心对称矩阵方程的解及其最佳逼近

利用J-中心对称矩阵的结构和约化性质,本文研究了J-中心对称矩阵方程的通解、最小二乘解,然后考虑了方程解集合中对给定矩阵的最佳逼近问题,并给出了唯一最佳逼近解的表达式。     

Solution Bounds of the Continuous and Discrete Lyapunov Matrix Equations

A unified approach is proposed to solve the estimation problem for the solution of continuous and discrete Lyapunov equations. Upper and lower matrix bounds and corresponding eigenvalue bounds of the solution of the so-called unified algebraic Lyapunov equation are presented in this paper. From the obtained results, the bounds for the solutions of continuous and discrete Lyapunov equations can be obtained as limiting cases. It is shown that the eigenvalue bounds of the unified Lyapunov equation are tighter than some parallel results and that the lower matrix bounds of the continuous Lyapunov equation are more general than the majority of those which have appeared in the literature.     

泛函微分方程的全局稳定周期解

本文综合运用相空间理论，泛函分析方法和李雅普诺夫第二方法，研究具无限时滞的泛函微分方程周期解的存在性，唯一性和稳定性问题，得到了新的结果．     

三次矩阵方程的解的判定

给定A∈Mn(F),g(x)=x3+ax2+bx+c∈F[x],本文讨论矩阵方程g(X)=A的解的存在性问题.在Li′s研究的基础上,当f(x)=p1(x)p2(x)…ps(x)时,我们给出g(X)=A有解的充要条件为对每一个pi(x),pi(g(x))在F[x]中存在ni次因式,ni=degpi(x).     

A Non-Krylov Subspace Method for Solving Large and Sparse Linear System of Equations

Most current prevalent iterative methods can be classified into the socalled extended Krylov subspace methods, a class of iterative methods which do not fall into this category are also proposed in this paper. Comparing with traditional Krylov subspace methods which always depend on the matrix-vector multiplication with a fixed matrix, the newly introduced methods (the so-called (progressively) accumulated projection methods, or AP (PAP) for short) use a projection matrix which varies in every iteration to form a subspace from which an approximate solution is sought. More importantly, an accelerative approach (called APAP) is introduced to improve the convergence of PAP method. Numerical experiments demonstrate some surprisingly improved convergence behaviors. Comparisons between benchmark extended Krylov subspace methods (Block Jacobi and GMRES) are made and one can also see remarkable advantage of APAP in some examples. APAP is also used to solve systems with extremely ill-conditioned coefficient matrix (the Hilbert matrix) and numerical experiments shows that it can bring very satisfactory results even when the size of system is up to a few thousands.     

Hybrid Methods in the Numerical Solution of Volterra Integro-differential Equations

The theory of hybrid methods in ordinary differential equationsis extended to deal with the numerical solution of Volterraintegro-differential equations. A convergence proof is givenin which it is attempted to follow the convergence proof givenin Gragg & Stetter (1964) for the numerical solution ofy¹ = f(x, y), y(0) = y_o, as closely as possible. Several numericalexamples are included. Also the stability polynomial of a hybridmethod using two off-step points and the stability regions fortwo particular methods are given.     

Controlling the Error in the Numerical Solution of Elliptic Equations

An adaptation of Synge's hypercircle method is presented thatallows some control of the error in the approximate solutionof linear elliptic differential equations using the finite elementmethod.     

泛灰线性方程组的泛灰矩阵求解方法

在概述泛灰数的概念与泛灰行列式运算的基础上 ,介绍了泛灰线性方法程组的泛灰解法 .根据泛灰数的性质 ,定义了泛灰矩阵 ,提出了泛灰线性方程组的泛灰矩阵解法 ,并给出了算例 .