Closed root-finding methods#
The roots of general nonlinear functions are more complicated than linear functions. We can seldom solve for the roots directly (notable exception being polynomial functions), and instead will need to search for them iteratively.
Iterative search methods are characterized by their order of convergence, which measure how successive guesses approach the true root. Given the true root \(x\), we can check how successive guesses approach it by calculating the error:
\[ x^{i+1}-x \propto [x^{i}-x]^k \]
where \(k\) is the order.
Bracketting methods#
Bracketing methods exploits the fact that functions change sign across the roots of a 1-D function (a simple applicaiton of the intermediate value theorem). This does not work for certain cases (eg: \(1/x\)).
Bisection methods#
Bisection methods are essentially a binary search for the root. If \(f(x)\) is continuous between bounds \(a\) and \(b>a\) and \(f(a)\) and \(f(b)\) are opposite signs, there must be a point \(c\) where \(f(c)=0\).
The algorithm is:
Given brackets \(a\) and \(b\)
Calculate the midpoint \(c = (b-a)/2\).
If \(f(c) \approx 0\) or \(a \approx b\): exit.
If \(f(c)>0\): set \(a = c\)
If \(f(c)<0\): set \(b = c\)
repeat
Graphically this is:
from scipy.optimize import bisect
def f(x):
return x**2 - 2
print('Setting x tolerance: \n')
xtols = [1e-1, 1e-2, 1e-3, 1e-4, 1e-5]
for xtol in xtols:
print(bisect(f, 1, 2, maxiter = 100, xtol = xtol))
print('\nSetting relative tolerance \n', bisect(f, 1, 2, maxiter = 100, rtol = 1e-12))
Setting x tolerance:
1.4375
1.4140625
1.4150390625
1.41424560546875
1.4142074584960938
Setting relative tolerance
1.4142135623715149
The error of the Bisection Method generaly follows:
\[ x^{i+1}-x = \frac{1}{2} [x^{i}-x] \]
and therefore has a linear order of convergence (\(k=1\)).
Method of False Position (Regula falsi)#
Let’s use more information! In bisection we are only interested in \(f(a,b)\) switching signs, but it stands to reason the larger \(f(b)\) is compared to \(f(a)\), the further the root is from \(b\)!
The method of false position uses this information to determine the next candidate solution:
\[ c= b - f(b) \frac{b-a}{f(b)-f(a)} \]
The same algorithm as for bisection is then applied to replace either \(a\) or \(b\) with \(c\) so that the root remains bracketted.
import numpy as np
import matplotlib.pyplot as plt
def f(x):
return x**2 - 2
# Example values for a and b
a = 1
b = 2
# Calculate f(a) and f(b)
fa = f(a)
fb = f(b)
# Calculate the next candidate solution c using the method of false position
c = b - fb * (b - a) / (fb - fa)
fc = f(c)
# Generate x values for the plot
x = np.linspace(a - 0.5, b + 0.5, 100)
# Plot the function
plt.plot(x, f(x), label='f(x)')
# Plot the initial bracket
plt.plot([a, b, a, b], [fa, fb, 0, 0], 'o', label='Initial Bracket')
# Plot the new candidate solution c
plt.plot([c, c], [fc, 0], 'ro', label='New Candidate (c)')
# Plot the line connecting (a, f(a)) and (b, f(b))
plt.plot([a, b], [fa, fb], '--', color='gray', label='Linear interpolation')
# Add labels and legend
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title('Method of False Position (Regula falsi) - One Iteration')
plt.legend()
plt.grid(True)
plt.show()
Note that the line joining the brackets approximates the tangent of the curve.
The method of False Position has an order of convergence of 1.618 (the Golden Ratio!):
\[ x^{i+1}-x \propto [x^i-x]^{1.618} \]
This is considered superlinear and a good thing!
Summary of bracketting methods#
Bracketting methods are usually robust but slow to converge and generlization to N-D is not trivial.
Through incorporating the additional information of linear interpolation, the method of Flase Position achieves superlinear convergence.
But bracketting is complicated in N-D, so let’s try to remove it.
!pip install Mint-NM
from Mint_NM import RootFinderClosed
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from IPython.display import HTML, display
import ipywidgets as widgets
Collecting Mint-NM
Downloading mint_nm-0.1.27-py3-none-any.whl.metadata (726 bytes)
Requirement already satisfied: numpy in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (2.3.4)
Requirement already satisfied: matplotlib in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (3.10.7)
Requirement already satisfied: ipywidgets in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (8.1.7)
Requirement already satisfied: IPython in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (9.6.0)
Requirement already satisfied: pyppeteer in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (2.0.0)
Requirement already satisfied: nbconvert in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (7.16.6)
Requirement already satisfied: scipy in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (1.16.3)
Requirement already satisfied: plotly in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from Mint-NM) (6.3.1)
Requirement already satisfied: decorator in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (5.2.1)
Requirement already satisfied: ipython-pygments-lexers in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (1.1.1)
Requirement already satisfied: jedi>=0.16 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (0.19.2)
Requirement already satisfied: matplotlib-inline in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (0.2.1)
Requirement already satisfied: pexpect>4.3 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (4.9.0)
Requirement already satisfied: prompt_toolkit<3.1.0,>=3.0.41 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (3.0.52)
Requirement already satisfied: pygments>=2.4.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (2.19.2)
Requirement already satisfied: stack_data in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (0.6.3)
Requirement already satisfied: traitlets>=5.13.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (5.14.3)
Requirement already satisfied: typing_extensions>=4.6 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from IPython->Mint-NM) (4.15.0)
Requirement already satisfied: wcwidth in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from prompt_toolkit<3.1.0,>=3.0.41->IPython->Mint-NM) (0.2.14)
Requirement already satisfied: parso<0.9.0,>=0.8.4 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jedi>=0.16->IPython->Mint-NM) (0.8.5)
Requirement already satisfied: ptyprocess>=0.5 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pexpect>4.3->IPython->Mint-NM) (0.7.0)
Requirement already satisfied: comm>=0.1.3 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from ipywidgets->Mint-NM) (0.2.3)
Requirement already satisfied: widgetsnbextension~=4.0.14 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from ipywidgets->Mint-NM) (4.0.14)
Requirement already satisfied: jupyterlab_widgets~=3.0.15 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from ipywidgets->Mint-NM) (3.0.15)
Requirement already satisfied: contourpy>=1.0.1 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (1.3.3)
Requirement already satisfied: cycler>=0.10 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (0.12.1)
Requirement already satisfied: fonttools>=4.22.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (4.60.1)
Requirement already satisfied: kiwisolver>=1.3.1 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (1.4.9)
Requirement already satisfied: packaging>=20.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (25.0)
Requirement already satisfied: pillow>=8 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (12.0.0)
Requirement already satisfied: pyparsing>=3 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (3.2.5)
Requirement already satisfied: python-dateutil>=2.7 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from matplotlib->Mint-NM) (2.9.0.post0)
Requirement already satisfied: six>=1.5 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from python-dateutil>=2.7->matplotlib->Mint-NM) (1.17.0)
Requirement already satisfied: beautifulsoup4 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (4.14.2)
Requirement already satisfied: bleach!=5.0.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from bleach[css]!=5.0.0->nbconvert->Mint-NM) (6.3.0)
Requirement already satisfied: defusedxml in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (0.7.1)
Requirement already satisfied: jinja2>=3.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (3.1.6)
Requirement already satisfied: jupyter-core>=4.7 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (5.9.1)
Requirement already satisfied: jupyterlab-pygments in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (0.3.0)
Requirement already satisfied: markupsafe>=2.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (3.0.3)
Requirement already satisfied: mistune<4,>=2.0.3 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (3.1.4)
Requirement already satisfied: nbclient>=0.5.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (0.10.2)
Requirement already satisfied: nbformat>=5.7 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (5.10.4)
Requirement already satisfied: pandocfilters>=1.4.1 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbconvert->Mint-NM) (1.5.1)
Requirement already satisfied: webencodings in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from bleach!=5.0.0->bleach[css]!=5.0.0->nbconvert->Mint-NM) (0.5.1)
Requirement already satisfied: tinycss2<1.5,>=1.1.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from bleach[css]!=5.0.0->nbconvert->Mint-NM) (1.4.0)
Requirement already satisfied: platformdirs>=2.5 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jupyter-core>=4.7->nbconvert->Mint-NM) (4.5.0)
Requirement already satisfied: jupyter-client>=6.1.12 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbclient>=0.5.0->nbconvert->Mint-NM) (8.6.3)
Requirement already satisfied: pyzmq>=23.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jupyter-client>=6.1.12->nbclient>=0.5.0->nbconvert->Mint-NM) (27.1.0)
Requirement already satisfied: tornado>=6.2 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jupyter-client>=6.1.12->nbclient>=0.5.0->nbconvert->Mint-NM) (6.5.2)
Requirement already satisfied: fastjsonschema>=2.15 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbformat>=5.7->nbconvert->Mint-NM) (2.21.2)
Requirement already satisfied: jsonschema>=2.6 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from nbformat>=5.7->nbconvert->Mint-NM) (4.25.1)
Requirement already satisfied: attrs>=22.2.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jsonschema>=2.6->nbformat>=5.7->nbconvert->Mint-NM) (25.4.0)
Requirement already satisfied: jsonschema-specifications>=2023.03.6 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jsonschema>=2.6->nbformat>=5.7->nbconvert->Mint-NM) (2025.9.1)
Requirement already satisfied: referencing>=0.28.4 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jsonschema>=2.6->nbformat>=5.7->nbconvert->Mint-NM) (0.37.0)
Requirement already satisfied: rpds-py>=0.7.1 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from jsonschema>=2.6->nbformat>=5.7->nbconvert->Mint-NM) (0.28.0)
Requirement already satisfied: soupsieve>1.2 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from beautifulsoup4->nbconvert->Mint-NM) (2.8)
Requirement already satisfied: narwhals>=1.15.1 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from plotly->Mint-NM) (2.10.0)
Requirement already satisfied: appdirs<2.0.0,>=1.4.3 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pyppeteer->Mint-NM) (1.4.4)
Requirement already satisfied: certifi>=2023 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pyppeteer->Mint-NM) (2025.10.5)
Requirement already satisfied: importlib-metadata>=1.4 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pyppeteer->Mint-NM) (8.7.0)
Collecting pyee<12.0.0,>=11.0.0 (from pyppeteer->Mint-NM)
Using cached pyee-11.1.1-py3-none-any.whl.metadata (2.8 kB)
Requirement already satisfied: tqdm<5.0.0,>=4.42.1 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pyppeteer->Mint-NM) (4.67.1)
Requirement already satisfied: urllib3<2.0.0,>=1.25.8 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pyppeteer->Mint-NM) (1.26.20)
Requirement already satisfied: websockets<11.0,>=10.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pyppeteer->Mint-NM) (10.4)
Requirement already satisfied: zipp>=3.20 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from importlib-metadata>=1.4->pyppeteer->Mint-NM) (3.23.0)
Requirement already satisfied: executing>=1.2.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from stack_data->IPython->Mint-NM) (2.2.1)
Requirement already satisfied: asttokens>=2.1.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from stack_data->IPython->Mint-NM) (3.0.0)
Requirement already satisfied: pure-eval in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from stack_data->IPython->Mint-NM) (0.2.3)
Downloading mint_nm-0.1.27-py3-none-any.whl (9.4 kB)
Using cached pyee-11.1.1-py3-none-any.whl (15 kB)
Installing collected packages: pyee, Mint-NM
?25l
Attempting uninstall: pyee
Found existing installation: pyee 13.0.0
Uninstalling pyee-13.0.0:
Successfully uninstalled pyee-13.0.0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 2/2 [Mint-NM]
?25h
ERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.
playwright 1.55.0 requires pyee<14,>=13, but you have pyee 11.1.1 which is incompatible.
Successfully installed Mint-NM-0.1.27 pyee-11.1.1
[notice] A new release of pip is available: 25.2 -> 25.3
[notice] To update, run: pip install --upgrade pip
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
Cell In[3], line 2
1 get_ipython().system('pip install Mint-NM')
----> 2 from Mint_NM import RootFinderClosed
3 import numpy as np
4 import matplotlib.pyplot as plt
File /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages/Mint_NM/__init__.py:1
----> 1 from .neuralnet_module import init_weights, tanh, tanh_derivative, forward, compute_loss, backward, plot_nn_diagram, init_model, forward_pass, backward_pass, step, reset_model, save_function, change_depth, change_width, draw_network, update_plots
2 from .openrootfinder_module import RootFinderOpen
3 from .closedrootfinder_module import RootFinderClosed
File /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages/Mint_NM/neuralnet_module.py:9
7 import numpy as np
8 import matplotlib.pyplot as plt
----> 9 import networkx as nx
10 from ipywidgets import VBox, HBox, Button, Text, Label, Output
11 from IPython.display import display, clear_output
ModuleNotFoundError: No module named 'networkx'
def f(x):
return np.cos(x) - x
rf = RootFinderClosed(f, a=0, b=1, tol=1e-6, max_iter=20)
rf.show_toggle_closed()
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
Cell In[4], line 4
1 def f(x):
2 return np.cos(x) - x
----> 4 rf = RootFinderClosed(f, a=0, b=1, tol=1e-6, max_iter=20)
5 rf.show_toggle_closed()
NameError: name 'RootFinderClosed' is not defined