Choosing the initial values (Newton's method) Let, say, I want to find an approximation of the root $r$ for $x^{3}=x+1$ using Newton's method. $$x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \quad(n \geq 0)$$
I guess the initial point is denoted by $x_0$. My question is: how do I find this point?
what I did was to finding a pair $a<b$ such that $f(a)f(b) < 0$. I found $a=1,b=2$. So $r$ must be in $[1,2]$. The initial point I choose  to be some random point in $[1,2]$. So I choose $x_0 = 1$ . Is this the correct rational behind finding an initial point?
 A: Making the problem more general, you are looking for the zero of a function $f(x)$ and you know that the solution is $\in (a,b)$.
If you have to decide if $x_0=a$ or $x_0=b$, it is quite simple :

*

*If $f(a)\times f''(a) >0$ then $x_0=a$ guarantees that the solution will be reached without any overshoot of the solution

*Else $x_0=b$
This is Darboux theorem.
Edit
In comments, @Carl Christian properly mentioned that this is necessary and sufficient provided that, in $[a,b]$, $f''(x)$ does not change sign. This was the first hypothesis in the linked paper (equation $(2)$) and the first theorem.
A: Although it is true that choosing any point in $[1,2]$ will lead to convergence with this problem, it is better to be safe.
Without any assumptions on the second derivative, you can guarantee convergence using the Newt-safe algorithm, which essentially combines bisection with Newton's method to guarantee every iteration remains in the current bracket.
Imagine for sake of example, your initial bracket was $[0,2]$ instead of $[1,2]$, and you attempted to start with $x_0=0$. But upon doing this, you found $x_1=-1\notin(0,2)$. Then it is clear Newton's method is not converging to the root and you should instead take $x_1=1$, the midpoint of the bracket. Now depending on the sign of $f(1)$, update the bracket. In this case the new bracket becomes $[1,2]$. Now trying Newton's method with $x_1=1$, we find that we are starting to converge.
Usually what occurs is bisection leads the way to "finding the initial point for Newton's method", as with the above example, and now you don't have to worry about starting close to the root at all. Despite Newton's method failing if you start with $x_0<1/\sqrt3$, Newt-safe will converge even with an initial bracket such as $[-10,10]$.
