{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Newton’s method and nonlinear equations\n", "\n", "In first-year calculus, most students learn [Newton’s method](https://en.wikipedia.org/wiki/Newton's_method) for solving nonlinear equations $f(x) = 0$, which iteratively improves a sequence of guesses for the solution $x$ by **approximating f by a straight line**. That is, it **approximates a *nonlinear* equation by a sequence of approximate *linear* equations**.\n", "\n", "This can be extended to *systems* of nonlinear equations as a **multidimensional Newton** method, in which we iterate by solving a sequence of linear (*matrix*) systems of equations. This is one example of an amazing fact: **linear algebra is a fundamental tool even for solving nonlinear equations**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Packages for this notebook" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/html": [ " \n" ], "text/plain": [ "HTML{String}(\" \\n\")" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/plain": [ "HTML{String}(\"\")" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "" ], "text/plain": [ "HTML{String}(\"\")" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ " \n" ], "text/plain": [ "HTML{String}(\" \\n\")" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Pkg.add.([\"Interact\", \"PyPlot\", \"ForwardDiff\"]) # uncomment this line to install packages\n", "using Interact, PyPlot" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## One-dimensional Newton\n", "\n", "The standard one-dimensional Newton’s method proceeds as follows. Suppose we are solving for a zero (root) of $f(x)$:\n", "\n", "$$\n", "f(x) = 0\n", "$$\n", "\n", "for an arbitrary (but differentiable) function $f$, and we have a guess $x$. We find an *improved* guess $x+\\delta$ by [Taylor expanding](https://en.wikipedia.org/wiki/Taylor_series) $f(x+\\delta)$ around $x$ to *first order* (linear!) in $\\delta$, and finding the . (This should be accurate if $x$ is *close enough* to a solution, so that the $\\delta$ is *small*.) That is, we solve:\n", "\n", "$$\n", "f(x + \\delta) \\approx f(x) + f'(x) \\delta = 0\n", "$$\n", "\n", "to obtain $\\delta = -f(x) / f'(x)$. Plugging this into $x+\\delta$, we obtain:\n", "\n", "$$\n", "\\boxed{\\mbox{new } x = x - f(x)/f'(x)}.\n", "$$\n", "\n", "This is called a **Newton step**. Then we simply repeat the process.\n", "\n", "Let's visualize this process for finding a root of $f(x) = 2\\cos(x) - x + x^2/10$ (a [transcendental equation](https://en.wikipedia.org/wiki/Transcendental_equation) that has no closed-form solution)." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "