bisection-method.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4f44ad1d-fb09-43c7-8ee5-0bbf5a5e71c5",
   "metadata": {},
   "source": [
    "# Bisection Method"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f90c5f35-b7b9-4c37-9f4f-793fcc4a68c5",
   "metadata": {},
   "source": [
    "- $f(x)$: The function (concave downwards in bounds)\n",
    "- $x'$: Current solution\n",
    "- $x^*$: Optimum value\n",
    "- $\\underline{x}$: Lower bound for $x$.\n",
    "- $\\bar{x}$: Upper bound for $x$.\n",
    "- $\\varepsilon$: Tolerance"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fc82273-718e-4a89-8397-b0f65ac84702",
   "metadata": {},
   "source": [
    "### The algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14c04b88-9962-4939-a292-5a39394b0ac9",
   "metadata": {},
   "source": [
    "- Step 0:\n",
    "- Set $\\varepsilon$, e.g., $\\varepsilon = 0.001$.\n",
    "- Set initial values for $\\underline{x}$ and $\\bar{x}$.\n",
    "- Set initial solution as"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa6e5ddd-abe9-4a88-ab3d-5057aa488358",
   "metadata": {},
   "source": [
    "$$\n",
    "x' = \\frac{\\underline{x} + \\bar{x}}{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91f3e575-30dd-40a0-8451-9709bd291e99",
   "metadata": {},
   "source": [
    "- Step n:\n",
    "- set $x' =  \\frac{\\underline{x} + \\bar{x}}{2}$\n",
    "- if $\\bar{x} - x' \\le 2 \\varepsilon$ then stop\n",
    "- Evaluate d = f'(x')\n",
    "- if $f'(x) \\ge 0$ then $\\underline{x} = x'$\n",
    "- otherwise $\\bar{x} = x'$\n",
    "- iterate Step n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e5d42587-3356-420f-b91d-bf02fbfc1454",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "f (generic function with 1 method)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(x) = -4x^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ca96f175-a9b6-43d1-9fe4-9b05f7ff179e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fderiv (generic function with 1 method)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fderiv(x) = -8x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "ea5e798d-8586-4639-b3d0-f4b9bd521725",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-6"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xlower = -6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "8b0932c4-ccb0-4738-8c41-a055fa5024ab",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xupper = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "01a030f6-0018-47f9-a7f0-034978ac76cd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0e-5"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "epsilon = 0.00001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "d8484cf3-227e-492a-8365-b7b872a21918",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "┌ Info: Results: \n",
      "│   xupper = 1.52587890625e-5\n",
      "│   xlower = -5.7220458984375e-6\n",
      "│   x = 4.76837158203125e-6\n",
      "│   i = 5\n",
      "└ @ Main In[23]:5\n"
     ]
    }
   ],
   "source": [
    "maxiter = 1000\n",
    "for i in 1:maxiter\n",
    "    x = (xupper + xlower) / 2.0\n",
    "    if (xupper - x) <= 2 * epsilon\n",
    "        @info \"Results: \" xupper xlower x i\n",
    "        break\n",
    "    end\n",
    "    fd = fderiv(x)\n",
    "    if fd >= 0\n",
    "        xlower = x\n",
    "    else\n",
    "        xupper = x\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ee28b8d-6047-4339-ab0d-a5f819fd6b9f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.7.1",
   "language": "julia",
   "name": "julia-1.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}