Topic 3 Lesson 9

Summary

This 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

00:00

🔍 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.

05:01

📝 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.

10:02

📉 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.

Keywords

💡Bisection method

The Bisection method is a numerical technique used to find an approximate solution to equations where finding an exact solution is difficult. In the context of the video, it is applied to approximate the square root of a given number. The method involves repeatedly halving the interval between a known lower and upper bound until the desired accuracy is achieved. The script illustrates this by narrowing down the search for the square root of a number between 0 and 1, using the midpoint of the interval and halving the range until the midpoint squared is close enough to the original number.

💡Square root

The square root of a number is a value that, when multiplied by itself, gives the original number. In the script, the focus is on approximating the square root of a non-negative real number less than or equal to 1. The video emphasizes the importance of this concept by explaining that the square root of a number x is between x and 1, and the Bisection method is used to approximate this value.

💡Floating point representation

Floating point representation refers to the way computers store and manipulate real numbers, which is limited by the number of bytes used. In the script, it is mentioned that due to the limited accuracy of this representation, the Bisection method is used to find an approximation of the square root that is within a certain tolerance, rather than the exact square root.

💡Tolerance parameter (epsilon)

Epsilon is a small positive number used to define the acceptable level of error in an approximation. In the video, epsilon is used as the tolerance parameter to determine when the approximation of the square root is close enough to the actual value. The script specifies that the approximation is acceptable if the absolute difference between the square of the approximation and the original number is less than epsilon, such as 10 to the power of -6.

💡Iterative approach

An iterative approach is a method of solving problems by repeating a process or calculation until a certain condition is met. The script describes a brute force iterative method where the interval between the number and 1 is divided into many points, and the method checks each point to find an approximation of the square root. However, this approach is criticized for being slow and inefficient.

💡Midpoint

The midpoint, or 'mid' in the script, is the average of the lower and upper bounds of the interval being considered. It is used in the Bisection method to determine the next point of interest in the search for the square root. The script explains that by comparing the square of the midpoint with the original number, the method can decide whether to narrow the search to the left or right half of the interval.

💡Interval

In the context of the Bisection method, an interval refers to the range of values between a lower and upper bound within which the solution is sought. The script describes how the interval is initially set between the given number and 1, and then repeatedly halved to narrow down the search for the square root.

💡Convergence rate

The convergence rate of an algorithm refers to how quickly it approaches the solution as iterations progress. The script mentions that while the Bisection method has a slower convergence rate compared to other methods like Heron's method, its convergence is more straightforward to analyze, making it a preferred choice for certain applications.

💡Binary search

Binary search is another term for the Bisection method, especially when applied to discrete problems such as searching for a specific value in a sorted list. The script notes that the Bisection method, also known as binary search, is efficient because it halves the search interval with each iteration, quickly reducing the error in the approximation.

💡Approximation error

Approximation error is the difference between the approximate value and the actual value. In the script, the approximation error is discussed in terms of how it decreases with each iteration of the Bisection method. It is calculated as the length of the search interval divided by 2, which becomes smaller with each iteration, indicating that the method quickly converges to the true square root.

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.