2
$\begingroup$

Well this question was in my homework, I have difficulty to "proof" it (or more correctly: seeing how I would solve it).

Consider a floating point system ($s \cdot b^e$ where $1\leq s \leq 10 - 1 \cdot 10^{-15}$ $b = 10$, $-300 \leq e \leq 300$ with special symbols for minus sign, 0 and infinity added). (coincidentally this is almost the computer's floating point system)

Newton's method of approximating a function's root is applied in this system to the function $f(x) = x^2 + \tfrac{1}{x}$ which has a unique root at $x=-1$ a zero derivative at $ \hat{x} = \sqrt[3]{\tfrac{1}{2}}$ and a singularity at $x = 0$.

Does the iteration converge for $x_0 = \hat{x}$?


the answer should be "yes"

When ignoring the number system and simply solving it, a zeo derivative means the tangent is a horizontal line. So the tangent never crosses the x axis and $x_1 = \infty$. However $\hat{x}$ can't be described in the floating point system, hence it will be approximated and rounding will cause the derivative to become non 0.

However this still doesn't prove newton's method will converge, it may also stay around this "local minimum", right? Or is this enough to say it converges?

$\endgroup$
  • $\begingroup$ The exact derivative at the inexact number is nonzero, but the calculated (inexact) derivative could be zero ... $\endgroup$ – Hagen von Eitzen Feb 18 '14 at 12:18
0
$\begingroup$

It's not completely clear to me from your specification what precision you're working in. That is, in the parlance of numerical analysis, how many digits does the significand $s$ have? I'm guessing, from the $10^{-15}$ term, that your precision is $15$, but the same basic ideas apply independent of the precision.

Assuming the precision is $15$, the two closest numbers to $x_0=\sqrt[3]{1/2}$ are $$0.793700525984099$$ and $$0.793700525984100.$$ The second of these happens to be slightly closer to and larger than $x_0$. Now, if you understand the geometry of Newton's method, it's not at all hard to see why the sequence must converge, as a number slightly larger than $x_0$ will lead to a large, negative value of $x_1$.

enter image description here

In fact, a direct computation with $$N(x)=x-\frac{x^4+x}{2 x^3-1}$$ shows that $N(0.793700525984100)$ is a number on the order of $-10^{-15}$ and that subsequent iterates converge slowly to $-1$. It's not at all hard to prove that this must happen, as $N$ is increasing on $(-\infty,-1]$ with a unique fixed point at $-1$. In fact, I bet you've seen a theorem like the following in your class:

Theorem: Suppose that $f$ is a positive, decreasing, twice differentiable function on $(-\infty,a]$ with $f(a)=0$ and $f''(x)>0$ for $x<a$. If $x_0<a$, then Newton's method starting at $x_0$ converges to $a$.

The basic idea behind the proof is to notice that, since $$x_{k+1} = N(x_k) = x_k-\frac{f(x_k)}{f'(x_k)},$$ we see that $x_{k+1}>x_k$, i.e. $(x_k)_k$ is monotone increasing. Furthermore, the convexity condition on $f$ can be used to show that $(x_k)_k$ is bounded above by $a$. Since $(x_k)_k$ is increasing and bounded above, it must be convergent and it must converge to a fixed point.

Incidentally, there is a standard way to visualize the basins of attraction of $N$ in the complex plane. Take a rectangular region and iterate Newton's function for each "pixel" in that region to find the corresponding limit. Then color each pixel according the root that is found. For your function, the image looks like so:

enter image description here

The initial points that lead to the root $-1$ are shown in red. The other two roots are complex and, since the original function is real valued for real input, can only be obtained by starting with a complex input. It appears that the only real numbers that don't converge to $-1$ are those that eventually hit the singularity at $\sqrt[3]{1/2}$ exactly. As that number is not representable exactly in your system, I'd venture to say that it is impossible to avoid convergence to $-1$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Though as this is was an "example exam question" - and during exams we're only allowed to take simple calculators (no graphical/programmable). - I can't help but still wonder if this question was actually solvable there. $\endgroup$ – paul23 Feb 19 '14 at 11:50
  • $\begingroup$ @paul23 I would say this is definitely doable in on an exam; I'd certainly expect a good numerical analysis student to be able to do it. Not only is it doable but the graph (which is not at all hard to come up with) makes it easy to see how to do it. From there, the only issue is whether your initial approximation to $(1/2)^(1/3)$ is an over-estimate or an underestimate and that's easy with your calculator. I did update my answer with a theorem that quantifies one geometrical observation. Hope that helps. $\endgroup$ – Mark McClure Feb 19 '14 at 12:39
0
$\begingroup$

Interval Newton method is perhaps more appropriate in place of the usual Newton's method when calculating with intervals (accounting for finite floating point representation), and particularly over intervals where the derivative contains zero, http://en.wikipedia.org/wiki/Interval_arithmetic#Interval_Newton_method

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.