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
Defaulting to user installation because normal site-packages is not writeable
Requirement already satisfied: Mint-NM in /home/runner/.local/lib/python3.12/site-packages (0.1.28)
Requirement already satisfied: numpy in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (2.3.5)
Requirement already satisfied: matplotlib in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (3.10.7)
Requirement already satisfied: networkx in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (3.6)
Requirement already satisfied: ipywidgets in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (8.1.8)
Requirement already satisfied: IPython in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (9.8.0)
Requirement already satisfied: pyppeteer in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (2.0.0)
Requirement already satisfied: nbconvert in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (7.16.6)
Requirement already satisfied: scipy in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (1.16.3)
Requirement already satisfied: plotly in /home/runner/.local/lib/python3.12/site-packages (from Mint-NM) (6.5.0)
Requirement already satisfied: decorator>=4.3.2 in /home/runner/.local/lib/python3.12/site-packages (from IPython->Mint-NM) (5.2.1)
Requirement already satisfied: ipython-pygments-lexers>=1.0.0 in /home/runner/.local/lib/python3.12/site-packages (from IPython->Mint-NM) (1.1.1)
Requirement already satisfied: jedi>=0.18.1 in /home/runner/.local/lib/python3.12/site-packages (from IPython->Mint-NM) (0.19.2)
Requirement already satisfied: matplotlib-inline>=0.1.5 in /home/runner/.local/lib/python3.12/site-packages (from IPython->Mint-NM) (0.2.1)
Requirement already satisfied: pexpect>4.3 in /usr/lib/python3/dist-packages (from IPython->Mint-NM) (4.9.0)
Requirement already satisfied: prompt_toolkit<3.1.0,>=3.0.41 in /home/runner/.local/lib/python3.12/site-packages (from IPython->Mint-NM) (3.0.52)
Requirement already satisfied: pygments>=2.11.0 in /usr/lib/python3/dist-packages (from IPython->Mint-NM) (2.17.2)
Requirement already satisfied: stack_data>=0.6.0 in /home/runner/.local/lib/python3.12/site-packages (from IPython->Mint-NM) (0.6.3)
Requirement already satisfied: traitlets>=5.13.0 in /home/runner/.local/lib/python3.12/site-packages (from IPython->Mint-NM) (5.14.3)
Requirement already satisfied: wcwidth in /home/runner/.local/lib/python3.12/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 /home/runner/.local/lib/python3.12/site-packages (from jedi>=0.18.1->IPython->Mint-NM) (0.8.5)
Requirement already satisfied: executing>=1.2.0 in /home/runner/.local/lib/python3.12/site-packages (from stack_data>=0.6.0->IPython->Mint-NM) (2.2.1)
Requirement already satisfied: asttokens>=2.1.0 in /home/runner/.local/lib/python3.12/site-packages (from stack_data>=0.6.0->IPython->Mint-NM) (3.0.1)
Requirement already satisfied: pure-eval in /home/runner/.local/lib/python3.12/site-packages (from stack_data>=0.6.0->IPython->Mint-NM) (0.2.3)
Requirement already satisfied: comm>=0.1.3 in /home/runner/.local/lib/python3.12/site-packages (from ipywidgets->Mint-NM) (0.2.3)
Requirement already satisfied: widgetsnbextension~=4.0.14 in /home/runner/.local/lib/python3.12/site-packages (from ipywidgets->Mint-NM) (4.0.15)
Requirement already satisfied: jupyterlab_widgets~=3.0.15 in /home/runner/.local/lib/python3.12/site-packages (from ipywidgets->Mint-NM) (3.0.16)
Requirement already satisfied: contourpy>=1.0.1 in /home/runner/.local/lib/python3.12/site-packages (from matplotlib->Mint-NM) (1.3.3)
Requirement already satisfied: cycler>=0.10 in /home/runner/.local/lib/python3.12/site-packages (from matplotlib->Mint-NM) (0.12.1)
Requirement already satisfied: fonttools>=4.22.0 in /home/runner/.local/lib/python3.12/site-packages (from matplotlib->Mint-NM) (4.61.0)
Requirement already satisfied: kiwisolver>=1.3.1 in /home/runner/.local/lib/python3.12/site-packages (from matplotlib->Mint-NM) (1.4.9)
Requirement already satisfied: packaging>=20.0 in /usr/lib/python3/dist-packages (from matplotlib->Mint-NM) (24.0)
Requirement already satisfied: pillow>=8 in /home/runner/.local/lib/python3.12/site-packages (from matplotlib->Mint-NM) (12.0.0)
Requirement already satisfied: pyparsing>=3 in /usr/lib/python3/dist-packages (from matplotlib->Mint-NM) (3.1.1)
Requirement already satisfied: python-dateutil>=2.7 in /usr/lib/python3/dist-packages (from matplotlib->Mint-NM) (2.8.2)
Requirement already satisfied: beautifulsoup4 in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (4.14.3)
Requirement already satisfied: bleach!=5.0.0 in /home/runner/.local/lib/python3.12/site-packages (from bleach[css]!=5.0.0->nbconvert->Mint-NM) (6.3.0)
Requirement already satisfied: defusedxml in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (0.7.1)
Requirement already satisfied: jinja2>=3.0 in /usr/lib/python3/dist-packages (from nbconvert->Mint-NM) (3.1.2)
Requirement already satisfied: jupyter-core>=4.7 in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (5.9.1)
Requirement already satisfied: jupyterlab-pygments in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (0.3.0)
Requirement already satisfied: markupsafe>=2.0 in /usr/lib/python3/dist-packages (from nbconvert->Mint-NM) (2.1.5)
Requirement already satisfied: mistune<4,>=2.0.3 in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (3.1.4)
Requirement already satisfied: nbclient>=0.5.0 in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (0.10.2)
Requirement already satisfied: nbformat>=5.7 in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (5.10.4)
Requirement already satisfied: pandocfilters>=1.4.1 in /home/runner/.local/lib/python3.12/site-packages (from nbconvert->Mint-NM) (1.5.1)
Requirement already satisfied: webencodings in /home/runner/.local/lib/python3.12/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 /home/runner/.local/lib/python3.12/site-packages (from bleach[css]!=5.0.0->nbconvert->Mint-NM) (1.4.0)
Requirement already satisfied: platformdirs>=2.5 in /usr/local/lib/python3.12/dist-packages (from jupyter-core>=4.7->nbconvert->Mint-NM) (4.5.0)
Requirement already satisfied: jupyter-client>=6.1.12 in /home/runner/.local/lib/python3.12/site-packages (from nbclient>=0.5.0->nbconvert->Mint-NM) (8.6.3)
Requirement already satisfied: pyzmq>=23.0 in /home/runner/.local/lib/python3.12/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 /home/runner/.local/lib/python3.12/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 /home/runner/.local/lib/python3.12/site-packages (from nbformat>=5.7->nbconvert->Mint-NM) (2.21.2)
Requirement already satisfied: jsonschema>=2.6 in /usr/lib/python3/dist-packages (from nbformat>=5.7->nbconvert->Mint-NM) (4.10.3)
Requirement already satisfied: attrs>=17.4.0 in /usr/lib/python3/dist-packages (from jsonschema>=2.6->nbformat>=5.7->nbconvert->Mint-NM) (23.2.0)
Requirement already satisfied: pyrsistent!=0.17.0,!=0.17.1,!=0.17.2,>=0.14.0 in /usr/lib/python3/dist-packages (from jsonschema>=2.6->nbformat>=5.7->nbconvert->Mint-NM) (0.20.0)
Requirement already satisfied: soupsieve>=1.6.1 in /home/runner/.local/lib/python3.12/site-packages (from beautifulsoup4->nbconvert->Mint-NM) (2.8)
Requirement already satisfied: typing-extensions>=4.0.0 in /usr/lib/python3/dist-packages (from beautifulsoup4->nbconvert->Mint-NM) (4.10.0)
Requirement already satisfied: narwhals>=1.15.1 in /home/runner/.local/lib/python3.12/site-packages (from plotly->Mint-NM) (2.13.0)
Requirement already satisfied: appdirs<2.0.0,>=1.4.3 in /home/runner/.local/lib/python3.12/site-packages (from pyppeteer->Mint-NM) (1.4.4)
Requirement already satisfied: certifi>=2023 in /usr/lib/python3/dist-packages (from pyppeteer->Mint-NM) (2023.11.17)
Requirement already satisfied: importlib-metadata>=1.4 in /home/runner/.local/lib/python3.12/site-packages (from pyppeteer->Mint-NM) (8.7.0)
Requirement already satisfied: pyee<12.0.0,>=11.0.0 in /home/runner/.local/lib/python3.12/site-packages (from pyppeteer->Mint-NM) (11.1.1)
Requirement already satisfied: tqdm<5.0.0,>=4.42.1 in /home/runner/.local/lib/python3.12/site-packages (from pyppeteer->Mint-NM) (4.67.1)
Requirement already satisfied: urllib3<2.0.0,>=1.25.8 in /home/runner/.local/lib/python3.12/site-packages (from pyppeteer->Mint-NM) (1.26.20)
Requirement already satisfied: websockets<11.0,>=10.0 in /home/runner/.local/lib/python3.12/site-packages (from pyppeteer->Mint-NM) (10.4)
Requirement already satisfied: zipp>=3.20 in /home/runner/.local/lib/python3.12/site-packages (from importlib-metadata>=1.4->pyppeteer->Mint-NM) (3.23.0)
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()