摘要本文分別採用了「二分法」、「牛頓法」、 「割線法」、3種方法討論如何求解方程「」，描述了每個演算法的演算法思想，給出了計算結果與迭代時間以及每一步迭代結果和解的精度，並且用多項式擬合了不同演算法的時間複雜度函式進行收斂性和時間複雜度分析比較了的優劣。在最後報告給出了其他可供使用的求根方法例如，「簡易牛頓演算法」、steffensenf迭代法並對它的思想和計算流程進行了簡單的介紹。
關鍵詞：二分法牛頓法割線法簡易牛頓法 steffensenf迭代法
一、計算機配置
作業系統：windows7旗艦版
處理器：intel(r) core(tm) i5-3210m [email protected]
安裝記憶體（ram）：4.00gb(2.91gb可用)
系統型別：32位作業系統
二、二分法計算實驗
2.1 二分法演算法思想和簡要描述
若f是區間[a,b]上的連續函式，且f(a)f(b)<0,根據連續函式閉區間零點定理，f在[a,b]內必有一零點。
利用這一思想：若f(a)f(b)<0,則計算c=(a+b)/2，並檢驗f(a)f(c)<0是否是真的，若是把c改為b重新開始；若不是真的，則f(c)f(b)<0,把c改為a；反覆重複上述過程。
2.2 matlab執行二分法程式
二分法求解f=x^3-9的根
引數設定：a,b設定為估計零點所在區間的上確界和下確界。
n設定為二分法for語句迭代次數。
alpha設定為最後結果f(x)的精度。
delta設定為最後結果x的精度。
若alpha，delta都符合設定的計算精度時，結束迭代並得出計算結果，否則一直迭代到n次）
設定初始值：設定引數a,b分別為為2,3；迭代次數n為50次；alpha和delta都設定為0.001。
列出計算結果：>> erfen(f,2,3,50,0.001,0.001)
n ab delta alpha
1.0000 2.0000 2.5000 0.5000 19.0000
2.0000 2.0000 2.2500 0.2500 7.6250
3.0000 2.0000 2.1250 0.1250 3.3906
4.0000 2.0625 2.1250 0.0625 1.5957
5.0000 2.0625 2.0938 0.0313 0.8220
6.0000 2.0781 2.0938 0.0156 0.4049
7.0000 2.0781 2.0859 0.0078 0.2040
8.0000 2.0781 2.0820 0.0039 0.1016
9.0000 2.0801 2.0820 0.0020 0.0507
10.0000 2.0801 2.0811 0.0010 0.0254
11.0000 2.0801 2.0806 0.0005 0.0127
12.0000 2.0801 2.0803 0.0002 0.0063
13.0000 2.0801 2.0802 0.0001 0.0032
14.0000 2.0801 2.0801 0.0001 0.0016
elapsed time is 0.316426 seconds.
三、牛頓法計算實驗
3.1 牛頓法演算法思想和簡要描述
我們有乙個函式f，其零點由數值計算得出，設r是f的乙個零點，x是r的乙個近似。若f的二階導數存在並且連續，則有泰勒定理，得
0=f(r)=f(x+h)=f(x)+hf』(x)+o(h^2)
其中h=r-x。若h較小（即x在r附近），則有理由略去o(h^2)項並且在餘下方程中求h。即得到h=-f(x)/f』(x)。
故x-f(x)/f』(x)是比x更好的乙個近似。牛頓法從r的乙個估計x0開始，得到更加準確的近似值xn。遞推式定義為：
3.2 matlab執行牛頓法程式
牛頓法求解f=x^3-9的根
引數設定：x0設定為函式f零點的近似。
n設定為牛頓法for語句迭代次數。
alpha設定為最後結果f(x)的精度。
delta設定為最後結果x的精度。
若alpha，delta都符合設定的計算精度時，結束迭代並得出計算結果，否則一直迭代到n次）
設定初始值：設定引數x0分別為為3；迭代次數n為50次；alpha和delta都設定為0.001。
列出計算結果：
>> newton(f,50,3,0.001,0.001)
n x f(x) delta alpha
1.0000 2.3333 3.7037 0.6667 3.7037
2.0000 2.1066 0.3483 0.2268 0.3483
3.0000 2.0804 0.0043 0.0262 0.0043
elapsed time is 0.166680 seconds.
四、割線法計算實驗
4.1 割線法演算法思想和簡要描述
割線法思路總體上與牛頓法一致，但是為了避免牛頓法中求函式導數所帶來的困難，用差商來近似的代替導數得到了割線法近似值的遞推式：
因為的計算需要和，所以開始時需要兩個初始點。
4.2 matlab執行割線法程式
割線法求解f=x^3-9的根
引數設定：a,b設定為函式f零點的兩個近似值。
n設定為牛頓法for語句迭代次數。
alpha設定為最後結果f(x)的精度。
delta設定為最後結果x的精度。
若alpha，delta都符合設定的計算精度時，結束迭代並得出計算結果，否則一直迭代到n次）
設定初始值：設定引數a,b分別為為3,4；迭代次數n為50次；alpha和delta都設定為0.001。
列出計算結果：
>> gexian(f,3,4,50,0.001,0.001)
nx0 delta alpha
13 1 37
2.0000 2.5135 0.4865 11.1202
3.0000 2.2125 0.3010 5.0486
4.0000 2.1034 0.1092 1.5254
5.0000 2.0815 0.0219 0.2874
6.0000 2.0801 0.0014 0.0181
elapsed time is 0.080747 seconds.
五、收斂性和時間複雜度分析
5.1 三種演算法的收斂性分析
從理論上來看，二分法每次估計的範圍都是前一次迭代時（a,b）區間的1/2，所以要達到千分位的精度至少應該進行10次左右的迭代；而牛頓法的收斂速度是最快的；割線法把牛頓演算法中的導函式用插商代替造成了一定的誤差，故收斂速度稍慢於牛頓迭代。
從實驗結果來看，結果也與理論上的判斷相符，在實驗精度取0.001的情況下，二分法迭代次數最多，進行了14次迭代；牛頓迭代演算法的次數最少，只進行了3次迭代就到達了0.001位的精度要求；割線迭代法相對於牛頓演算法的迭代次數要稍多一點，進行了6次迭代。
5.2 三種演算法的時間複雜度分析
我們用迭代次數n來反映演算法的要解決問題的規模並作為自變數，用tic toc函式記錄每次迭代所花費的時間，記錄隨著n的不斷增大，各演算法所耗費時間的變化趨勢，得到如下函式影象：
二分法的漸進時間複雜度函式影象
牛頓法的漸進時間複雜度函式影象
割線法的漸進時間複雜度的函式影象
從三種演算法的漸進時間複雜度函式影象容易看出，隨著n的不斷增大是影象大致呈線性變化，說明了每次迭代所進行的計算量都是大致相當的，可以認為是三種演算法都是穩定的。
影象也反映出二分法的計算時間明顯大於另外兩種演算法，這是由於二分法每乙個迴圈語句內都要進行求f(a),f(b),f(a)*f(b),(a+b)/2四次計算計算量大於其他兩種演算法；牛頓法相較於割線法雖然收斂速得更快，但每次迭代都要重新計算f(x和f』(x)，相比於割線法每次只需計算乙個f(x)，計算量要稍大一些，所以每次迭代耗時更多。
六、其他可供使用的演算法
6.1 簡易牛頓法演算法思想簡述
簡易牛頓法即將
二分法課件
3.1.2用二分法求方程的近似解 第1課時 沂水縣第四中學劉德珍 學習目標 一 知識與技能 1 了解二分法是求方程近似解的常用方法。2 能借助計算器用二分法求相應方程的近似解。二 過程與方法 1 通過 用二分法求方程近似解 的探索過程，體會數形結合 數學逼近等思想的運用。2 通過設定生活情境，讓學生...
方程與函式零點 二分法
1.若函式在區間上的圖象為連續不斷的一條曲線，則下列說法正確的是 a 若，不存在實數使得 b 若，存在且只存在乙個實數使得 c 若，有可能存在實數使得 d 若，有可能不存在實數使得 2.已知函式f x 在區間 a，b 上單調，且f a f b 0，則方程f x 0在區間 a，b 內 a.至少有一實根...
非線性方程解法二分法實驗報告
第七章非線性方程解法 二分法 考察有根區間 a,b 取中點x0 b a 2 將它分為兩半，假設中點x0不是f x 的零點，然後進行根的搜尋，即查詢f x0 與f a 是否同號，如果確係同號，說明所求的根x在x0的右側，這是令a1 x0，b1 b 否則x必在x0的左側，這是令a1 a,b1 x0,不管...