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$

  • $\begingroup$ What do you mean by "convergence time"? $\endgroup$
    – Nik Weaver
    May 23, 2021 at 14:37
  • $\begingroup$ 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$ $\endgroup$ May 23, 2021 at 14:43
  • $\begingroup$ 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}$ ... $\endgroup$
    – Nik Weaver
    May 23, 2021 at 15:15
  • $\begingroup$ added full context and my sketch of proof $\endgroup$ May 23, 2021 at 16:45
  • $\begingroup$ 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? $\endgroup$
    – username
    May 23, 2021 at 17:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy