Recent results on iteration theory: iteration groups and semigroups in the real case

In this survey paper we present some recent results in the iteration theory. Mainly, we focus on the problems concerning real iteration groups (flows) and semigroups (semiflows) such as existence, regularity and embeddability. We also discuss some issues associated to the problem of embedddability, i.e. iterative roots and approximate iterability. The topics of this paper are: (1) measurable iteration semigroups; (2) embedding of diffeomorphisms in regular iteration semigroups in \({{\mathbb{R}}^n}\) space; (3) iteration groups of fixed point free homeomorphisms on the plane; (4) embedding of interval homeomorphisms with two fixed points in a regular iteration group; (5) commuting functions and embeddability; (6) iterative roots; (7) the structure of iteration groups on an interval; (8) iteration groups of homeomorphisms of the circle; (9) approximately iterable functions; (10) set-valued iteration semigroups; (11) iterations of mean-type mappings; (12) Hayers–Ulam stability of the translation equation. Most of the results presented here was obtained by the means of functional equations. We indicate the relations between the iteration theory and functional equations.     

Foundations for an iteration theory of entire quasiregular maps

The Fatou-Julia iteration theory of rational functions has been extended to uniformly quasiregular mappings in higher dimension by various authors, and recently some results of Fatou-Julia type have also been obtained for non-uniformly quasiregular maps. The purpose of this paper is to extend the iteration theory of transcendental entire functions to the quasiregular setting. As no examples of uniformly quasiregular maps of transcendental type are known, we work without the assumption of uniform quasiregularity. Here the Julia set is defined as the set of all points such that the complement of the forward orbit of any neighbourhood has capacity zero. It is shown that for maps which are not of polynomial type, the Julia set is non-empty and has many properties of the classical Julia set of transcendental entire functions.     

On inexact Newton methods based on doubling iteration scheme for non‐symmetric algebraic Riccati equations

Newton iteration method can be used to find the minimal non‐negative solution of a certain class of non‐symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non‐symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd.     

Nevanlinna theory and iteration of rational maps

In 1993, J. Silverman [7] studied finiteness questions for integer points in the orbits of rational functions on the projective line. This paper proves the complex hyperbolicity analogs of Silvermans results.The first author is supported in part by NSA under grant number MSPF-02G-175. The United State Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.Acknowledgments. The authors wish to thank the referee for many helpful comments and suggestions.     

A sequential implicit function theorem for the chords iteration

In this paper we study the local convergence of the method $$0 \in f\left( {p,x_k } \right) + A\left( {x_{k + 1} - x_k } \right) + F\left( {x_{k + 1} } \right),$$ in order to find the solution of the generalized equation $$find x \in X such that 0 \in f\left( {p,x} \right) + F\left( x \right).$$ We first show that under the strong metric regularity of the linearization of the associated mapping and some additional assumptions regarding dependence on the parameter and the relation between the operator A and the Jacobian $\nabla _x f\left( {\bar p,\bar x} \right)$ , we prove linear convergence of the method which is uniform in the parameter p. Then we go a step further and obtain a sequential implicit function theorem describing the dependence of the set of sequences of iterates of the parameter.     

A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases

In order to compute the smallest eigenvalue together with an eigenfunction of a self-adjoint elliptic partial differential operator one can use the preconditioned inverse iteration scheme, also called the preconditioned gradient iteration. For this iterative eigensolver estimates on the poorest convergence have been published by several authors. In this paper estimates on the fastest possible convergence are derived. To this end the convergence problem is reformulated as a two-level constrained optimization problem for the Rayleigh quotient. The new convergence estimates reveal a wide range between the fastest possible and the slowest convergence.     

A geometric theory for preconditioned inverse iteration I: Extrema of the Rayleigh quotient

The discretization of eigenvalue problems for partial differential operators is a major source of matrix eigenvalue problems having very large dimensions, but only some of the smallest eigenvalues together with the eigenvectors are to be determined. Preconditioned inverse iteration (a “matrix-free” method) derives from the well-known inverse iteration procedure in such a way that the associated system of linear equations is solved approximately by using a (multigrid) preconditioner. A new convergence analysis for preconditioned inverse iteration is presented. The preconditioner is assumed to satisfy some bound for the spectral radius of the error propagation matrix resulting in a simple geometric setup. In this first part the case of poorest convergence depending on the choice of the preconditioner is analyzed. In the second part the dependence on all initial vectors having a fixed Rayleigh quotient is considered. The given theory provides sharp convergence estimates for the eigenvalue approximations showing that multigrid eigenvalue/vector computations can be done with comparable efficiency as known from multigrid methods for boundary value problems.     

Metric Boolean algebras and constructive measure theory

 This work concerns constructive aspects of measure theory. By considering metric completions of Boolean algebras – an approach first suggested by Kolmogorov – one can give a very simple construction of e.g. the Lebesgue measure on the unit interval. The integration spaces of Bishop and Cheng turn out to give examples of such Boolean algebras. We analyse next the notion of Borel subsets. We show that the algebra of such subsets can be characterised in a pointfree and constructive way by an initiality condition. We then use our work to define in a purely inductive way the measure of Borel subsets. Received: 9 November 2000 / Revised version: 23 March 2001 / Published online: 12 July 2002     

A geometric theory for preconditioned inverse iteration applied to a subspace

The aim of this paper is to provide a convergence analysis for a preconditioned subspace iteration, which is designated to determine a modest number of the smallest eigenvalues and its corresponding invariant subspace of eigenvectors of a large, symmetric positive definite matrix. The algorithm is built upon a subspace implementation of preconditioned inverse iteration, i.e., the well-known inverse iteration procedure, where the associated system of linear equations is solved approximately by using a preconditioner. This step is followed by a Rayleigh-Ritz projection so that preconditioned inverse iteration is always applied to the Ritz vectors of the actual subspace of approximate eigenvectors. The given theory provides sharp convergence estimates for the Ritz values and is mainly built on arguments exploiting the geometry underlying preconditioned inverse iteration.     

Index iteration theory for symplectic paths and multiple periodic solution orbits

In this paper, a survey on the index iteration theory for symplectic paths is given. Three applications of this theory are presented including closed characteristics on convex hypersurfaces and brake orbits on bounded domains.     

Metric critical point theory: Potential Well Theorem and its applications

Recent results show evidence of the fact that the notion of critical point has a purely metric nature. In this paper, after giving the fundamental definitions of critical and regular points for continuous functions, we survey some applications of the nonsmooth critical point theory. Our basic tool is a Potential Well Theorem. Conferenza tenuta da A. Ioffe il 9 ottobre 1995     

Inexact primal-dual interior point iteration for linear programs in function spaces

Motivated by a simple optimal control problem with state constraints, we consider an inexact implementation of the primal-dual interior point algorithm of Zhang, Tapia, and Dennis. We show how the control problem can be formulated as a linear program in an infinite dimensional space in two different ways and prove convergence results.The research of this author was supported by an Overseas Research Scholarship of the Ministry of Education, Science and Culture of Japan.The research of this author was supported by National Science Foundation grants #DMS-9024622 and #DMS-9321938, North Atlantic Treaty Organization grant #CRG 920067, and an allocation of computing resources from the North Carolina Supercomputing Program.The research of this author was supported by North Atlantic Treaty Organization grant #CRG 920067.     

基于梯型密度函数的连续分布随机数近似生成方法

讨论了产生连续分布随机数的近似方法,给出了基于梯型密度函数表示的连续分布随机数近似算法,应用近似算法给出了几种常见类型随机数的实验结果．