Bisection theorem proof and convergence analysis

A presentation given by me and my class mates in numerical analysis class.

2. Bisection theorem analysis
State and prove the Bisection theorem
Find the error bound of the Bisection method

3. Presented by;
Hamza Nawaz CU-369-2017
Tauseef Ullah CU-358-2017
Salman Khan CU-384-2017
Waqar Ahmad CU-373-2017
Supervisor;
Madam Nudrat

4. Bisection Method a quick overview
Given a continuous function f (??????) on the interval [a , b] with
f (a) ∙ f (b) < 0, there must be a root in (a, b).
To find a root: set [&#3627408462;
1 , &#3627408463;
1] = [a , b].
Set &#3627408464;
1=
&#3627408462;1+&#3627408463;1
2
and compute f (&#3627408464;
1).
i.If f (&#3627408464;
1) = 0, then quit with root &#3627408464;
1 (must be very lucky.)
ii.If (f (&#3627408462;
1) ∙ f (&#3627408464;
1) < 0), then set [&#3627408462;
2 , &#3627408463;
2] = [&#3627408462;
1 , &#3627408464;
1],
iii.Otherwise (f (&#3627408464;
1) ∙ f (&#3627408463;
1) < 0) set [&#3627408462;
2 , &#3627408463;
2] = [&#3627408464;
1 , &#3627408463;
1],
Repeat with &#3627408464;
2=
&#3627408462;2+&#3627408463;2
2

6. State and prove the Bisection theorem
•Statement:
A function f (??????) is continuous on an interval [a, b]
such that f (a) and f (b) have opposite sign, and
the equation f (??????) = 0 has a real root ?????? in (a, b).
If &#3627408464;
??????
∞
??????=0 is the sequence of midpoints of the intervals (which
brackets the root ??????), generated by the Bisection method then,
??????−&#3627408464;
??????≤
&#3627408463;−&#3627408462;
2
??????+1
??????&#3627408476;?????? &#3627408475;=0,1,2,……

7. Further, the sequence &#3627408464;
??????
∞
??????=0 converges to the root ?????? :
lim
??????→∞
&#3627408464;
??????=??????
If there exists a root ?????? in the interval [a, b], then the distance
between any point ?????? in the interval [a, b] and the root is not
greater than the length of the interval, i.e.,
??????−??????≤&#3627408463;−&#3627408462;

8. Given:
A function y = f (??????)
For which f (??????) = f (a) or f (??????) = f (b)
 f (a) ∙ f (b) <0
 f (α) = 0
A sequence &#3627408464;
??????
∞
??????=0 converging to ??????
??????−??????≤&#3627408463;−&#3627408462;
To prove:
1)??????−&#3627408464;
??????≤
&#3627408463;−&#3627408462;
2
??????+1
??????&#3627408476;?????? &#3627408475;=0,1,2,……

2)lim
??????→∞
&#3627408464;
??????=??????

10. •Proof:
If L denotes the length of the recent root-bracketing interval
obtained by the Bisection method then
after first iteration, ??????
1=
1
2
&#3627408463;−&#3627408462;=
&#3627408463;−&#3627408462;
2

and so on,
after nth iteration, ??????
??????=
1
2
&#3627408463;−&#3627408462;
2
??????−1
=
&#3627408463;−&#3627408462;
2
??????

Thus, any point ?????? in the root-bracketing interval after nth iteration is
not farther from the root than the length of the interval. That is,
??????−??????≤
&#3627408463;−&#3627408462;
2
??????

11. Specifically, if ??????=&#3627408464;
??????is the mid point of the most recent interval,
then the root ?????? is lying on either side of &#3627408464;
??????. Therefore,
??????−&#3627408464;
??????≤half of the length of the interval=
1
2
&#3627408463;−&#3627408462;
2
??????

??????−&#3627408464;
?????? =
&#3627408463;−&#3627408462;
2
??????+1

Hence proved.
This relation serves as the absolute error bound (maximum absolute
error) for the Bisection method.

12. Find the error bound of the Bisection method
Let ??????
?????? denotes the error ??????−&#3627408464;
??????. Assuming the error ??????
?????? after nth
iteration be equal to the maximum absolute error, then
??????
??????=
&#3627408463;−&#3627408462;
2
??????+1

??????
??????=
1
2
&#3627408463;−&#3627408462;
2
??????
=
1
2
2
&#3627408463;−&#3627408462;
2
??????−1
…=
1
2
??????
&#3627408463;−&#3627408462;
2
1

??????
??????=
1
2
??????
??????
0

13. Note that, the right hand side of this relation would tend to be
zero as n becomes large.
Hence, the error ??????
?????? approaches zero. That is,
lim
??????→∞
ℇ
??????=lim
??????→∞
??????−&#3627408464;
??????=0
lim
??????→∞
&#3627408464;
??????=??????
Hence proved.
Clearly, the Bisection method always converges.

14. Questions are welcome

15. AlhamdULilah