Newton’s Method

  1. For any positive number \(N,\) here is a simple method for approximating the square root of \(N.\) Start by guessing/estimating some positive integer \(x\) near \(\sqrt{N}.\) Plugging \(x\) into the formula \[x_\star = \frac{1}{2}\left(x + \frac{N}{x}\right)\] 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 “next guess” formula that results would result from applying Newton’s method to approximate a solution of the equation \(x^2-N=0,\) hence justifying why this Babylonian method works.
    2. Write a computer program that iteratively applies this formula to calculate the square root of a number. Note: a TI-83/84+ calculators is programmable.
    3. Using this formula, write a recursive computer program that calculates the square root of a number accurate to the precision of the language’s analogue of the float data type.
    4. Come up with similar recursive formulas for the following operations:
      \(\displaystyle \sqrt[3]{x} \)
      \(\displaystyle \frac{1}{x} \)
  2. The equation \(\cos(x) = x\) has a single solution. We call it the Dottie Number.
    1. Demonstrate Newton’s method by calculating the Dottie number accurate to eight decimal places.
    2. Write a program that performs Newton’s Method, and use that program to calculate the Dottie number accurate to the precision of the language’s float data type. Note the TI-83/84+ series of calculators are programmable. Can your program calculate \(x\) to arbitrary precision?
    3. Put your calculator in radians mode. 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?
  3. In general, there is no explicit formula for the roots of polynomial of degree higher than four. However we can use Newton’s method to approximate the roots of any polynomial. Approximate the value of the single real root of this polynomial using Newton’s method. \[x^5 + 2x^4 + 3x^3 + 4x^2 + 5x +6\]
  4. The polynomial \(x^3-x\) has three roots: \(-1\) and \(0\) and \(1.\) Determine the set of all real numbers \(x\) such that Newton’s method will converge to \(1\) upon being initiated with guess \(x\).
  5. The arctangent function has a single root at zero. But, depending on the initial guess, Newton’s method might fail to hone in on this root, and will 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 guesses Newton’s method will converge to zero, and for which initial guesses Newton’s method will diverge.
  6. Sometimes Newton’s method fails to converge, but not because the successive approximations blow up towards infinity.
    1. Consider the polynomial \(x^3-2x+2.\) This polynomial has a root at \(x \approx -1.7693.\) However, applying Newton’s method, if we start with the initial guess at zero, the method will not converge to the root. Investigate why Newton’s method fails in this case. Are there any other initial guesses for which Newton’s method will fail to converge to the root?
    2. Similarly, investigate \(x^5-x-1\) with an initial guess of zero.

    3. To ascribe vocabulary to the phenomenon that the previous prompts demonstrate, certain initial guesses \(x_0\) may not lead to a sequence \(x_1, x_2, \dotsc\) that converges to the root of the function, but instead enter an orbit. The polynomial \(x^3-2x+2\) with initial guess \(x_0=0\) induces a \(2\)-orbit, The polynomial \(x^5-x-1\) with initial guess \(x_0=0\) induces and \(3\)-orbit.

      Given a positive integer \(n\) find an example of a polynomial that will induce an \(n\)-orbit for an initial guess of zero.