Mètode de la bisecció

Algunes iteracions del mètode de la bisecció aplicat 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 a trobar l'arrel o una aproximació d'aquesta.

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 de l'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 a 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 r_{n}\leq b_{n}$:

$r_{n}={\frac {a_{n}+b_{n}}{2}},\quad a_{n+1}={\begin{cases}a_{n}&{\mbox{si }}f(a_{n})\cdot f(r_{n})<0\\r_{n}&{\mbox{si }}f(a_{n})\cdot f(r_{n})>0\end{cases}},\quad b_{n+1}={\begin{cases}b_{n}&{\mbox{si }}f(b_{n})\cdot f(r_{n})<0\\r_{n}&{\mbox{si }}f(b_{n})\cdot f(r_{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 }r_{n}=\lim _{n\to \infty }b_{n}$

Demostració de la convergència

Sigui r una arrel continguda en l'interval [a,b]. L'interval de cerca en el pas n-èssim té longitud

$l_{n}={\frac {b_{n}-a_{n}}{2}}={\frac {\left|b-a\right|}{2^{n}}}$

Com que $r_{n}$ es troba sempre a l'interval de cerca,

$\left|r-r_{n}\right|\leq {\frac {\left|b-a\right|}{2^{n}}}$

Prenent límits,

$\lim _{n\to \infty }|r-r_{n}|=0\rightarrow \lim _{n\to \infty }r_{n}=r$

Fita de l'error

L'error comès al realitzar $n\geq 0$ iteracions del mètode és

$\varepsilon :=|r-r_{n}|<{\frac {b-a}{2^{n+1}}}$

Per aconseguir un error inferior a $\varepsilon$, el nombre d'iteracions $n$ a realitzar ha de ser

$n>{\frac {\ln(b-a)-\ln(\varepsilon )}{\ln(2)}}-1$

Vegeu també

• Mètode de Newton

Bibliografia

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