Black holes on the plane drawn by a Wiener process

Summary We say that the discD()R ², of radius , located around the origin isp-covered in timeT by a Wiener processW(·) if for anyzD() there exists a 0tT such thatW(t) is a point of the disc of radiusp, located aroundz. The supremum of those 's (0) is studied for which,D() isp-covered inT.     

Monotonically convergent iterative methods for nonlinear systems of equations

Summary This paper deals with discrete analogues of nonlinear elliptic boundary value problems and with monotonically convergent iterative methods for their numerical solution. The discrete analogues can be written asM(u)u+H(u)=0, whereM(u) is ann%n M-matrix for eachu ⁿ andH: ^{n n} . The numerical methods considered are the natural undeerrelaxation method, the successive underrelaxation method, and the Jacobi underrelaxation method. In the linear case and without underrelaxation these methods correspond to the direct, the Gauss-Seidel, and the Jacobi method for solving the underlying system of equations, resp. For suitable starting vectors and sufficiently strong underrelaxation, the sequence of iterates generated by any of these methods is shown to converge monotonically to a solution of the underlying system.     

Stability radius of polynomials occurring in the numerical solution of initial value problems

This paper deals with polynomial approximations(x) to the exponential function exp(x) related to numerical procedures for solving initial value problems. Motivated by stability requirements, we present a numerical study of the largest diskD()={z C: |z+|} that is contained in the stability regionS()={z C: |(z)|1}. The radius of this largest disk is denoted byr(), the stability radius. On the basis of our numerical study, several conjectures are made concerningr _m,p=sup {r(): _m,p}. Here _{m, p} (1pm; p, m integers) is the class of all polynomials(x) with real coefficients and degree m for which(x)=exp(x)+O(x ^p+1) (forx 0).     

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.     

Quadratically constrained least squares and quadratic problems

Summary We consider the following problem: Compute a vectorx such that Ax–b₂=min, subject to the constraint x₂=. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse.It is also possible to extend this technique to a constrained quadratic form: For a symmetric matrixA we consider the minimization ofx ^T A x–2b ^T x subject to the constraint x₂=.Some numerical examples are given.This work was in part supported by the National Science Foundation under Grant DCR-8412314 and by the National Institute of Standards and Technology under Grant 60NANB9D0908.     

A remark on fixed points of functors in topological categories

For a topological category over Set we prove that if a functor T: has a fixed cardinal (i.e. for each object K with card (UK)= we have card (UTK)), then T has a least fixed point, and if T has a successive pair of fixed cardinals and ⁺, then T has a greatest fixed point. This extends results of Adámek and Koubek.Partial financial support of the Grant Agency of the Czech Republic under Grant No. 201/93/0950 is gratefully acknowledged.     

Some remarks on the approximation in the strong sense

. , , , , . , . , , .

---

---

On the 70th birthday of Professor S. M. Nikol'skii     

Mouvement moyen et système dynamique gaussien

Summary In the situation of the classical mean motion, we haven planets moving in the plane, planetk+1 being a satellite of planetk. A classcal result then states that planetn has a mean motion,i.e. its mean angular speed between time 0 and timet has a limit whent. We show in this article that any real gaussian dynamical system can be interpreted as the limit of this situation, whenn. From a given nonatomic probability measure on [0,], we construct a transformationT of the complex brownian path (B _u)_0u1 which preserves Wiener measure.T is defined as the limit of a sequenceT _n, whereT _n acts as the motion of 2ⁿ planets. In this way we get a real gaussian dynamical system, whose spectral measure is the symetric probability on [-,] obtained from . The transformationT can be inserted in a flow (T ^t) _t, and the orbitstZ _t=B ₁T ^t still have almost surely a mean motion, which is the mean of .     

Nonlinear eigenvalue approximation

