2. Newton’s method

Newton’s method is an iterative method for finding the roots of a real-valued function.
It starts with an initial guess for the root (x0) and iteratively refines this guess using the formula to calculate a new x value closer to the root: x1 = x0 - f(x0) / f’(x0), until a desired level of accuracy is achieved.
../_images/newtons_quadratic.png

Pseudocode:
define newton(f(x), f’(x), x0, max_iter, tol)
i ← 0
while i < max_iter
x1 ← x0 - f(x0) / f’(x0)
if abs(x1 - x0) <= tol then
return x1
x0 ← x1
i ← i + 1
return x1
This pseudocode defines a function newton that takes five arguments: f(x), f’(x), x0, max_iter, and tol.
The function initializes a loop counter i to 0 and enters a while loop that iterates max_iter times.
The maximum number of iterations allowed is specified by the max_iter parameter.
In each iteration, the code calculates a new value for x1 using the formula x1 = x0 - f(x0) / f’(x0).
It then checks if the absolute difference between x1 and x0 is less than tol.
If it is, the function returns x1.
Otherwise, the value of x0 is updated to be equal to x1 and the loop counter i is incremented by 1.
After the loop has completed, the function returns the final value of x1.
Python implementation:
def newton(f, df, x0, max_iter, tol):
    i = 0
    while i < max_iter:
        x1 = x0 - f(x0) / df(x0)
        if abs(x1 - x0) <= tol:
            return x1
        x0 = x1
        i += 1
    return x1

2.1. Usage Example - cubic

../_images/newtons_cubic.png 


 1"""newton's method: cubic
 2"""
 3
 4def newton(f, df, x0, max_iter, tol):
 5    i = 0
 6    while i < max_iter:
 7        x1 = x0 - f(x0) / df(x0)
 8        if abs(x1 - x0) <= tol:
 9            return x1
10        x0 = x1
11        i += 1
12    return x1
13
14f = lambda x: x**3 - 2
15df = lambda x: 3 * x**2
16
17result = newton(f, df, 1.5, 100, 1e-6)
18print(result)
19
20# 1.2599210498953948
21

This is an example of how you can use the newton’s method
to find the root of the function y = x3 - 2.
The f function calculates the value of x3 - 2 for a given value of x.
The df function calculates the derivative of f, which is 3x2.
The code then calls the newton function with f set to the f lambda function, df set to the df lambda function, x0 set to an initial guess of 1.5, max_iter set to 100, and tolerance, tol, set to 1e-6.
The output value of 1.2599210498953948 is an approximate root of the function y = x3 - 2 found using Newton’s method with an initial guess of 1.5, a maximum of 100 iterations, and a tolerance of 1e-6.

2.2. Usage Example - exponential

../_images/newtons_exponential.png 


 1"""newton's method: exponential
 2"""
 3# import the math module to use the exponential function
 4import math
 5
 6def newton(f, df, x0, max_iter, tol):
 7    i = 0
 8    while i < max_iter:
 9        x1 = x0 - f(x0) / df(x0)
10        if abs(x1 - x0) <= tol:
11            return x1
12        x0 = x1
13        i += 1
14    return x1
15
16f = lambda x: math.exp(x) - 3
17df = lambda x: math.exp(x)
18
19
20result = newton(f, df, 1, 100, 1e-6)
21print(result)
22# 1.0986122886681096
23