Mètode de la bisecció

Algunes iteraciones del métode de la bisecció aplicades en un interval [a₁;b₁]. El punt roig és l'arrel de la funció.

En matemàtiques, el mètode de la bisecció és un algorisme de cerca d'arrels d'una funció contínua en un interval. L'algorisme consisteix en dividir repetidament l'interval en dos subintervals i seleccionar el que conté l'arrel, fins trobar l'arrel o una aproximació de la mateixa.

Introducció

El mètode es basa en el teorema del valor intermedi (TVI), segons el qual, tota funció contínua f en un interval tancat [a,b] s'anul·la en algun punt del interval si els signes de f(a) i f(b) són contraris.

Descripció del mètode:

• Es comprova que $f(a)\cdot f(b)<0$
• Es calcula el punt mitjà m de l'interval [a,b] i s'avalua f(m).
• Si f(m)=0, m és una arrel. Si no, es comprova que f(m) té signe contrari que f(a) ó f(b).
• Es redefineix l'interval [a,b] com [a,m] ó [m,b] segons s'haja determinat en quin d'aquests intervals es produeix un canvi de signe.
• Es repeteix el procés amb l'interval fins arribar a la precisió desitjada.

Si existeixen més d'una arrel, no es pot assegurar a quina d'aquestes convergeix el mètode.

Algorisme

Es defineixen tres successions $a_{n}\leq p_{n}\leq b_{n}$:

$p_{n}={\frac {a_{n}+b_{n}}{2}},\quad a_{n+1}={\begin{cases}a_{n}&{\mbox{si }}f(a_{n})\cdot f(p_{n})<0\\p_{n}&{\mbox{si }}f(a_{n})\cdot f(p_{n})>0\end{cases}},\quad b_{n+1}={\begin{cases}b_{n}&{\mbox{si }}f(b_{n})\cdot f(p_{n})<0\\p_{n}&{\mbox{si }}f(b_{n})\cdot f(p_{n})>0\end{cases}}$

on els valors inicials venen donats per:

$a_{0}:=a,\quad b_{0}:=b$

Es pot provar que les tres successions convergeixen a la mateixa arrel:

$\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }p_{n}=\lim _{n\to \infty }b_{n}$

Demostración de la convergencia

Suponiendo que se cumplen las condiciones iniciales para la puesta en práctica del algoritmo, definimos r como una raíz dentro del intervalo [a, b]. El intervalo de búsqueda en el n-ésimo paso tiene longitud:

Como $r_{n}$, que es la raíz n-ésima calculada, se encuentra siempre dentro del intervalo de búsqueda, tenemos entonces que:

Tomando límites,

Queda demostrado entonces, que si se cumplen las condiciones iniciales del problema, el método de bisección converge al menos, a una de las raíces que se encuentran en el intervalo señalado.

Cota de error

El error cometido tras realizar $n\geq 0$ iteraciones del método de bisección es

Para lograr un error inferior a $\varepsilon$, el número de iteraciones $n$ a realizar debe ser

Bibliografía

• Richard L Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0-534-38216-9.
• Corliss, George (1977), "Which root does the bisection algorithm find?", SIAM Review 19 (2): 325–327, ISSN 1095-7200, DOI 10.1137/1019044