首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 203 毫秒
1.
Fast algorithms for enclosing minimal 2-norm solutions in underdetermined systems are proposed. For developing these algorithms, theory for computing error bounds for numerical solutions is established. Moreover techniques for accelerating the enclosure and obtaining smaller error bounds are introduced. Numerical results show the properties of the proposed algorithms.  相似文献   

2.
To obtain upper bounds on the distance of a binary linear code, many probabilistic algorithms have been proposed. The author presents a general variation to these algorithms, specific for cyclic codes, which is shown to be an improvement. As an example, the author optimizes Brouwer's algorithm to find the best upper bounds on the dual distance of BCH[255,k,d].  相似文献   

3.
Summary. In this paper, we are concerned with a matrix equation where A is an real matrix and x and b are n-vectors. Assume that an approximate solution is given together with an approximate LU decomposition. We will present fast algorithms for proving nonsingularity of A and for calculating rigorous error bounds for . The emphasis is on rigour of the bounds. The purpose of this paper is to propose different algorithms, the fastest with flops computational cost for the verification step, the same as for the LU decomposition. The presented algorithms exclusively use library routines for LU decomposition and for all other matrix and vector operations. Received June 16, 1999 / Revised version received January 25, 2001 / Published online June 20, 2001  相似文献   

4.
Theory, algorithms and LAPACK-style software for computing a pair of deflating subspaces with specified eigenvalues of a regular matrix pair (A, B) and error bounds for computed quantities (eigenvalues and eigenspaces) are presented. Thereordering of specified eigenvalues is performed with a direct orthogonal transformation method with guaranteed numerical stability. Each swap of two adjacent diagonal blocks in the real generalized Schur form, where at least one of them corresponds to a complex conjugate pair of eigenvalues, involves solving a generalized Sylvester equation and the construction of two orthogonal transformation matrices from certain eigenspaces associated with the diagonal blocks. The swapping of two 1×1 blocks is performed using orthogonal (unitary) Givens rotations. Theerror bounds are based on estimates of condition numbers for eigenvalues and eigenspaces. The software computes reciprocal values of a condition number for an individual eigenvalue (or a cluster of eigenvalues), a condition number for an eigenvector (or eigenspace), and spectral projectors onto a selected cluster. By computing reciprocal values we avoid overflow. Changes in eigenvectors and eigenspaces are measured by their change in angle. The condition numbers yield bothasymptotic andglobal error bounds. The asymptotic bounds are only accurate for small perturbations (E, F) of (A, B), while the global bounds work for all (E, F.) up to a certain bound, whose size is determined by the conditioning of the problem. It is also shown how these upper bounds can be estimated. Fortran 77software that implements our algorithms for reordering eigenvalues, computing (left and right) deflating subspaces with specified eigenvalues and condition number estimation are presented. Computational experiments that illustrate the accuracy, efficiency and reliability of our software are also described.  相似文献   

5.
In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239–298]. The upper bounds are proved by direct combinatorial means. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008  相似文献   

6.
We consider Smolyak's construction for the numerical integration over the d‐dimensional unit cube. The underlying class of integrands is a tensor product space consisting of functions that are analytic in the Cartesian product of ellipses. The Kronrod–Patterson quadrature formulae are proposed as the corresponding basic sequence and this choice is compared with Clenshaw–Curtis quadrature formulae. First, error bounds are derived for the one‐dimensional case, which lead by a recursion formula to error bounds for higher dimensional integration. The applicability of these bounds is shown by examples from frequently used test packages. Finally, numerical experiments are reported. This revised version was published online in June 2006 with corrections to the Cover Date.  相似文献   

7.
In this paper we consider computing estimates of the norm of the error in the conjugate gradient (CG) algorithm. Formulas were given in a paper by Golub and Meurant (1997). Here, we first prove that these expressions are indeed upper and lower bounds for the A-norm of the error. Moreover, starting from these formulas, we investigate the computation of the l 2-norm of the error. Finally, we define an adaptive algorithm where the approximations of the extreme eigenvalues that are needed to obtain upper bounds are computed when running CG leading to an improvement of the upper bounds for the norm of the error. Numerical experiments show the effectiveness of this algorithm. This revised version was published online in August 2006 with corrections to the Cover Date.  相似文献   

8.
We prove that the polynomials used for obtaining the best known upper bounds for some kissing numbers (the maximum number of nonoverlapping unit spheres that can touch a unit sphere in n dimensions) are best between the polynomials of the same or lower degree. We give also some extremal polynomials we have obtained using a method proposed in [4]. The upper bounds obtained in this way are slightly better than these from [1]. However the improvements are not in the integer part for dimensionsn 18.  相似文献   

9.
We analyze the stability of the Cooley-Tukey algorithm for the Fast Fourier Transform of ordern=2 k and of its inverse by using componentwise error analysis.We prove that the components of the roundoff errors are linearly related to the result in exact arithmetic. We describe the structure of the error matrix and we give optimal bounds for the total error in infinity norm and inL 2 norm.The theoretical upper bounds are based on a worst case analysis where all the rounding errors work in the same direction. We show by means of a statistical error analysis that in realistic cases the max-norm error grows asymptotically like the logarithm of the sequence length by machine precision.Finally, we use the previous results for introducing tight upper bounds on the algorithmic error for some of the classical fast Helmholtz equation solvers based on the Faster Fourier Transform and for some algorithms used in the study of turbulence.  相似文献   

10.
Summary Given a hermitian (normal) matrixA with known eigenelements, we study the behavior of these elements under a hermitian perturbationH. With a symmetric 2×2 matrix, the problem is explicit (algebraic equation of 2nd degree), and we try, in the case of ann×n hermitian matrix, to obtain upper bounds which are as close as possible of exact results forn=2. The results are collected in § I. They state in a unified manner some results of Davis [2], Gavurin [4], Golub [5], Kato-Temple [7], Ortega [3], Wilkinson [8] and others.In § II, we apply this theory to produce error bounds for eigenelements computed by theQR and Jacobi methods. The given error bounds are realistic and easy to compute during the algorithms. When the separation distance between eigenvalues ofA approaches zero, the problem of computing eigenelements ofA+H is ill-conditionned with respect to the eigenvalues, the eigenvectors being orthogonal. The precision then obtained is given.
Perturbation d'une matrice hermitienne ou normale
  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号