SharedTA Sandbox / Hao's Sandbox / Slides / Lab 09.sagewsOpen in CoCalc
Author: HAO LEE
Views : 5

Bisection Search

Number Guessing Game

  • The host have a number in mind
  • Audiance try to guess the number
  • When the auduance guess a number, the host will answer: "too high" or "too low"


    If this number ranges from 1 to 100, can all of the students in our class participate?

No, if all the students need to participate, the number need to be larger than 2^19


Describe what has happened!

Pseudocode

higherBound = maxRange
lowerBound = minRange
while(Not found)
    1. guess a number within higherBound and lowerBound
    2. if(guess number > target)
           higherBound = guess
       else
           lowerBound = guess
    3. if higherBound - lowerBound < some small range
       exit while loop

Bifurcation

Quantitative Change Induces Qualitive Change

Goal: Find the Point Where Number of Eq. Points Change!

r =0.1 fig1 = plot(0.5*x^2/(1+x^2),(x,0,6),color='red') fig2 = plot(r*x,(x,0,6),color='blue') fig1+fig2

How many equilibrium points we have with current r?

assume(x>=0) curFun = 0.5*x^2/(1+x^2)-r*x solve(curFun==0,x) curFun.roots() len(solve(curFun==0,x)) len(curFun.roots())
Error in lines 2-2 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute flags=compile_flags) in namespace, locals File "", line 1, in <module> TypeError: unsupported operand type(s) for *: 'function' and 'sage.symbolic.expression.Expression'

How to get the value?

intPoints = curFun.roots() for i in range(len(intPoints)): float(intPoints[i][0])
0.20871215252208009 4.7912878474779195 0.0

How to Search for Bifurcation

For searching first bifurcation (2 equilibrium points to 3 equilibrium points)

  • Find r that has 3 equilibrium points, set this r as higher bound

  • Find r that has 2 equilibrium points, set this r as lower bound

  • guess a new r in this range

  • if has 3 equilibrium points => update higher bound

  • if has 2 equilibrium points => update lower bound

  • if higher bound is close to lower bound => end

How to guess efficiently?

higherBound = 1 lowerBound = 0.1 assume(x,'real') assume(x>=0) rList=[] while(higherBound-lowerBound>0.0001): # ha ha do your own lab float(rGuess) fig1 = plot(0.5*x^2/(1+x^2),(x,0,5)) fig2 = plot(rGuess*x,(x,0,5)) fig1+fig2
0.25001831054687507

P.S. solve does not always work!

(however, we will not see it in this lab)

r = 0.3 k = 25 solve(r*(1-x/k)-x/(1+x^2),x) find_root(r*(1-x/k)-x/(1+x^2),0,2) find_root(r*(1-x/k)-x/(1+x^2),3,5) find_root(r*(1-x/k)-x/(1+x^2),20,25)
[x == -1/2*(1/27*I*sqrt(9553223) + 6475/27)^(1/3)*(I*sqrt(3) + 1) - 62/3*(-I*sqrt(3) + 1)/(1/27*I*sqrt(9553223) + 6475/27)^(1/3) + 25/3, x == -1/2*(1/27*I*sqrt(9553223) + 6475/27)^(1/3)*(-I*sqrt(3) + 1) - 62/3*(I*sqrt(3) + 1)/(1/27*I*sqrt(9553223) + 6475/27)^(1/3) + 25/3, x == (1/27*I*sqrt(9553223) + 6475/27)^(1/3) + 124/3/(1/27*I*sqrt(9553223) + 6475/27)^(1/3) + 25/3] 0.32789714277901966 3.621997059419165 21.050105797801766

The End!!