HP Labs Technical Reports

On the Existence of Cycle Times for Some Nonexpansive Maps

Gunawardena, Jeremy ; Keane, Mike

HPL-BRIMS-95-03
May, 1995

Keyword(s): cycle time, dynamical system, min-maz function, nonexpansive map, supremum norm

Abstract: We consider functions F: Rⁿ → Rⁿ which are homogenous and nonexpansive in the norm. We refer to these as topical functions. We study the existence of cycle time vector _X(F) = lim_k → ∞ F^k (x)/k, which if it exists, is independent of x ε Rⁿ. For a restricted class of topical functions, the cycle time is known to be implicated in the existence of fixed points and this provides the motivation for the present paper. We give a characterisation of topical functions which extends an earlier result of Crandall and Tartar. We show that the sequence F^k(x)/k converges weakly, in the sense that its images under the functions t(x₁, ··· , x_n) = max(x₁, ··· , x_n) and b(x₁, ··· , x_n) = min(x₁, ··· , x_n) always converge. We show that under suitable conditions, weak convergence may be realised by the convergence by components of the vector sequence F(0)/k. We show further that when n=2, _X itself exists. When n = 3, it may not, as we give a family of examples which show the extent of the departure from convergence. We discuss the problem characterising those topical functions for which _X does not exist.

Back to Index