MHB Newton-Raphson algorithm for the root of tanh

[ognik]

The N-R (iterative) formula is: xⁱ⁺¹=xⁱ - f(xⁱ) / f '(xⁱ). A textbook exercise states that the N-R method does not converge for an initial guess of x >~ 1.

I wrote the required program for tanh and found the method diverges at x >~ 1.0886. But I don't understand why it is this value - the N-R formula divides by f '(xⁱ) (which is the slope of f(xⁱ)) - so I thought where that slope/derivative approached zero would cause diverging, but with tanh that seems to happen closer to 2 than to 1.0886?

Second question is - how would I use the N-R formula itself to work out the actual value at which it will diverge? I tried differentiating the whole N-R explicit equation and got 1-sinh(x) which didn't tell me much.

Intuitions and hints much appreciated

 

[Nono713]

The key here is to notice that the slope just needs to be small enough that the iteration sends $x_{i + 1}$ farther from the root (that is, $0$) than $x_i$. Then because the function is odd and the slope is strictly decreasing, the next iteration will send $x_{i + 2}$ farther from the root than $x_{i + 1}$, and so on, in other words, plain divergence (without oscillation). So your divergence condition on $x_0$ should be:
$$\left \lvert x_0 \right \rvert < \left \lvert x_1 \right \rvert$$
That is:
$$\left \lvert x_0 \right \rvert < \left \lvert x_0 - \frac{f(x_0)}{f'(x_0)} \right \rvert$$
Now since the function is odd we can restrict ourselves to studying $x_0 \geq 0$, and it is easy to see from the graph that we must have $x_1 \leq 0$, hence we can write:
$$x_0 < \frac{f(x_0)}{f'(x_0)} - x_0$$
That is, simplifying and expanding $f$ and its derivative:
$$2x_0 < \cosh{x_0} \sinh{x_0}$$
In other words:
$$2 x_0 < \frac{1}{2} \sinh{2 x_0}$$
So that you want to solve for:
$$u < \frac{1}{2} \sinh{u}$$
Unfortunately expanding the $\sinh$ term into exponential form shows that there is in fact no elementary expression for the solutions of the inequality above, but you can of course evaluate the solutions numerically. Consider the function:
$$g(u) = u - \frac{1}{2} \sinh{u}$$
Plotting it gives:

Notice there are exactly three roots, which are at $u = 0$ and $u \approx \pm 2.17732$ (these roots can be found by using the Newton-Raphson method on the function $g$, for which it works quite well). Now recall that we have restricted ourselves to $x_0 \geq 0$ for simplicity, hence $u \geq 0$ so we can discard the negative half of the function, so that we are only interested in $g$ taking negative values for all $u > 2.17732$ approximately, for which:
$$u - \frac{1}{2} \sinh{u} < 0 ~ ~ ~ \implies ~ ~ ~ u < \frac{1}{2} \sinh{u}$$
Substituting back into $x_0$, we find:
$$x_0 = \frac{1}{2} u \approx \frac{1}{2} 2.17732 \approx 1.08866$$
And so we conclude that the Newton-Raphson method fails to converge for all starting points $x_0 > 1.08866$ approximately, and by symmetry for all starting points $x_0 < -1.08866$ approximately, since for those $x_0$ we get $0 < \lvert x_0 \rvert < \lvert x_1 \rvert < \lvert x_2 \rvert < \cdots$.

If you can then show that the Newton-Raphson iteration does in fact converge for all $-1.08866 < x_0 < 1.08866$, which can be done anagolously by showing that for such starting values $x_0 \ne 0$ we get $\lvert x_0 \rvert > \lvert x_1 \rvert > \lvert x_2 \rvert \to 0$, then the behaviour of the $\tanh$ function over the reals under the Newton-Raphson iteration will have been fully determined, with one attractor of "radius" 1.08866 roughly near the root and divergence everywhere else.
​

 

[ognik]

Awesome reply, thanks.
But what if I take u < 1/2 sinh(u), divide both side by u, multiply by 2
Then I have 2 < sinh(u)/u

Expanding sinh(x) is x + x^3/3! + x^5/5! + ...
So sinh(u)/u is 1 + u²/3! + u⁴5! + ...
which leaves u²3! + u⁴5! + ... > 1

I stopped here because it did not look like I would get U > 1.08866 out of the above, just wondering what was wrong with the above approach?

 

[Nono713]

Awesome reply, thanks.
But what if I take u < 1/2 sinh(u), divide both side by u, multiply by 2
Then I have 2 < sinh(u)/u

Expanding sinh(x) is x + x^3/3! + x^5/5! + ...
So sinh(u)/u is 1 + u²/3! + u⁴5! + ...
which leaves u²3! + u⁴5! + ... > 1

I stopped here because it did not look like I would get U > 1.08866 out of the above, just wondering what was wrong with the above approach?

Nothing wrong, that is perfectly fine, and that indeed gives $u > 2.17732$ (which translates to $x_0 > 1.08866$) (in your last equation you multiplied by the factorials instead of dividing). You would still have to evaluate $2.17732$ numerically, though, I believe there is no simple formula for it (but I could be wrong!). We have that $u = 2.17732$ is the solution of $\sinh(u) / u = 2$.

 

[ognik]

Oops - yes, I accidentally left out the '/' when I transcribed from my paper scribblings ...but I find myself in the embarrassing position of not knowing how to go about solving the series properly. All I could do was to consider only the first 2 terms (which I know is not accurate enough) and set v=u². Then I get v^{2/5! + v/3! -1 = 0 (I put = in place of > because I know the answer I get will be the value at which divergence starts)
I rewrote that as v2 + 20v - 120 = 0 and used the quadratic equation to find roots of -10 + or - 14.8323, which leaves u = 4.8323 and ultimately x = 1.09913. I'm fairly sure including at least the 3rd term in the series would make it far more accurate, but I have no idea how to solve the equation including that - my maths is somewhat rusty I'm afraid.}