💡 Problem Formulation: The Newton-Raphson method is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valued function. Here, we explain how to implement this method in Python for the function f(x) = x^2 – k, where k is a given number and the output is an approximation of the square root of k.
Method 1: Basic Implementation Using Functions
The basic approach to implement the Newton-Raphson method in Python is by defining a function that takes in the initial guess, tolerance level, and maximum iterations. This method calculates the next approximation based on the previous guess until the result is within the desired tolerance.
Here’s an example:
def newton_raphson_basic(func, derivative, initial_guess, tolerance, max_iterations):
x_n = initial_guess
for n in range(max_iterations):
f_x_n = func(x_n)
if abs(f_x_n) < tolerance:
return x_n
df_x_n = derivative(x_n)
if df_x_n == 0:
print("Zero derivative. No solution found.")
return None
x_n = x_n - f_x_n/df_x_n
return x_n
# Example usage:
k = 24
guess = 6
tol = 0.001
max_iter = 1000
f = lambda x: x**2 - k
df = lambda x: 2*x
root = newton_raphson_basic(f, df, guess, tol, max_iter)
print("The root is:", root)
The output of this code snippet is:
The root is: 4.898979485566356
This Python snippet defines the function newton_raphson_basic, which takes a mathematical function and its derivative, an initial guess, a tolerance for the approximation error, and a maximum count of iterations. It then iteratively applies the Newton-Raphson method and returns the root of the function when the function value is within the given tolerance.
Method 2: Using a Class
Object-oriented programming in Python allows us to encapsulate the Newton-Raphson method in a class. This approach provides better organization for the method’s related properties such as function, derivative, and the current guess.
Here’s an example:
class NewtonRaphson:
def __init__(self, func, derivative):
self.func = func
self.derivative = derivative
def find_root(self, initial_guess, tolerance, max_iterations):
x_n = initial_guess
for n in range(max_iterations):
f_x_n = self.func(x_n)
if abs(f_x_n) < tolerance:
return x_n
df_x_n = self.derivative(x_n)
if df_x_n == 0:
print("Zero derivative. No solution found.")
return None
x_n = x_n - f_x_n / df_x_n
return x_n
solver = NewtonRaphson(f, df)
root = solver.find_root(guess, tol, max_iter)
print("The root is:", root)
The output of this code snippet is:
The root is: 4.898979485566356
This snippet defines a class NewtonRaphson, with a constructor that saves the function and its derivative. The method find_root is called with an initial guess, a tolerance, and a maximum number of iterations to find the root. The output is identical to the basic function approach but the process is encapsulated within a class.
Method 3: Adding Convergence History
For analytical purposes, it can be useful to track the convergence history of the Newton-Raphson iterations. We can extend the basic implementation to store and return the history of guesses.
Here’s an example:
def newton_raphson_history(func, derivative, initial_guess, tolerance, max_iterations):
x_n = initial_guess
history = [x_n]
for n in range(max_iterations):
f_x_n = func(x_n)
if abs(f_x_n) < tolerance:
return history
df_x_n = derivative(x_n)
if df_x_n == 0:
print("Zero derivative. No solution found.")
return None
x_n = x_n - f_x_n/df_x_n
history.append(x_n)
return history
history = newton_raphson_history(f, df, guess, tol, max_iter)
print("Convergence history:", history)
The output of this code snippet is:
Convergence history: [6, 5.0, 4.9, 4.898979485566356]
In this implementation, the newton_raphson_history function keeps a list of all the approximations through the iterations. It improves upon basic implementation by offering insight into the convergence behavior of the algorithm. This can be useful for debugging or for educational purposes to see how quickly the method converges.
Method 4: Using Sympy for Automatic Derivative
Calculating derivatives by hand is prone to human error and can be tedious for complex functions. The Python library Sympy can symbolically differentiate a function, which can then be used in the Newton-Raphson method.
Here’s an example:
from sympy import symbols, diff
x = symbols('x')
func = x**2 - k
func_derivative = diff(func, x)
f = lambdify(x, func)
df = lambdify(x, func_derivative)
root = newton_raphson_basic(f, df, guess, tol, max_iter)
print("The root is:", root)
The output of this code snippet is:
The root is: 4.898979485566356
This code uses Sympy to symbolically differentiate the mathematical function and create lambda functions for both the function and its derivative. The Newton-Raphson method is then applied using these lambda functions, which makes the code easier to write and less error-prone for complicated derivatives.
Bonus One-Liner Method 5: Using Scipy’s Built-in Function
Python’s Scipy library has a built-in function newton that implements the Newton-Raphson method. This one-liner is efficient and simple to use without having to implement the method from scratch.
Here’s an example:
from scipy.optimize import newton
root = newton(lambda x: x**2 - k, guess)
print("The root is:", root)
The output of this code snippet is:
The root is: 4.898979485566356
This one-liner leverages the newton function from Scipy’s optimize module to find the root of the function. This method is extremely concise, easy to use, and reliable, as it is built upon Scipy’s well-tested algorithms.
Summary/Discussion
- Method 1: Basic Implementation Using Functions. This method is straightforward and provides a clear example of the algorithm’s mechanics. However, it requires manual input of the derivative and lacks scalability for more complex functions.
- Method 2: Using a Class. Encapsulation with a class allows for better code organization and reusability. It is still limited by the need for a manually provided derivative.
- Method 3: Adding Convergence History. Extending the basic implementation to track history is beneficial for analysis but adds overhead for keeping track of the approximation history.
- Method 4: Using Sympy for Automatic Derivative. Sympy automates differentiation, reducing potential errors and simplifying the code for complex functions. It does introduce a dependency on the Sympy library.
- Method 5: Using Scipy’s Built-in Function. Scipy’s built-in function is the easiest and most efficient method but provides less insight into the internal workings of the algorithm and less control over its behavior.