On the numerical solution of ill‐conditioned linear systems by regularization and iteration

We propose to reduce the (spectral) condition number of a given linear system by adding a suitable diagonal matrix to the system matrix, in particular by shifting its spectrum. Iterative procedures are then adopted to recover the solution of the original system. The case of real symmetric positive definite matrices is considered in particular, and several numerical examples are given. This approach has some close relations with Riley's method and with Tikhonov regularization. Moreover, we identify approximately the aforementioned procedure with a true action of preconditioning.     

On the connectedness of the solution set to linear complementarity systems

This paper establishes sufficient conditions for the connectedness of nontrivial subsets of the solution set to linear complementarity systems with special structure. Connectedness may be important to investigate stability and sensitivity questions, parametric problems, and for extending a Lemke-type method to a new class of problems. Such a property may help in analyzing the structure of the feasible region by checking the explicitly given matrices of the resulting conditions. From the point of view of geometry, the question is how to analyze the combined geometrical object consisting of a Riemannian manifold, a pointed cone, and level sets determined by linear inequalities.This paper has been mainly prepared while the author was visiting the Department of Mathematics at the University of Pisa. This research was partialy supported by the Hungarian National Research Foundation, Grant No. OTKA-2568.     

独立约束条件下线性模型的参数估计

对线性回归的未知参数估计问题,在某些种假设的条件下已有结论,对有约束条件的情况下,线性回归模型中参数估计如何,本文给出了带有独立的约束条件下线性回归模型中参数β的最小二乘估计。     

Mixed,componentwise condition numbers and small sample statistical condition estimation of Sylvester equations

We present a componentwise perturbation analysis for the continuous‐time Sylvester equations. Componentwise, mixed condition numbers and new perturbation bounds are derived for the matrix equations. The small sample statistical method can also be applied for the condition estimation. These condition numbers and perturbation bounds are tested on numerical examples and compared with the normwise condition number. The numerical examples illustrate that the mixed condition number gives sharper bounds than the normwise one. Copyright © 2011 John Wiley & Sons, Ltd.     

Optimally conditioned scaled ABS algorithms for linear systems

Using a strict bound of Spedicato to the condition number of bordered positive-definite matrices, we show that the scaling parameter in the ABS class for linear systems can always be chosen so that the bound of a certain update matrix is globally minimized. Moreover, if the scaling parameter is so chosen at every iteration, then the condition number itself is globally minimized. The resulting class of optimally conditioned algorithms contains as a special case the class of optimally stable algorithms in the sense of Broyden.This work was done in the framework of research supported by MPI, Rome, Italy, 60% Program.     

State estimation of linear dynamical systems under bounded control

The problem of estimation of all possible states that a linear system under bounded control may take (namely, the reachable or attainable set) is addressed. A number of previously developed Lyapunov techniques for estimating the reachable set of ann-dimensional linear system are extended and compared. The techniques produce over-estimates in the form ofn-dimensional ellipsoids. Illustrative examples are solved.This work was supported by the Natural Sciences and Engineering Research Council of Canada, Operating Grant Nos. A-0621 and A-4080, and by Research Personnel Support from the Dean of Science, Memorial University of Newfoundland, Canada.     

Adaptive solution of infinite linear systems by Krylov subspace methods

In this paper we consider the problem of approximating the solution of infinite linear systems, finitely expressed by a sparse coefficient matrix. We analyse an algorithm based on Krylov subspace methods embedded in an adaptive enlargement scheme. The management of the algorithm is not trivial, due to the irregular convergence behaviour frequently displayed by Krylov subspace methods for nonsymmetric systems. Numerical experiments, carried out on several test problems, indicate that the more robust methods, such as GMRES and QMR, embedded in the adaptive enlargement scheme, exhibit good performances.     

Necessary and sufficient conditions for distinguishability of linear control systems

Distinguishability plays a crucial rule in studying observability of hybrid system such as switched system. Recently, for two linear systems, Lou and Si gave a condition not only necessary but also sufficient to the distinguishability of linear systems. However, the condition is not easy enough to verify. This paper will give a new equivalent condition which is relatively easy to verify.     

Inner and outer bounds for the solution set of parametric linear systems

Consider linear systems involving affine-linear dependencies on interval parameters. Presented is a free C-XSC software implementing a generalized parametric fixed-point iteration method for verified enclosure of the parametric solution set. Some specific features of the corresponding algorithm concerning sharp enclosure of the contracting matrix and inner approximation of the solution enclosure are discussed.     

Hyperplane method for reachable state estimation for linear time-invariant systems

A numerical algorithm is presented for generating inner and outer approximations for the set of reachable states for linear time-invariant systems. The algorithm is based on analytical results characterizing the solutions to a class of optimization problems which determine supporting hyperplanes for the reachable set. Explicit bounds on the truncation error for the finite-time case yield a set of so-called -supporting hyperplanes which can be generated to approximate the infinite-time reachable set within an arbitrary degree of accuracy. At the same time, an inner approximation is generated as the convex hull of points on the boundary of the finite-time reachable set. Numerical results are presented to illustrate the hyperplane method. The concluding section discusses directions for future work and applications of the method to problems in trajectory planning in servo systems.This research was supported in part by Digital Equipment Corporation through the American Electronics Association Fellowship Loan Program and by the National Science Foundation under Grant No. ECS-84-04607.     

Locally Farkas-Minkowski linear inequality systems

