1
$\begingroup$

I am using Newton's method under MATLAB to find the roots of $f(x) = x^3 -10x +2 $.

The professor has asked us to verify that the algorithm always converge to a roots of $f(x)$ except for a finite number of points.

I've tried $\sqrt{ \frac{10}{3} }$ and $-\sqrt{ \frac{10}{3} }$ because $f '(x) = 0$ at these points (thus $ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $ cannot exist). I'm not sure because when I put these points in the MATLAB's algorithm, it converges to a root of $f(x)$. Maybe it's because MATLAB works with numerical values?

$\endgroup$
  • 2
    $\begingroup$ This is not true. There are countably many points where the algorithm ends up eventually landing in a critical point. And there is a period of length 2. $\endgroup$ – Andrés E. Caicedo May 13 '17 at 17:34
  • $\begingroup$ What do you mean by "there is a period of length 2"? $\endgroup$ – Hugues May 13 '17 at 19:01
  • $\begingroup$ Maybe the professor is looking for situations when $x_{n+2}=x_n$. In this case, the approximation will keep bouncing between two points, hence period of length 2. $\endgroup$ – Samadin May 13 '17 at 19:19
  • $\begingroup$ @DocMogrog I explain in the answer. Drawing a diagram may help to follow the details of the behavior of the iteration on the sequences I describe. $\endgroup$ – Andrés E. Caicedo May 13 '17 at 19:39
  • $\begingroup$ The professor is looking for a finite number of points between -5 and 5. Later in the exercice it's written : "In fact, there is an infinite number of initial points with which the algorithm does not converge..." $\endgroup$ – Hugues May 13 '17 at 19:39
1
$\begingroup$

Suppose $f(x)=ax^3+bx^2+cx+d$ is a cubic with three real roots $r_1<r_2<r_3$, as is the case in the specific case you are considering (in your case, there is a root between $-4$ and $-3$, another one between 0 and 1, and another between 3 and 4). Let $N_f$ be the function associated to Newton's method applied to $f$, that is, $$ N_f(x)=x-\frac{f(x)}{f'(x)}.$$ Note that the fixed points of $N_f$ are precisely the roots of $f$.

Let $c_1<c_2$ be the critical points of $f$. Note that $N_f$ is defined at all $x$ except at $c_1$ and $c_2$, since $f'(c_i)=0$. Also, let $u$ be the inflection point of $f$, so $r_1<c_1<r_2<c_2<r_3$ and $c_1<u<c_2$. Note that $$ N_f'(x)=\frac{f(x)f''(x)}{(f'(x))^2}. $$ In particular, $N_f$ is monotone in the interval $(c_1,u)$ and in the interval $(u,c_2)$.

Denote by $O_x$ the orbit of the point $x$ under $N_f$, that is, the set $\{x,N_f(x),N_f(N_f(x)),\dots\}$, under the convention that the set is finite if, for some $n$, the $n$-fold iterate $N_f(\dots(N_f(x))\dots)$ is one of the $c_i$ (in which case $O_x$ is the set of iterates of $x$ until we reach $c_i$). Otherwise, the set is finite if for some $n$, the $n$-fold iterate as above is one of the $r_i$. Otherwise, the set is infinite, unless the sequence $x,N_f(x),N_f(N_f(x)),\dots$ eventually repeats itself. In the case of cubics, this happens for precisely two values of $x$, as described below. Now, if $f$ is more complicated than a cubic, $O_x$ could well be infinite and the sequence it describes be divergent, but in the case under consideration, it always happens that if $O_x$ is infinite, then the sequence of iterates of $x$ converges to one of the $r_i$. Let's write $O_x\to r_i$ in that case.

Under the assumptions just set up, and using the notation just described, we can find an infinite increasing sequence $t_1<t_2<\dots$, an infinite decreasing sequence $s_1>s_2>\dots$, and points $t$ and $s$ such that $\lim_{n\to\infty}t_n=t$, $\lim_{n\to\infty}s_n=s$, $$ \begin{align} r_1<c_1<t_1<t_2<\dots<t<&\,r_2<s<\dots<s_2<s_1<c_2<r_3,\\ t<&\,u<s,\end{align} $$ and the following happen:

  • If $x\in (-\infty,c_1)$, then $O_x\subset(-\infty,c_1)$ and $O_x\to r_1$.
  • If $x\in (c_2,\infty)$, then $O_x\subset(c_2,\infty)$ and $O_x\to r_3$.
  • If $x\in (t,s)$, then $O_x\subset(t,s)$ and $O_x\to r_2$.
  • $N_f(t)=s$ and $N_f(s)=t$. (This is the period of length 2 I referred to in a comment.)
  • If $x\in(c_1,t_1)$, then $N_f(x)\in(c_2,\infty)$, so $O_x\to r_3$.
  • $N_f(t_1)=c_2$.
  • If $x\in(s_1,c_2)$, then $N_f(x)\in(-\infty,c_1)$, so $O_x\to r_1$.
  • $N_f(s_1)=c_1$.
  • If $x\in (t_1,t_2)$, then $N_f(x)\in(s_1,c_2)$, so $O_x\to r_1$.
  • $N_f(t_2)=s_1$.
  • If $x\in (s_2,s_1)$, then $N_f(x)\in(c_1,t_1)$, so $O_x\to r_3$.
  • $N_f(s_2)=t_1$.
  • If $x\in (t_2,t_3)$, then $N_f(x)\in(s_2,s_1)$, so $O_x\to r_3$.
  • $N_f(t_3)=s_2$.
  • Etc.

Note that Newton's method starting at $x$ diverges if and only if $x$ belongs to the infinite set $$\{c_1\}\cup\{t_i:i=1,2,\dots\}\cup\{t,s\}\cup\{s_i:i=1,2,\dots\}\cup\{c_2\}.$$ Otherwise, it converges as specified above. In particular, note that we can find values of $x$ arbitrarily close to $t$ (or to $s$) such that $O_x\to r_i$ for $i=1,2,3$. One has to be particularly careful using numerical methods when starting near either of these two points $t,s$.

The dynamics of Newton's method applied to polynomials is a pretty topic. A reasonable exposition of the case of cubics can be found in

The Dynamics of Newton's Method for Cubic Polynomials, by James A. Walsh. The College Mathematics Journal, Vol. 26, No. 1 (Jan., 1995), pp. 22-28.

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