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     

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.     

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.     

An extremal property of outer functions

Our main result is the following: iff (z) is in the space H², and F(z) is its outer part, then F⁽ⁿ⁾_H2F⁽ⁿ⁾_H2(n=1,2,...), the left side being finite if the right side is finite. Under certain essential restrictions, this. inequality was proved by B. I. Korenblyum and V. S. Korolevich [1].Translated from Matematicheskie Zametki, Vol. 10, No. 1, pp. 53–56, July, 1971.     

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.     

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.     

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.     

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     

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     

On the condition number of linear least squares problems in a weighted Frobenius norm

LetA be anm × n, m n full rank real matrix andb a real vector of sizem. We give in this paper an explicit formula for the condition number of the linear least squares problem (LLSP) defined by min Ax–b₂,x ⁿ . Let and be two positive real numbers, we choose the weighted Frobenius norm [A, b] _F on the data and the usual Euclidean norm on the solution. A straightforward generalization of the backward error of [9] to this norm is also provided. This allows us to carry out a first order estimate of the forward error for the LLSP with this norm. This enables us to perform a complete backward error analysis in the chosen norms.Finally, some numerical results are presented in the last section on matrices from the collection of [5]. Three algorithms have been tested: the QR factorization, the Normal Equations (NE), the Semi-Normal Equations (SNE).     

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).     

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.     

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     

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].     

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.     

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.     

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.     

Logarithms and imaginary powers of closed linear operators

The imaginary powersA ^it of a closed linear operatorA, with inverse, in a Banach spaceX are considered as aC ₀-group {exp(itlogA);t R} of bounded linear operators onX, with generatori logA. Here logA is defined as the closure of log(1+A) – log(1+A ^–1). LetA be a linearm-sectorial operator of typeS(tan ), 0(/2), in a Hilbert spaceX. That is, |Im(Au, u)| (tan )Re(Au, u) foru D(A). Then ±ilog(1+A) ism-accretive inX andilog(1+A) is the generator of aC ₀-group {(1+A) ^it ;t R} of bounded imaginary powers, satisfying the estimate (1+A) ^it exp(|t|),t R. In particular, ifA is invertible, then ±ilogA ism-accretive inX, where logA is exactly given by logA=log(1+A)–log(1+A ^–1), and {A ^it;t R} forms aC ₀-group onX, with the estimate A ^it exp(|t|),t R. This yields a slight improvement of the Heinz-Kato inequality.     

Numerical stability of descent methods for solving linear equations

Summary In this paper we perform a round-off error analysis of descent methods for solving a liner systemAx=b, whereA is supposed to be symmetric and positive definite. This leads to a general result on the attainable accuracy of the computed sequence {x _i } when the method is performed in floating point arithmetic. The general theory is applied to the Gauss-Southwell method and the gradient method. Both methods appear to be well-behaved which means that these methods compute an approximationx _i to the exact solutionA ^–1 b which is the exact solution of a slightly perturbed linear system, i.e. (A+A)x _i =b, A of order A, where is the relative machine precision and · denotes the spectral norm.     

Least squares algorithms for finding solutions of overdetermined linear equations which minimize error in an abstract norm

In this paper overdetermined linear equations inn unknowns are considered. Ifm is the number of equations, let _m be equipped with a smooth strictly convex norm, ·. Algorithms for finding best-fit solutions of the system which minimize the ·-error are given. The algorithms are iterative and in particular apply to the important case where _m is given thel ^p -norms, (1<p<). The algorithms consist of obtaining a least square solution i.e. carrying out an orthogonal projection at each stage of the iteration and solving a non-linear equation in a single real variable. The convergence of the algorithms are proved in the paper.