When you have a polynomial around the n > 4 mark, there is not general method for an analytic solution
Resulting to numerical methods
One of the methods is Bisection
The method is you have your real function f(x) = 0 and an interval [a, b] that f(x) is continuous on
The assumption is that after the root-seperation process, f(x) = 0 has at best one root within [a, b]
To begin
The method starts splitting the interval [a, b] where there is a mid point x₀ = (a+b)/2
With this a few rules follow (The if statements in the code)
If f(a) = 0, root is ξ=a
If f(b) = 0, root is ξ=b
If f(a)*f(b) < 0, root is in ξ ∈ (a,b)
If f(a)*f(b) > 0, there is no root in ξ ∈ (a,b)
If neither are true, the boundaries increase or decrease
a will go in nondecreasing order and b will go in decreasing order
If f(x₀) = 0, ξ = x₀ (Adding to the rules uptop)
How much the bound increases by is donated by a constant expand in the code
which is set to 0.1e0
Because of the boundary shift, there is a new midpoint.
Now we can only have a finite number of iterations, otherwise it will loop forever. (variable maxIter)
Because of this, the answer only can be approximate
However the loop can be terminated by following the conditions
|f(x_i)| <= 𝜺 and |b_i - a_i| <= 𝜺|x_i|
These are used in line 71 inside the Bisection function
------------------------------------------------------------------
In the code above, there are two functions
Func and Bisection
Starting with Func
The Func function takes and returns a double
Func stores the function f(x) = 0 that you want to find the roots for.
In this case our function is x²+2x-3=0
NOTE: This algorithm works for all real powers
Next is the Bisection function
This function takes in a double function a double for the minimum interval number
and a double for the maximum interval number.
Then a reference variable for storing the root.
Inside the function
all the variables are created for the necessary computational tasks
Got the variables for epsilon, the max iterations and your functions. (Naming conventions could be better)
finalA will be f(a)
finalB will be f(b)
finalRoot will be f(ξ)
The actual calculations start by running the current interval through the function and conditions to check for validity.
Once they pass
the algorithm starts to iterate
Inside the for loop
the algorithm checks to see if the midpoint is the root.
The if statement in line 71 is our loop termination conditionals.
-----------------------------------------------------------------------------------
Moving on to main
First make the appropriate function calls
and create all the variables needed to apply or store data.
root_min and root_max is our interval
Notably: [root_min, root_max]
we run a loop to make sure the minimum interval number does not exceed the maximum interval number.
Inside the while loop the contraction of the interval begins
then it goes into the bisector function
our bisector variable is to see if the bisector function has terminated
If the bisector does not pass the proceeding if statement
The interval will contract
If every conditions is passed
it will display the root as well as the interval it was on
-----------------------------------------------------------------------------------------------------------
As said previously
the output is approximated
I used a quadratic equation to show the approximations better
using the normal quadratic equation we could have gotten an exact result
but this Bisection Method is used for higher order polynomials.
So
The original solution to our function is
x = -3
x = 1
As you can see in our out put tho we got
x = -3.1
x = 0.9
So both have an absolute error of 0.1
