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     

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.     

A note on operator norm inequalities

If P is a positive operator on a Hilbert space H whose range is dense, then a theorem of Foias, Ong, and Rosenthal says that: [(P)]^–1T[(P)]<-12 max {T, P^–1TP} for any bounded operator T on H, where is a continuous, concave, nonnegative, nondecreasing function on [0, P]. This inequality is extended to the class of normal operators with dense range to obtain the inequality [(N)]^–1T[(N)]<-12c² max {tT, N^–1TN} where is a complex valued function in a class of functions called vase-like, and c is a constant which is associated with by the definition of vase-like. As a corollary, it is shown that the reflexive lattice of operator ranges generated by the range NH of a normal operator N consists of the ranges of all operators of the form (N), where is vase-like. Similar results are obtained for scalar-type spectral operators on a Hilbert space.This author gratefully acknowledges the support of Central Michigan University in the form of a Research Professorship.     

Multicritical phenomena in flow of viscoelastic liquids. 2. Zaremba-Fromm-De Witt liquid model generalized to the relaxation time spectrum

The effect of the relaxation time spectrum on the critical, i.e., limiting, conditions of stable shear flow of viscoelastic liquids at small Reynolds numbers was investigated. The approach developed in [1] was generalized to the Zimm, Rouse, Spriggs, and Ferry-Landel-Williams (FLW) viscoelastic relaxation time spectra. The FLW spectrum depicts the plateau of the viscoelasticity of high-molecular-weight polymer melts. The problem of the frequency dependence of the components of the complex shear modulus at different steady-state flow rates for the case of periodic shear directed both parallel to steady-state flow and orthogonal to it was solved for all of the listed models. The results of the experiment on superposition of periodic shear on the steady-state flow of a moderately concentrated solution of polyisobutylene were compared with the results of calculating the effect of steady-state flow on the frequency viscoelastic functions for liquids whose viscoelasticity is approximated by a Spriggs relaxation time spectrum. The calculation showed that in flow of liquids approximated by Rouse, Zimm, or Spriggs spectra, only parallel and orthogonal elastic losses of stability occur and dissipative loss of stability does not. Three types of instability (two elastic — parallel and orthogonal - and one dissipative — parallel) predict the prospects for use of the FLW spectrum. For this model, like the models using the Rouse and Zimm spectra, the shear rate at which instability is generated, especially dissipative instability, is a function of the number of relaxation times considered in the calculation. It was found that the predicted generation of dissipative instability begins for shear rates qD^* greater than the critical rates of generation of elastic parallel qE^* and elastic orthogonal qE^* instabilities, in contrast to the ZFD model which predicts that qE^*<qD^*<qE^*. The critical shear rates are correlated with the appearance of supermolecular viscoelastic structures caused by shear flow, called elastic-dissipative by analogy with dissipative structures.For communication 1 see [1].Institute of Polymer Mechanics, Latvian Academy of Sciences, Riga, LV-1006, Latvia. Translated from Mekhanika Kompozitnykh Materialov, No. 1, pp. 119–135, January–February, 1997.     

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     

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     

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     

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.     

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.     

A remark on normal derivations of Hilbert-Schmidt type

LetB (H) denote the algebra of operators on the separable Hilbert spaceH. LetC ₂ denote the (Hilbert) space of Hilbert-Schmidt operators onH, with norm .₂ defined by S ₂ ² =(S,S)=tr(SS ^*). GivenA, B B (H), define the derivationC (A, B):B(H)B(H) byC(A, B)X=AX-XB. We show that C(A,B)X+S ₂ ² =C(A,B)X ₂ ² +S ₂ ² holds for allXB(H) and for everySC ₂ such thatC(A, B)S=0 if and only if reducesA, ker S reducesB, andA | S and B| ker S are unitarily equivalent normal operators. We also show that ifA, BB(H) are contractions andR(A, B)B(H)B(H) is defined byR(A, B)X=AXB-X, thenSC ₂ andR(A, B)S=0 imply R(A,B)X+S ₂ ² =R(A,B)X ₂ ² +S ₂ ² for allXB(H).     

Uniform convexity and the distribution of the norm for a Gaussian measure

Summary We show that if a Banach space E has a norm · such that the modulus of uniform convexity is bounded below by a power function, then for each Gaussian measure on E the distribition of the norm for has a bounded density with respect to Lebesgue measure. This result is optimum in the following sense:If (a _n) is an arbitrary sequence with a _n0, there exists a uniformly convex norm N(·) on the standard Hilbert space, equivalent to the usual norm such that the modulus of convexity of this norm satisfies , and a Gaussian measure on E such that the distribution of the norm for does not have a bounded density with respect to Lebesgue measure.     

On the stability of semi-implicit methods for ordinary differential equations

The aim of this paper is to analyze the stability properties of semi-implicit methods (such as Rosenbrock methods,W-methods, and semi-implicit extrapolation methods) for nonlinear stiff systems of differential equations. First it is shown that the numerical solution satisfies y ₁ (h)y ₀, if the method is applied with stepsizeh to the systemy =Ay ( denotes the logarithmic norm ofA). Properties of the function(x) are studied. Further, conditions for the parameters of a semi-implicit method are given, which imply that the method produces contractive numerical solutions over a large class of nonlinear problems for sufficiently smallh. The restriction on the stepsize, however, does not depend on the stiffness of the differential equation. Finally, the presented theory is applied to the extrapolation method based on the semi-implicit mid-point rule.     

On the norm of polynomials of two adjoint projections

Letf(X, Y) be a polynomial of two non-commuting variables and letP be an arbitrary nontrivial projection operator in Hilbert space. The class of all polynomialsf(X, Y) for which f(P, P ^*) depends only onf and P are described. In the case when such a dependence exists the explicit formula is obtained. Some applications to singular integral operators are given.     

On the Monotone Error Rule for Parameter Choice in Iterative and Continuous Regularization Methods

We consider in Hilbert spaces linear ill-posed problems Ax = y with noisy data y satisfying y –y. Regularized approximations x _r to the minimum-norm solution x of Ax = y are constructed by continuous regularization methods or by iterative methods. For the choice of the regularization parameter r (the stopping index n in iterative methods) the following monotone error rule (ME rule) is used: we choose r = r _ME (n = n _ME) as the largest r-value with the guaranteed monotonical decrease of the error x _r – x for r [0, r _ME] (x _n – x <#60; x _n–1 – x for n = 1, 2, ..., n _ME). Main attention is paid to iterative methods of gradient type and to nonstationary implicit iteration methods. As shown, the ME rule leads for many methods to order optimal error bounds. Comparisons with other rules for the choice of the stopping index are made and numerical examples are given.This revised version was published online in October 2005 with corrections to the Cover Date.     

Discretely normed Abelian groups

A discrete norm on an Abelian groupA is a non-negative function · A which satisfies the triangle inequality, is homogenous with respect to scaling ofA by and is bounded away from 0 onA/{0}.A countable Abelian group is discretely normed if and only if the group is free.     

An algorithm for best approximate solutions ofAx=b with a smooth strictly convex norm

Summary In this paper, overdetermined systems ofm linear equations inn unknowns are considered. With ^m equipped with a smooth strictly convex norm, ·, an iterative algorithm for finding the best approximate solution of the linear system which minimizes the ·-error is given. The convergence of the algorithm is established and numerical results are presented for the case when · is anl _p norm, 1<p<.Portions of this paper are taken from the author's Ph.D. thesis at Michigan State University     

On the norms of polynomials of two adjoint projections and a shift

LetP be a projection (non-selfadjoint in general), andV a selfadjoint involution acting in a Hilbert spaceH. In this paper the polynomialsF(X, Y, Z) of three non-commuting variables are described such that the norms F(P, P ^*,V) depend only on P. A method of calculation of the norms F(P, P ^*,V) for such polynomials is given. For polynomialsF(P, P ^*) this problem was investigated in [KMF], [FKM].     

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.     

Parsimonious Least Norm Approximation

A theoretically justifiable fast finite successive linear approximation algorithm is proposed for obtaining a parsimonious solutionto a corrupted linear system Ax=b+p, where the corruption p is due to noise or error in measurement. The proposedlinear-programming-based algorithm finds a solution x by parametrically minimizing the number of nonzeroelements in x and the error Ax-b-p₁.Numerical tests on a signal-processing-based exampleindicate that the proposed method is comparable to a method that parametrically minimizesthe 1-norm of the solution x and the error Ax-b-p₁, and that both methods are superior, byorders of magnitude, to solutions obtained by least squares as well by combinatorially choosing an optimal solution with a specific number of nonzero elements.     

Comparison theorems for nonlinear evolution equations and their application to the investigation of the dependence of the solutions of the equation ut=δϕ(u) ON ϕ and on the boundary conditions

One obtains estimates of the form, whereu. are generalized solutions of the equationsdu/dt=Au, du/dt=Bu whileA, B are non-linear,m-dissipative operators in a Banach space, and there exists an operatorP:D(A)D(B), such thatPw · W+BPw –Aw, uniformly on some setw. These results are applied to the investigation of the dependence of the solutions of the Cauchy, Dirichlet problems and of the problem with the boundary condition –du/dn=(u) for the equation u₁=(u) on the continuous nondecreasing functions and.Translated from Problemy Matematicheskogo Analiza, No. 9, pp. 183–198, 1984.The author is sincerely grateful to O. A. Ladyzhenskaya and N. N. Ural'tseva for their interest in this paper and for useful discussions.