BisectionMethod.yml

#Bisection Method

#Type 1: Line and a pause
#Type 2: Input
#Type 3: Number
#Type 4: No pause in line
#Type 5: Graph
#Type 6: Video Links
#Type 7: 2 Variable Array
#Type 8: Shaded Area Pair


l01:
  id: 1
  content: "Bisection Method is a type of Bracketing Method"
  type: 1

l02:
  id: 2
  content: "It is based on the idea of continuity of a function"
  type: 1

l03:
  id: 3
  content:
    message: "Each continuous function follows the Intermediate Value Theorem. We have a video for you if you need a refresher on IVT"
    link: https://youtu.be/ufFla_aAHFU
  type: 6

l04:
  id: 4
  content: "In Bisection Method, we first start with an interval where we know a root exists"
  type: 1


l06:
  id: 1
  content: "Let us consider x^3 - x -2"
  type: 1

l07:
  id: 7
  content:
    y:  x^3 -x-2
    xmin: -5
    xmax: 5
    hold: 1
    hold: 1
  type: 5

l08:
  id: 8
  content: "By plotting the graph, we can see that a root exists between -2 and 2"
  type: 1

l11:
  id: 11
  content:
    x1: -2
    x2: 2
    hold: 1
    hold: 1
  type: 5

l18:
  id: 18
  content: "But, the root can be ANYWHERE between -2 and +2"
  type: 1

l19:
  id: 19
  content: "And we want to reduce this interval of uncertainty"
  type: 1

l20:
  id: 20
  content: "So we divide the interval in the middle"
  type: 1

l99: 
  id: 99
  content:
    x1: 0 
    hold: 1
  type: 5

l21:
  id: 21
  content: "This is where the 'bi-' part comes from. Bisection = Two sections. It is sometimes also called the interval halving method"
  type: 1

l97:
  id: 97
  content: "Now we'll check if the midpoint is the root. We can see that f(0)= -2. So it is not a root."
  type: 1

l98:
  id: 98
  content: "What now?"
  type: 1

l40:
  id: 40
  content: "We repeat this procedure and we stop when the mid-point we have chosen is a root of the function"
  type: 1

l41:
  id: 41
  content: "But that is seldom the case. Yeah, bummer."
  type: 1 

l42:
  id: 42
  content: "So we repeat the whole process till the interval is small enough"
  type: 1 

l43:
  id: 43
  content: "...or till we find the root"
  type: 1 

l44:
  id: 44
  content: "....which we usually don't"
  type: 1

l45:
  id: 45
  content: "....so we stop the process when we are satisfied"
  type: 1 

l46:
  id: 46
  content: "Well, yeah"
  type: 1

l47:
  id: 47
  content: "What do we mean by satisfied?"
  type: 1

l48:
  id: 48
  content: "An example shall explain"
  type: 1


a53:
  id: 54
  content: "Note: we'll get to the mathematics of Bisection Method in a while. Feel the method first though."
  type: 1

l49:
  id: 49
  content: "Let us see the solution for the next 5 iterations."
  type: 1 


c24:
  id: 56
  content:
    x1: -2
    x2: 0
    x3: 2
  type: 8


a51:
  id: 51
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 0
    x2: 2
    hold: 1
  type: 5

a03: 
  id: 99
  content:
    x1: 1 
    hold: 1
  type: 5

b04:
  id: 56
  content:
    x1: 0
    x2: 1
    x3: 2
  type: 8

l51:
  id: 51
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1
    x2: 2
    hold: 1
  type: 5

a04: 
  id: 99
  content:
    x1: 1.5 
    hold: 1
  type: 5

b06:
  id: 56
  content:
    x1: 1
    x2: 1.5
    x3: 2
  type: 8

a05:
  id: 52
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1.5
    x2: 2
    hold: 1
  type: 5

b49:
  id: 49
  content: "How do we know where the root lies? We'll get to that later"
  type: 1 

a06: 
  id: 99
  content:
    x1: 1.75 
    hold: 1
  type: 5

b07:
  id: 56
  content:
    x1: 2
    x2: 1.75
    x3: 1.5
  type: 8

l53:
  id: 53
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1.500
    x2: 1.750
    hold: 1
  type: 5

d07: 
  id: 99
  content:
    x1: 1.625 
    hold: 1
  type: 5

b08:
  id: 56
  content:
    x1: 1.750
    x2: 1.625
    x3: 1.5
  type: 8

l54:
  id: 54
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1.625
    x2: 1.500
    hold: 1
  type: 5

