2
$\begingroup$

Let's say that we have a $C^\infty$ differentiable function , $f(x)$ and we either know apriori, or make the ansatz/postulate that a root which we are seeking is known to lie in some interval [m-1,m+1] where m is the midpoint.

What are some ways of modifying the function $f(x)$ so that the Newton iteration

$N_f (t) = t - \frac{f (t)}{\dot{f} (t)}$

cannot go outside of the interval if started from a point within the interval (which is generally different from the midpoint)

Using min/max, or piecewise functions, is not a solution because these functions are not differentiable, and the iteration would simply reach the boundary of the interval and stay there.

Squashing $\frac{f (t)}{\dot{f} (t)}$ with $\tanh \left( \frac{f (t)}{\dot{f} (t)} \right)$ will also not work in this case, since it could still escape the interval by making multiple hops even though each hop $x_{n+1}$ would move no greater than 1 from $x_n$

I thought about introducing a repelling fixed point at the ends of the interval but I'm not quite sure how to do that.

I'm not looking for the interval Newton method, that's something different.

thanks in advance

based on the comment below , the mapping function $$f(t) = a+{(b-a) \left( 1+{{\rm e}^{-{\frac {t-a}{b-a}}}} \right) ^{-1}}$$

can be used, here, with $a=308.36982554421727540$ and $b=310.36982554421727540$

the inverse function is

$${\it invf} \left( t \right) =a\ln \left( -{\frac {b-t}{-t+a}} \right) -\ln \left( -{\frac {b-t}{-t+a}} \right) b+a$$

enter image description here

and the function I am trying to find the roots of, the Hardy Z function in this case, is

enter image description here

where the root of the modified function isn't even found in the interval.. it seems that I need the mapping function $f(t)$ to map to a and b much faster than it is, since indeed the root is there, but not in the interval. If I go ahead and find that root and invert the mapping, thats not the root either.

The function Z(f(t)) has its root at 312.16854074213271881 so it cannot be inverted to a real number since it lies outside the interval, it evaluates to 309.86500608950761935-6.28318530717958647*I

$\endgroup$

3 Answers 3

3
$\begingroup$

You cannot quite do what you ask for, because if there is any point $p$ within the interval that has a very small derivative of $f$ and a nonzero value of $f$ such that $f/'f$ then $p$ will take the next guess outside the interval, regardless of whether you add a "barrier" at the end of the interval.

However, you can do what you want as follows: Consider the function $$ g(x) = f\left(\frac2\pi \tan^{-1}x\right) $$ Use the ordinary Newton's method to solve $g(x) = 0$. The set of guesses cannot leave the interval of $(-1,1)$ in the argument of $f(t)$ since the arctan is always between $-\frac\pi 2$ and $\frac\pi 2$. When you have your solution $x_0$, then the solution of $f(t)=0$ is at $$ t=\frac2\pi \tan^{-1}x_0 $$

$\endgroup$
2
  • $\begingroup$ In this case, the argument of the function is the positive real numbers, so I'd really need a centered version of that, see this other question I asked that math.stackexchange.com/questions/2142892/… where I do something similiar with the tanh function $\endgroup$
    – crow
    Feb 17, 2017 at 1:30
  • $\begingroup$ its not smooth, but you can map the point back inside the interval since it will never jump out of the interval by a distance greater than 1.. whatever distance it jumps out by, you can add or subtract that distance to the point it jumped over, to reflect it back inside the interval. $r (t, l, u) = \left\{ \begin{array}{ll} l + (l - t) & t < l\\ u - (t - u) & t > u\\ t & l \leqslant t \leqslant u \end{array} \right.$ and the iteration function being $r \left( t - \tanh \left( \frac{f (t)}{\dot{f} (t)} \right), c - 1, c + 1 \right)$ since $$| \tanh (x) | \leqslant 1$$ $\endgroup$
    – crow
    Feb 17, 2017 at 5:03
1
$\begingroup$

You know that the root $x$ you are looking for is such that $a<x<b$ and your solver is not able to handle bounds.

What you can do is to define $$x=a+\frac{b-a}{1+e^{-t}}$$ which then gives an infinite domain for $t$.

Start Newton at $t=0$ which corresponds to $x=\frac{a+b}2$.

$\endgroup$
1
  • $\begingroup$ Interesting, a slight modification which I need, is to use the transformation $$a+{(b-a) \left( 1+{{\rm e}^{-{\frac {t-a}{b-a}}}} \right) ^{-1}}$$ which has the limit as t=-inf being equal to a and as t->inf being equal to b .. once a zero is found then it can be inverted with $a\ln \left( -{\frac {b-y}{a-y}} \right) -\ln \left( -{\frac {b-y}{a- y}} \right) b+a$ does that seem correct? $\endgroup$
    – crow
    Feb 17, 2017 at 16:35
0
$\begingroup$

Time traveller is here. Perhaps you're looking for a Interval Newton's method wiki not wiki. The idea is to iterate intervals $[a_k..b_k]$. Defining a point on each interval, say $x_k\equiv (a_k+b_k)/2$ we

  1. get new interval

$$ [a_{k+1}..b_{k+1}] = x_k - f(x_k)/f'([a_k..b_k]), $$

Note that left side of equation is not simply $[x_k - f(x_k)/f'(a_k) \,\, .. \,\, x_k - f(x_k)/f'(b_k)]$, see here

  1. find its intersection with the previous

$$ [a_{k+1}..b_{k+1}] := [a_{k+1}..b_{k+1}] \cap [a_k..b_k]. $$

  1. repeat.
$\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.