1、 （教育評議會主辦）二分法二分法?三分法三分法?組長組長:吳家發吳家發組員組員:張煒軒張煒軒 蔡銘耀蔡銘耀 彭榮信彭榮信 潘樂琛潘樂琛 袁旺波袁旺波Winning project in the 2007-08 Mathematics Project Competition引言引言 一元一次方程一元一次方程 例例:非線性的方程非線性的方程 例例:3x 2=10 x6 x+5=0二分法二分法三分法三分法三分捨取法三分捨取法 Fibonacci search Fibonacci search 引言引言 O12xyf(2)f(1)y=f(x)二分法二分法 把區間分半把區間分半解解設設7)f(4 xx0
2、74x二分法二分法(答案準確至4位小數)求區間 內 的根。所求的根為1.6266(準確至4位小數)21 x074x7)f(4xx設步驟abf(a)f(m)f(b)111.5221.51.75231.51.6251.75141.6265869151.626647951.626708985151.6265869151.6266174331.62664795161.6265869151.6266021741.626617433二分法二分法二分法的缺點二分法的缺點 運算運算多多 步驟步驟多多三分法三分法3abbxn3abaxmabxmxn第第 點點 =23第第 點點 =13三分法三分法O12xyf(2
3、)f(1)y=f(x)三分法三分法3abaxm3abbxn步驟abf(a)f(xm)f(xn)f(b)111.333331.666672 +21.333331.444441.555561.66667 +31.555561.592591.629631.66667 +41.592591.604941.617281.62963 +51.617281.62141.625511.62963 +61.625511.626891.628261.62963+71.625511.625971.626431.62689 +81.626431.626581.626731.62689+91.626431.626481
4、.626531.62658 +101.626531.626551.626561.62658 +所求的根為1.6266(準確至4位小數)求區間 內 的根。(準確至4位小數)21 x074x7)f(4 xx設二分法和三分法比較二分法和三分法比較區間減少速度區間減少速度 二分法每次能縮減剩二分法每次能縮減剩 ，三分法每次縮減剩，三分法每次縮減剩 ，2131不論不論 n 是多少是多少,nn3121所以，三分法所須步驟所以，三分法所須步驟明顯較少明顯較少 121131221231步驟二分法三分法12.nn21n31.二分法：二分法：二分法和三分法比較二分法和三分法比較步驟的量步驟的量 三分法：三分法：二
5、分法需二分法需 個步驟，三分法則需個步驟，三分法則需 個步驟。個步驟。2loglogx3loglogx2logloglog2log121xnxxnn3logloglog3log131xnxxnn設經設經n步驟後，區間為原有的步驟後，區間為原有的x1二分法變三分法步驟百分改變：二分法變三分法步驟百分改變：二分法和三分法比較二分法和三分法比較%1002loglog2loglog3loglogxxx 36.9%三分法的優點三分法的優點 步驟步驟比二分法比二分法少少三分法的缺點三分法的缺點 較二分法較二分法複雜複雜，計算，計算步驟繁複步驟繁複 較較容易出錯容易出錯二分法和三分法比較二分法和三分法比較)
6、f(x二分法和三分法比較二分法和三分法比較二分法二分法三分三分法法完成的步驟完成的步驟兩個兩個一個一個計算計算 的值的值一次一次兩次兩次區間減少區間減少50%50%66.7%66.7%三分法三分法並未完美並未完美，三分捨取法三分捨取法 二分法和三分法比較二分法和三分法比較我們再為三分法作出改良，我們再為三分法作出改良，三分捨取法三分捨取法 捨遠捨遠0 取近取近0三分捨取法三分捨取法三分捨取法三分捨取法Oabxyf(b)f(a)y=f(x)Oxyy=f(x)f(a)a bf(b)三分捨取法三分捨取法所求的根為1.6266(準確至4位小數)求區間 內 的根。(答案準確至4位小數)設 21 x074
7、x7)f(4 xx3abaxm3abbxn步驟abf(a)f(xm)f(xn)f(b)111.333331.666672-6-3.839540.71611921.333331.555561.66667-3.83954-1.144730.7161131.555561.59261.629631.66667-1.14473-0.566800.052710.7161141.59261.617291.62963-0.56680-0.158500.0527151.617291.625521.62963-0.15850-0.018170.0527161.625521.626891.62963-0.01817
8、0.005400.0527171.625521.626431.62689-0.01817-0.002520.0054081.626431.626581.62689-0.002520.000060.0054091.626431.626531.62658-0.00252-0.000800.00006101.626531.626561.62658-0.00080-0.000290.000061.626561.62658-0.000290.00006三分捨取法三分捨取法 在在三分捨取法三分捨取法 求區間求區間 內內 的根這題目中的根這題目中:21 x074x二分法計算了二分法計算了次函數值次函數值三分
9、法計算了三分法計算了次函數值次函數值三分捨取法計算了三分捨取法計算了次函數值次函數值三分捨取法三分捨取法 所求的根為1.6266(準確至4位小數)求區間 21 x074x3abaxm3abbxn步驟abf(a)f(xm)f(xn)f(b)111.333331.666672-6-3.839540.71611921.333331.555561.66667-3.83954-1.144730.7161131.555561.59261.629631.66667-1.14473-0.566800.052710.7161141.59261.617291.62963-0.56680-0.158500.0527
10、151.617291.625521.62963-0.15850-0.018170.0527161.625521.626891.62963-0.018170.005400.0527171.625521.626431.62689-0.01817-0.002520.0054081.626431.626581.62689-0.002520.000060.0054091.626431.626531.62658-0.00252-0.000800.00006101.626531.626561.62658-0.00080-0.000290.000061.626561.62658-0.000290.00006
11、的根。(答案準確至4位小數)設 內 7)f(4 xx我們計算出，我們計算出，試試一一點的實驗概率為點的實驗概率為 。試試二二點的實驗概率為點的實驗概率為 。三分捨取法三分捨取法 3525二分法：二分法：三分法：三分法：三分捨取法：三分捨取法：三分捨取法三分捨取法 xxlog32.32loglogxxlog19.43loglog2xxxlog93.2523loglog2533loglog%12%100log32.3log32.3log93.2xxx百分改變：百分改變：計算函數的次數:可見，三分捨取法是眾多方法中計算量可見，三分捨取法是眾多方法中計算量最少最少的。的。三分捨取法三分捨取法 所以所以
12、,三分捨取法是三分捨取法是成功成功的的 三分捨取法的捨取原則三分捨取法的捨取原則先試較接近先試較接近0的點。的點。多分捨取法多分捨取法 For a search using n function evaluations,the optimal method is to divide the interval into ratio using the first n Fibonacci numbersIf n is large,we may use the golden section search instead,where the interval is always divided using the golden ratioOptimal Search MethodOptimal Search Method完完