a77: 
  id: 99
  content:
    x1: 1.5625 
    hold: 1
  type: 5

b09:
  id: 56
  content:
    x1: 1.6250
    x2: 1.5625
    x3: 1.5000
  type: 8

l56:
  id: 56
  content:
    y: x^3 - x -2
    xmin: 1.400
    xmax: 1.600
    x1: 1.5623
    x2: 1.5
    hold: 1
  type: 5

l55:
  id: 55
  content: "Now we can stop. NO, but surely we must go on. Let's adjust the graph scales to see what happens"
  type: 1

d08: 
  id: 99
  content:
    x1: 1.53125 
    hold: 1
  type: 5

b10:
  id: 56
  content:
    x1: 1.5625
    x2: 1.53125
    x3: 1.5
  type: 8

l57:
  id: 57
  content:
    y: x^3 - x -2
    xmin: 1.4
    xmax: 1.6
    x1: 1.53125
    x2: 1.5
    hold: 1
  type: 5

d09: 
  id: 99
  content:
    x1: 1.515625 
    hold: 1
  type: 5

b11:
  id: 56
  content:
    x1: 1.5
    x2: 1.515625
    x3: 1.53125
  type: 8

l58:
  id: 58
  content:
    y: x^3 - x -2
    xmin: 1.4
    xmax: 1.6
    x1: 1.515625 
    x2: 1.53125
    hold: 1
  type: 5

a07: 
  id: 99
  content:
    x1: 1.523438 
    hold: 1
  type: 5

b12:
  id: 56
  content:
    x1: 1.53125
    x2: 1.523438
    x3: 1.515625
  type: 8

l59:
  id: 59
  content:
    y: x^3 - x -2
    xmin: 1.4
    xmax: 1.6
    x1: 1.515625 
    x2: 1.523438
    hold: 1
  type: 5

a07: 
  id: 99
  content:
    x1: 1.519531 
    hold: 1
  type: 5

b13:
  id: 56
  content:
    x1: 1.515625
    x2: 1.519531
    x3: 1.523438
  type: 8

l60:
  id: 60
  content:
    y: x^3 - x -2
    xmin: 1.4
    xmax: 1.6
    x1: 1.519531 
    x2: 1.523438 
    hold: 1
  type: 5

a08: 
  id: 99
  content:
    x1: 1.521484 
    hold: 1
  type: 5

b14:
  id: 56
  content:
    x1: 1.523438
    x2: 1.521484
    x3: 1.519531
  type: 8

l62:
  id: 62
  content:
    y: x^3 - x -2
    xmin: 1.519
    xmax: 1.522
    x1: 1.519531 
    x2: 1.521484 
    hold: 1
  type: 5


l61:
  id: 61
  content: "You would say, now we can stop. No, let's go further. Notice the adjusted scale"
  type: 1

a09: 
  id: 99
  content:
    x1: 1.520508 
    hold: 1
  type: 5

d15:
  id: 56
  content:
    x1: 1.519531
    x2: 1.520508
    x3: 1.524840
  type: 8

l63:
  id: 63
  content:
    y: x^3 - x -2
    xmin: 1.519
    xmax: 1.522
    x1: 1.520508 
    x2: 1.521484 
    hold: 1
  type: 5

a10: 
  id: 99
  content:
    x1: 1.520996 
    hold: 1
  type: 5

b16:
  id: 56
  content:
    x1: 1.520508
    x2: 1.520996
    x3: 1.521484
  type: 8

l64:
  id: 64
  content:
    y: x^3 - x -2
    xmin: 1.519
    xmax: 1.522
    x1: 1.520996 
    x2: 1.521484 
    hold: 1
  type: 5

a11: 
  id: 99
  content:
    x1: 1.521240 
    hold: 1
  type: 5

b17:
  id: 56
  content:
    x1: 1.520996
    x2: 1.521240
    x3: 1.521484
  type: 8

l65:
  id: 65
  content:
    y: x^3 - x -2
    xmin: 1.519
    xmax: 1.522
    x1: 1.521240 
    x2: 1.521484 
    hold: 1
  type: 5

a12: 
  id: 99
  content:
    x1: 1.521362 
    hold: 1
  type: 5

b18:
  id: 56
  content:
    x1: 1.521240
    x2: 1.521362
    x3: 1.521484
  type: 8

l66:
  id: 66
  content:
    y: x^3 - x -2
    xmin: 1.519
    xmax: 1.522
    x1: 1.521362 
    x2: 1.521484
    hold: 1
  type: 5

