We know how to manually solve quadratic equations to find zero.
Step 0
Suppose you want to find two points where this test holds:
f(x_1) f(x_2) < 0
This tests for two points that enclose a zero.
If we find these two points, we can squeeze-in on the midpoint (x_3) to find the zero.
Step 1: Get midpoint
x_i = \frac{x_{i-1} + x_{i-2}}{2}
Step 2: Have we found the zero?
If:
f(x_i) = 0 \\ \text{ or } \\ |x_{i-2} - x_{i-1}| < \epsilon
We can x_i is the zero if it literally is zero, or it is within our acceptable range of error.
Step 3: Shrink window
If f(x_i) * f(x_{i - 1}) > 0 then
x_{i-1} = x_{i-2}
Step 4: Loop
Now, go to Step 1
Example
f(x) = 3x^2 -4x + 1
Step 0:
x_0 = 0.5, x_1 = 1.8
f(x_0) = -0.25 \times 3.53 < 0
Iteration 1:
x_2 = \frac{x_1 + x_0}{2} = 1.15
f(1.15) = 0.3675
Not zero or in acceptabe range, so we’ll shrink.
x_i = 0.5
Iteration 2:
x_3 = \frac{x_1 + x_2}{2} = \frac{0.5 + 1.15}{2} = 0.825
f(0.825) = -0.258125
Shrink again.
Iteration 3:
x_4 = \frac{x_3 + x_2}{2} = \frac{0.825 + 1.15}{2} = 0.9875
f(x_4) = f(0.9875) = - 0.02453125
Shrink again
$ x_3 = 1.15 $
Iteration 4:
x_5 = \frac{x_3 + x_4}{2} = \frac{0.9875 + 1.15}{2} = 1.06875
f(x_5) = f(1.06875) = 0.1516796875
We just lost the zero!
Problems
This problem is very slow, and kinda sucks.
Next class, Newton’s algorithm. We go from needing 100 iterations to like 5.
x = x_0 - \frac{f(x_0)}{f'(x_0)}
x_i = x_{i-1} - \frac{f(x_{i-1})}{f'(x_{i-1})}