{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# \n", "\n", "# Zeros of functions\n", "\n", "Read about this topic here: [Solving for zeros with\n", "julia](http://mth229.github.io/zeros.html).\n", "\n", "These questions are related to the real zeros of a real-valued function\n", "$f$. That is, those values of $x$ with $f(x)=0$.\n", "\n", "Finding zeros of a polynomial (called “roots” when the function is a\n", "polynomial) is a familiar task that can be aided by a few key equations,\n", "such as the quadratic equation. However, in general, finding a zero of a\n", "function will require a numeric approach. The `Roots` package of `Julia`\n", "will provide some features. This is loaded when `MTH229` is:" ], "id": "ac9860de-1203-4b64-8b11-fd0b2d00881f" }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [ "using MTH229\n", "using Plots\n", "plotly()" ], "id": "2" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Graphically, a zero of a continuous function $f(x)$ occurs where the\n", "graph crosses or touches the $x$-axis. Without much work, a zero can be\n", "*estimated* to one or two decimal points from a graph. For example, we\n", "can zoom in on the zero of $f(x) = x^5 + x - 1$ by graphing over\n", "$[0,1]$:" ], "id": "2fe40bb2-b091-48b5-a5ff-5d36b0a30d67" }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "output_type": "display_data", "metadata": {}, "data": { "text/html": [ "" ] } } ], "source": [ "f(x) = x^5 + x - 1\n", "plot(f, 0, 1)\n", "plot!(zero, 0, 1)" ], "id": "6" }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can see that the zero is near $0.75$, but be careful reading too much\n", "into a graph. Since there are only so many pixels in a graph, and\n", "typically even fewer points chosen, what looks like a curve is really\n", "just a stick figure if you zoom in far enough. Replotting over a smaller\n", "domain can give more accuracy, but it is better to use a graph to get a\n", "sense of what the desired answer is *near* or *between* and then use a\n", "*numeric* method to “zoom” in on the answer. In this project we discuss\n", "one such method for “zooming in” – the *bisection method* - when the\n", "zero is between two values, such as in this plot where the zero is\n", "clearly between, say, $0$ and $1$.\n", "\n", "#### The bisection method\n", "\n", "The bisection method is a consequence on the *intermediate value\n", "theorem*:\n", "\n", "> The [intermediate value\n", "> theorem](https://en.wikipedia.org/wiki/Intermediate_value_theorem)\n", "> states that if a continuous function, $f$, over an interval, $[a, b]$,\n", "> takes values $f(a)$ and $f(b)$ at each end of the interval, then it\n", "> also takes any value between $f(a)$ and $f(b)$ at some point within\n", "> the interval.\n", "\n", "For our purposes, this is specialized to “Bolzano’s theorem:”\n", "\n", "> If a continuous function has values of opposite sign inside a closed\n", "> interval, then it has a zero in that interval\n", "\n", "In particular, if $f(x)$ is *continuous* on $[a,b]$ **and** $f(a)$ and\n", "$f(b)$ have different signs, then there **must** be a value $c$ with\n", "$a < c < b$ where $f(c) = 0$.\n", "\n", "There may be more than one zero, but there is a guarantee of at least\n", "one.\n", "\n", "## The bisection algorithm\n", "\n", "Not all functions can have their real zeros solved algebraically, and\n", "not all applications can be answered by the accuracy provided by a\n", "graph. In such situations, numeric methods may be of interest.\n", "\n", "To illustrate the bisection method, we discuss one step. This step is\n", "then repeated until termination.\n", "\n", "Consider $f(x) = \\sin(x)$. A graph shows plainly that there is a zero\n", "between $3$ and $4$. Formally, as $\\sin(3) > 0$ and $\\sin(4) < 0$ and\n", "the $\\sin(x)$ function is continuous, this zero is guaranteed by\n", "Bolzano. The algorithm works by taking this observation of a bracketing\n", "interval ($[3,4]$) and reducing it in size by half at each step.\n", "\n", "Let $[a,b] = [3,4]$ and $c = (a+b)/2 = 3.5$ be the mid-point. The value\n", "of $f(c)$ must either be negative, positive, or zero. If $f(c)$ is zero,\n", "we are done – a zero to $f$ between $[a,b]$ was identified. Otherwise,\n", "either $f(a)$ and $f(c)$ or $f(c)$ and $f(b)$ have different signs. Form\n", "a new interval $[a,c]$ in the first case and $[c,b]$ in the second. This\n", "interval is half the size and has the same property of bracketing the\n", "guaranteed zero. The algorithm iterates this step until termination.\n", "\n", "The `MTH229` package defines a `bisection` method implementing the\n", "bisection method, it assumes it has been passed values $a < b$ with\n", "$f(a)$ and $f(b)$ having different signs. In short, `[a,b]` is a\n", "bracketing interval for $f$.\n", "\n", "Running this demo illustrates the division:" ], "id": "7a008e33-770a-47c6-9a94-899ecbc6095f" }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [ "bisection(sin, 3, 4)" ], "id": "8" }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first line shows `[3,4]`, the second the resulting interval\n", "`[3, 3.5]`, the third the resulting interval `[3, 3.25]`, the fourth the\n", "resulting interval `[3.125, 3.25]`, etc.\n", "\n", "In the demo, after $8$ iterations, there isn’t enough resolution to show\n", "more subdivisions, but mathematically, unless the algorithm finds an\n", "exact zero, this process would continue infinitely, with the bracketing\n", "interval getting infinitely small. In the process this traps the zero.\n", "\n", "On the computer, the process basically stops when the size of the\n", "bracketing interval gets too small to subdivide using floating point\n", "numbers, unless instructed otherwise.\n", "\n", "## The fzero function\n", "\n", "In the `Roots` package is the `fzero` method that implements the\n", "bisection method, only a bit more carefully. The `MTH229` package loads\n", "this for you.\n", "\n", "For a bracketing interval, it is guaranteed to find a `c` such that the\n", "function changes sign between adjacent floating point values around `c`,\n", "or `c` is an exact zero. It is used as: `fzero(f, a, b)`:" ], "id": "cc19100e-0264-4a64-b69d-1770607807af" }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "output_type": "display_data", "metadata": {}, "data": { "text/plain": [ "1.4142135623730951" ] } } ], "source": [ "f(x) = x^2 - 2\n", "fzero(f, 1, 2) # finds sqrt(2)" ], "id": "10" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solving $f(x) = c$\n", "\n", "Suppose the job is to identify when the function\n", "$f(x) = e^x / (1 + e^x)$ is equal to $3/4$. That is solving\n", "$f(x) = 3/4$. Our tool solves $f(x) = 0$. To use it, we define\n", "$eqn(x) = f(x) - 3/4$. Then $eqn(x)$ is zero when $f(x)$ is $3/4$.\n", "\n", "The function $f(x)$ is *increasing* so we can be very lazy with finding\n", "a bracketing interval, as $eqn(0)$ will be negative and $eqn(100)$ very\n", "close to $1$ and by monotonicity there can only be one zero, we have:" ], "id": "d9af9081-b878-44ed-8487-6e11a59869d0" }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "output_type": "display_data", "metadata": {}, "data": { "text/plain": [ "1.0986122886681096" ] } } ], "source": [ "f(x) = exp(x) / (1 + exp(x))\n", "eqn(x) = f(x) - 3/4\n", "fzero(eqn, 0, 100)" ], "id": "12" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solving for $f(x) = g(x)$.\n", "\n", "Many problems are more naturally expressed by solving $f(x) = g(x)$, and\n", "not $f(x) = 0$, as expected by `fzero`. This is no issue, as it only\n", "requires the extra step of defining a function of the differences\n", "$eqn(x) = f(x) - g(x)$, as $u(x) = 0$ implies $f(x) = g(x)$.\n", "\n", "For example, find the intersection point of $4 - e^{x/10} = e^{x/15}$.\n", "\n", "First graph to see approximately where the answer is. From the graph,\n", "identify a bracket and then use `fzero` to numerically estimate the\n", "intersection point.\n", "\n", "We could plot both functions:" ], "id": "844ed54e-e46d-4b51-b6c1-05f086e8006f" }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "output_type": "display_data", "metadata": {}, "data": { "text/html": [ "" ] } } ], "source": [ "f(x) = 4 - exp(x/10)\n", "g(x) = exp(x/15)\n", "plot(f, 0, 20)\n", "plot!(g, 0, 20)" ], "id": "14" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Or we could plot the difference:" ], "id": "1a19fc0e-ed09-4248-a9e9-f02ecc2478de" }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "output_type": "display_data", "metadata": {}, "data": { "text/html": [ "" ] } } ], "source": [ "eqn(x) = f(x) - g(x)\n", "plot(eqn, 0, 20)\n", "plot!(zero, 0, 20)" ], "id": "16" }, { "cell_type": "markdown", "metadata": {}, "source": [ "From *either* graph, we see quickly that the interval $[5,10]$ will be a\n", "bracketing interval for $\\text{eqn}(x)$. We can numerically zoom in on\n", "the the intersection point with:" ], "id": "16cb5d47-7f03-49cc-a257-f6f463c751cb" }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "output_type": "display_data", "metadata": {}, "data": { "text/plain": [ "8.205886667065423" ] } } ], "source": [ "fzero(eqn, 5, 10)" ], "id": "18" }, { "cell_type": "markdown", "metadata": {}, "source": [ "------------------------------------------------------------------------" ], "id": "d260d934-c0ff-4164-84fc-7080c982e559" }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# your commands begin here\n", "\n" ], "id": "20" } ], "nbformat": 4, "nbformat_minor": 5, "metadata": { "kernel_info": { "name": "julia" }, "kernelspec": { "name": "julia", "display_name": "Julia", "language": "julia" }, "language_info": { "name": "julia", "codemirror_mode": "julia", "version": "1.10.0" } } }