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,