Question

In lecture 3, Dr Guttag goes through using the bisection method to calculate a square root. I understand that we can predict the number of iterations the bisection method will take to arrive at an answer by setting epsilon = (upper bound - lower bound) / 2^k

Since we know epsilon and both bounds we solve for k. However, when he does this calculation at the end of lecture three (around the 42 minute mark), he uses epsilon^2 instead of epsilon. Can anyone explain to me the mathematical reason for this?

Thank you in advance.

Answer 1

i believe its a way to have epsilon always positive...i mean since epsilon could be positive and negative....or i could be wrong...need to see the lecture for it:P but i have no time atm.

Answer 2

Thank you very much for your response. Perhaps if I give more information it may help elaborate my question without anyone having to watch the video to answer it.

In the lecture, the professor covers the bisection method. Specifically, he uses the method to estimate square roots. He explains how we can predict the number of iterations the bisection method will require to converge on the root. From other readings, my understanding is that the equation for this calculation is

\[\epsilon = | b - a | / 2^k\]

Where epsilon is the predetermined accuracy we desire, a and b are the end points of the range that contains the root we are searching for, and k is the number of iterations.

In the example in the lecture, the professor uses the method to calculate the square root of 12,345.
--- He sets epsilon = 0.01
--- He defines the range as 0 --> 12345
--- He runs his code, it takes 26 iterations to arrive at an answer of 111.08.
--- He then asks, "Why 26?", and goes on to discuss how one can go about predicting the number of iterations we can expect, via the above equation. This is where he loses me, for
instead of doing
\[0.01 = | 0 - 12345 | / 2^k\]he does
\[(0.01)^2 = | 0 - 12345 | / 2^k\]Why is it correct to use epsilon^2 instead of epsilon in this case?