4. Mètode de la bisecció

El mètode de la bisecció és un algorisme de cerca d’arrels d’una funció contínua en un interval. L’algorisme defineixen tres successions \(a_n \le r_n \le b_n\) que convergeixen a la mateixa arrel, per \(n > 0\):

\[\begin{split}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}\end{split}\]

Els valors inicials són:

\[a_0 := a,\quad b_0:=b\]

Dissenya la funció següent i desa-la al mòdul biseccio (fitxer biseccio.py).

biseccio.succ_biseccio(f, a, b, eps)

Calcula la successió \((a_i, b_i)\) per \(0 \le i \le n\) fins al primer \(n\) que compleixi \(|a_n - b_n| < \text{eps}\).

Paràmetres:

f (function) – funció de la qual volem trobar un zero a l’interval \([a, b]\)

Tipus de retorn:

list(tuple)

Retorna:

llista de les tuples \((a_i, b_i)\)

Per exemple:

>>> def f1(x):
...     return 2*x - 6
>>> eps = 1e-3

>>> c = succ_biseccio(f1, 2.9, 3.15, eps)

Valors arrodonits dels extrems dels intervals.

>>> [(round(e, 3), round(d, 3)) for e, d in c]
[(2.9, 3.15), (2.9, 3.025), (2.962, 3.025), (2.994, 3.025), (2.994, 3.009), (2.994, 3.002), (2.998, 3.002), (3.0, 3.002), (3.0, 3.001)]

Només el darrer interval té una longitud més petita que eps.

>>> [abs(e - d) < eps for e, d in c] == [False]*8 + [True]
True

El punt mig del darrer interval s'acosta prou al zero de la funció en
l'interval.

>>> e, d = c[-1]
>>> f1((e + d)/2) < eps
True

Disposes de més tests al fitxer test-succ_biseccio.txt.

Nota

El paràmetre f és una funció i es crida en el cos de la funció succ_biseccio() amb la sintaxi habitual: f(a) per exemple.