• Feb 20, 2016 Simpson’s 1/3rd Rule Integration SCILAB CODE(Program/Macro). Bisection Method – PYTHON CODE and ANIMATION. Random Walkers walking on a 2D grid.
• This video tutorial will show you on how to create a program that will solve/give the approximate root of any given nonlinear algebraic equations using the B.

May 16, 2017 Scilab, Programming, Numerical Analysis, Bisection Method. Bisection Method C Program Output. Enter two initial guesses: 0 1 Enter tolerable error: 0.0001 Step x0 x1 x2 f (x2) 1 0.000000 1.000000 0.500000 0.053222 2 0.500000 1.000000 0.750000 -0.856061 3 0.500000 0.750000 0.625000 -0.356691 4 0.500000 0.625000 0.562500 -0.141294 5 0.500000 0.562500 0.531250 -0.041512 6 0.500000 0.531250 0.515625 0. Equations using Bisection method Scilab code Solution 1.1 Bisection Method 1 //OperatingSystem Windows10 2 //SCILABversion5.5.2 3 //ExperimentNo.1.

• Related Questions & Answers

• Selected Reading

Given with the function f(x) with the numbers a and b where, f(a) * f(b) > 0 and the function f(x) should lie between a and b i.e. f(x) = [a, b]. The task is to find the value of root that lies between interval a and b in function f(x) using bisection method.

What is bisection method?

Bisection method is used to find the value of a root in the function f(x) within the given limits defined by ‘a’ and ‘b’. The root of the function can be defined as the value a such that f(a) = 0.

Example

Now, If a function f(x) is continuous in the given interval [a..b] and also, sign of f(a) ≠ sign of f(b) then there will be a value m which belongs to the interval a and b such that f(m) = 0

Value m [a..b] Such that f(m) = 0

I.e. m is the value of root which can be multiple

Given below is the figure which is showing the intervals f(a) and f(b). To find the root between these intervals the limit is divided into parts and stored in the variable m i.e.

m = (a + b) / 2

After the division of limits new interval will be generated as shown in the figure given below

Example

Approach that we are using in the below program is as follow −

• Input the equation and the value of intervals a and b
• Divide the intervals as : m = (a + b) / 2
  • Print m is the root
• If f(m) ≠ 0
  • Check if f(a) * f(m) < 0
  • Then root will lie between a and m
  • Check if f(b) * f(m) < 0
  • Then root will lie between b and m

Algorithm

Example

Output

The most basic problem in Numerical Analysis (methods) is the root-finding problem.

For a given function f(x), the process of finding the root involves finding the value of x for which f(x) = 0. If the function equals zero, x is the root of the function.

A root of the equation f(x) = 0 is also called a zero of the function f(x).

The Bisection Method, also called the interval halving method, the binary search method, or the dichotomy method. is based on the Bolzano’s theorem for continuous functions.

Theorem (Bolzano): If a function f(x) is continuous on an interval [a, b] and f(a)·f(b) < 0, then a value c ∈ (a, b) exist for which f(c) = 0.

Image: Example of a continuous function

A function is continuous when small changes of the argument gives also in small changes in the result. In other words, if x changes with small steps f(x) will also change with small steps, it doesn’t give big “jumps” of the result.

f(a)·f(b) < 0 means that f(a) and f(b) have different signs, which means that one of them is above the x-axis and the other one below the x-axis. In this case, if we plot the f(x) function, at some point, it will cross the x-axis. The x value for which the plot is crossing the x-axis is the root of the equation f(x) = 0.

The Bisection Method looks to find the value c for which the plot of the function f crosses the x-axis. The c value is in this case is an approximation of the root of the function f(x). How close the value of c gets to the real root depends on the value of the tolerance we set for the algorithm.

Image: The Bisection Method explained

For a given function f(x),the Bisection Method algorithm works as follows:

1. two values a and b are chosen for which f(a) > 0 and f(b) < 0 (or the other way around)
2. interval halving: a midpoint c is calculated as the arithmetic mean between a and b, c = (a + b) / 2
3. the function f is evaluated for the value of c
4. if f(c) = 0 means that we found the root of the function, which is c
5. if f(c) ≠ 0 we check the sign of f(c):
   • if f(c) has the same sign as f(a) we replace a with c and we keep the same value for b
   • if f(c) has the same sign as f(b), we replace b with c and we keep the same value for a
6. we go back to step 2. and recalculate c with the new value of a or b

The algorithm ends when the values of f(c) is less than a defined tolerance (e.g. 0.001). In this case we say that c is close enough to be the root of the function for which f(c) ~= 0.

In order to avoid too many iterations, we can set a maximum number of iterations (e.g. 1000) and even if we are above the defined tolerance, we keep the last value of c as the root of our function.

Image: The Bisection Method Explained as a Logic Diagram

The best way of understanding how the algorithm work is by looking at an example.

For the function f(x) below find the best approximation of the root given the tolerance of TOL = 0.01 and a maximum of NMAX = 1000 iterations.

[f(x) = 10 – x^2 ]

In the table below we are going to calculate the values described in the logic diagram above:

