> For the complete documentation index, see [llms.txt](https://jona-projects.gitbook.io/kiwicalc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jona-projects.gitbook.io/kiwicalc/numerical-methods/single-root-finding-algorithms.md).

# Single Root Finding Algorithms

Single-root algorithms find a single root of a function.

#### Single-Root Algorithms

Some numerical root-finding methods are only destined to find only 1 solution, depending on the given input. Amongst them, is the well known Newton-Raphson method, Halley's method, Steffensen's method, etc. Each of these methods requires different parameters, and different numbers of iterations, and has pros and cons.

**Newton-Raphson method**

The Newton-Raphson method is one of the most known root-finding algorithms. Its formula is also rather simple: 

$$
x\_{n+1} = x\_n - \frac{f(x)}{f'(x)}
$$

 The process of this method, seen here in the formula is quite simple to comprehend: First, we choose the initial value - an arbitrary number, preferably close to the root. Then, the next item will be equal to the previous item, minus the division between the function and its derivative (with the previous number). Then, we repeat the process, until the value of the function with our item is very close to 0. For more details visit [the wikipedia page about Newton's method](https://en.wikipedia.org/wiki/Newton%27s_method) Newton's method is implemented in this library via the `newton_raphson()` method. You can import it directly, like this:

`from kiwicalc import newton_raphson` This is the signature of the method:

```python
def newton_raphson(f_0: Callable, f_1: Callable, initial_value: float = 0, epsilon=0.00001) -> float:                   
```

The method accepts a function \`f\_0\`, a derivative \`f\_1\` , and an initial value. You can also change the default epsilon value, which is \`0.00001\`. Epsilon represents how close a point be close to the x axis to be considered a root. For example, lets find a root of the following polynomial: 

$$
2x^3 -5x^2 -23x - 10
$$

For that, we can express the function its derivative via lambda expressions, and choose an initial guess for the result.

```python
origin_function = lambda x: 2 * x ** 3 - 5 * x ** 2 - 23 * x - 10
first_derivative = lambda x: 6 * x ** 2 - 10 * x - 23
initial_value = 8
print(newton_raphson(origin_function, first_derivative, initial_value))

# output:
# 5.0
                    
```

Thus we know that $$x = 5$$ is one of the roots of the function!

Lets try using a different initial value, $$-10$$ for instance:

```python
other_solution = newton_raphson(origin_function, first_derivative, -10)
print(other_solution)
# output:
# -2.0
                    
```

We discovered another root! $$x = -2.0$$.

**Example 4 - Integrating the Newton-Raphson method with the Function class**

Say we defined the same function from the previous example:

```python
origin_function = Function("f(x) = 2x^3 -5x^2 -23x - 10")             
```

Now we can get its derivative (as a Function object):

```python
first_derivative:Function = origin_function.derivative()
```

And use the newton\_raphson method the same as eariler:

```python
solution = newton_raphson(origin_function,first_derivative,9)
print(solution)
# output:
# 5.0
```

You could also shorten this process, by calling to `newton_raphson()` from inside the `Function` class:

```python
origin_function = Function("f(x) = 2x^3 -5x^2 -23x - 10")
print(origin_function.newton(7))

# output:
# 5.0
```

That way, you only need to pass the initial value as a parameter ( in this case, 7). Similarly, you can integrate it with the classes regarding algebraic expressions in this project:

**Example 2 - Integrating the Newton-Raphson method to find the roots of Algebraic expressions**

```python
x = Var('x')
print((2*x**3 - 5*x**2 - 23*x - 10).newton(5))
```

**Halley's Method**

Halley's method, named after the British Mathematician [Halley Edmund](broken://pages/pTRMHHLCs8F75wD3kRE1) \`(1656 - 1742)\` is another method for finding a single root of a function. Unlike the aforementioned Newton's method, Halley's method also requires the second derivative of a function. However, it converges cubically to the solution, compared to Newton's method which converges quadratically, and hence it will take less iterations to find the solution. This is the method's formula (this step is returned until convergence with the solution): 

$$
x\_{n+1} = x\_n - \frac{2 f(x\_n) f'(x\_n)}{2 \[f'(x\_n)]^2 - f(x\_n) f''(x\_n)}
$$

It's considered a good practice to use Halley's method instead of Newton's method when it's easy to find the derivatives of a function. This is the signature of the implementation of halley's method:

```python
 def halleys_method(f_0: Callable, f_1: Callable, f_2: Callable, initial_value: float, epsilon: float = 0.00001,
                        nmax:int=100000):
                        
```

Here are some examples for different approaches to using Halley's method:

```python
                        
f_0 = lambda n: 2 * n ** 3 - 5 * n ** 2 - 23 * n - 10 # function
f_1 = lambda n: 6 * n ** 2 - 10 * n - 23 # first derivative
f_2 = lambda n: 12 * n - 10 # second derivative
initial_value = 0 # initial approximation ( doesn't have to be 0 obviously )
print(halleys_method(f_0, f_1, f_2, initial_value))

# output:
# -0.49999999999999994
                        
                    
```

Therefore, we know that \`x = -0.5\` is a solution. You can round up the result to -0.5 via the `round_decimal()` method, if that bothers you, or if you need to present the result to the user.

**Chebychev's method**

$$
x\_{n+1} = x\_n - \frac{f(x\_n)}{f'(x\_n)} \left( 1 + \frac{f(x\_n) f''(x\_n)}{2 (f'(x\_n))^2} \right)
$$

Chebychev's Method is named by the 19th century Russian Mathematician Pafnuty Chebyshev. It shares many characteristics with Halley's method's ; Both methods are used to find a single root, both a have 3rd order of convergence, and both require the function, its derivative, its second derivative and an initial value.

Some researchers have managed to [optimize chebychev's method](https://www.sciencedirect.com/science/article/pii/S0885064X09000375) by some modifications, but these newer versions are not currently supported in this version. In order to use this method, you must import it beforehand from the library: `from kiwicalc import chebychevs_method` Here are some examples of using Chebychev's method:

```python
                            
f_0 = lambda n: 2 * n ** 3 - 5 * n ** 2 - 23 * n - 10
f_1 = lambda n: 6 * n ** 2 - 10 * n - 23
f_2 = lambda n: 12 * n - 10
initial_value = 0 # It doesn't have to be zero obviously
print(chebychevs_method(f_0, f_1, f_2, initial_value))

# output:
# -0.4999999999999998
                            

```

**Steffensen's Method**

Steffensen's method is another single root-finding method. It differs from the previous two in that it only requires a function and an initial value, compared to Newton's method which also requires the first derivative and Halley's method which also requires the first and second derivative. It is considered a good practice to use Steffensen's method when you wish to find one root of a function, but differentiating it isn't possible, or too costly in time or memory.

In order to use the method you must import it first:

`from kiwicalc import steffensen_method`

Lets test out Steffensen's Method. As mentioned before, it takes two parameters, a function and an initial approximation. So lets apply it to the function $$2x^3 -5\*x - 7$$ and the initial value $$8$$.      

```python
print(steffensen_method(lambda x: 2 * x ** 3 - 5 * x - 7, 8))

# output:
# 2.050976417088196
                              
```

Therefore, we know that $$x=2.0501$$ is approximately the root of the function.

**Bisection Method**

The bisection method is a single root-finding algorithm which only applies for continuous functions. Unlike the aforementioned methods, the bisection method requires two x values that their corresponding y values are of opposite signs, in addition to the function of course. This ensures that a root is found between these two dots (remember that the function needs to be continuous). Knowing that, the method will perform a "binary search", namely, the method will split the interval between the two dots into 2 in each iteration. It's considered a rather easy and intuitive method, but it's also quite slow compared to some other numeric algorithms.

In order to use this method you must import it first: `from kiwicalc import bisection_method`

Here is the signature of the method:

```python
def bisection_method(f: Callable, a: float, b: float, epsilon: float = 0.00001, nmax: int = 10000):
                    
```

Here are some examples of using the method: Consider the function $$f(x) = x^2 - 5x$$. Let's graph it:<br>

We want to show that the function has two roots on $$x=5$$. We know that $$f(2) < 0$$ and that $$f(9) > 0$$. Since they have opposite y values, when we enter $$2$$ and $$9$$ to the bisection method, it will converge to the root between them, which is $$x=5$$ in this case.               &#x20;

```python
parabola = lambda x: x ** 2 - 5 * x # creating the function
print(bisection_method(parabola, 2, 9))

# output:
# 4.999995231628418
                        
```

As you can see, we got a pretty good approximation of the root. If that's not enough for you , you can always round the result with the `round_decimal()` method or decrease the epsilon parameter of the function. However, keep in mind that decreasing the epsilon parameter would also lead to more iterations, and consequently to a slower execution.