Question regarding upper bound of fixed-point function

Question

The problem is to estimate the value of $\sqrt[3]{25}$ using fixed-point iteration. Since $\sqrt[3]{25} = 2.924017738$, I start with $p_0 = 2.5$. A sloppy C++ program yield an approximation to within $10^{-4}$ by $14$ iterations.

#include <cmath>
#include <iostream>

using namespace std;

double fx( double x ) {
    return 5.0 / sqrt( x );
}

void fixed_point_algorithm( double p0, double accuracy ) {
    double p1;
    int n = 0;
    do {
        n++;
        p1 = fx( p0 );
        cout << n << ": " << p1 << endl;
        if( abs( p1 - p0 ) <= accuracy ) {
            break;
        }   
        p0 = p1;
    } while( true );
    cout << "n = " << n << ", p_n = " << p1 << endl;
}

int main() {
    fixed_point_algorithm( 2.5, 0.0001 );
} 

Then I tried to solve it mathematically using the these two fixed-point theorems:

Fixed-point Theorem Let $g \in C[a,b]$ be such that $g(x) \in [a,b]$, for all $x$ in $[a,b]$. Suppose, in addition, that $g'$ exists on $(a,b)$ and that a constant $0 < k < 1$ exists with $$|g'(x)| \leq k, \text{ for all } x \in (a, b)$$ Then, for any number $p_0$ in $[a,b]$, the sequence defined by $$p_n = g(p_{n-1}), n \geq 1$$ converges to the unique fixed-point in $[a,b]$

Corollary
If $g$ satisfies the hypotheses of Theorem 2.4, then bounds for the error involved in using $p_n$ to approximate $p$ are given by $$|p_n - p| \leq k^n \max\{p_0 - a, b - p_0\}$$ and $$|p_n - p| \leq \dfrac{k^n}{1-k}|p_1 - p_0|, \text{ for all } n \geq 1$$

I picked the interval $[2.5, 3.0],$ $$g(x) = \dfrac{5}{\sqrt{x}}$$ $$g'(x) = \dfrac{-5}{2 \cdot x^{3/2}}$$ Plugging in several values in $(2.5, 3.0)$ convince me $x = 2.5$ yield the largest value of $k$. $$\implies \lim_{x\to\ 2.5} \bigg|\dfrac{-5}{2\cdot x^{3/2}} \bigg| = \dfrac{\sqrt{10}}{5}$$ So I chose $k = \dfrac{\sqrt{10}}{5}$, where $p_1 = g(p_0) = \sqrt{10}$. Then I solved for $n$ in the inequality equation: $$ 10^{-4} \leq |p_n - p| \leq \dfrac{k^n}{1-k}|p_1 - p_0|$$ $$\dfrac{\bigg(\dfrac{\sqrt{10}}{5}\bigg)^n}{1-\dfrac{\sqrt{10}}{5}}|\sqrt{10} - 2.5| \geq 10^{-4}$$ And I got $n \approx 18$ which is odd :(. From my understanding fixed-point iteration converges quite fast, so 4 iteration is significant. Then I tried to vary the interval to see if the result can come closer to 14, but I couldn't find any interval that satisfied. So I guess either my upper bound must be wrong or I didn't fully understand the theorem. Can anyone give me a hint?

Thank you,

Answer 1

The discrepancy is caused by taking the maximal derivative in the interval [2.5, 3.0]:

$$k = \max |g'(x)| = |g'(2.5)| = \sqrt{10}/5 = 0.632$$

So, you assume that the solution error is decreased by $0.632$ at each iteration step, and you would need at least 18 (I got 21) iterations to bring the error to $0.0001$.

However, the derivative is much smaller in the neighborhood of the solution:

$$k = |g'(\text{solution})| = |g'(2.924)| = 0.5$$

If you estimate with this $k$, the error is halved at each iteration, and you need only 14 iterations to decrease it to $0.00008$. This is too optimistic, because at the beginning of the iteration you should use $k = 0.623$ and only later move to $k=0.5$. But this analysis should explain the discrepancy between the theoretical estimation and the numerical iteration.

Answer 2

If I understand this right, $p_n$ converges to a fixed point of $g$. Taking $g(x)=\sqrt5/x$ as you have done, the fixed point of $g$ is not the $\root3\of{25}$ that you are after, but rather it is $\root4\of5$. So it's no wonder everything is going haywire.