Round-off error analysis of iterations for large linear systems

Summary We deal with the rounding error analysis of successive approximation iterations for the solution of large linear systemsA _x =b. We prove that Jacobi, Richardson, Gauss-Seidel and SOR iterations arenumerically stable wheneverA=A ^*>0 andA has PropertyA. This means that the computed resultx _k approximates the exact solution with relative error of order A·A ^–1 where is the relative computer precision. However with the exception of Gauss-Seidel iteration the residual vector Ax _k –b is of order A² A ^–1 and hence the remaining three iterations arenot well-behaved.This work was partly done during the author's visit at Carnegie-Mellon University and it was supported in part by the Office of Naval Research under Contract N00014-76-C-0370; NR 044-422 and by the National Science Foundation under Grant MCS75-222-55     

Ein Störungssatz für abgeschlossene,lineare Operatoren

Zusammenfassung In vorliegender Note wird ein Satz von Kato [7] über die Störung eines abgeschlossenen, normal auflösbaren OperatorsT mit endlichem Null-defekt (T) durch einen streng singulären Operator verallgemeinert. Zu diesem Zweck wird für jedes 0 mit Hilfe des Kuratowskischen Nichtkompaktheitsmaßes eine KlasseC von beschränkten, linearen Operatoren eingeführt, welche sowohl die streng singulären Operatoren als auch die OperatorenS mit S enthält.Das erzielte Resultat steht in engem Zusammenhang mit den Untersuchungen von Gol'denteinn, Gohberg und Markus [5] und von Gol'denteienn und Markus [6].     

Generalizations of the projection method with applications to SOR theory for hermitian positive semidefinite linear systems

Summary Ann×n complex matrixB is calledparacontracting if B₂1 and 0x[N(I-B)]Bx₂<x₂. We show that a productB=B _k B _k–1 ...B ₁ ofk paracontracting matrices is semiconvergent and give upper bounds on the subdominant eigenvalue ofB in terms of the subdominant singular values of theB _i 's and in terms of the angles between certain subspaces. Our results here extend earlier results due to Halperin and due to Smith, Solomon and Wagner. We also determine necessary and sufficient conditions forn numbers in the interval [0, 1] to form the spectrum of a product of two orthogonal projections and hence characterize the subdominant eigenvalue of such a product. In the final part of the paper we apply the upper bounds mentioned earlier to provide an estimate on the subdominant eigenvalue of the SOR iteration matrix associated with ann×n hermitian positive semidefinite matrixA none of whose diagonal entries vanish.The work of this author was supported in part by NSF Research Grant No. MCS-8400879     

The measure of a translated ball in uniformly convex spaces

Let (E, ¦·¦) be a uniformly convex Banach space with the modulus of uniform convexity of power type. Let be the convolution of the distribution of a random series inE with independent one-dimensional components and an arbitrary probability measure onE. Under some assumptions about the components and the smoothness of the norm we show that there exists a constant such that |{·<t}–{·+r<t}|r ^q , whereq depends on the properties of the norm. We specify it in the case ofL spaces, >1.     

Upper bounds for theL p -norms of martingales

Summary Let (f _n ) be a martingale. We establish a relationship between exponential bounds for the probabilities of the typeP(|f _n |>·T(f _n )) and the size of the constantC _p appearing in the inequality f ^* _p C _p T ^*(f) _p , for some quasi-linear operators acting on martingales.This research was supported in part by NSF Grant, no. DMS-8902418On leave from Academy of Physical Education, Warsaw, Poland     

Numerical stability of the Chebyshev method for the solution of large linear systems

Summary This paper contains the rounding error analysis for the Chebyshev method for the solution of large linear systemsAx+g=0 whereA=A ^* is positive definite. We prove that the Chebyshev method in floating point arithmetic is numerically stable, which means that the computed sequence {x _k} approximates the solution such that x _k – is of order AA ^–1 where is the relative computer precision.We also point out that in general the Chebyshev method is not well-behaved, which means that the computed residualsr _k=Ax _k+g are of order A²A ^–1.This work was supported in part by the Office of Naval Research under Contract N0014-67-0314-0010, NR 044-422 and by the National Science Foundation under Grant GJ32111     

