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
#include
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,