Added incremental search and bisection methods totutorials.

1 files changed, 86 insertions, 0 deletions

diff --git a/tutorials/module_3/2_roots_optimization.md b/tutorials/module_3/2_roots_optimization.md
index 3a288cc..9734d40 100644
--- a/tutorials/module_3/2_roots_optimization.md
+++ b/tutorials/module_3/2_roots_optimization.md
@@ -2,11 +2,97 @@
 
 Root Finding Methods or non-linear equation solvers.
 
+
+In this section we will cover four different methods to find a root of a function. Let us take a step back and think algorithmically. To find a root numerically, we can implement a search algorithm. 
+
+Let's consider a phone book - a database of names and numbers sorted alphabetically by last name. Our goal is to find the phone number of James Watt (our root). We could make an algorithm that starts at the the first page, checks to see if the current name equals our target (Watt), if it doesn't, check the next entry. This is method is called *incremental search*. As you may see, this can take very long if the database is very large.
+
+> [!NOTE] Example Phonebook Database Entries
+> **A** – Archimedes  
+> **B** – Bernoulli
+> **C** – Curie
+> **D** – Darwin
+> **E** – Einstein
+> **F** – Feynman
+> **G** – Galileo
+> **H** – Hubble
+> **I** – Ibn Sina
+> **J** – Joule
+> **K** – Kelvin
+> **L** – Leonardo
+> **M** – Maxwell
+> **N** – Newton 
+> **O** – Oppenheimer 
+> **P** – Pascal
+> **Q** – Quetelet
+> **R** – Röntgen
+> **S** – Schrödinger
+> **U** – Urey
+> **V** – Volta
+> **W** – Watt
+> **X** – Xenophon 
+> **Y** – Yukawa
+> **Z** – Zuse
+
+Another approach may be to index the book and jump straight to the 'W' names however this requires two steps. Let us introduce *Bisection*.
+
 ## Incremental Search
+Incremental search
+
+
 
 ## Bisection
+This method start by sectioning the database into two halves. We can do this with a phone book by simply opening it in the middle of the book. In our data set, we have find the middle entry to be 'M - Maxwell'. Since all names are sorted alphabetically we can conclude that we will find our target in the second half, essentially eliminating the first half. Doing this a second time gives us our new midpoint 'S – Schrödinger' and a third time get us to our target 'W - Watt'. In only 3 iterations we have reached out target goal. This is a huge improvement from the Incremental search (22 iterations) versus our new 3 iterations.
+
+This exact same concept can be applied to finding roots of functions. Instead of comparing strings we are comparing floats. For computers this is a lot easier to do. Take a moment to  think about how you would program this.
+
+```python
+import numpy as np
+
+def my_bisection(f, a, b, tol): 
+    # approximates a root, R, of f bounded 
+    # by a and b to within tolerance 
+    # | f(m) | < tol with m the midpoint 
+    # between a and b Recursive implementation
+    
+    # check if a and b bound a root
+    if np.sign(f(a)) == np.sign(f(b)):
+        raise Exception(
+         "The scalars a and b do not bound a root")
+        
+    # get midpoint
+    m = (a + b)/2
+    
+    if np.abs(f(m)) < tol:
+        # stopping condition, report m as root
+        return m
+    elif np.sign(f(a)) == np.sign(f(m)):
+        # case where m is an improvement on a. 
+        # Make recursive call with a = m
+        return my_bisection(f, m, b, tol)
+    elif np.sign(f(b)) == np.sign(f(m)):
+        # case where m is an improvement on b. 
+        # Make recursive call with b = m
+        return my_bisection(f, a, m, tol)
+```
+
+### Example
+
+```python
+f = lambda x: x**2 - 2
+
+r1 = my_bisection(f, 0, 2, 0.1)
+print("r1 =", r1)
+r01 = my_bisection(f, 0, 2, 0.01)
+print("r01 =", r01)
+
+print("f(r1) =", f(r1))
+print("f(r01) =", f(r01))
+```
 
 ## Modified Secant
+We can do better.
+
 
 ## Newton-Raphson