A restart algorithm for computing fixed points without an extra dimension

An algorithm to compute a fixed point of an upper semicontinuous point to set mapping using a simplicial subdivision is introduced. The new element of the algorithm is that for a given grid it does not start with a subsimplex but with one (arbitrary) point only; the algorithm will terminate always with a subsimplex. This subsimplex yields an approximation of a fixed point and provides the starting point for a finer grid. Some numerical results suggest that this algorithm converges more rapidly than the known algorithms. Moreover, it is very simple to implement the algorithm on the computer.     

An improvement of fixed point algorithms by using a good triangulation

We consider measures for triangulations ofR ⁿ. A new measure is introduced based on the ratio of the length of the sides and the content of the subsimplices of the triangulation. In a subclass of triangulations, which is appropriate for computing fixed points using simplicial subdivisions, the optimal one according to this measure is calculated and some of its properties are given. It is proved that for the average directional density this triangulation is optimal (within the subclass) asn goes to infinity. Furthermore, we compare the measures of the optimal triangulation with those of other triangulations. We also propose a new triangulation of the affine hull of the unit simplex. Finally, we report some computational experience that confirms the theoretical results.     

The octahedral algorithm,a new simplicial fixed point algorithm

A new variable dimension simplicial algorithm for the computation of solutions of systems of nonlinear equations or the computation of fixed points is presented. It uses the restrart technique of Merrill to improve the accuracy of the solution. The algorithm is shown to converge quadratically under certain conditions. The algorithm should be efficient and relatively easy to implement.Partially supported by the Western Michigan University Sabbatical and Faculty Research Funds.     

A variable dimension fixed point algorithm and the orientation of simplices

A variable dimension algorithm with integer labelling is proposed for solving systems ofn equations inn variables. The algorithm is an integer labelling version of the 2-ray algorithm proposed by the author. The orientation of lower dimensional simplices is studied and is shown to be preserved along a sequence of adjacent simplices.     

A new subdivision for computing fixed points with a homotopy algorithm

In this paper a triangulation is introduced for homotopy methods to compute fixed points on the unit simplex or inR ⁿ . This triangulation allows for factors of incrementation of more than two. The factor may be of any size and even different at each level. Also the starting point on a new level may be any gridpoint of the last found completely labelled subsimplex on the last level. So, the decision which new factor of incrementation and which starting point is used, can be made on the ground of previous approximations. Doing so, the convergence rate can be accelerated without using restart methods.     

Efficiency and implementation of simplicial zero point algorithms

In this paper we compare the efficiency of several simplicial variable dimension algorithms. To do so, we first treat the issues of degeneracy and accelerating. We present a device for solving degeneracy. Furthermore we compare several accelerating techniques. The technique of iterated quasi-Newton steps after each major cycle of the simplicial algorithm is implemented in a computer code, which is used to compare the efficiency of the (n+1)-ray, 2n-ray, 2 ⁿ -ray and (3 ⁿ −1)-ray algorithms. Except for the (n+1)-ray algorithm, the number of function evaluations does not differ very much between the various algorithms. It appeared, however, that the 2 ⁿ -algorithm needs considerably less computation time.     

A unifying model based on retraction for fixed point algorithms

We present a unifying model based on retraction for several restart fixed point algorithms. The model embraces the interpretation of the algorithms in terms of stationary point problem by van der Laan and Talman and fully explains the 2-ray method.     

Variable dimension algorithms: Basic theory,interpretations and extensions of some existing methods

In this paper we establish a basic theory for variable dimension algorithms which were originally developed for computing fixed points by Van der Laan and Talman. We introduce a new concept primal—dual pair of subdivided manifolds and by utilizing it we propose a basic model which will serve as a foundation for constructing a wide class of variable dimension algorithms. Our basic model furnishes interpretations to several existing methods: Lemke's algorithm for the linear complementarity problem, its extension to the nonlinear complementarity problem, a variable dimension algorithm on conical subdivisions and Merrill's algorithm. We shall present a method for solving systems of equations as an application of the second method and an efficient implementation of the fourth method to which our interpretation leads us. A method for constructing triangulations with an arbitrary refinement factor of mesh size is also proposed.     

