# Question regarding upper bound of fixed-point function

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,

-
What's "Theorem 2.4"? –  Guess who it is. Oct 6 '11 at 10:37
maybe this one :limit of some (constantfunction)=constantlimit of(function) –  dato datuashvili Oct 6 '11 at 10:51
Do you have to use $f(x) = 5/\sqrt{x}$? You should get better convergence with $f(x) = 2x/3 + 25/(3x^2)$, and it's faster to calculate too. –  Ilmari Karonen Oct 6 '11 at 11:51
@Ilmari Karonen: Since this chapter is before Newton section, I can't use Newton method. Furthermore, if the program run on that function yields 14 iterations, then I assume there must be a $k$ such that I can solve for $n$ approximate to 14. Thank you. –  Chan Oct 7 '11 at 3:28

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.

-
Thanks a lot. I still think there is a way to pick only one $k$. –  Chan Oct 9 '11 at 4:35
The theorem must always be valid. It has to use the maximum of the derivative in the respective interval and it guarantees that the number of iterations will surely be smaller than the stated estimation. The concrete iteration will always be better, because during the iteration the derivative can only get smaller than the maximum used by the theorem. The theoretical estimation will be too conservative when the derivative changes a lot, it will be tighter if the derivative changes a litle. So, if you started the iteration with 2.9, then k = 0.506, and the theoretical estimation would be better. –  Jiri Oct 9 '11 at 10:11
@Jiry: Nice explanation! Now I'm convinced. Thanks a lot ;) –  Chan Oct 9 '11 at 11:08

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.

-
Right, it was supposed to be $\frac5{\sqrt x}$, not $\frac{\sqrt 5}{x}$... –  Guess who it is. Oct 6 '11 at 11:46
It was my typo. Sorry for the confusion. Edited. –  Chan Oct 6 '11 at 20:00