---
tags: Mathematical modeling and optimization
title: 1.2. Finding the root of equation
---

## 1.2. Finding the roots of equation

Solving equations are one of the most general tasks when dealing with engineering problems. Solution of high order polynomial or exponent involved equation is never easy to acquire. Numerical methods serve as very handy alternatives to deliver rapid and accurate results.

### 1.2.1. Numerical method approaching the solution
__Newton-Raphson method__ and the __secant method__ are both iterative techniques used for finding the roots of a real-valued function, which essentially means solving equations of the form $f(x)=0$.

#### Newton-Raphson Method:

<img align="center" src="https://upload.wikimedia.org/wikipedia/commons/8/83/Methode_newton.png" width="60%">

The Newton-Raphson method is based on linear approximation. Given an initial guess $x_0$, the next approximation $x_n+1$ is computed as follows:

$$x_{n+1}=x_n−\frac{f(x_n)}{f^\prime(x_n)}$$

where:
- $f(x)$ is the function for which we are trying to find the root.
- $f^\prime(x)$ is the derivative of $f$ with respect to $x$.

Iterative Process:
1. Choose an initial guess $x_0$.
2. Iterate using the formula until the result converges to the desired accuracy.

Convergence:

The method typically converges rapidly if the initial guess is close to the root and if the function is well-behaved.

__Implementation__

def newton_raphson(f, f_prime, x0, tolerance=1e-6, max_iterations=100):
    """
    Newton-Raphson method for finding the root of a function.

    Parameters:
    - f: The function for which to find the root.
    - f_prime: The derivative of the function.
    - x0: Initial guess.
    - tolerance: Desired accuracy.
    - max_iterations: Maximum number of iterations.

    Returns:
    - Approximation of the root.
   """
    x = x0
    for i in range(max_iterations):
        fx = f(x)
        f_prime_x = f_prime(x)

        if abs(fx) < tolerance:
            return x  # Close enough to the root

        x = x - fx / f_prime_x

    raise ValueError("Newton-Raphson method did not converge")

#### Secant Method:
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/9/92/Secant_method.svg/800px-Secant_method.svg.png" width="50%">
Formula:

The secant method is a numerical technique that doesn't require the computation of derivatives. Given two initial guesses $x_0$ and $x_1$, the next approximation $x_{n+1}$ is given by:

$$ x_{n+1}=x_n−\frac{f(x_n)⋅(x_n−x_{n−1})}{f(x_n)−f(x_{n−1})}$$

Iterative Process:

1. Choose two initial guesses $x_0$ and $x_1$.
2. Iterate using the formula until the result converges to the desired accuracy.

Convergence:

The secant method usually converges slower than Newton's method but has the advantage of not requiring the computation of derivatives.

__Implementation:__

def secant_method(f, x0, x1, tolerance=1e-6, max_iterations=100):
    """
    Secant method for finding the root of a function.

    Parameters:
    - f: The function for which to find the root.
    - x0, x1: Initial guesses.
    - tolerance: Desired accuracy.
    - max_iterations: Maximum number of iterations.

    Returns:
    - Approximation of the root.
    """
    for i in range(max_iterations):
        fx0 = f(x0)
        fx1 = f(x1)

        if abs(fx1) < tolerance:
            return x1  # Close enough to the root

        x2 = x1 - (fx1 * (x1 - x0)) / (fx1 - fx0)

        x0, x1 = x1, x2

    raise ValueError("Secant method did not converge")

#### Comparison:

__Newton-Raphson__:
- One initial guess needed.
- Requires the computation of the derivative.
- Generally faster convergence if the initial guess is close to the root.

__Secant__:
- Two initial guesses needed.
- Does not require the computation of derivatives.
- Convergence might be slower, especially if the initial guesses are not close to the root.

Both methods are powerful tools for root-finding, and the choice between them often depends on the specific characteristics of the problem at hand.

__See also__

Similar functions are provided by python module SciPy, which can be directly called without implemented individually. More information: [scipy.optimize.newton](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.newton.html).

__Further more__

The Newton/Secant method are numerical strategies starting from $x_0$ (and $x_1$) to approach the $y=0$ intersection. Starting from different $x_0$ values, found root will be different. Based on this, the entire roots of the function has to be approached by several initial guesses. The thorough assessment in __number of root__ shall be investigated first.

### <ins>Scenario -- root of polynomial function</ins>
find the root of the function:
$$x^5 - 150 x^3 - 20 x -4 = 0$$

[__Sample solution__](https://cocalc.com/share/public_paths/26a0fee2f89ea24d590d8ed11c73ec3e3d60e624)

---
[__BACK TO CONTENT__](https://hackmd.io/@SamuelChang/H1LvI_eYn)