共查询到20条相似文献,搜索用时 15 毫秒
1.
The generalized eigenvalue problem with H a Hankel matrix and the corresponding shifted Hankel matrix occurs in number of applications such as the reconstruction of the shape of a polygon
from its moments, the determination of abscissa of quadrature formulas, of poles of Padé approximants, or of the unknown powers
of a sparse black box polynomial in computer algebra. In many of these applications, the entries of the Hankel matrix are
only known up to a certain precision. We study the sensitivity of the nonlinear application mapping the vector of Hankel entries
to its generalized eigenvalues. A basic tool in this study is a result on the condition number of Vandermonde matrices with
not necessarily real abscissas which are possibly row-scaled.
B. Beckermann was supported in part by INTAS research network NaCCA 03-51-6637.
G. H. Golub was supported in part by DOE grant DE-FC-02-01ER41177.
G. Labahn was supported in part by NSERC and MITACS Canada grants. 相似文献
2.
This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial. 相似文献
3.
Let T and be arbitrary nonnegative, irreducible, stochastic matrices corresponding to two ergodic Markov chains on n states. A function κ is called a condition number for Markov chains with respect to the (α, β)–norm pair if . Here π and are the stationary distribution vectors of the two chains, respectively. Various condition numbers, particularly with respect
to the (1, ∞) and (∞, ∞)-norm pairs have been suggested in the literature. They were ranked according to their size by Cho
and Meyer in a paper from 2001. In this paper we first of all show that what we call the generalized ergodicity coefficient
, where e is the n-vector of all 1’s and A
# is the group generalized inverse of A = I − T, is the smallest condition number of Markov chains with respect to the (p, ∞)-norm pair. We use this result to identify the smallest condition number of Markov chains among the (∞, ∞) and (1, ∞)-norm
pairs. These are, respectively, κ
3 and κ
6 in the Cho–Meyer list of 8 condition numbers. Kirkland has studied κ
3(T). He has shown that and he has characterized transition matrices for which equality holds. We prove here again that 2κ
3(T) ≤ κ(6) which appears in the Cho–Meyer paper and we characterize the transition matrices T for which . There is actually only one such matrix: T = (J
n
− I)/(n − 1), where J
n
is the n × n matrix of all 1’s.
This research was supported in part by NSERC under Grant OGP0138251 and NSA Grant No. 06G–232. 相似文献
4.
James Weldon Demmel 《Numerische Mathematik》1987,51(3):251-289
Summary The condition number of a problem measures the sensitivity of the answer to small changes in the input. We call the problem ill-posed if its condition number is infinite. It turns out that for many problems of numerical analysis, there is a simple relationship between the condition number of a problem and the shortest distance from that problem to an ill-posed one: the shortest distance is proportional to the reciprocal of the condition number (or bounded by the reciprocal of the condition number). This is true for matrix inversion, computing eigenvalues and eigenvectors, finding zeros of polynomials, and pole assignment in linear control systems. In this paper we explain this phenomenon by showing that in all these cases, the condition number satisfies one or both of the diffrential inequalitiesm·2DM·2, where D is the norm of the gradient of . The lower bound on D leads to an upper bound 1/m(x) on the distance. fromx to the nearest ill-posed problem, and the upper bound on D leads to a lower bound 1/(M(X)) on the distance. The attraction of this approach is that it uses local information (the gradient of a condition number) to answer a global question: how far away is the nearest ill-posed problem? The above differential inequalities also have a simple interpretation: they imply that computing the condition number of a problem is approximately as hard as computing the solution of the problem itself. In addition to deriving many of the best known bounds for matrix inversion, eigendecompositions and polynomial zero finding, we derive new bounds on the distance to the nearest polynomial with multiple zeros and a new perturbation result on pole assignment. 相似文献
5.
Ji-guang Sun 《Numerische Mathematik》1992,61(1):265-275
Summary This paper concerns with measures of the sensitivity of a nondefective multiple eigenvalue of a matrix. Different condition numbers are introduced starting from directional derivatives of the multiple eigenvalue. Properties of the condition numbers defined by Stewart and Zhang [4] are studied; especially, the Wilkinson's theorem on matrices with a very ill-conditioned eigenproblem is extended.This research was supported by the Institute for Advanced Computer Studies of the University of Maryland and the Swedish Natural Science Research Council 相似文献
6.
Using a set of landmarks to represent a rigid body, a rotation of the body can be determined in least-squares sense as the solution of an orthogonal Procrustes problem. We discuss some geometrical properties of the condition number for the problem of determining the orthogonal matrix representing the rotation. It is shown that the condition number critically depends on the configuration of the landmarks. The problem is also reformulated as an unconstrained nonlinear least-squares problem and the condition number is related to the geometry of such problems. In the common 3-D case, the movement can be represented by using a screw axis. Also the condition numbers for the problem of determining the screw axis representation are shown to closely depend on the configuration of the landmarks. The condition numbers are finally used to show that the used algorithms are stable. 相似文献
7.
Summary. We consider the problem of minimizing
the spectral condition number of a positive definite matrix
by completion:
\noindent where is
an Hermitian positive definite
matrix, a matrix and is
a free Hermitian matrix. We reduce
this problem to an optimization problem for a convex function
in one variable. Using the minimal solution of this problem
we characterize the complete set of matrices that give the minimum
condition number.
Received October 15, 1993 相似文献
8.
Ji-guang Sun 《Numerische Mathematik》1995,69(3):373-382
Summary.
This paper is a continuation of the author [6] in Numerische
Mathematik.
Let be a nondefective multiple eigenvalue of
multiplicity
of an complex matrix , and let
be the
secants of the canonical
angles between the left and right invariant subspaces of
corresponding to the multiple eigenvalue . The analysis
of this paper shows that the quantities
are the worst-case condition numbers of the multiple eigenvalue
.
Received September 28, 1992 / Revised version
received January 18, 1994 相似文献
9.
Ana Marco 《Linear algebra and its applications》2010,433(7):1254-1264
The problem of polynomial least squares fitting in which the usual monomial basis is replaced by the Bernstein basis is considered. The coefficient matrix of the overdetermined system to be solved in the least squares sense is then a rectangular Bernstein-Vandermonde matrix. In order to use the method based on the QR decomposition of A, the first stage consists of computing the bidiagonal decomposition of the coefficient matrix A. Starting from that bidiagonal decomposition, an algorithm for obtaining the QR decomposition of A is the applied. Finally, a triangular system is solved by using the bidiagonal decomposition of the R-factor of A. Some numerical experiments showing the behavior of this approach are included. 相似文献
10.
Structured matrices, such as Cauchy, Vandermonde, Toeplitz, Hankel, and circulant matrices, are considered in this paper. We apply a Kronecker product-based technique to deduce the structured mixed and componentwise condition numbers for the matrix inversion and for the corresponding linear systems. 相似文献
11.
Masato Kimura 《Numerische Mathematik》1996,73(2):209-233
Summary.
We apply the boundary element methods (BEM) to the interior Dirichlet problem of the
two dimensional Laplace equation, and its discretization is carried out
with the collocation method using piecewise linear elements. In this paper,
some precise asymptotic estimations for the discretization matrix
(where denotes
the division number) are investigated. We show that the maximum norm of
and the condition number of
have the forms:
and , respectively, as
, where the constants
and are explicitly given in
the proof. Although these estimates
indicate illconditionedness of this numerical computation,
the -convergence
of this scheme with maximum norm is
proved as an application of the main
results.
Received
January 25, 1993 / Revised version received March 13,
1995 相似文献
12.
Bernhard Beckermann 《Numerische Mathematik》2000,85(4):553-577
Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices,
and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or
eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the
famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our
results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation
at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative
solution of linear systems of equations.
Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000 相似文献
13.
Bibhas Adhikari 《Linear algebra and its applications》2011,434(9):1989-2017
We derive explicit computable expressions of structured backward errors of approximate eigenelements of structured matrix polynomials including symmetric, skew-symmetric, Hermitian, skew-Hermitian, even and odd polynomials. We determine minimal structured perturbations for which approximate eigenelements are exact eigenelements of the perturbed polynomials. We also analyze structured pseudospectra of a structured matrix polynomial and establish a partial equality between unstructured and structured pseudospectra. Finally, we analyze the effect of structure preserving linearizations of structured matrix polynomials on the structured backward errors of approximate eigenelements and show that structure preserving linearizations which minimize structured condition numbers of eigenvalues also minimize the structured backward errors of approximate eigenelements. 相似文献
14.
This paper gives sensitivity analyses by two approaches forL andU in the factorizationA=LU for general perturbations inA which are sufficiently small in norm. By the matrix-vector equation approach, we derive the condition numbers for theL andU factors. By the matrix equation approach we derive corresponding condition estimates. We show how partial pivoting and complete
pivoting affect the sensitivity of the LU factorization.
The material presented here is a part of the first author's PhD thesis under the supervision of the second author. This research
was supported by NSERC of Canada Grant OGP0009236. 相似文献
15.
We consider different iterative methods for computing Hermitian solutions of the coupled Riccati equations of the optimal control problem for jump linear systems. We have constructed a sequence of perturbed Lyapunov algebraic equations whose solutions define matrix sequences with special properties proved under proper initial conditions. Several numerical examples are included to illustrate the effectiveness of the considered iterations. 相似文献
16.
In this paper, we consider shifted tridiagonal matrices. We prove that the standard algorithm to compute the LU factorization
in this situation is mixed forward-backward stable and, therefore, componentwise forward stable. Moreover, we give a formula
to compute the corresponding condition number in O(n) flops.
This research has been partially supported by Dirección General de Investigación (Ministerio de Ciencia y Tecnología) of Spain
through grants BFM2003-06335-C03-02 and MTM2006-06671 as well as by the Postdoctoral Fellowship EX2004-0658 provided by Ministerio
de Educación y Ciencia of Spain. 相似文献
17.
Under the Golub-Van Loan condition for the existence and uniqueness of the scaled total least squares (STLS) solution, a first order perturbation estimate for the STLS solution and upper bounds for condition numbers of a STLS problem have been derived by Zhou et al. recently. In this paper, a different perturbation analysis approach for the STLS solution is presented. The analyticity of the solution to the perturbed STLS problem is explored and a new expression for the first order perturbation estimate is derived. Based on this perturbation estimate, for some STLS problems with linear structure we further study the structured condition numbers and derive estimates for them. Numerical experiments show that the structured condition numbers can be markedly less than their unstructured counterparts. 相似文献
18.
This paper is concerned with solving linear system (In+BL?B2B1)x=b arising from the Green’s function calculation in the quantum Monte Carlo simulation of interacting electrons. The order of the system and integer L are adjustable. Also adjustable is the conditioning of the coefficient matrix to give rise an extreme ill-conditioned system. Two numerical methods based on the QR decomposition with column pivoting and the singular value decomposition, respectively, are studied in this paper. It is proved that the computed solution by each of the methods is weakly backward stable in the sense that the computed is close to the exact solution of a nearby linear system
19.
Estimates for the condition number of a matrix are useful in many areas of scientific computing, including: recursive least squares computations, optimization, eigenanalysis, and general nonlinear problems solved by linearization techniques where matrix modification techniques are used. The purpose of this paper is to propose anadaptiveLanczosestimator scheme, which we callale, for tracking the condition number of the modified matrix over time. Applications to recursive least squares (RLS) computations using the covariance method with sliding data windows are considered.ale is fast for relatively smalln-parameter problems arising in RLS methods in control and signal processing, and is adaptive over time, i.e., estimates at timet are used to produce estimates at timet+1. Comparisons are made with other adaptive and non-adaptive condition estimators for recursive least squares problems. Numerical experiments are reported indicating thatale yields a very accurate recursive condition estimator.Research supported by the US Air Force under grant no. AFOSR-88-0285.Research supported by the US Army under grant no. DAAL03-90-G-105.Research supported by the US Air Force under grant no. AFOSR-88-0285. 相似文献
20.
Summary We derive lower bounds for the -condition number of then×n-Vandermonde matrixV
n(x) in the cases where the node vectorx
T=[x1, x2,...,xn] has positive elements or real elements located symmetrically with respect to the origin. The bounds obtained grow exponentially inn. withO(2n) andO(2n/2), respectively. We also compute the optimal spectral condition numbers ofV
n(x) for the two node configurations (including the optimal nodes) and compare them with the bounds obtained.Dedicated to the memory of James H. WilkinsonSupported, in part, by the National Science Foundation under grant CCR-8704404 相似文献