4
$\begingroup$

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,

  • 0
    @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.2011-10-07

2 Answers 2

2

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.

  • 0
    @Jiry: Nice e$x$planation! Now I'm convinced. Thanks a lot ;)2011-10-09
1

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.

  • 0
    It was my typo. Sorry for the confusion. Edited.2011-10-06