nth Root of an equation

Solution of Linear and Non-linear equations

Using Bisection, Newton Raphson and Secant methods, find out roots of the equation.

To approximate $n$th root of a number up to a given number of significant digits.
Solve transcendental equations (a) $\alpha = \tan \alpha$, (b) $\sin \alpha = \sqrt{m}\alpha$.
Determine the depth up to which a spherical homogeneous object of given radius and density will sink into a fluid of given density.

Root Finding Methods

1. Bisection Method

The Bisection Method is a numerical technique for finding the root of a function by iteratively narrowing an interval ([a, b]) where the function changes sign.

Steps:

Choose two points $ a $ and $ b $ such that $ f(a) :nbsphinx-math:`cdot `f(b) < 0 $.
Compute the midpoint $ c = \frac{a + b}{2} $.
Check the sign of $ f(c) $:
- If $ f(c) = 0 $, then $ c $ is the root.
- If $ f(a) :nbsphinx-math:`cdot `f(c) < 0 $, set $ b = c $; else, set $ a = c $.
Repeat until $ |f(c)| $ is within a desired tolerance.

Advantages:

Simple and always converges if $ f(x) $ is continuous.
Does not require derivatives.

Disadvantages:

Convergence is slow.
Requires two initial points that bracket a root.

2. Newton-Raphson Method

The Newton-Raphson Method is an iterative method that uses the derivative of the function to approximate roots. It converges quickly but requires the function to be differentiable.

Formula:

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

Steps:

Choose an initial guess $ x_0 $.
Compute $ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} $.
Repeat until $ |f(x_n)| $ is sufficiently small.

Advantages:

Faster convergence compared to the Bisection Method.
Works well for smooth functions.

Disadvantages:

Requires the derivative $ f’(x) $.
May fail if $ f’(x) = 0 $ or if the function is not well-behaved.

3. Secant Method

The Secant Method is similar to Newton-Raphson but does not require the derivative. Instead, it approximates the derivative using two points.

Formula:

\[x_{n+1} = x_n - \frac{f(x_n)(x_n - x_{n-1})}{f(x_n) - f(x_{n-1})}\]

Steps:

Choose two initial guesses $ x_0 $ and $ x_1 $.
Compute $ x_2 $ using the secant formula.
Repeat until $ |f(x_n)| $ is sufficiently small.

Advantages:

Faster than the Bisection Method.
Does not require the derivative.

Disadvantages:

Can fail if $ f(x_n) = f(x_{n-1}) $.
May not converge as reliably as Newton-Raphson.

Algorithm for Finding the nth Root of a Number

This algorithm outlines three methods for approximating the nth root of a number A: Bisection Method, Newton-Raphson Method, and Secant Method.

1. Bisection Method:

Goal: Find a root of the function f(x) = x^n - A within a given interval [a, b].
Assumptions: The function f(x) is continuous on the interval [a, b]. f(a) and f(b) have opposite signs (ensuring a root exists within the interval).
Steps:
1. Initialize an interval [a, b] such that the nth root of A lies within it (e.g., [0, max(1, A)]).
2. Set a required tolerance (required_tol) based on the desired number of significant digits.
3. While the width of the interval (b - a) is greater than the required tolerance:
  1. Calculate the midpoint mid = (a + b) / 2.
  2. Evaluate mid^n - A.
  3. If (mid^n - A) and (a^n - A) have opposite signs, the root lies in the interval [a, mid]. Set b = mid.
  4. Otherwise, the root lies in the interval [mid, b]. Set a = mid.
  5. Update mid = (a + b) / 2.
4. Return the midpoint mid as the approximate nth root, rounded to the desired number of significant digits.

2. Newton-Raphson Method:

Goal: Find a root of the function f(x) = x^n - A using an iterative approach based on the tangent line to the function.
Formula: x_new = x - (x^n - A) / (n * x^(n-1))
Steps:
1. Choose an initial guess x for the nth root (e.g., A / n).
2. Set a required tolerance (required_tol) based on the desired number of significant digits.
3. Enter a loop that continues indefinitely (or until a breaking condition is met).
4. Calculate the next approximation x_new = x - (x**n - A) / (n * x**(n - 1)).
5. Check for convergence: If abs(x_new - x) < required_tol, break.
6. Update x = x_new.
7. Return x, rounded to the desired number of significant digits.

3. Secant Method:

Goal: Find a root of the function f(x) = x^n - A using an iterative approach based on the secant line through two previous points.
Formula: x_new = x1 - f(x1) * (x1 - x0) / (f(x1) - f(x0)) where f(x) = x^n - A.
Steps:
1. Choose two initial guesses x0 and x1 (e.g., 0 and A / (2 * n)).
2. Set a required tolerance (required_tol).
3. While abs(x1 - x0) > required_tol:
  1. Calculate f_x0 = x0^n - A and f_x1 = x1^n - A.
  2. Calculate x_new = x1 - f_x1 * (x1 - x0) / (f_x1 - f_x0).
  3. Update x0 = x1 and x1 = x_new.
4. Return x1, rounded to the desired number of significant digits.

Finding the nth Root of a Number using Numerical Methods

Problem Statement

Given a number A and an integer n, we need to find x such that:

\[x^n = A\]

using numerical methods up to a specified number of significant digits.

[7]:

import math

def bisection_nth_root(A, n, sig_digits, tol=1e-10):
    """Bisection method to approximate the nth root of A."""
    a, b = (0, max(1, A))  # Initial interval
    mid = (a + b) / 2.0
    required_tol = 0.5 * 10 ** (-sig_digits)

    while abs(mid**n - A) > required_tol:
        if (mid**n - A) * (a**n - A) < 0:
            b = mid
        else:
            a = mid
        mid = (a + b) / 2.0

    return round(mid, sig_digits)

def newton_nth_root(A, n, sig_digits):
    """Newton-Raphson method to approximate the nth root of A."""
    x = A / n  # Initial guess
    required_tol = 0.5 * 10 ** (-sig_digits)

    while True:
        x_new = x - (x**n - A) / (n * x**(n - 1))
        if abs(x_new - x) < required_tol:
            break
        x = x_new

    return round(x, sig_digits)

def secant_nth_root(A, n, sig_digits):
    """Secant method to approximate the nth root of A."""
    x0, x1 = A / n, A / (2 * n)  # Initial guesses
    required_tol = 0.5 * 10 ** (-sig_digits)

    while abs(x1 - x0) > required_tol:
        f_x0 = x0**n - A
        f_x1 = x1**n - A
        x_new = x1 - f_x1 * (x1 - x0) / (f_x1 - f_x0)
        x0, x1 = x1, x_new

    return round(x1, sig_digits)

Example: Compute Cube Root of 27

Let’s compute $ \sqrt[3]{27} $ using all three methods with five significant digits.

[8]:

## Example Usage
A = 27  # Find cube root of 27
n = 3
sig_digits = 5

print("Bisection Method:", bisection_nth_root(A, n, sig_digits))
print("Newton-Raphson Method:", newton_nth_root(A, n, sig_digits))
print("Secant Method:", secant_nth_root(A, n, sig_digits))

Bisection Method: 3.0
Newton-Raphson Method: 3.0
Secant Method: 3.0