i	a	b	c	f(a)	f(b)	f(c)
0	-2	5	1.5	6	-15	7.75
1	1.5	5	3.25	7.75	-15	-0.5625
2	1.5	3.25	2.375	7.75	-0.5625	4.359375
3	2.375	3.25	2.8125	4.359375	-0.5625	2.0898438
4	2.8125	3.25	3.03125	2.0898438	-0.5625	0.8115234
5	3.03125	3.25	3.140625	0.8115234	-0.5625	0.1364746
6	3.140625	3.25	3.1953125	0.1364746	-0.5625	-0.2100220
7	3.140625	3.1953125	3.1679688	0.1364746	-0.2100220	-0.0360260
8	3.140625	3.1679688	3.1542969	0.1364746	-0.0360260	0.0504112
9	3.1542969	3.1679688	3.1611328	0.0504112	-0.0360260	0.0072393

At initialization (i = 0) we choose a = -2 and b = 5. After evaluating the function in both points we can see that f(a) is positive while f(b) is negative. This means that between these points, the plot of the function will cross the x-axis in a particular point, which is the root we need to find.

After 9 iterations the value of f(c) is less than our defined tolerance (0.0072393 < 0.01). This means that the value that approximates best the root of the function f is the last value of c = 3.1611328.

We can check our result by solving our quadratic equations in a classic way:

[ begin{equation*} begin{split}
10 – x^2 &= 0
x^2 &= 10

Bisection Method Program In C

x &= sqrt{10} = pm 3.16227766

Bisection Method Program In Scilab With Answers

end{split} end{equation*} ]

Below you can see an animation of the f(x) plot for every iteration. Notice how the [a, b] interval (red horizontal line) is halved at each iteration, until it’s converging into a point where the plot is crossing the x-axis (value of x in that point being the root of the function f).

Image: The Bisection Method animation
for f(x) = 10 – x²

The example calculated in the table is also executed in the C code below. The results are the same as those calculated in the table. Use this C code (copy and past to into a *.c file and execute) to examine the impact of tolerance (e.g 0.0001) on the number of iterations necessary to converge to a solution.

The same algorithm is implemented in a Scilab script. Play with the a, b, TOL and NMAX parameters to understand their impact on the method.

As you can see, the Bisection Method converges to a solution which depends on the tolerance and number of iteration the algorithm performs. There is a dependency between the tolerance and number of iterations. For a particular tolerance we can calculate how many iterations n we need to perform.

Every iteration the algorithm generates a series of intervals [a_n, b_n] which is half of the previous one:

[b_n – a_n = frac{b-a}{2^n} =|c-x| tag{1}]

The tolerance ε is the absolute value of the difference between the actual root of the function x and the approximation c.

[varepsilon=|c-x| tag{2}]

For the algorithm to converge within an absolute error tolerance (ε), we need to have:

[|c-x| le varepsilon tag{3}]

By replacing inequality (3) with equation (1), we get:

[frac{b-a}{2^n}le varepsilon tag{4}]

Solving inequality (4), we obtain:

[2^n ge frac{b-a}{varepsilon} tag{5}]

We apply the logarithm function to both sides of the inequality (5):

[log(2^n) ge logleft (frac{b-a}{varepsilon} right ) tag{6}]

Solving (6), we get:

[ begin{equation*} begin{split}
n cdot log(2) &ge logleft (frac{b-a}{varepsilon} right )
n &ge frac{logleft (frac{b-a}{varepsilon} right )}{log(2)}
end{split} end{equation*} ]

From the above result we can understand that, using the Bisection Method, in order to calculate an approximate root of a function within tolerance ε, the number n of iterations we need to perform is:

Bisection Method Program In Scilab Download

[ begin{equation} begin{split}
bbox[#FFFF9D]{n ge frac{logleft (frac{b-a}{varepsilon}right )}{log(2)}}
end{split} end{equation} ]

For the example presented in this tutorial our algorithm performed 9 iterations until it found the solution within the imposed tolerance. Let’s apply the above formula to see what is the minimum calculated number of iterations.

[ begin{equation*} begin{split}
a &= -2
b &= 5
varepsilon &= 0.01
n &ge frac{logleft (frac{5+2}{0.01} right )}{log(2)}
n &ge 9.45
end{split} end{equation*} ]

The result shown that we need at least 9 iterations (the integer of 9.45) to converge the solution within the predefined tolerance, which is exactly how many iterations our algorithm performed.

The Bisection Method is a simple root finding method, easy to implement and very robust. The disadvantages of this method is that it’s relatively slow. Because of this, most of the time, the bisection method is used as a starting point to obtain a rough value of the solution which is used later as a starting point for more rapidly converging methods.

Bisection Method Program In Scilab Online

The Bisection Method is summarized in the poster below:

Image: The Bisection Method Explained Poster (click on it for higher resolution)

Test your knowledge in the Bisection Method by taking the quiz below:

Bisection Method Program In Scilab C

QUIZ! (click to open)

For any questions or observations regarding this tutorial please use the comment form below.

Don’t forget to Like, Share and Subscribe!

Next Article

4 Comments

Hussain Khan

I been asked to do a bisection method for heat transfer and radiation. the function (Ts) = a.Ts^4 + b .ts + c. I need to determine a,b and c

John Lee

There is an issue with the algorithm.
The tolerance should be set for |a-b|, not |f(c)| because if the f is very close to the x axis, say nearly in parallel with x axis, even |f(c)| is very small, but x could be still far far away from the root.
For example if the function f is
f(x)=0.0000001x, the f(c) could be very small and inside the given tolerance, but x could be very far from the root.

lonz

nice in depth

mahmoudali ali

very useful information