Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2017 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 10


Problem

Newton’s method applied to the equation $f(x) = x^3-x$ takes the form of the iteration $x_{n+1} =x_n-\frac{(x_n)^3-x_n}{3{x_n}^2-1} , n = 0,1,2,\ldots$

(a) What are the roots of $f(x) = 0$?

(b) Study the behavior of the iteration when $x_0 > \frac{1}{\sqrt{3}}$ to conclude that the sequence $\{x_0,x_1,\ldots\}$ approaches the same root as long as you choose $x_0 > \frac{1}{\sqrt{3}}$. It may be helpful to start with the case $x_0>1$.

(c) Assume $-\alpha < x_0 < \alpha$. For what number $\alpha$ does the sequence always approach $0$?

(d) For $x_0 \in(\alpha,\frac{1}{\sqrt{3}})$ the sequence may approach either of the roots $\pm x^{*}$. Can you find an (implicit) expression that can be used to determine limits $a_i$ and $a_{i+1}$ such that if $x0 \in (a_i,a_{i+1})$ then the sequence approaches $(-1)^i{x^{*}}$. Hint:$a_1 = \frac{1}{\sqrt{3}}, a_i > a_{i+1}$ and $a_i$ approaches $\frac{1}{\sqrt{5}}$ when $i$ becomes large.


Solution

(a) The roots are $(-1,0,1)$.

(b) First consider $x_0 > 1$. Let $x_{n+1} = 1 + \epsilon$ and $x_n = 1 + \delta$ with $\delta > 0$. The iteration gives $0 <\frac{\epsilon}{\delta} < \frac{2}{3}$. Next consider $\frac{1}{\sqrt{3}} < x_0 < 1$. As the signs of the numerator and denominator in the rational part of the iteration does not change on the interval under consideration we find that $x_1 > 1$. Finally, $x_0 = 1$ produces $x_1 = 1$.

To answer (c), rewrite the iteration as$x_{n+1} =-\frac{2(x_n)^3}{1-3(x_n)^2 }$, and note that for $0<=x_0 < \frac{1}{\sqrt{3}}$ the next iterate will be non-positive. Insisting that $-x_0 < x_1 <= 0$, so that $x_1$ will be closer to zero than $x_0$ gives the limiting case $x_1 =-x_0$, or $\alpha (1-3\alpha^2) =-2\alpha^3$, which has the solution $\alpha = \frac{1}{\sqrt{5}}$.

Finally the implicit recurrence in (d) is obtained by running Newton backwards $a_i-\frac{a_i^3-a_i}{3a_i^2-1}$ = $-a_{i-1}, a_1 = \frac{1}{\sqrt{3}},\ldots,a_{\infty}= \frac{1}{\sqrt{5}}$.

See also

2017 UNM-PNM Contest II (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10
All UNM-PNM Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_UNM-PNM_Statewide_High_School_Mathematics_Contest_II_Problems/Problem_10&oldid=100618"