32  Newton’s method

Newton’s method replaces a nonlinear system by its first-order Taylor approximation at each iteration.

In the next exercise, we derive the Newton–Raphson method for root finding.

Let \(f : \Omega \subset \mathbb{R}^n \to \mathbb{R}^n\) be a function of class \(C^2\). We seek \(\mathbf{x}\in\Omega\) such that \(f(\mathbf{x})=0\).

Assume we have an initial guess \(\mathbf{x}_0\in\Omega\).

Exercises

Exercise 32.1 Explain why the following polynomial is a good approximation to \(f(\mathbf{x})\) near \(\mathbf{x}_0\): \[p(\mathbf{x}) = f(\mathbf{x}_0) + J(\mathbf{x}-\mathbf{x}_0), \quad J = Df(\mathbf{x}_0).\]

Exercise 32.2 Newton’s method now finds a new guess \(\mathbf{x}_1\) by finding the root of the Taylor polynomial, i.e., \(p(\mathbf{x}_1) = 0\). Write down a formula for \(\mathbf{x}_1\), assuming that the matrix \(J\) has an inverse.

Exercise 32.3 Suppose the true solution is \(\mathbf{x}_* \in \Omega\), and assume that the error in \(\mathbf{x}_0\) is sufficiently small. Find an estimate for the error of \(\mathbf{x}_1\). Assuming that the error can be converted to significant digits \(n\), what is the number of significant digits in \(\mathbf{x}_1\)? Hint: Look at the remainder term.

Exercise 32.4 Suppose successive iterations are performed. How many digits do you have after \(k\) iterations?

Exercise 32.5 Make a Python implementation of Newton’s method and test it on the following function: \[f(x,y) = (e^x y^3 - 1, y^2 - \sin(x) - 1).\] It can be an idea to try and visualize the function. Two roots are: \[\{ (4.38277027, 0.23202192), \; (0,1) \}\] Try different initial guesses \(\mathbf{x}_0\), close to the roots and further away. How many iterations do you need to achieve machine precision for your guesses? Can you find more roots?