Summary For each in some domainD in the complex plane, letF() be a linear, compact operator on a Banach spaceX and letF be holomorphic in . Assuming that there is a so thatI–F() is not one-to-one, we examine two local methods for approximating the nonlinear eigenvalue . In the Newton method the smallest eigenvalue of the operator pencil [I–F(),F()] is used as increment. We show that under suitable hypotheses the sequence of Newton iterates is locally, quadratically convergent. Second, suppose 0 is an eigenvalue of the operator pencil [I–F(),I] with algebraic multiplicitym. For fixed leth() denote the arithmetic mean of them eigenvalues of the pencil [I–F(),I] which are closest to 0. Thenh is holomorphic in a neighborhood of andh()=0. Under suitable hypotheses the classical Muller's method applied toh converges locally with order approximately 1.84.     

Complete problems withL-samplable distributions

The average case complexity classes P, L-samplable and NL, L-samplable are defined. We show that Deterministic Bounded Halting is complete for P, L-samplable and that Graph Reachability is complete for NL-samplable, both problems with a universal logspace samplable distribution.     

On condition numbers and the distance to the nearest ill-posed problem

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·²DM·², 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.     

Total flux estimates for a finite element approximation of the Dirichlet problem using the boundary penalty method

Summary This paper considers a fully practical piecewise linear finite element approximation of the Dirichlet problem for a second order self-adjoint elliptic equation,Au=f, in a smooth region< ⁿ (n=2 or 3) by the boundary penalty method. Using an unfitted mesh; that is ^h , an approximation of with dist (, ^h )Ch ² is not in general a union of elements; and assuminguH ⁴ () we show that one can recover the total flux across a segment of the boundary of with an error ofO(h ²⁾. We use these results to study a fully practical piecewise linear finite element approximation of an elliptic equation by the boundary penalty method when the prescribed data on part of the boundary is the total flux.Supported by a SERC research studentship     

Über Mosers regularisiertes Variationsproblem für minimale Blätterungen desn-dimensionalen Torus

We consider regular and Cantor-like minimal foliations of the (n+1)-dimensional TorusT ⁿ⁺¹ whose leaves minimize a given variational integral. Each leaf of such a generalized foliation lies in the universal coveringR ⁿ⁺¹ within a finite distance to the affine leaves (z, x+) of fixed R ⁿ . We show that the conjugation-functionU (x,), mapping the affine leaves (x, x+) into the leaves(x,U (x,x+)) of the generalized foliation, is itself a minimal solution of an extended degenerate variational problem onT ⁿ +1. If R ⁿ /Q ⁿ the functionU is characterized in a unique way as (discontinuous) limit of the minimal solutions of the corresponding regularized problem.     

Harmonic analysis on tori

We consider measurable subsets {ofR}ⁿ with 0<m()<, and we assume that has a spectral set . (In the special case when is also assumed open, may be obtained as the joint spectrum of a family of commuting self-adjoint operators {H _k: 1kn} in L ² () such that each H _k is an extension of i(/x _k) on C _c (), k=1, ..., n.)It is known that is a fundamental domain for a lattice if is itself a lattice. In this paper, we consider a class of examples where is not assumed to be a lattice. Instead is assumed to have a certain inhomogeneous form, and we prove a necessary and sufficient condition for to be a fundamental domain for some lattice in {ofR}ⁿ. We are thus able to decide the question, fundamental domain or not, by considering only properties of the spectrum . Our criterion is obtained as a corollary to a theorem concerning partitions of sets which have a spectrum of inhomogeneous form.Work supported in part by the NSF.Work supported in part by the NSRC, Denmark.     

A study of semiiterative methods for nonsymmetric systems of linear equations

Summary Given a nonsingular linear systemA x=b, a splittingA=M–N leads to the one-step iteration (1)x _m =T X _m–1 +c withT:=M ^–1N andc:=M ^–1 b. We investigate semiiterative methods (SIM's) with respect to (1), under the assumption that the eigenvalues ofT are contained in some compact set of , with 1. There exist SIM's which are optimal with respect to , but, except for some special sets , such optimal methods are not explicitly known in general. Using results about maximal convergence of polynomials and uniformly distributed nodes from approximation and function theory, we describe here SIM's which are asymptotically optimal with respect to . It is shown that Euler methods, extensively studied by Niethammer-Varga [NV], are special SIM's. Various algorithms for SIM's are also derived here. A 1-1 correspondence between Euler methods and SIM's, generated by generalized Faber polynomials, is further established here. This correspondence gives that asymptotically optimal Euler methods are quite near the optimal SIM's.Dedicated to Professor Karl Zeller (Universität Tübingen) on the occasion of his sixtieth birthday (December 28, 1984)     

Sur les bornes d'erreur a posteriori pour les éléments propres d'opérateurs linéaires

Summary The theoretical framework of this study is presented in Sect. 1, with a review of practical numerical methods. The linear operatorT and its approximationT _n are defined in the same Banach space, which is a very common situation. The notion of strong stability forT _n is essential and cannot be weakened without introducing a numerical instability [2]. IfT (or its inverse) is compact, most numerical methods are strongly stable. Without compactness forT(T ^–1) they may not be strongly stable [20].In Sect. 2 we establish error bounds valid in the general setting of a strongly stable approximation of a closedT. This is a generalization of Vainikko [24, 25] (compact approximation). Osborn [19] (uniform and collectivity compact approximation) and Chatelin and Lemordant [6] (strong approximation), based on the equivalence between the eigenvalues convergence with preservation of multiplicities and the collectively compact convergence of spectral projections. It can be summarized in the following way: , eigenvalue ofT of multiplicitym is approximated bym numbers, _n is their arithmetic mean.- _n and the gap between invariant subspaces are of order _n =(T-T _n)P. IfT _n ^* converges toT ^*, pointwise inX ^*, the principal term in the error on - _n is . And for projection methods, withT _n= _n T, we get the bound . It applies to the finite element method for a differential operator with a noncompact resolvent. Aposteriori error bounds are given, and thegeneralized Rayleigh quotient TP _n appears to be an approximation of of the second order, as in the selfadjoint case [12].In Sect. 3, these results are applied to the Galerkin method and its Sloan variant [22], and to approximate quadrature methods. The error bounds and the generalized Rayleigh quotient are numerically tested in Sect. 4.

---

Sur les bornes d'erreur a posteriori pour les éléments propres d'opérateurs linéaires

     

Varieties of modular ortholattices

The bottom of the lattice of varieties of modular ortholattices is described. The theorem that is proved is;THEOREM. Every variety of modular ortholattices which is different from all the MOn, 0n, contains MO.The theorem is proved by translating the problem, at least partially, into the language of regular rings.Communicated by R. Wille     

A relation between Chung's and Strassen's laws of the iterated logarithm

Summary Let W(t) be a standard Wiener process and let f(x) be a function from the compact class in Strassen's law of the iterated logarithm. We investigate the lim inf behavior of the variable sup ¦W(xT)(2T loglog T)^–1/2–f(x)¦, 0x1 suitably normalized as T.This extends Chung's result valid for f(x)0, stating that lim inf.[ sup ¦(2T loglogT)^–1/2 W(xT)¦(loglog T)^–1]=/4 a.s. T 0x1     

Decompositions of factor maps involving bi-closing maps

We describe all possible decompositions of a finite-to-one factor map : _A S, from an irreducible shift of finite type onto a sofic shift, into two maps =, such that the range of is a shift of finite type, and is bi-closing. We also give necessary and sufficient conditions for to be almost topologically conjugate overS to a bi-closing map.     

∑II∑ threshold formulas

A II formula has the form, where eachL is either a variable or a negated variable. In this paper we study the computation of threshold functions by II formulas. By combining the proof of the Fredman-Komlós bound [5, 10] and a counting argument, we show that fork andn large andkn/2, every II formula computing the threshold functionT _k ⁿ has size at least exp . Fork andn large andkn ^2/3, we show that there exist II formulas for computingT _k ⁿ with size at most exp .