Newton's Method

The equation \(\cos(x) \!=\! x\) has a single solution, referred to as Dottie number.
1. Calculate the Dottie number accurate to within one-thousandth.
2. Write a computer program that performs Newton’s Method, and use that program to calculate the Dottie number accurate to the precision of your chosen language’s float data type. Note the TI-83/84+ series of calculators are programmable. Can you make your program recursive?
3. Take the cosine of any number. Then take the cosine of that result. And then take the cosine of that result. And then take the cosine of that result. Keep doing this for awhile, and you should notice that this process converges to that same solution to \(\cos(x) = x\). Assuming this does converge, why must it converge to this same number?
The arctangent function has a single root at zero. But depending on the initial seed, Newton’s method might fail to hone in on this root, and may instead return numbers further and further away from zero. Graph the function \({y = \arctan(x)},\) and based on the geometry of the graph figure out for which initial seeds Newton’s method will converge to zero, and for which initial seeds Newton’s method will diverge.
For any positive number \(N,\) here is a simple method for approximating the square root of \(N.\) Start by estimating some positive integer \(x\) near \(\sqrt{N}.\) Plugging \(x\) into the formula \(x_\star = \tfrac{1}{2}\bigl(x + \tfrac{N}{x}\bigr)\) will result in a number \(x_\star\) that is closer to \(\sqrt{N}\) than \(x.\) In fact, plugging any input into this formula will return a number closer to \(\sqrt{N}\) than the input. Furthermore, the successive outputs that result from recursively applying this formula, plugging each output back in as the next input, will approach the exact value of \(\sqrt{N}.\) This procedure is commonly called the Babylonian method for computing square roots since it was known to Babylonian mathematicians millennia ago.
1. Show that this formula is the same as the formula that would result from applying Newton’s method to approximate a solution of the equation \(x^2-N=0.\) This justifies why the Babylonian method works.
2. Write a computer program that iteratively applies this formula to approximate the square root of a number accurate to the precision of your chosen language’s float data type. Note the TI-83/84+ series of calculators are programmable. Can you make your program recursive?
3. Come up with similar recursive formulas for the operations \(\sqrt[3]{x} \) and \(\frac{1}{x}\,. \) It can be tough to figure out the one for \(\frac{1}{x}\). The procedure you get for it though, called Newton-Raphson division, is rather noteworthy.
The polynomial \(x^3-3x+5\) has a single root at approximately \({-2.279.}\) However, applying Newton’s method with an initial seed of \(c_0 = 1\) will not converge to this root. Why not?
The polynomial \(x^3-x\) has three roots: \(-1\) and \(0\) and \(1.\) Describe the set of all possible seeds for which Newton’s method will converge to the root \(1.\)
Sometimes Newton’s method fails to converge, but not because the successive approximations blow up towards infinity like in the example with arctangent.
1. Consider the polynomial \(x^3-2x+2.\) This polynomial has a root at approximately \({-1.769.}\) However, applying Newton’s method with an initial seed of \(c_0 = 0\) will not converge to this root. Investigate why Newton’s method fails in this case.
2. Similarly, investigate the polynomial \(x^5-x-1\) by running Newton’s method with an initial seed of \(c_0 = 0.\)
3. In those previous examples we see that there exist polynomials for which a certain initial seed \(c_0\) will generate a sequence \(\{c_0, c_1, c_2, \dotsc\}\) that eventually repeats, creating a cycle in which Newton’s method gets stuck instead of converging to a root. If such a cycle is \(n\) numbers long, we’ll call it an \(n\)-cycle. E.g. the polynomial \(x^3-2x+2\) with initial seed \(c_0=0\) induces a \(2\)-cycle, and the polynomial \(x^5-x-1\) with initial seed \(c_0=0\) induces and \(3\)-cycle.
  
  Problem: For a positive integer \(n\) find an example of a polynomial and initial seed that will induce an \(n\)-cycle.
  
  Questions: Does there exist a seed that induces a cycle for every polynomial? If not, can the polynomials that admit cycle-inducing seeds be characterized?