Compute 5 \sqrt{5} using Bisection method

Algebra Level 4

With the help of the bisection method, let us try to find 5 \sqrt{5} by using the following equation y ( x ) = x 2 5 y(x) = x^2 -5 Bisection is a Binary search method which is based on the Intermediate Value Theorem. Using bisection method to find 5 \sqrt{5} , we start by a closed interval [ a , b ] [a,b] on which y \large y changes sign, We divide the interval in half. We then replace [ a , b ] [a,b] by the half-interval on which
y \large y changes sign. This process is repeated until the interval has a total length less than certain tolerance ϵ \large \epsilon .

If we started with an interval a b ab of length 1.5 1.5 , where a = ( 1.5 , 0 ) a = (1.5,0) and b = ( 3 , 0 ) b = (3,0) . [note that y ( a ) = 3 , 75 < 0 , y(a) = - 3,75 < 0, and y ( b ) = 4 > 0 y(b) = 4 > 0 ].
Find the number of steps required to find 5 \sqrt{5} when ϵ = 1 0 6 \large \epsilon = 10^{-6} ?

31 21 18 40

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Manuel Kahayon
Jan 3, 2017

Every iteration halves the length of the interval. We want to find the number of iterations n n such that 1.5 1.5 divided by 2 2 n n times is less than 1 0 6 10^{-6} .

This is equivalent to finding the minimum value of n n such that 1.5 2 n 1 0 6 \frac{1.5}{2^n} \leq 10^{-6} , or that 2 n 1 , 500 , 000 2^n \geq 1,500,000 . Taking the logarithm of both sides to the base 2 2 gives us n 20.51 n \geq 20.51 , and the smallest positive integer which satisfies this is n = 21 n = \boxed{21} .

Great, with the bisection method, the function doesn't matter!

It gets interesting when the function has multiple roots like say solving \( \sin x = 0 with a starting interval of [ 0 , 100 ] [0, 100 ] , and then trying to guess which root we end up with.

Calvin Lin Staff - 4 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...