a13: 
  id: 99
  content:
    x1: 1.521423 
    hold: 1
  type: 5

d19:
  id: 56
  content:
    x1: 1.521484
    x2: 1.521423
    x3: 1.521368
  type: 8

l68:
  id: 68
  content:
    y: x^3 - x -2
    xmin: 1.5213
    xmax: 1.5215
    x1: 1.521362 
    x2: 1.521423 
    hold: 1
  type: 5

l67:
  id: 67
  content: "What about now? EVEN MORE. Keep looking at the scale"
  type: 1

a14: 
  id: 99
  content:
    x1: 1.521393 
    hold: 1
  type: 5

d20:
  id: 56
  content:
    x1: 1.521423
    x2: 1.521393
    x3: 1.521392
  type: 8

l69:
  id: 69
  content:
    y: x^3 - x -2
    xmin: 1.5213
    xmax: 1.5215
    x1: 1.521362 
    x2: 1.521393 
    hold: 1
  type: 5

a15: 
  id: 99
  content:
    x1: 1.521378 
    hold: 1
  type: 5

b21:
  id: 56
  content:
    x1: 1.521362
    x2: 1.521378
    x3: 1.521393
  type: 8

l70:
  id: 70
  content:
    y: x^3 - x -2
    xmin: 1.5213
    xmax: 1.5215
    x1: 1.521378 
    x2: 1.521393 
    hold: 1
  type: 5

a16: 
  id: 99
  content:
    x1: 1.521385 
    hold: 1
  type: 5

b22:
  id: 56
  content:
    x1: 1.521393
    x2: 1.521385
    x3: 1.521378
  type: 8

l71:
  id: 71
  content:
    y: x^3 - x -2
    xmin: 1.5213
    xmax: 1.5215
    x1: 1.521378 
    x2: 1.521385
    hold: 1
  type: 5

a17: 
  id: 99
  content:
    x1: 1.521381 
    hold: 1
  type: 5

b23:
  id: 56
  content:
    x1: 1.521385
    x2: 1.521381
    x3: 1.521378
  type: 8

l72:
  id: 72
  content:
    y: x^3 - x -2
    xmin: 1.5213
    xmax: 1.5215
    x1: 1.521378 
    x2: 1.521381
    hold: 1
  type: 5

d18: 
  id: 99
  content:
    x1: 1.521379 
    hold: 1
  type: 5

d24:
  id: 56
  content:
    x1: 1.521378
    x2: 1.521379
    x3: 1.521381
  type: 8

l74:
  id: 74
  content:
    y: x^3 - x -2
    xmin: 1.52137
    xmax: 1.52139
    x1: 1.521379 
    x2: 1.521381 
    hold: 1
  type: 5

l73:
  id: 73
  content: "It's becoming pointless. But let's still go further. Look at the scales again"
  type: 1

a19: 
  id: 99
  content:
    x1: 1.521380 
    hold: 1
  type: 5

b24:
  id: 56
  content:
    x1: 1.521381
    x2: 1.521380
    x3: 1.521379
  type: 8

l75:
  id: 75
  content:
    y: x^3 - x -2
    xmin: 1.52137
    xmax: 1.52139
    x1: 1.521379 
    x2: 1.521380 
    hold: 1
  type: 5

a20: 
  id: 99
  content:
    x1: 1.521380 
    hold: 1
  type: 5

l79:
  id: 79
  content: "Okay let's stop here"
  type: 1

l80:
  id: 80
  content: "What is small enough? So when do we stop?"
  type: 1

l81:
  id: 81
  content: "Whenever you've found the solution to sufficient decimal places"
  type: 1

l82:
  id: 82
  content: "Sometimes we get lucky and find the exact root (At a point when f(c) = 0)  THis is the case with finite non-repeating roots"
  type: 1

l83:
  id: 83
  content: "Otherwise, we are satisfied when the solution is correct up to a few decimal places"
  type: 1

l84:
  id: 84
  content: "For infinite decimal numbers, there will always be some error/tolerance limit"
  type: 1

l85:
  id: 85
  content: "It will take infinite time to find inifite decimal points so we say after a stage:  'This is enough for our work'"
  type: 1

l86:
  id: 86
  content: "And the error is too small to be neglected for practical purposes"
  type: 1

l87:
  id: 87
  content: "The biggest error there can be will be the length of the interval"
  type: 1

