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

Difference between revisions of "2017 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 10"

(Created page with " == Problem == Newton’s method applied to the equation <math>f(x) = x^3-x</math> takes the form of the iteration <math>x_{n+1} =x_n-\frac{(x_n)^3-x_n}{3{x_n}^2-1} , n = 0,...")
 
(→‎Solution)
Line 15: Line 15:
  
 
== Solution==
 
== Solution==
 +
(a) The roots are <math>(-1,0,1)</math>.
  
 +
(b) First consider <math>x_0 > 1</math>. Let <math>x_{n+1} = 1 + \epsilon</math> and <math>x_n = 1 + \delta</math> with <math>\delta > 0</math>. The iteration gives <math>0 <\frac{\epsilon}{\delta} < \frac{2}{3}</math>. Next consider <math>\frac{1}{\sqrt{3}} < x_0 < 1</math>. 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 <math>x_1 > 1</math>. Finally, <math>x_0 = 1</math> produces <math>x_1 = 1</math>.
  
 +
To answer (c), rewrite the iteration as<math> x_{n+1} =-\frac{2(x_n)^3}{1-3(x_n)^2 }</math>, and note that for <math>0 ≤ x_0 < \frac{1}{\sqrt{3}}</math> the next iterate will be non-positive. Insisting that <math>-x_0 < x_1 <= 0</math>, so that <math>x_1</math> will be closer to zero than <math>x_0</math> gives the limiting case <math>x_1 =-x_0</math>, or <math>α(1-3\alpha^2) =-2\alpha^3</math>, which has the solution <math>\alpha = \frac{1}{\sqrt{5}</math>.
 +
 +
Finally the implicit recurrence in (d) is obtained by running Newton backwards
 +
<math>a_i=−\frac{a_i^3-a_i}{3a_i^2-1}= −a_{i−1}, a_1 = \frac{1}{\sqrt{3},\ldots,a_{\inf} = \frac{1}{\sqrt{5}}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 04:53, 19 January 2019


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}}$ (Error compiling LaTeX. Unknown error_msg) 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 $α(1-3\alpha^2) =-2\alpha^3$ (Error compiling LaTeX. Unknown error_msg), which has the solution $\alpha = \frac{1}{\sqrt{5}$ (Error compiling LaTeX. Unknown error_msg).

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_{\inf} = \frac{1}{\sqrt{5}}$ (Error compiling LaTeX. Unknown error_msg).

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=100617"