# Banach fixed point theorem / convergence squeeze

I am trying to prove a convergence result on an iterative scheme which has the initial point defined as $$x_1 = \frac{1 - s(x_0)}{s(x_0)}$$ where s(x) is some unknown function.

Here is my theorem and attempted quick sketch of a proof:

For the function $$s(x)$$ defined as a general polynomial of the form $$c_1x^{k_1} + c_2x^{k_2} + ... c_mx^{k_m}$$ where $$k_1 > k_2 > ... > k_m$$ and $$x \geq 0$$, the convergence time of the algorithm is bounded by that of monic polynomials.

Proof: We proceed by bounding the polynomial cost function. For $$0 \leq x < 1$$, we have \begin{align*} c_1x^{k_m} < c_1x^{k_1} + c_2x^{k_2} + ... + c_mx^{k_m} < \tilde C x^{k_m} \end{align*} where $$\tilde C := \sum_i^m c_i$$ and identically for $$x \geq 1$$ \begin{align*} c_1x^{k_1} < c_1x^{k_1} + c_2x^{k_2} + ... + c_mx^{k_m} < \tilde C x^{k_1} \end{align*} For convenience, let $$s_0 := c_1x^{k_1} + c_2x^{k_2} + ... + c_mx^{k_m}$$. Using the above bound we demonstrate the following bounds on algorithm for the polynomial \begin{align*} c_1x^{k_m} &< s(x) < \tilde C x^{k_m} \\ \frac{1}{c_1x^{k_m}} - 1 &> \frac{1}{s(x)} - 1 > \frac{1}{\tilde C x^{k_m}} - 1 \end{align*} Thus, we have the algorithm bound \begin{align*} x_1(s=c_1x^{k_m}) > x_1(s=s_0) > x_1(s=\tilde C x^{k_m}) \end{align*} Lastly, manipulating the result from Banach we have \begin{align*} t \geq \ln\left(\frac{(1-L) |x_t - x^*|}{|x_1 - x_0|}\right) / \ln(L) \end{align*} and substituting the output of the algorithm for $$x_1$$ gives us \begin{align*} t \geq \ln\left(\frac{(1-L) |x_t - x^*|}{|x_1(s_0) - x_0|}\right) / \ln(L) \end{align*} Denote this bound as $$\tau_{s_0}$$. Combining the bound with the algorithm bound (tag) gives us \begin{align*} \tau_{c_1x_0^{k_m}} < \tau_{s_0} < \tau_{\tilde C x_0^{k_m}} \end{align*} bounding the polynomial function's convergence time with monomials. $$\square$$

• What do you mean by "convergence time"? May 23, 2021 at 14:37
• in this case, the $t$ in the first inequality which is number of iterations for the distance between $x_t - x^*$ to be less than $\epsilon$ May 23, 2021 at 14:43
• I mean, you might get lucky and have $x_0$ be the fixed point for $g$. Or it could be the fixed point for $C_1x^{k_1}$ or $C_2x^{k_2}$ ... May 23, 2021 at 15:15
• added full context and my sketch of proof May 23, 2021 at 16:45
• Actually your inequalities hold if all the $c_k$ are positive, which is not any polynomial. Otherwise there is an issue when you go from $a<x<b$ to $\frac1b > \frac1x >\frac1a$. If the all the coefficients are positive it is a strictly increasing function, which is an easier thing to use..but in any case, what is the question? May 23, 2021 at 17:23