Appendix J — Homework: Root finding

Submit this homework via Dropbox. For the deadline please consult the schedule posted on Blackboard.

  • Python-scripts are submitted in one file called: homework9.py

J.1 Exercise 1

Use the Newton-Raphson method from the lecture and calculate the roots of the following functions. Please use the Newton-Raphson method that we programmed ourselves, not the built in one from the scipy.optimize library. I want to see whether you are able to correctly program a function as an input argument and then "handle" this function input inside of your algorithm.

Then check your answers using the bisection method.

  1. \(log(x) - exp(-x)\) using \(x_0 = 2\)
  2. \(x^3 - x - 3\) using \(x_0 = 0\)
  3. \(x^3 - 7x^2 + 14x - 8\) using \(x_0 = 1.1, 1.2, . . . , 1.9\)
  4. \(log(x) \times exp(-x)\) using \(x_0 = 2\)

J.2 Exercise 2

The bisection method can be generalized to deal with the case f(xl)f(xr) > 0, by broadening the bracket. That is, we reduce xl and/or increase xr , and try again. A reasonable choice for broadening the bracket is to double the width of the interval [xl,xr], that is (in pseudo-code):

m = (xl + xr )/2
w = xr - xl
xl = m - w
xr = m + w

Incorporate bracket broadening into the function bisection given in the lecture. Note that broadening is not guaranteed to find xl and xr such that f(xl)f(xr)<= 0, so you should include a limit on the number of times it can be tried.

Now use your modified bisection function to find a root of

\[f(x) = (x - 1)^3 - 2x^2 + 10 - sin(x),\]

starting with xl = 1 and xr = 2.

J.3 Bonus: Exercise 3

How do we know \(\pi = 3.1415926\) (to 7 decimal places)? One way of finding \(\pi\) is to solve \(sin(x) = 0.\) By definition the solutions to \(sin(x) = 0\) are \(k \times \pi\) for \(k = 0, \pm 1, \pm 2, \dots\), so the root closest to 3 should be \(\pi\).

  1. Use a root-finding algorithm, such as the Newton-Raphson algorithm, to find the root of sin(x) near 3.

  2. How close can you get to \(\pi\)? (You may use the function \(sin(x)\) provided by Python.)

  3. The function sin(x) is transcendental, which means that it cannot be written as a rational function of x. Instead we have to write it as an infinite sum:

    \[sin(x) = \sum_{k=0}^{\infty} {(-1)^k \frac{x^{2k+1}}{(2k + 1)!}}\]

    This is the infinite order Taylor expansion of sin(x) about 0. In practice, to calculate \(sin(x)\) numerically we have to truncate this sum, so any numerical calculation of \(sin(x)\) is an approximation. In particular the function sin(x) provided by Python is only an approximation of sin(x) (though a very good one).

    Define the following function in Python (use def):

    \[f_n(x)= \sum_{k=0}^{n}{(-1)^k \frac{x^{2k+1}}{(2k + 1)!}}\]

    (Hint: in order to form this sum you should use a loop over n iterations. You do not need to program the factorial, just use m.factorial())

    Then plot \(f_n(x)\) over the range \([0, 7]\) three times. The first time choose n=7, the second time choose n=8 and for the third time choose n=9. Do you see a difference in the sine functions in your plots as you increase the n. Just plot all three functions into the same figure then any differences should be obvious. For large n your plot should look like the wavy plot of s sin() function.

    Warning

    Don't pick n larger than 20 or so. The factorials will explode pretty quickly.

  4. Choose a large value of n and solve \(f_n(x) = 0\) near 3. Can you get an approximation of the number \(\pi\) that is correct up to 6 decimal places?