A fixed point approach to the stability of isometries

In this paper, we apply a fixed point theorem to the proof of Hyers-Ulam-Rassias stability property for isometries from a normed space into a Banach space, in which the parallelogram law holds.     

A Schauder-type fixed point theorem

In this brief note we study Schauder's second fixed point theorem in the space $(\mathit{BC},6\cdot 6)$ of bounded continuous functions $\varphi :[0,\infty )\to {\Re }^n$ with a view to reducing the requirement that there is a compact map to the requirement that the map is locally equicontinuous. Several examples are given, both motivating and applying the theory.     

Roundoff error analysis of fast DCT algorithms in fixed point arithmetic

Discrete cosine transforms (DCT) are essential tools in numerical analysis and digital signal processing. Processors in digital signal processing often use fixed point arithmetic. In this paper, we consider the numerical stability of fast DCT algorithms in fixed point arithmetic. The fast DCT algorithms are based on known factorizations of the corresponding cosine matrices into products of sparse, orthogonal matrices of simple structure. These algorithms are completely recursive, are easy to implement and use only permutations, scaling, butterfly operations, and plane rotations/rotation-reflections. In comparison with other fast DCT algorithms, these algorithms have low arithmetic costs. Using von Neumann–Goldstine’s model of fixed point arithmetic, we present a detailed roundoff error analysis for fast DCT algorithms in fixed point arithmetic. Numerical tests demonstrate the performance of our results.      

An extension of Tarski's fixed point theorem and its application to isotone complementarity problems

Tarski's fixed point theorem is extended to the case of set-valued mappings, and is applied to a class of complementarity problems defined by isotone set-valued operators in a complete vector lattice.     

Renorming of and the fixed point property

For any , let P_k denote the natural projections on ℓ₁. Let |||||| be an equivalent norm of ℓ₁ that satisfies all of the following four conditions:

(1) There are α>4 and a positive (decreasing) sequence (α_n) in (0,1) such that for any normalized block basis {f_n} of (ℓ₁,||||||) and xℓ₁ with P_k−1(x)=x and |||x|||<α_k,

(2) There are two strictly decreasing sequences {β_k} and {γ_k} with

such that for any normalized block basis {f_n} of (ℓ₁,||||||) and x with (I−P_k)(x)=x,

(3) For any , I−P_k=1.

(4) The unit ball of (ℓ₁,||||||) is σ(ℓ₁,c₀)-closed.

In this article, we prove that the space (ℓ₁,||||||) has the fixed point property for the nonexpansive mapping. This improves a previous result of the author.

On a fixed point theorem of Kirk

W.A. Kirk [J. Math. Anal. Appl. 277 (2003) 645-650] first introduced the notion of asymptotic contractions and proved the fixed point theorem for this class of mappings. In this note we present a new short and simple proof of Kirk's theorem.     

A surjection theorem and a fixed point theorem for a class of positive operators

This paper is concerned with α-convex operators on ordered Banach spaces. A surjection theorem for 1-convex operators in order intervals is established by means of the properties of cone and monotone iterative technique. It is assumed that 1-convex operator A is increasing and satisfies Ay−Ax?M(y−x) for θ?x?y?v₀, where θ denotes the zero element and v₀ is a constant. Moreover, we prove a fixed point theorem for -convex operators by using fixed point theorem of cone expansion. In the end, we apply the fixed point theorem to certain integral equations.     

A note on two fixed point problems

We extend the applicability of the Exterior Ellipsoid Algorithm for approximating n-dimensional fixed points of directionally nonexpanding functions. Such functions model many practical problems that cannot be formulated in the smaller class of globally nonexpanding functions. The upper bound 2n²ln(2/) on the number of function evaluations for finding -residual approximations to the fixed points remains the same for the larger class. We also present a modified version of a hybrid bisection-secant method for efficient approximation of univariate fixed point problems in combustion chemistry.