This paper introduces thelocally Farkas-Minkowski (LFM) linear inequality systems in a finite dimensional Euclidean space. These systems are those ones that satisfy that any consequence of the system that is active at some solution point is also a consequence of some finite subsystem. This class includes the Farkas-Minkowski systems and verifies most of the properties that these systems possess. Moreover, it contains the locally polyhedral systems, which are the natural external representation of quasi-polyhedral sets. TheLFM systems appear to be the natural external representation of closed convex sets. A characterization based on their properties under the union of systems is provided. In linear semi-infinite programming, theLFM property is the more general constraint qualification such that the Karush-Kuhn-Tucker condition characterizes the optimal points. Furthermore, the pair of Haar dual problems has no duality gap.     

The solution of fuzzy linear systems by non-linear programming: a financial application

Fuzzy linear systems of equations play a major role in various financial applications. In this paper we analyse a particular fuzzy linear system: the derivation of the risk neutral probabilities in a fuzzy binary tree. This system has previously been investigated and different solutions to different forms of the same system have been proposed.     

On the Perron exponents of discrete linear systems

This note studies properties of Perron or lower Lyapunov exponents for discrete time varying system. It is shown that for diagonal system of order s there are at most 2^s-1 lower Lyapunov exponents. By example it is demonstrated that in non-diagonal case it is possible to have arbitrarily many different Perron exponents. Finally it is shown that the exponent is almost everywhere equal to the lower Lyapunov exponent of the matrices coefficient sequence.     

On common linear copositive Lyapunov functions for pairs of stable positive linear systems

We study the common linear copositive Lyapunov functions of positive linear systems. Firstly, we present a theorem on pairs of second order positive linear systems, and give another proof of this theorem by means of properties of geometry. Based on the process of the proof, we extended the results to a finite number of second order positive linear systems. Then we extend this result to third order systems. Finally, for higher order systems, we give some results on common linear copositive Lyapunov functions.     

Computing the conditioning of the components of a linear least‐squares solution

In this paper, we address the accuracy of the results for the overdetermined full rank linear least‐squares problem. We recall theoretical results obtained in (SIAM J. Matrix Anal. Appl. 2007; 29 (2):413–433) on conditioning of the least‐squares solution and the components of the solution when the matrix perturbations are measured in Frobenius or spectral norms. Then we define computable estimates for these condition numbers and we interpret them in terms of statistical quantities when the regression matrix and the right‐hand side are perturbed. In particular, we show that in the classical linear statistical model, the ratio of the variance of one component of the solution by the variance of the right‐hand side is exactly the condition number of this solution component when only perturbations on the right‐hand side are considered. We explain how to compute the variance–covariance matrix and the least‐squares conditioning using the libraries LAPACK (LAPACK Users' Guide (3rd edn). SIAM: Philadelphia, 1999) and ScaLAPACK (ScaLAPACK Users' Guide. SIAM: Philadelphia, 1997) and we give the corresponding computational cost. Finally we present a small historical numerical example that was used by Laplace (Théorie Analytique des Probabilités. Mme Ve Courcier, 1820; 497–530) for computing the mass of Jupiter and a physical application if the area of space geodesy. Copyright © 2008 John Wiley & Sons, Ltd.     

Numerical solution of parameter‐dependent linear systems

We are interested in the numerical solution of the complex large linear system, (σ²A+σB+C)x=f(σ), for many, possibly a few hundreds, values of the complex parameter σ in a wide range. We assume that A, B and C are large, sparse, symmetric matrices, as is the case in several application problems. In particular, we focus on the following structured right‐hand side, f(σ)=FΦ(σ), where F is a (tall) rectangular matrix whose entries are independent of σ. We propose to approximate the solution x=x(σ) by means of a projection onto a single vector subspace, and a subsequent solution of the reduced dimension problem, for all values of interest of the parameter σ. Numerical experiments report the effectiveness of our approach on real application problems. Copyright © 2005 John Wiley & Sons, Ltd.     

A characterization of constant-time linear control systems satisfying the Pontryagin maximum principle

Using the subdifferential, we extend the main characterization of Banach linear systems satisfying the Pontryagin maximum principle, given in our previous paper (Ref. 1), to the case whenF andX are locally convex spaces and the norm ofF is replaced by an arbitrary continuous convex functionalh onF.     

Positive solution for asymptotically linear elliptic systems

In this paper, we show that semilinear elliptic systems of the form (1) possess at least one positive solution pair (u, v)∈H¹(?^N)×H¹(?^N), where λ and µ are nonnegative numbers, f(x, t) and g(x, t) are continuous functions on ?^N×? and asymptotically linear as t→+∞. Copyright © 2009 John Wiley & Sons, Ltd.     

Differential equations and solution of linear systems

Many iterative processes can be interpreted as discrete dynamical systems and, in certain cases, they correspond to a time discretization of differential systems. In this paper, we propose to derive iterative schemes for solving linear systems of equations by modeling the problem to solve as a stable state of a proper differential system; the solution of the original linear problem is then computed numerically by applying a time marching scheme. We discuss some aspects of this approach, which allows to recover some known methods but also to introduce new ones. We give convergence results and numerical illustrations. AMS subject classification 65F10, 65F35, 65L05, 65L12, 65L20, 65N06     

Regular linear systems governed by systems with state, input and output delays

^** Email: hadd{at}ucam.ac.ma^*** Email: idrissi{at}ucam.ac.ma In this paper, we give a new reformulation of linear systemswith delays in input, state and output. We show that these systemscan be written as a regular linear system without delays. Thetechnique used here is essentially based on the theory recentlydeveloped by Salamon and Weiss and the shift in semigroup properties.Our framework can be applied, in particular, when the delayoperators are given by Riemann–Stieltjes integrals.