Mètode de la bisecció

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 ${\displaystyle 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.

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

${\displaystyle 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:

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

Es pot provar que les tres successions convergeixen a la mateixa arrel:^[1]

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

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

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

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

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

Prenent límits,

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

L'error comès al realitzar ${\displaystyle n\geq 0}$ iteracions del mètode és^[1]

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

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

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

• Mètode de Newton

• 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.