FilesExpand file tree

master

/

bisection.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (47 loc) · 1.63 KB

master

/

bisection.py

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (47 loc) · 1.63 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

from collections.abc import Callable

def bisection(function: Callable[[float], float], a: float, b: float) -> float:

"""

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.

>>> bisection(lambda x: x ** 2 - 4 * x + 3, 0, 2)

1.0

>>> bisection(lambda x: x ** 2 - 4 * x + 3, 2, 4)

3.0

>>> bisection(lambda x: x ** 2 - 4 * x + 3, 4, 1000)

Traceback (most recent call last):

...

ValueError: could not find root in given interval.

"""

start: float = a

end: float = b

if function(a) == 0: # one of the a or b is a root for the function

return a

elif function(b) == 0:

return b

elif (

function(a) * function(b) > 0

): # if none of these are root and they are both positive or negative,

# then this algorithm can't find the root

raise ValueError("could not find root in given interval.")

else:

mid: float = start + (end - start) / 2.0

while abs(start - mid) > 10**-7: # until precisely equals to 10^-7

if function(mid) == 0:

return mid

elif function(mid) * function(start) < 0:

end = mid

else:

start = mid

mid = start + (end - start) / 2.0

return mid

def f(x: float) -> float:

return x**3 - 2 * x - 5

if __name__ == "__main__":

print(bisection(f, 1, 1000))

import doctest

doctest.testmod()