l88:
  id: 88
  content: "To learn more about error analysis, go to http://en.wikipedia.org/wiki/Bisection_method#Analysis"
  type: 1


l09:
  id: 09
  content: "Plotting graphs is a great way to figure out your initial guess. Here our initial guess was 0, the midpoint of the interval [-2,2] we chose."
  type: 1

# l97:
#   id: 96
#   content: "But we cannot always draw the graph to find our initial guess. It's too time-consuming. So let us use some math."
#   type: 1

# l14:
#   id: 14
#   content: "A quick way to figure out if a root lies in the interval (or bracket) is to see if the product of values of (continuous) polynomial (or function) at both end points is less than zero or not"
#   type: 1

l15:
  id: 15
  content: "i.e. if the interval is [a,b] then f(a).f(b) < 0 tells us that the value of the function at a and at b is opposite"
  type: 1

l17:
  id: 17
  content: "Since the function has opposite signs at the end points, and since it is continuous, by Intermediate Value Theorem, it must have passed through a point at which y=0 in the interval [a,b]"
  type: 1

l96:
  id: 96
  content: "Hence if f(a).f(b) <0, then at least one root lies in the interval [a,b]"
  type: 1

l12:
  id: 12
  content: "f(-2) = -ve and f(2) = +ve in our example. f(-2).f(2) = -ve."
  type: 1


l24:
  id: 24
  content: "We split the interval into two at the midpoint 0."
  type: 1


l22:
  id: 22
  content: "Now we know that either the root will lie in the left half or in the right half,  since we chose the bracket in such a way that there is just one root."
  type: 1

l23:
  id: 23
  content: " Let's try it out."
  type: 1


l26:
  id: 26
  content:
    message: "Will the root be in 1. [-2,0] or in [0,2]?  Hint: Use f(a).f(b) <0"
    answer: 2
  type: 2

l27:
  id: 27
  content: "We can see that f(0) is not zero. So x=0 is not a root"
  type: 1

l28:
  id: 28
  content: "Let's try the process again"
  type: 1

l29:
  id: 29
  content:
    message: "What will be the mid-point this time?"
    answer: 1
  type: 2

l30:
  id: 30
  content:
    message: "Okay! Will the root like in 1. [0,1] or 2. [1,2]?"
    answer: 2
  type: 2

l31:
  id: 31
  content: "You will see that at each step, our interval is getting smaller (by half)"
  type: 1

l32:
  id: 32
  content: "This means our region of uncertainty is decreasing"
  type: 1

l33:
  id: 33
  content: "Looking at the graph makes it easy to determine the new interval we shall be focusing on,  but since this is an algorithm, we need to use a numerical approach"
  type: 1

l34:
  id: 34
  content: "Let c be the midpoint of the interval [a,b] i.e. c=(a+b)/2  and consider the product f(a).f(c)"
  type: 1

l35:
  id: 35
  content:
    message: "If f(a).f(c) < 0 where does the root lie?  1. [a,c] 2. [c,b] 3. At c 4. Cannot be determined"
    answer: 1
  type: 2

l36:
  id: 36
  content:
    message: "What if f(c) = 0 ?  1. [a,c] 2. [c,b] 3. At c 4. Cannot be determined"
    answer: 3
  type: 2

l37:
  id: 37
  content:
    message: "And finally, if f(a).f(c). > 0, where does the root lie?  1. [a,c] 2. [c,b] 3. At c 4. Cannot be determined"
    answer: 2
  type: 2

l38:
  id: 38
  content: "Also, you'll notice that after each iteration, our function value is getting closer to zero"
  type: 1 

e01:
  id: 01
  content: "Let's look at the graph one more time and link it to our numerical method"
  type: 1



f01:
  id: 1
  content: "Let us consider x^3 - x -2 again"
  type: 1

f02:
  id: 7
  content:
    y:  x^3 -x-2
    xmin: -5
    xmax: 5
    hold: 1
    hold: 1
  type: 5


f04:
  id: 11
  content:
    x1: -2
    x2: 2
    hold: 1
  type: 5


g01:
  id: 01
  content: "f(-2) = -ve, f(2) = +ve | f(-2).f(2) = -ve | f(0)= -2 | So root is in [0,2] as f(0).f(2) = -ve"
  type: 4

f08: 
  id: 99
  content:
    x1: 0 
    hold: 1
  type: 5


f11:
  id: 56
  content:
    x1: -2
    x2: 0
    x3: 2
  type: 8


f12:
  id: 51
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 0
    x2: 2
    hold: 1
  type: 5


