{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Bisection method"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We first import the modules and functions that we need."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"%matplotlib inline\n",
"%config InlineBackend.figure_format = 'svg'\n",
"from numpy import exp,sin,linspace,sign,abs\n",
"from matplotlib.pyplot import plot,grid,xlabel,ylabel"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First we define the function for which the root is required."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"def fun(x):\n",
" #f = x**2 - 4*x*sin(x) + (2*sin(x))**2\n",
" f = exp(x) - sin(x)\n",
" return f"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us plot and visualize the function."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"x = linspace(-4,-2,100)\n",
"f = fun(x)\n",
"plot(x,f,'r-')\n",
"grid(True)\n",
"xlabel('x')\n",
"ylabel('f');"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"From the figure, we see that $[-4,-2]$ is a bracketing interval. We now implement the bisection method."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1 -3.00000000e+00 1.00000000e+00 1.90907076e-01\n",
" 2 -3.50000000e+00 5.00000000e-01 3.20585844e-01\n",
" 3 -3.25000000e+00 2.50000000e-01 6.94209267e-02\n",
" 4 -3.12500000e+00 1.25000000e-01 6.05288259e-02\n",
" 5 -3.18750000e+00 6.25000000e-02 4.61629389e-03\n",
" 6 -3.15625000e+00 3.12500000e-02 2.79283147e-02\n",
" 7 -3.17187500e+00 1.56250000e-02 1.16471966e-02\n",
" 8 -3.17968750e+00 7.81250000e-03 3.51301957e-03\n",
" 9 -3.18359375e+00 3.90625000e-03 5.52273640e-04\n",
" 10 -3.18164062e+00 1.95312500e-03 1.48021741e-03\n",
" 11 -3.18261719e+00 9.76562500e-04 4.63932552e-04\n",
"Function value is below tolerance\n",
"\n"
]
}
],
"source": [
"# Initial interval [a,b]\n",
"a, b = -4.0, -2.0\n",
"\n",
"N = 100 # Maximum number of iterations\n",
"eps = 1.0e-4 # Tolerance on the interval\n",
"delta = 1.0e-4 # Tolerance on the function\n",
"\n",
"fa, fb = fun(a), fun(b)\n",
"sa, sb = sign(fa), sign(fb)\n",
"\n",
"for i in range(N):\n",
" e = b-a\n",
" c = a + 0.5*e\n",
" if abs(e) < eps*abs(c):\n",
" print(\"Interval size is below tolerance\\n\")\n",
" break\n",
" fc = fun(c)\n",
" if abs(fc) < delta:\n",
" print(\"Function value is below tolerance\\n\")\n",
" break\n",
" sc = sign(fc)\n",
" if sa != sc:\n",
" b = c\n",
" fb = fc\n",
" sb = sc\n",
" else:\n",
" a = c\n",
" fa = fc\n",
" sa = sc\n",
" print(\"%5d %16.8e %16.8e %16.8e\"%(i+1,c,abs(b-a),abs(fc)))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.6"
}
},
"nbformat": 4,
"nbformat_minor": 1
}