Open methods#
Another class of root finding algorithms does not require bracketting, and is therefore deemed open. This alleviates the issue of N-D dimensionalization at the expense of robustness. They are usually faster than bracketting methods since we are not constantly updating the brackets, but our method is now succeptible to divergence which encroaches on the concept of a well behaved function.
Secant method#
Let’s reconsider the method of False Position but now we always disregard bracket updating and simply take \(c\) as our new guess. Our algorithm is now:
Take 2 initial guesses: \(x^i\)
Calculate the next guess:
\[x^{i+1} = {x^i} - f(x^{i}) \frac{x^i-x^{i-1}}{f(x^i)-f(x^{i-1})} \]
Check if tolerance is met
(Which tolerance?)
import numpy as np
import matplotlib.pyplot as plt
def f(x):
return x**2 - 2
def secant_method(f, x0, x1, tolerance=1e-6, max_iterations=100):
"""
Finds the root of a function using the secant method.
Args:
f: The function to find the root of.
x0: The initial guess.
x1: The second initial guess.
tolerance: The desired tolerance for the root.
max_iterations: The maximum number of iterations.
Returns:
The approximate root of the function.
"""
print(f"Iteration 0: x = {x1}")
x_values = [x0, x1]
for i in range(max_iterations):
x_new = x1 - f(x1) * (x1 - x0) / (f(x1) - f(x0))
x_values.append(x_new)
print(f"Iteration {i+1}: x = {x_new}")
if abs(f(x_new)) < tolerance:
return x_new, x_values
x0 = x1
x1 = x_new
return None, x_values
# Initial guesses
x0 = 1
x1 = 2
# Find the root using the secant method
root, x_values = secant_method(f, x0, x1)
if root:
print("Approximate root:", root)
plt.plot(root, 0, 'go', label='Approximate root')
else:
print("Secant method did not converge within the maximum number of iterations.")
error = abs(np.array(x_values)-root)
print("\nThe sequence of errors is:")
for i,e in enumerate(error):
print('Iteration, ', i, ' error in x is ', e)
# Plot the function and the secant method iterations
x = np.linspace(.9, 2.1, 100)
plt.plot(x, f(x), label='f(x)')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title('Secant Method')
plt.grid(True)
# Plot the initial guesses
plt.plot([x0, x1], [f(x0), f(x1)], 'o', label='Initial guesses')
# Plot each iteration of the secant method
for i in range(len(x_values) - 1):
plt.plot([x_values[i], x_values[i+1]], [f(x_values[i]), f(x_values[i+1])], '--', color='gray')
plt.plot(x_values[i+1], 0, 'ro', label=f'x_{i+2}' if i < 2 else None)
plt.legend()
plt.show()
Iteration 0: x = 2
Iteration 1: x = 1.3333333333333335
Iteration 2: x = 1.4000000000000001
Iteration 3: x = 1.4146341463414633
Iteration 4: x = 1.41421143847487
Iteration 5: x = 1.4142135620573204
Approximate root: 1.4142135620573204
The sequence of errors is:
Iteration, 0 error in x is 0.4142135620573204
Iteration, 1 error in x is 0.5857864379426796
Iteration, 2 error in x is 0.08088022872398692
Iteration, 3 error in x is 0.014213562057320273
Iteration, 4 error in x is 0.00042058428414293303
Iteration, 5 error in x is 2.12358245033073e-06
Iteration, 6 error in x is 0.0
The Secant method maintains superlinear convergence … but we can do better with a little more information…
The Newton-Raphson method#
Take another look at the fraction in the Secant method update equation:
\[x^{i+1} = {x^i} - f(x^{i}) \frac{x^i-x^{i-1}}{f(x^i)-f(x^{i-1})} \]
This is an (inverse) approximation of \(\frac{\partial f}{\partial x}\), the derivative of \(f\)! Typically, we are able to find this quantity, and the algorithm becomes:
\[ x^{i+1} = {x^i} - \frac{f(x^{i})}{f'(x^i)} \]
or, solving for the increment \(\Delta x = x^{i+1}-x^i\) and dropping the indicies,
\[\begin{split} \begin{align}
\Delta x &= - \frac{f(x)}{f'(x)} \\
f'(x) \Delta x &= - f(x)
\end{align} \end{split}\]
import numpy as np
import matplotlib.pyplot as plt
def f(x):
return x**2 - 2
def df(x):
return 2*x
def newton_raphson(f, df, x0, tolerance=1e-6, max_iterations=100):
"""
Finds the root of a function using the Newton-Raphson method.
Args:
f: The function to find the root of.
df: The derivative of the function.
x0: The initial guess.
tolerance: The desired tolerance for the root.
max_iterations: The maximum number of iterations.
Returns:
The approximate root of the function.
"""
x_values = [x0]
print(f"Iteration 0: x = {x0}")
for i in range(max_iterations):
x_new = x0 - f(x0) / df(x0)
x_values.append(x_new)
print(f"Iteration {i+1}: x = {x_new}")
if abs(f(x_new)) < tolerance:
return x_new, x_values
x0 = x_new
return None, x_values
# Initial guess
x0 = 1
# Find the root using the Newton-Raphson method
root, x_values = newton_raphson(f, df, x0)
if root:
print("Approximate root:", root)
plt.plot(root, 0, 'go', label='Approximate root')
else:
print("Newton-Raphson method did not converge within the maximum number of iterations.")
error = abs(np.array(x_values)-root)
print("\nThe sequence of errors is:")
for i,e in enumerate(error):
print('Iteration, ', i, ' error in x is ', e)
# Plot the function and the Newton-Raphson method iterations
x = np.linspace(.9, 2.1, 100)
plt.plot(x, f(x), label='f(x)')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title('Newton-Raphson Method')
plt.grid(True)
# Plot the initial guess
plt.plot([x0], [f(x0)], 'o', label='Initial guess')
# Plot each iteration of the Newton-Raphson method
for i in range(len(x_values) - 1):
plt.plot([x_values[i], x_values[i+1]], [f(x_values[i]), f(x_values[i+1])], '--', color='gray')
plt.plot(x_values[i+1], 0, 'ro', label=f'x_{i+2}' if i < 2 else None)
plt.legend()
plt.show()
Iteration 0: x = 1
Iteration 1: x = 1.5
Iteration 2: x = 1.4166666666666667
Iteration 3: x = 1.4142156862745099
Iteration 4: x = 1.4142135623746899
Approximate root: 1.4142135623746899
The sequence of errors is:
Iteration, 0 error in x is 0.41421356237468987
Iteration, 1 error in x is 0.08578643762531013
Iteration, 2 error in x is 0.002453104291976871
Iteration, 3 error in x is 2.123899820016817e-06
Iteration, 4 error in x is 0.0
The Newton-Raphson method has quadratic convergence (\(k=2\)) near the root which is a great result! It does so, however at the cost of calculating the Jacobian and solving a linear system.
!pip install Mint-NM
from Mint_NM import RootFinderOpen
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from IPython.display import HTML, display
import ipywidgets as widgets
Requirement already satisfied: Mint-NM in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (0.1.27)
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)
Requirement already satisfied: pyee<12.0.0,>=11.0.0 in /opt/hostedtoolcache/Python/3.11.13/x64/lib/python3.11/site-packages (from pyppeteer->Mint-NM) (11.1.1)
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)
[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 RootFinderOpen
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'
# User Inputs Below:
# Function and derivative
f = lambda x: x**3 -27
fprime = lambda x: 3*x**2
# Initial Guess(es) and Specifications
x0 = 27.0
x1 = 25.0
tol = 1e-6
max_iter = 20
solver = RootFinderOpen(f=f, fprime=fprime, x0=x0, x1=x1, tol=tol, max_iter=max_iter)
solver.show_toggle_open(interval_ms=750)
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
Cell In[4], line 13
10 tol = 1e-6
11 max_iter = 20
---> 13 solver = RootFinderOpen(f=f, fprime=fprime, x0=x0, x1=x1, tol=tol, max_iter=max_iter)
14 solver.show_toggle_open(interval_ms=750)
NameError: name 'RootFinderOpen' is not defined
# Function and derivative
f = lambda x: x**2 + 2
fprime = lambda x: 2*x
# Initial Guess(es) and Specifications
x0 = 5.0
x1 = 1.0
tol = 1e-6
max_iter = 15
solver = RootFinderOpen(f=f, fprime=fprime, x0=x0, x1=x1, tol=tol, max_iter=max_iter)
solver.show_toggle_open(interval_ms=750)
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
Cell In[5], line 11
8 tol = 1e-6
9 max_iter = 15
---> 11 solver = RootFinderOpen(f=f, fprime=fprime, x0=x0, x1=x1, tol=tol, max_iter=max_iter)
12 solver.show_toggle_open(interval_ms=750)
NameError: name 'RootFinderOpen' is not defined