(教育评议会主办)课件

1、 （教育評議會主辦） 二分法? 三分法?組長:吳家發組員:張煒軒 蔡銘耀 彭榮信 潘樂琛 袁旺波Winning project in the 2007-08 Mathematics Project Competition （教育評議會主辦） 引言 一元一次方程 例:非線性的方程 例:3x 2 = 10 x6 x + 5 = 0引言 一元一次方程 3x 2 = 10 x6 x +二分法三分法三分捨取法 Fibonacci search 引言 二分法引言 O12xyf(2)f(1)y = f(x)二分法 把區間分半解設O12xyf(2)f(1)y = f(x)二分法解二分法 (答案準確至4位小數)

2、求區間 內 的根。 所求的根為1.6266 (準確至4位小數)設步驟abf(a)f(m)f(b)111.5221.51.75231.51.6251.75141.6265869151.626647951.626708985151.6265869151.6266174331.62664795161.6265869151.6266021741.626617433二分法 (答案準確至4位小數)求區間 內 的根。 所求二分法二分法的缺點 運算多 步驟多二分法二分法的缺點三分法abxmxn第 點 =23第 點 =13三分法abxmxn2313三分法O12xyf(2)f(1)y = f(x)三分法O12xy

3、f(2)f(1)y = f(x)三分法步驟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.626531.62658+10

4、1.626531.626551.626561.62658+所求的根為1.6266 (準確至4位小數)求區間 內 的根。(準確至4位小數) 設三分法步驟abf(a)f(xm)f(xn)f(b)111.3二分法和三分法比較區間減少速度 二分法每次能縮減剩 ，三分法每次縮減剩 ， 不論 n 是多少, 所以，三分法所須步驟明顯較少 步驟二分法三分法12.n.二分法和三分法比較區間減少速度 不論 n 是多少, 所以，二分法：二分法和三分法比較步驟的量 三分法：二分法需 個步驟，三分法則需 個步驟。 設經n步驟後，區間為原有的二分法：二分法和三分法比較步驟的量三分法：設經n步驟後，區二分法變三分法步驟百分

5、改變：二分法和三分法比較 36.9%二分法變三分法步驟百分改變：二分法和三分法比較 36.9三分法的優點 步驟比二分法少三分法的缺點 較二分法複雜，計算步驟繁複 較容易出錯二分法和三分法比較三分法的優點二分法和三分法比較二分法和三分法比較二分法三分法完成的步驟兩個一個計算 的值一次兩次區間減少50%66.7%二分法和三分法比較二分法三分法完成的步驟兩個一個計算 的三分法並未完美，三分捨取法 二分法和三分法比較我們再為三分法作出改良，三分法並未完美，二分法和三分法比較我們再為三分法作出改良，三分捨取法 捨遠0 取近0三分捨取法三分捨取法三分捨取法三分捨取法Oabxyf(b)f(a)y = f(x

6、)三分捨取法Oabxyf(b)f(a)y = f(x)Oxyy = f(x)f(a)a bf(b)三分捨取法Oxyy = f(x)f(a)a bf(b)三分捨取法所求的根為1.6266 (準確至4位小數)求區間 內 的根。(答案準確至4位小數) 設 步驟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

7、.62963-0.56680-0.158500.0527151.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.

8、626561.62658-0.000290.00006三分捨取法 所求的根為1.6266 (準確至4位小數)求區間 內 在三分捨取法 求區間 內 的根這題目中:二分法計算了次函數值三分法計算了次函數值三分捨取法計算了次函數值在三分捨取法 求區間 內 的根這題目中:二分法計算了三分捨取法 所求的根為1.6266 (準確至4位小數)求區間 步驟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-

9、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.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.

10、626531.626561.62658-0.00080-0.000290.000061.626561.62658-0.000290.00006 的根。(答案準確至4位小數)設 內 三分捨取法 所求的根為1.6266 (準確至4位小數)求區我們計算出，試一點的實驗概率為 。試二點的實驗概率為 。三分捨取法 3525三分捨取法 3525二分法：三分法：三分捨取法：三分捨取法 百分改變：計算函數的次數 :二分法：三分捨取法 百分改變：計算函數的次數 :可見，三分捨取法是眾多方法中計算量最少的。三分捨取法 所以, 三分捨取法是成功的 可見，三分捨取法是眾多方法中計算量最少的。三分捨取法 所以,三分捨取法的捨取原則先試較接近0的點。 多分捨取法三分捨取法的捨取原則多分捨取法 For a search using n function evaluations, the optimal method is to divide the interval into ratio using the first n Fibonacci numbe