lizfcm/notes/Oct-18.org

Error Analysis Of Bisection Root Finding:

e_0 ≤ b - a = b_0 - a_0 e_1 ≤ b_1 - a_1 = 1/2(b_0 - a_0) e_2 ≤ b_2 - a_2 = 1/2(b_1 - a_1) = (1/2)^2(b_0 - a_0) e_k ≤ b_k - a_k = 1/2(b_k-1 - a_k-1) = ⋯ = (1/2)^k (b_0 - a_0)

e_k ≤ (1/2)^k (b_0 - a_0) = tolerance ⇒ log(1/2^k) + log(b_0 - a_0) = log(tolerance) ⇒ k log(1/2) + log(tolerance) - log(b_0 - a_0) ⇒ k log(1/2) = log(tolerance / (b_0 - a_0)) ⇒ k ≥ log(tolerance / (b_0 - a_0)) / log(1/2)

The Bisection Method applied to an interval [a, b] for a continous function will reduce the error each time through by at least one half.

xk+1 - x_k

≤ 1/2

x_k - x^*