# interval halving converges linearly

###### Theorem 1.

The interval halving algorithm converges linearly.

###### Proof.

To see that interval halving (or bisection) converges linearly we use the alternative definition of linear convergence that says that $$ for some constant $1>c>0$.

In the case of interval halving, $|{x}_{i+1}-{x}_{i}|$ is the length of the interval^{} we should search for the solution in and has ${x}_{i+2}$ as its midpoint^{}. We have then that this interval has half the length of the previous interval which means, ${\mathrm{\u0e50\x9d\x91\x99\u0e50\x9d\x91\x92\u0e50\x9d\x91\x9b\u0e50\x9d\x91\x94\u0e50\x9d\x91\u0e01\u0e42\x84\x8e}}_{i+1}=\frac{1}{2}\u0e42\x81\u0e02{\mathrm{\u0e50\x9d\x91\x99\u0e50\x9d\x91\x92\u0e50\x9d\x91\x9b\u0e50\x9d\x91\x94\u0e50\x9d\x91\u0e01\u0e42\x84\x8e}}_{i}$. Thus $c=1/2$ and we have exact linear convergence.
โ

Title | interval halving converges linearly |
---|---|

Canonical name | IntervalHalvingConvergesLinearly |

Date of creation | 2013-03-22 14:21:02 |

Last modified on | 2013-03-22 14:21:02 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 14 |

Author | rspuzio (6075) |

Entry type | Theorem |

Classification | msc 49M15 |