Characterizations of logA≥logB and normaloid operators via Heinz inequality

In 1951, Heinz showed the following useful norm inequality:If A, B0and XB(H), then AXB ^r X^1–r A ^r XB ^r holds for r [0, 1]. In this paper, we shall show the following two applications of this inequality:Firstly, by using Furuta inequality, we shall show an extension of Cordes inequality. And we shall show a characterization of chaotic order (i.e., logAlogB) by a norm inequality.Secondly, we shall study the condition under which , where is Aluthge transformation ofT. Moreover we shall show a characterization of normaloid operators (i.e.,r(T)=T) via Aluthge transformation.     

Attracting properties for one dimensional flows of a general barotropic viscous fluid. Periodic flows

Summary We consider the motion of a barotropic compressible fluid in a one dimensional bounded region with impermeable boundary, see equation (1.1). Here, u(t, q) denotes the velocity and v(t, q) the specific volume. The quantity log v(t, q) measures the displacement of v(t, q) with respect to the equilibrium v 1. For the sake of brevity we denote here different norms by the simbol . We show that there is a positive constant r₀=r₀(), a small ball B₁ (r) (with radius R₁ (r), ), and a large ball B(r) (with radius R(r), ) such that the following holds, for each r [0, r₀ [(i) If f(t) < r for all t 0, and if (u(0), log v(0))R(r) (i.e. (u(0), log v(0)) B(r)) then, for sufficiently large values of t, (u(t), log v(t))R₁ (r); (ii) The solutions starting at time t=0 from the large ball B(r) have all the same asymptotic behaviour (see (1.11)); (iii) If f is T-periodic then there is a (unique) T-periodic solution (u(t), log v(t)) inside the small ball B₁ (r). This periodic solution atracts all solutions which intersect the large ball B(r). Periodic solutions had been previously studied only for very specific pressure laws, namely p(v)-log v and p(v)-v^–1.     

A superfast algorithm for multi-dimensional Padé systems

For a vector ofk+1 matrix power series, a superfast algorithm is given for the computation of multi-dimensional Padé systems. The algorithm provides a method for obtaining matrix Padé, matrix Hermite Padé and matrix simultaneous Padé approximants. When the matrix power series is normal or perfect, the algorithm is shown to calculate multi-dimensional matrix Padé systems of type (n ₀,...,n _k ) inO(n · log²n) block-matrix operations, where n=n ₀+...+n _k . Whenk=1 and the power series is scalar, this is the same complexity as that of other superfast algorithms for computing Padé systems. Whenk>1, the fastest methods presently compute these matrix Padé approximants with a complexity ofO(n²). The algorithm succeeds also in the non-normal and non-perfect case, but with a possibility of an increase in the cost complexity.Supported in part by NSERC grant No. A8035.Partially supported by NSERC operating grant No. 6194.     

Small into isomorphisms onL ∞ spaces

IfT is an isomorphism ofL (A, ) intoL (B, ) which satisfies the condition T T ^–11+, where (A, ) is a -finite measure space, thenT/T is close to an isometry with an error less than 4.     

Convergence of random products of compact contractions in Hilbert space

Let {T₁, ..., T_N} be a finite set of linear contraction mappings of a Hilbert space H into itself, and let r be a mapping from the natural numbers N to {1, ..., N}. One can form S_n=T_r(n)...T_r(1) which could be described as a random product of the T_i's. Roughly, the S_n converge strongly in the mean, but additional side conditions are necessary to ensure uniform, strong or weak convergence. We examine contractions with three such conditions. (W): x_n1, Tx_n1 implies (I-T)x_n0 weakly, (S): x_n1, Tx_n1 implies (I-T)x_n0 strongly, and (K): there exists a constant K>0 such that for all x, (I-T)x²K(x²–Tx²).We have three main results in the event that the T_i's are compact contractions. First, if r assumes each value infinitely often, then S_n converges uniformly to the projection Q on the subspace _i= ₁ ^N [x|T_ix=x]. Secondly we prove that for such compact contractions, the three conditions (W), (S), and (K) are equivalent. Finally if S=S(T₁, ..., T_N) denotes the algebraic semigroup generated by the T_i's, then there exists a fixed positive constant K such that each element in S satisfies (K) with that K.     

The possibility of integral formulas in R n

We consider the integral We solve the problem of determination of necessary and sufficient conditions in order that (u) be independent of the values of u(x) inside a bounded domain . These conditions are written in the form of a set of differential equations for the functions f(x,u,¯p,T^ij) on the set m{x; u+¯p+ T^ij<}. For such functions (u) is represented in the form of a boundary integral.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 52, pp. 35–51, 1975.     

A note on sub-multiplicative norms

Summary IfX is a finite-dimensional linear space andL(X) the linear space of linear operators onX thenL(X) may be represented asXX ^*. IfE={e ₁, ...,e _n } is a basis forX and e _j y _j ^* is a typical element ofXX ^*, then norms can be introduced onL(X) in the form y _j ^* e _j . Given that the norm onX isE-absolute we derive a necessary and sufficient condition for the norm onL(X) to be submultiplicative.     

On discrete and continuous norms in Paley-Wiener spaces and consequences for exponential frames

It is well known that for certain sequences {t_n}_n the usual L^p norm ·_p in the Paley-Wiener space PW ^p is equivalent to the discrete norm f_p,{tn}:=( _n=– |f(t_n)|^p)^1/p for 1 p = < and f_,{tn}:=sup _n|f(t_n| for p=). We estimate f_p from above by Cf_p, _n and give an explicit value for C depending only on p, , and characteristic parameters of the sequence {t_n}_n. This includes an explicit lower frame bound in a famous theorem of Duffin and Schaeffer.     

Limits of canonicalU-processes andB-valuedU-statistics

It is shown that the limite law of canonicalU-process is the law of a chaos process which has a versio with bounded and ·₂ continuous paths. This is also true forB-valued canonicalU-statistics with values in a separable Banach space. Some properties of Banach spaces of type 2 related withU-statistics are presented.Research partially supported by NSF Grants No. DMS-9000132 and No. DMS-8505550 and carried out in the University of Connecticut and the MSRI.     

Extreme values and the law of the iterated logarithm

Summary IfX takes values in a Banach spaceB and is in the domain of attraction of a Gaussian law onB, thenX satisfies the compact law of the iterated logarithm (LIL) with respect to a regular normalizing sequence { _n } iffX satisfies a certain integrability condition. The integrability condition is equivalent to the fact that the maximal term of the sample {X ₁, X ₂,..., X _n} does not dominate the partial sums {S _n}, and here we examine the precise influence of these maximal terms and its relation to the compactLIL. In particular, it is shown that if one deletes enough of the maximal terms there is always a compactLIL with non-trivial limit set.Supported in part by NSF Grant MCS-8219742Work done while visiting the University of Wisconsin, Madison, with partial support by NSF Grant MCS-8219742     

Continuity of Approximation by Neural Networks in Lp Spaces

Devices such as neural networks typically approximate the elements of some function space X by elements of a nontrivial finite union M of finite-dimensional spaces. It is shown that if X=L ^p () (1<p< and R ^d ), then for any positive constant and any continuous function from X to M, f–(f)>f–M+ for some f in X. Thus, no continuous finite neural network approximation can be within any positive constant of a best approximation in the L ^p -norm.     

Stability inL 1 of some integral operators

A class of Markov operators appearing in biomathematics is investigated. It is proved that these operators are asymptotic stable inL ¹, i.e. lim _n P ⁿ f=0 forfL ¹ and f(x) dx=0.     

A Note on the Optimal L 2-Estimate of the Finite Volume Element Method

In this note, the optimal L ²-error estimate of the finite volume element method (FVE) for elliptic boundary value problem is discussed. It is shown that u–u _{h 0}Ch ²|ln h|^1/2f_1,1 and u–u _{h 0}Ch ²f_1,p , p>1, where u is the solution of the variational problem of the second order elliptic partial differential equation, u _h is the solution of the FVE scheme for solving the problem, and f is the given function in the right-hand side of the equation.     

The fractional parts of a sum of polynomials

LetX=(x ₁,...,x _s ) be a vector ofs real components and , whereP _j (x _j ) are polynomials of exact degree k with real coefficients and without constant terms. The authors extend a result of Davenport and obtain an approximation on f(X) where t means the distance fromt to the nearest integer.