科學計算方法2(二分法)

1、非線性方程 二分法迭代,科學計算方法2, ,GPS (Global Positioning System),Reference: Timothy Sauer, Numerical Analysis,非線性科學是當今科學發(fā)展的一個重要研究方向,其中非線性方程的求根是一個不可或缺的研究內容。然后非線性方程的求根非常困難。,高于次的代數方程,不存在通用的求根公式,超越方程一般很難直接求出其準確解,例:,求 f (x)= 0 根的問題包括如下方面:,根的存在性,即f(x)=0有沒有根? 若有,有 幾個根?,根的范圍,確定有根區(qū)間,根的精度,已知一個根的近似值后,能否 將它精確到足夠精度?,Where

2、is Flight MH370?,定理2(零點定理) 若函數f在閉區(qū)間a, b上連續(xù),且f(a)與f(b)異號, 則至少存在一點 x0屬于(a, b),使得f(x0)=0,即方程f(x)=0在(a, b)內至少有一個根。,零點定理回答了根的存在性和根的范圍的 問題,如何去尋找足夠精度的根？,游戲:模仿幸運52請同學們猜測這部電腦的價格？,化大為小,a0,b0,a1,b1=a0,x0 a1,b1=x0,b0,已知f(x)=0在a0,b0內有一根,且f(a0)f(b0)0,(2)判斷若f(xn-1) f(an-1)0,則anan-1,bn xn-1 否則 anxn-1, bnbn-1,x0 x1

3、,二分法迭代,(1)計算 xn-1=0.5(an-1+bn-1)和f(xn-1) 判斷若f(xn-1)=0,則xn-1是根,否則轉下一步;,例 1 二分法求方程 在區(qū)間 0, 1內的根。,函數在0,1內有唯一零點, 故0,1是隔根區(qū)間。,解: 令,x4=0.5(0.4375+0.5)=0.4688作為近似值, 誤差不超過1/(25) 。 精確值0.443573534104293。,二分法迭代將得到一系列區(qū)間序列,定理2.2 設x*是 f(x)=0在a0, b0內的唯一根,且 f(a 0)f(b 0)0,則二分過程中各區(qū)間的中點數列,性質1. f(an)f(bn)0; 2. bn an = (b

4、0 a0)/ 2n,滿足 | xn x*| (b 0 a 0)/ 2n+1,注記: 若要,思想簡單, 僅需函數值符號, 容易實現(xiàn)。,二分法的反思:,收斂速度慢和不能求復根等不足。,function root = bisect(func,x1,x2,n) for i = 1:n x3 = 0.5*(x1 + x2); f3 = feval(func,x3); if f3 = 0 root = x3; return end if f2*f3 0 x1 = x3; f1 = f3; else x2 = x3; f2 = f3; end end,練習 1,試試實現(xiàn)二分法？,標準: 1. 代碼美 2. 文檔美,作業(yè) 1,試試設計新的求根方法？,標準: 文檔(word, ppt 或 pdf)和代碼,提示: 黃金分割方法(華羅庚),設f(x) = 0的根為 x*,通過迭代計算,產生序列: x0 x1 x2 xn,只須,迭代的思想,迭代法是一種逐次逼近法, 這種方法使用某個固定公式反復校正根的近似值, 使之逐步精確化, 最后得到滿足精度要求的結果。,蘋果成功的原因,Comes out with industry-sha