Approximating fixed points of weakly contracting mappings
The authors continue their previous works [cf. for example \textit{K. Sikorski, C. W. Tsay} and \textit{H. Wozniakowski}, J. Complexity 9, No. 1, 181-200 (1993; Zbl 0772.41033)] on the problem of approximating fixed points of contractive functions with contractive factor \(q\) close to 1. They present an inscribed ellipsoid (IE) algorithm that enjoys an \(O(n(\ln 1/\varepsilon)+ \ln (1/(1-q)))\) bound on the number of function evaluations to compute \(\varepsilon\)-approximations. Their analysis implies that (1) the dimensional deflation procedure in the circumscribed (CE) algorithm is not necessary and that the resulting ``plain CE algorithm enjoys an \(O(n^{2} \ln (1/\varepsilon)+ \ln (1/(1-q)))\) upper bound on the number of function evaluations; (2) the IE algorithm solves the problem in the residual sense, i.e. computes \(x\) such that \(\|f(x)-x\|\leq\delta,\) with \(O(n\ln(1/\delta))\) function evaluations for every \(q\leq 1\).
- An ellipsoid algorithm for the computation of fixed points
- Complexity of fixed points. I
- scientific article; zbMATH DE number 4205881 (Why is no real title available?)
- scientific article; zbMATH DE number 47206 (Why is no real title available?)
- scientific article; zbMATH DE number 4123531 (Why is no real title available?)
- scientific article; zbMATH DE number 480243 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 3327467 (Why is no real title available?)
- Linear Matrix Inequalities in System and Control Theory
- On optimality of Krylov's information when solving linear operator equations
- On the complexity of approximating the maximal inscribed ellipsoid for a polytope
- Optimal solution of nonlinear equations
- Random walks and anO*(n5) volume algorithm for convex bodies
- The Approximation of Fixed Points of a Continuous Mapping
- A recursive algorithm for the infinity-norm fixed point problem
- On modeling and complete solutions to general fixpoint problems in multi-scale systems with applications
- Unique end of potential line
- A note on two fixed point problems
- A modified Seidel method for calculating the fixed points of contractive mappings
- Application of Canonical Duality Theory to Fixed Point Problem
- Circumscribed ellipsoid algorithm for fixed-point problems
- scientific article; zbMATH DE number 5509929 (Why is no real title available?)
- Spherical algorithms and evaluation of the fixed point set
- Iterative Methods for Fixed Points of Asymptotically Weakly Contractive Maps
- scientific article; zbMATH DE number 1791683 (Why is no real title available?)
- Unique End of Potential Line
- Computing a fixed point of contraction maps in polynomial queries
- Approximation of fixed points of weakly contractive nonself maps in Banach spaces
- A two-dimensional bisection envelope algorithm for fixed points
- On the weak-approximate fixed point property
- Existence and computation of short-run equilibria in economic geography
- Scientific contributions of Leo Khachiyan (a short overview)
- Optimal bounds on finding fixed points of contraction mappings
This page was built for publication: Approximating fixed points of weakly contracting mappings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1974567)
