finds where function becomes 0 in [a,b] using bolzano >>> bisection(lambda x: x ** 3 - 1, -5, 5) 1.0000000149011612 >>> bisection(lambda x: x ** 3 - 1, 2, 1000) Traceback (most recent call last): ... ValueError: could not find root in given interval. >>> bisectio
(function: Callable[[float], float], a: float, b: float)
| 2 | |
| 3 | |
| 4 | def bisection(function: Callable[[float], float], a: float, b: float) -> float: |
| 5 | """ |
| 6 | finds where function becomes 0 in [a,b] using bolzano |
| 7 | >>> bisection(lambda x: x ** 3 - 1, -5, 5) |
| 8 | 1.0000000149011612 |
| 9 | >>> bisection(lambda x: x ** 3 - 1, 2, 1000) |
| 10 | Traceback (most recent call last): |
| 11 | ... |
| 12 | ValueError: could not find root in given interval. |
| 13 | >>> bisection(lambda x: x ** 2 - 4 * x + 3, 0, 2) |
| 14 | 1.0 |
| 15 | >>> bisection(lambda x: x ** 2 - 4 * x + 3, 2, 4) |
| 16 | 3.0 |
| 17 | >>> bisection(lambda x: x ** 2 - 4 * x + 3, 4, 1000) |
| 18 | Traceback (most recent call last): |
| 19 | ... |
| 20 | ValueError: could not find root in given interval. |
| 21 | """ |
| 22 | start: float = a |
| 23 | end: float = b |
| 24 | if function(a) == 0: # one of the a or b is a root for the function |
| 25 | return a |
| 26 | elif function(b) == 0: |
| 27 | return b |
| 28 | elif ( |
| 29 | function(a) * function(b) > 0 |
| 30 | ): # if none of these are root and they are both positive or negative, |
| 31 | # then this algorithm can't find the root |
| 32 | raise ValueError("could not find root in given interval.") |
| 33 | else: |
| 34 | mid: float = start + (end - start) / 2.0 |
| 35 | while abs(start - mid) > 10**-7: # until precisely equals to 10^-7 |
| 36 | if function(mid) == 0: |
| 37 | return mid |
| 38 | elif function(mid) * function(start) < 0: |
| 39 | end = mid |
| 40 | else: |
| 41 | start = mid |
| 42 | mid = start + (end - start) / 2.0 |
| 43 | return mid |
| 44 | |
| 45 | |
| 46 | def f(x: float) -> float: |