Consider the problem of finding the roots of $f(x)$. We assume that there is a single root $x_*$ between $a$ and $b$, $a < x_* < b$.
Assume also that the sign of $f''(x)$ does not change for $x \in [a,b]$.
It is well known that if $f(a) f''(a) > 0$ then the Newton method converges to the solution without overshoot. See, for instance, https://en.wikipedia.org/wiki/Newton%27s_method#Analysis and Newton iteration converges monotonically
Now, what if $f(a) f''(a) < 0$?
Under which conditions can we establish that the Newton approximation method will converge after a single overshoot, which will occur precisely at the first iteration?
Let
\begin{equation}
x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)}
\end{equation}
and $x_0=a$,
\begin{equation}
x_{1} = a – \frac{f(a)}{f'(a)}
\end{equation}
Under which conditions does $x_1 > x_*$ and $f(x_1) f''(x_1) > 0$?
This question is a follow up to Darboux' theorem on the convergence of Newton's method
A reference with a theorem or insights would be very helpful. In particular, I was not able to extract the answer to the question above from the following paper
"Sur la méthode d'approximation de Newton", Nouvelles annales de mathématiques: journal des candidats aux écoles polytechnique et normale, serie 2, vol 8 (1869), pp.17-27
Concrete example
Let $0 < p < 1$ and $0.5 < q < 1$.
Assume
\begin{align}
&f(x)=(8(q-0.5)^2{p}^3+(-34(q-0.5)^2-1.5){p}^2 + \nonumber \\
&\quad\quad\quad +(40(q-0.5)^2+6)p-16(q-0.5)^2-4)/(p-2)^2. \label{eq:cubic2}
\end{align}
We search for $x_*$ such that $f(x_*)=0$.
Then, $x_* \approx x_1$,
\begin{align}
x_* & \approx x_1 \\
& = x_0 – \frac{f(x_0)}{f'(x_0)} \\
&= 0.845 + \frac{1.23688 q^2-1.23688 q+0.31}{-2.38422 q^2+2.38422 q+2} \label{eq:pstarf}
\end{align}
where $x_0=0.845$.
It is easy to show that $x_0 < x_* \leq 1$.
How can I show that $x_1 > x_*$ using general properties of the global convergence of Newton approximation method?
Additional remark
Clearly, the root of $f(x)$ is the same as the root of $g(x)$,
\begin{align}
&g(x)=(8(q-0.5)^2{p}^3+(-34(q-0.5)^2-1.5){p}^2 + \nonumber \\
&\quad\quad\quad +(40(q-0.5)^2+6)p-16(q-0.5)^2-4).
\end{align}
Then,
\begin{align}
x_* & \approx x_0 – \frac{g(x_0)}{g'(x_0)} \\
&= 0.845-\frac{1.650041 (q – 0.5)^2 + 0.0010375}{0.3234 (q – 0.5)^2 – 3.465}
\end{align}
where $x_0=0.845$. However, Newton approximation convergence is much slower for $g(x)$ than $f(x)$. Still, for $g(x)$ we known that NAM will never overshoot, as $g(x_0) g''(x_0) > 0$. Is there a way to check in advance why/if $f(x)$ is a best input for Newton approximation than $g(x)$ with respect to convergence time, but that $g(x)$ is best with respect to number of overshoots?
Best Answer
This is too long for comments.
To make the problem easier, let us define $k=\left(q-\frac{1}{2}\right)^2$ which makes $$g(p)=8 k p^3-\frac{68 k+3}{2} p^2+2(20 k+3) p-4 (4 k+1)$$ where $0 \leq k \leq \frac 14$.
As you did show, $g(p)\,g''(p) \geq 0$ for any $ p_0 \geq 2-\frac{2}{\sqrt{3}}$ (typo in your paper - look at what equation $(32)$ gives). So, by Darboux theorem, starting Newton iterations with $p_0$ ensures convergence without any overshoot during the path to solution. However, this does not mean that $p_0$ is the best starting point.
Anyway, using it, we shall have $$p_1=2-\frac{2}{\sqrt{3}}-\frac{\left(48-32 \sqrt{3}\right) k}{\left(144-84 \sqrt{3}\right) k+9 \sqrt{3}}\,\, > p_0\qquad \forall \, 0 \leq k \leq \frac 14$$
Starting with $p_0=2-\frac{2}{\sqrt{3}}$, here are the results for the first iterations where you cannot notice any overshoot. $$\left( \begin{array}{cccccc} k & p_1 & p_2 & p_3 & p_4 & \text{solution} \\ 0.00 & 0.845299 & 0.845299 & 0.845299 & 0.845299 & 0.845299 \\ 0.01 & 0.850068 & 0.850078 & 0.850078 & 0.850078 & 0.850078 \\ 0.02 & 0.854845 & 0.854892 & 0.854892 & 0.854892 & 0.854892 \\ 0.03 & 0.859631 & 0.859747 & 0.859747 & 0.859747 & 0.859747 \\ 0.04 & 0.864427 & 0.864648 & 0.864648 & 0.864648 & 0.864648 \\ 0.05 & 0.869232 & 0.869604 & 0.869605 & 0.869605 & 0.869605 \\ 0.06 & 0.874046 & 0.874622 & 0.874622 & 0.874622 & 0.874622 \\ 0.07 & 0.878869 & 0.879709 & 0.879709 & 0.879709 & 0.879709 \\ 0.08 & 0.883702 & 0.884872 & 0.884874 & 0.884874 & 0.884874 \\ 0.09 & 0.888544 & 0.890123 & 0.890125 & 0.890125 & 0.890125 \\ 0.10 & 0.893395 & 0.895469 & 0.895473 & 0.895473 & 0.895473 \\ 0.11 & 0.898256 & 0.900921 & 0.900928 & 0.900928 & 0.900928 \\ 0.12 & 0.903126 & 0.906492 & 0.906503 & 0.906503 & 0.906503 \\ 0.13 & 0.908006 & 0.912193 & 0.912211 & 0.912211 & 0.912211 \\ 0.14 & 0.912895 & 0.918038 & 0.918067 & 0.918067 & 0.918067 \\ 0.15 & 0.917794 & 0.924044 & 0.924089 & 0.924089 & 0.924089 \\ 0.16 & 0.922702 & 0.930227 & 0.930295 & 0.930295 & 0.930295 \\ 0.17 & 0.927619 & 0.936606 & 0.936708 & 0.936708 & 0.936708 \\ 0.18 & 0.932547 & 0.943203 & 0.943355 & 0.943355 & 0.943355 \\ 0.19 & 0.937483 & 0.950043 & 0.950266 & 0.950266 & 0.950266 \\ 0.20 & 0.942430 & 0.957153 & 0.957478 & 0.957478 & 0.957478 \\ 0.21 & 0.947386 & 0.964566 & 0.965034 & 0.965034 & 0.965034 \\ 0.22 & 0.952352 & 0.972317 & 0.972987 & 0.972988 & 0.972988 \\ 0.23 & 0.957328 & 0.980448 & 0.981405 & 0.981407 & 0.981407 \\ 0.24 & 0.962313 & 0.989008 & 0.990371 & 0.990374 & 0.990374 \\ 0.25 & 0.967308 & 0.998053 & 0.999992 & 1.000000 & 1.000000 \end{array} \right)$$
In any manner, it is possible to generate a quite good (theoretically based) estimate of the starting point. It write $$\color{blue}{p_0=\frac{\sum_{n=0}^4 a_n\,k^n } {\sum_{n=0}^4 b_n\,k^n }}$$ where $$\left( \begin{array}{ccc} n & a_n & b_n \\ 0 & 1458 \left(-3+\sqrt{3}\right) & -2187 \\ 1 & -1944 \left(-113+65 \sqrt{3}\right) & 2916 \left(25-14 \sqrt{3}\right) \\ 2 & 1728 \left(-2817+1630 \sqrt{3}\right) & 2592 \left(-638+371 \sqrt{3}\right) \\ 3 & 1152 \left(38303-22115 \sqrt{3}\right) & 576 \left(27345-15794 \sqrt{3}\right) \\ 4 & 512 \left(-262761+151697 \sqrt{3}\right) & 768 \left(-66129+38174 \sqrt{3}\right) \end{array} \right)$$ Using this $p_0$, the table below reproduces the first iterate $p_1$ of Newton method as well as the solution. $$\left( \begin{array}{cccc} k & p_0 & p_1 & \text{solution} \\ 0.00 & 0.845299 & 0.845299 & 0.845299 \\ 0.01 & 0.850078 & 0.850078 & 0.850078 \\ 0.02 & 0.854892 & 0.854892 & 0.854892 \\ 0.03 & 0.859747 & 0.859747 & 0.859747 \\ 0.04 & 0.864648 & 0.864648 & 0.864648 \\ 0.05 & 0.869605 & 0.869605 & 0.869605 \\ 0.06 & 0.874622 & 0.874622 & 0.874622 \\ 0.07 & 0.879709 & 0.879709 & 0.879709 \\ 0.08 & 0.884874 & 0.884874 & 0.884874 \\ 0.09 & 0.890125 & 0.890125 & 0.890125 \\ 0.10 & 0.895473 & 0.895473 & 0.895473 \\ 0.11 & 0.900928 & 0.900928 & 0.900928 \\ 0.12 & 0.906503 & 0.906503 & 0.906503 \\ 0.13 & 0.912211 & 0.912211 & 0.912211 \\ 0.14 & 0.918067 & 0.918067 & 0.918067 \\ 0.15 & 0.924088 & 0.924089 & 0.924089 \\ 0.16 & 0.930294 & 0.930295 & 0.930295 \\ 0.17 & 0.936706 & 0.936708 & 0.936708 \\ 0.18 & 0.943351 & 0.943355 & 0.943355 \\ 0.19 & 0.950259 & 0.950266 & 0.950266 \\ 0.20 & 0.957465 & 0.957478 & 0.957478 \\ 0.21 & 0.965012 & 0.965034 & 0.965034 \\ 0.22 & 0.972951 & 0.972988 & 0.972988 \\ 0.23 & 0.981343 & 0.981407 & 0.981407 \\ 0.24 & 0.990265 & 0.990374 & 0.990374 \\ 0.25 & 0.999813 & 1.000000 & 1.000000 \end{array} \right)$$
In other words, one single iteration is required. We could even do better increasing the degree of expansion of the new $p_0$.