g02:
  id: 03
  content: "f(0) = -ve, f(2) = +ve | f(0).f(2) = -ve | f(1)= -2 | So root is in [1,2] as f(1).f(2) = -ve"
  type: 4

f13: 
  id: 99
  content:
    x1: 1 
    hold: 1
  type: 5

f14:
  id: 56
  content:
    x1: 0
    x2: 1
    x3: 2
  type: 8

f15:
  id: 51
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1
    x2: 2
    hold: 1
  type: 5


g05:
  id: 05
  content: "f(1) = -ve, f(2) = +ve | f(1).f(2) = -ve | f(1.5)= -0.125 | So root is in [1.5,2] as f(1.5).f(2) = -ve"
  type: 4

f16: 
  id: 99
  content:
    x1: 1.5 
    hold: 1
  type: 5

f17:
  id: 56
  content:
    x1: 1
    x2: 1.5
    x3: 2
  type: 8

f18:
  id: 52
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1.5
    x2: 2
    hold: 1
  type: 5


g06:
  id: 06
  content: "f(1.5) = -ve, f(2) = +ve | f(1.5).f(2) = -ve | f(1.75)= 1.6094 | So root is in [1.5,1.75] as f(1.5).f(1.75) = -ve"
  type: 4

f20: 
  id: 99
  content:
    x1: 1.75 
    hold: 1
  type: 5

f21:
  id: 56
  content:
    x1: 2
    x2: 1.75
    x3: 1.5
  type: 8

f22:
  id: 53
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1.500
    x2: 1.750
    hold: 1
  type: 5


g07:
  id: 7
  content: "f(1.5) = -ve, f(1.75) = +ve | f(1.5).f(1.75) = -ve | f(1.625)= 0.666 | So root is in [1.5,1.625] as f(1.5).f(1.625) = -ve"
  type: 4

f23: 
  id: 99
  content:
    x1: 1.625 
    hold: 1
  type: 5

f24:
  id: 56
  content:
    x1: 1.750
    x2: 1.625
    x3: 1.5
  type: 8

f25:
  id: 54
  content:
    y: x^3 - x -2
    xmin: -5
    xmax: 5
    x1: 1.625
    x2: 1.500
    hold: 1
  type: 5


g08:
  id: 08
  content: "f(1.5) = -ve, f(1.625) = +ve | f(1.5).f(1.625) = -ve | f(1.5625)= 0.2522 | So root is in [1.5,1.5625] as f(1.5).f(1.5625) = -ve"
  type: 4

f26: 
  id: 99
  content:
    x1: 1.5625 
    hold: 1
  type: 5

f27:
  id: 56
  content:
    x1: 1.6250
    x2: 1.5625
    x3: 1.5000
  type: 8

f29:
  id: 55
  content: "Got how things work?"
  type: 1


l90:
  id: 90
  content: "Binary Chopping has one advantage and disadvantage"
  type: 1

l91:
  id: 91
  content: "Advantage: It always works.  If a root has been bracketed, bisection method will always find the root  As long as the equation is of the form f(x) = 0  Note: f(x) = x will stumble the good ol' bisection method  However, this can be corrected by using f(x)-x = 0 as the new equation"
  type: 1

l92:
  id: 92
  content: "Disadvantage: It's slow"
  type: 1

l93:
  id: 93
  content: "It's the one friend you can always depend on  but is so slothful that you will only call him is there is no one else around. "
  type: 1

l94:
  id: 94
  content: "In practical terms  We usually don’t have to use bisection method alone.  We use it along with an open method to make it a rather effective tool."
  type: 1


l10:
  id: 10
  content: "Passing Remark #1: This equation has two complex roots as well but we cannot use bisection method for it. In case you're curious, we use the Lehmer-Schur algorithm, a generalization of the bisection method for the complex plane"
  type: 1



l05:
  id: 5
  content: "Passing Remark #2: it is important to choose your bracket (or interval) in such a way that only one root lies in the interval"
  type: 1


l89:
  id: 89
  content: "Passing Remark #3: Want to find all the roots?  This whole method can be performed on all the brackets to find  all roots of the polynomial (or zeroes of the function)"
  type: 1



l39:
  id: 39
  content: "To Think About: We also use the same algorithm with binary search method.  But there is one difference.  We won't tell you what the answer is. That's for you to think :)"
  type: 1

l16:
  id: 16
  content: "Another thing to Think About: We know there's a bisection method. Could there be a trisection method as well?"
  type: 1