PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] interval halving (Algorithm)

Interval halving is an efficient method for solving equations. The requirements for using this method are that we have an equation $ f(x)=0$ where $ f(x)$ is a continuous function, and two values $ x_1$ and $ x_2$ such that $ f(x_1)f(x_2)<0$. Since $ f(x_1)$ and $ f(x_2)$ have opposite signs, we know by the intermediate value theorem that there exists a solution $ \hat{x}$ and that $ x_1 \leq \hat{x}\leq x_2$, and with only $ n+1$ function evaluations we can find a shorter interval of length $ \epsilon=\vert x_1-x_2\vert 2^{-n}$ that contains $ \hat{x}$. If we take the solution $ x_{s}=(x_1+x_2)/2$ we get an error $ \vert x_s-\hat{x}\vert< \epsilon$.

Algorithm INTERVALHALVING( $ x_1,x_2,f(x),\epsilon $)
Input: $ x_1, x_2, f(x)$ as above. $ \epsilon$ is the length of the desired interval
Output: A solution to the equation $ f(x)=0$ that lies in an interval of length $ <\epsilon$ . Requires $ f(x_1)f(x_2)<0$

$ start \gets min(x_1,x_2)$
$ end \gets max(x_1,x_2)$
$ middle \gets (start+end)/2$

while $ end-start< \epsilon$
$\textstyle \parbox{\textwidth}{ \textbf{begin}\\ \hspace*{0.4in}\parbox{\textwi... ...extwidth}{$start \gets middle$} $middle \gets (start+end)/2$ }\\ \textbf{end} }$ $ x_s \gets (start+end)/2$ // the solution

The algorithm works by taking an interval $ [x_1,x_2]$ and dividing it into two intervals of equal size. Look at a point in the middle, $ x_m$. If the function changes sign in the interval $ [x_1,x_m]$, that is $ f(x_1)f(x_m)<0$, then by the intermediate value theorem we have a solution in this interval. If not, then the solution is in the interval $ [x_m,x_2]$. Repeat this until you get a sufficiently smal interval.

Interval halving is very useful in that it only requires the function to be continuous. More efficient methods like Newton's method require that the function is differentiable and that we have to have a good starting point. Interval halving has linear convergence while Newton's method has quadratic convergence.



"interval halving" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

Other names:  bisection algorithm

This object's parent.

Attachments:
interval halving converges linearly (Theorem) by rspuzio
Log in to rate this entry.
(view current ratings)

Cross-references: quadratic convergence, linear convergence, differentiable, Newton's method, point, size, algorithm, contains, length, interval, function, solution, intermediate value theorem, opposite, continuous function, equations
There are 2 references to this entry.

This is version 9 of interval halving, born on 2004-04-25, modified 2007-08-22.
Object id is 5804, canonical name is IntervalHalving.
Accessed 4953 times total.

Classification:
AMS MSC: 49M15 (Calculus of variations and optimal control; optimization :: Methods of successive approximations :: Methods of Newton-Raphson, Galerkin and Ritz types)
Pending Errata and Addenda
None.
[ View all 6 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)