Topic 3 Lesson 9
Summary
TLDRThis lesson introduces the Bisection method for approximating square roots of numbers between 0 and 1, avoiding the power operator due to floating-point inaccuracies. The method efficiently narrows the search interval by halving it with each iteration, aiming for an approximation error less than a given tolerance, epsilon. The script explains the iterative process, provides a Python code example, and compares the Bisection method's efficiency to Heron's method, highlighting its straightforward convergence analysis.
Takeaways
- π The lesson focuses on the Bisection method, a numerical technique used to approximate the square root of a given number.
- π’ It is assumed that the number \( x \) is non-negative and less than or equal to 1, ensuring the square root is between \( x \) and 1.
- π The method avoids using the power operator and instead relies on the properties of the square root function within the given interval.
- π The goal is to find an approximation \( p \) such that \( |p^2 - x| < \epsilon \), where \( \epsilon \) is a given tolerance (e.g., \( 10^{-6} \)).
- π« A brute force approach would involve checking many points, which is inefficient and slow.
- π The Bisection method improves efficiency by examining the midpoint of the interval and narrowing the search based on whether the midpoint squared is less than or greater than \( x \).
- π’ The midpoint is calculated as \( \text{mid} = \frac{\text{low} + \text{high}}{2} \), where \( \text{low} \) and \( \text{high} \) are the current bounds of the search interval.
- π The method iteratively halves the search interval, significantly reducing the number of steps needed to achieve the desired accuracy.
- π The error approximation decreases exponentially with each iteration, making the Bisection method highly efficient for finding square roots.
- π The lesson also mentions Heron's method, which has a faster convergence rate but is less straightforward to analyze compared to the Bisection method.
Q & A
What is the main topic of the lesson?
-The main topic of the lesson is the Bisection method, specifically its application in approximating the square root of a given number.
Why is it assumed that the number x is less than or equal to 1?
-It is assumed that x is less than or equal to 1 for simplicity, ensuring that the square root of x is between x and 1, which makes the problem more manageable.
What is the significance of the intersection point between y=sqrt(x) and y=x?
-The intersection point between y=sqrt(x) and y=x is significant because it indicates that for x values between 0 and 1, the square root of x will also be between x and 1.
Why is the brute force iterative approach considered slow?
-The brute force iterative approach is considered slow because it involves dividing the interval between x and 1 into many points and traversing them one by one, potentially requiring a large number of steps.
What is the main idea behind the Bisection method?
-The main idea behind the Bisection method is to examine the middle element of the interval between x and 1, compare it with the square root of x, and then narrow down the search interval based on the comparison, effectively bisecting the search space at each iteration.
How does the Bisection method improve efficiency compared to the brute force approach?
-The Bisection method improves efficiency by reducing the search interval length by half at each iteration, thus quickly narrowing down the possible values for the square root.
What is the stopping condition for the while loop in the Bisection method algorithm?
-The stopping condition for the while loop is when the absolute value of (mid*mid - x) is less than or equal to epsilon, indicating that the approximation is within the desired tolerance.
How does the Bisection method handle the case when mid*mid is less than x?
-When mid*mid is less than x, the method updates the lower bound of the search interval (low) to mid, effectively narrowing the search to the interval between mid and high.
How does the Bisection method handle the case when mid*mid is greater than x?
-When mid*mid is greater than x, the method updates the upper bound of the search interval (high) to mid, effectively narrowing the search to the interval between low and mid.
What is the relationship between the number of iterations and the approximation error in the Bisection method?
-The approximation error decreases exponentially with the number of iterations. After k iterations, the error is at most (1/2^(k+1)), which shows that the method can quickly reduce the error to a very small value.
How does the Bisection method compare to Heron's method in terms of convergence rate?
-While Heron's method has a faster convergence rate, its convergence analysis is less trivial than that of the Bisection method, which is more straightforward and easier to understand.
Outlines
π Introduction to the Bisection Method for Square Root Approximation
This paragraph introduces the Bisection method, a numerical technique used for approximating the square root of a non-negative real number 'x' that is less than or equal to 1. The method avoids using the power operator and assumes that the square root of 'x' lies between 'x' and 1. It discusses the limitations due to floating point representation and the acceptable level of accuracy defined by a tolerance parameter 'epsilon'. The paragraph also contrasts the Bisection method with a brute force approach, highlighting the efficiency of the former by iteratively narrowing down the search interval and dividing the interval length by 2 with each iteration.
π Algorithm Translation to Python Code for Bisection Method
The second paragraph translates the Bisection method algorithm into Python code. It explains the initialization of variables 'low' and 'high' to represent the search interval, with 'mid' calculated as their average. A while loop is used with a stopping condition based on the difference between 'mid' squared and 'x'. The body of the loop includes conditional statements to update 'low' or 'high' based on whether 'mid' squared is less than or greater than 'x', ensuring the search interval is narrowed down correctly. The paragraph also discusses the importance of updating 'mid' to avoid an infinite loop and concludes with a practical example using 'x' as 0.5 and 'epsilon' as 0.01, demonstrating the iterative process of narrowing down to the approximate square root.
π Analysis of the Bisection Method's Efficiency and Comparison with Other Methods
The final paragraph delves into the efficiency of the Bisection method by analyzing the decrease in the search interval's length after each iteration, which is halved exponentially. It provides a formula for the interval length after 'k' iterations and estimates the approximation error, which is the maximum distance between 'mid' and the actual square root of 'x'. The error is shown to decrease with each iteration, capped by the reciprocal of 2 raised to the power of 'k+1'. The paragraph concludes by comparing the Bisection method with Heron's method, noting that while Heron's method may have a faster convergence rate, the Bisection method's convergence analysis is more straightforward. It also mentions that the Bisection method, also known as binary search, will be applied to discrete problems later in the course.
Mindmap
Keywords
π‘Bisection method
π‘Square root
π‘Floating point representation
π‘Tolerance parameter (epsilon)
π‘Iterative approach
π‘Midpoint
π‘Interval
π‘Convergence rate
π‘Binary search
π‘Approximation error
Highlights
The lesson focuses on the Bisection method for approximating the square root of a given number.
Assumption made that the number x is between 0 and 1, ensuring the square root of x is between x and 1.
Floating point representation with limited accuracy is used, requiring an acceptable tolerance level.
The brute force iterative approach is slow, involving dividing the interval into many points and checking each one.
The Bisection method is introduced as a more efficient alternative to the brute force approach.
The Bisection method involves examining the middle element of the interval and comparing it with the square root of x.
If the middle element squared is close enough to x, it is considered a good approximation of the square root.
The method narrows down the search interval based on whether the middle element squared is less than or greater than x.
The search interval length is halved with each iteration, making the Bisection method very efficient.
The algorithm is translated into Python code, demonstrating how to implement the Bisection method programmatically.
Variables low and high are used to track the search interval, with mid initialized to their average.
A while loop is used with a condition based on the absolute value of (mid*mid - x) being greater than epsilon.
The search interval is updated based on whether mid squared is less than or greater than x.
The mid variable is updated after updating low and high to avoid an infinite loop.
The approximate square root is printed when the condition is no longer met, indicating a close enough approximation.
An example is provided where x = 0.5 and epsilon = 0.01, demonstrating the iterative process of the Bisection method.
The speed and efficiency of the Bisection method are analyzed, showing how the search interval length decreases exponentially.
The approximation error is estimated, showing that it decreases with each iteration.
A comparison is made with Heron's method, noting that while it may have a faster convergence rate, its analysis is less straightforward.
The Bisection method, also known as binary search, is highlighted for its applicability in both numerical and discrete problems.
Transcripts
In this lesson, we will study the
Bisection method illustrated on
the problem of approximating the
square root of a given number.
Given a non negative real number x we would
like to approximate its square root,
without using the power operator star star.
For simplicity, we are going to assume
that x is less than or equal to 1.
So x is a number between 0 and 1,
so that square root of x is between x and
1, and this is the case because if
you look at the curve of the function,
this is square root of x and
this is y = x. They intersect here.
This is 1 and this is 1.
So if x is between 0 and 1.
This is x.
This is square root of x.
Square root of x is between x and
1 and we're not after the square
root exactly because we're using
the floating point representation,
which is 8 byte and it has limited accuracy,
so we have to accept certain accuracy.
We're OK with any answer
p approximation p of the square
root such that p square or
equivalently p * p
-x in absolute value is
less than epsilon for some given
tolerance parameter epsilon,
such as epsilon equal 10 to the -6.
The brute force iterative approach
is to divide the interval between
x and 1 into many many points,
let's say 1,000,000 equally spaced points,
and then traverse those points,
loop over the points one by one to find the point
p such that p * p is close enough to x.
Now, the drawback of this
approach is that it is very slow.
It would take in the order
of 1,000,000 steps.
We know that square root of x is in
the interval between x and 1.
Instead of searching for square
root of x iteratively,
as in the previous example,
the idea is to examine the middle element
of the interval between
x and 1 so this is mid .
The average of x and 1 x + 1 over 2,
and then compare the mid square
with x. If case one, if we are lucky,
if the absolute value of mid square
-x is less than epsilon,
where epsilon is our given tolerance
parameter, we're done. mid is a
desired approximation of the
square root. Will stop.
If mid square
is less than x, or equivalently
mid less than square root of x,
then we know that
square root of x is greater than
mid and it is less than 1,
so it must be in this sub interval.
If
in the remaining case, mid
square is greater than x
or equivalently, mid greater than square
root of x and square root of x is less than mid.
It is also greater than or equal to x,
so it must be in this sub interval.
So here if mid times mid less than x
we narrow down the search to
the interval between mid and 1.
Else, we narrow down the search
to the interval between x and mid.
This is called the Bisection method
becauses we're bisecting the search interval,
and this is very efficient
because at each, so at this iteration,
at each iteration,
we're dividing the search
interval length by 2.
We're going to keep on doing this
until we get that mid squared
-x absolute value is at most epsilon.
Initially,
the length of our search is at
most 1. After the first iteration,
its length would be at most half.
After the second iteration,
the length of the search interval
would be at most 1 over 4.
And so, after k iteration,
the length of our search interval will
be at most 1 over 2 to the k.
Note that here it's easy to
multiply mid by mid and
a key point here is that by
comparing mid times mid with x,
we can actually tell whether
mid square root of x is on
this side or on that side.
Translate this algorithm into a Python code.
We need two variables low and high
to keep track of our search interval
low is initially X and high is initially one.
We also need a third variable mid
Initialized to the average of low and high
(low+high)/2
we have a loop.
I will use a while loop and this is the.
stopping condition so the loop conditon
condition is going to be while
absolute value of (mid*mid - x)
is strictly greater than epsilon
mid*mid - x
strictly greater than optional.
And in the body of the while,
first we check this case.
If mid times mid.
Is less than X. In the general case,
we need to narrow down the search interval
to the interval between mid and high,
which boils down to updating the low to mid.
high remains the same and there is no point
in saying high = high
Else, which correspond to this case,
and more specifically to the
case when mid*mid
is strictly greater than X.
They cannot be equal because
of the loop condition here.
Else we update high, so high becomes
mid. Mid and low remains the same
What's missing is the update statement.
We need to update mid
After updating low and high
without updating mid
if we enter this loop
we will get stuck in infinite loop.
So here we update mid again
mid = (low+high)/2
And at the end, when we're done, we print
mid as the approximate square root.
This is the clean version of the code.
Same code except here we initially read X.
On the float, this is epsilon.
We could also get epsilon from the user
here we initialize low, high, and mid
this is our loop and this is the if else statement
and here we update mid
and at the end we print the
square root of X is mid,
note that if initially we were lucky and
mid*mid is close enough to x
then we're not going to enter this
loop and will immediately after
setting the mid, will print the Mid
as the approximate square root.
Let's track it now in an example where
X = 0.5 and epsilon 0.01.
This is low initialized to x = 0.5
high to one and this is
mid and this is mid times mid
not close enough to x with respect to epsilon
to 0.01 and it is greater than X.
So we narrowed down to the left subinterval
we find mid again
mid*mid is not close enough
to X and it is less than X
so we narrow down to the
right subinterval
Again mid times mid is not close
enough to axe and it is less than X,
so narrow down to the right subinterval.
And here also mid*mid
is not close enough
and it is greater than X.
So we narrowed down to the left subinterval
here mid times mid
Is close enough to X with respect to 0.01,
so 0.01, so we stop.
Now, when analyzed,
the speed of the bisection method.
As previously noted,
the length of our search interval decreases
exponentially with the number of iteration.
In particular,
before entering the loop,
our search interval
we start at X and the low is X,
and the high is one
the length is 1-x
After first iteration we divide by two,
so we get (1-x)/2
After the second iteration
we divide by two again.
So we get (1-x)/(2^2)
After K iterations we will get
(1-x)/(2^k)
Now we need to estimate the
error, approximation error,
which is the absolute value of
mid - square root of x
In general,
this is our search interval
low , High. This is mid.
And this is square root of X.
Somewhere in this interval.
We need to estimate.
This distance, in the worst case
square root of X is here or here.
So in the worst case,
this error is at most the length
of the interval over 2. So
mid - square root of X absolute value
is at most interval length/2
which is (high-low)/2
Therefore, Given that we know the
search interval length from this column
before entering the loop,
the error is at most (1 - X)/2.
This (1 - X)/2, which is at most half.
Similarly, here there are is at most
the length is (1-x)/2, so the error
would be at most (1-x)/(2^2)
which is at most (1/2^2) and so on.
After second iteration we get (1/2^3)
after K iteration get (1/2^(k+1))
In summary, after K iteration,
the approximation error is
at most (1/2^(k+1))
So for K equal, for example 10,
after 10 iterations will get the error to.
The error will be upper bounded
by (1/2^11)
Which is why
which is why the bisection method
is efficient.
It can quickly decrease the error.
A final remark is that Heron's method
which we have seen in the first topic in
this course has a faster convergence rate,
but its convergence analysis is less
trivial than that of the bisection method.
In this lesson,
we've seen the bisection method
applied to the numerical problem
of approximating the square root.
The bisection method is also
called binary search. Later in this
course we will see binary search
applied to discrete problems such as
searching a sorted list of numbers.
5.0 / 5 (0 votes)