Newton’s Method

  1. The Dottie number is the sole solution to the equation \(\cos(x) \!=\! x\,.\)

    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 analogue of the float data type. If your program is iterative, can you re-write it to be recursive?
    3. Using a calculator or computer, do the following procedure: Start with any number. Take the cosine of number. Take the cosine of that result. 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 the Dottie number, the solution to the equation \(\cos(x) = x\). Why does this process converge to the Dottie number?
  2. 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?
  3. The polynomial \({x^3\!-\!x}\) has three roots, located at \(-1\) and \(0\) and \(1.\) Describe the set of all initial seeds for which Newton’s method converges to the root \(1.\)

  4. Here is a simple method for calculating \(\sqrt{n}\) to any decimal precision for any positive number \(n.\) Start by guessing some number \(x\) near \(\sqrt{n}.\) Plugging this guess \(x\) into the formula \(x_\star = \tfrac{1}{2}\bigl(x + \tfrac{n}{x}\bigr)\) will always result in an output \(x_\star\) that is closer to \(\sqrt{n}\) than \(x.\) Iterating this procedure, re-evaluating that formula at successive outputs, results in better and better approximations 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 one that results from applying Newton’s method to approximate a solution to \({x^2\!-\!n\!=\!0.}\)
    2. Determine similar recursive formulas for the \(\sqrt[3]{n} \) and the \(\tfrac{1}{n}\) operations. (The procedure you get for the division operation \(\tfrac{1}{n}\) is noteworthy, and is commonly referred to as Newton-Raphson division.)
  5. The arctangent function has a single root at zero. But depending on the initial seed, Newton’s method might fail to converge to 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.

  6. 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 why Newton’s method fails for the polynomial \({x^5\!-\!x\!-\!1}\) 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. Define an \(n\)-cycle as such a cycle containing \(n\) unique numbers.

      1. Given a positive integer \(n,\) find an example of a polynomial and initial seed \(c_0\) for which Newton’s method induces an \(n\)-cycle.
      2. Does there exist an initial seed that induces a cycle for every polynomial? If not, can the polynomials that admit cycle-inducing seeds be characterized?
  7. Newton’s method for approximating a zero \(r\) of a function \(f\) is based on the geometric intuition that the line tangent to the graph of \(f\) at \(x=c_\star\) (near \(r\)) will intersect the \(x\)-axis at a point closer to \(r\) than \(c_\star.\) This intuition results in the recursive formula \(c_{n+1} = c_n - f(c_n)/f'(c_n)\,.\) However, one could instead consider the parabola tangent to the graph of \(f\) at \(x=c_\star\,.\) Whereas the tangent line’s value and first derivative match \(f\)’s at a point, the tangent parabola’s value and first derivative and second derivative match \(f\)’s at a point. This parabola, due to its curvature, should intersect the \(x\)-axis nearer to \(r\) than the tangent line. What is the recursive formula that results from considering tangent parabolas instead of tangent lines? (Note, this is referred to as Halley’s method for parabolas specifically, and Householder’s method for higher-degree polynomials in general.)