第3章解方程fx=0的迭代法

第3章解方程f(x)=0的迭代法3.1逐次迭代法3.2Newton法3.3割線法3.4二分法3.5根的分離和求全部單根概述非線性方程:高次代數(shù)方程，超越方程非線性方程的根：單根：f(x)=0但f’(x)≠0k重根:f(x)=…=f(k-1)(x)=0,但f(k)(x)≠0非線性方程求根的3個主要問題：(1)根的存在性:

有沒有根?有幾個根?(2)根的隔離:確定根的區(qū)間,使只有1個根(3)根的精確化:使根的近似值不斷精確化，直到滿足給定精度.3.1逐次迭代法3.1.1逐次迭代思想及迭代公式設f(x)在[a,b]上連續(xù)，且f(x)=0有唯一根x*。1、作同解變換：注：同解變換不是唯一的，可以有多種形式。2、對給定初值x0∈[a,b]，構造迭代公式：3.1逐次迭代法收斂性分析：當序列{xn}收斂于x*，且在x*處連續(xù)，就有：即n充分大時，xn就可作為x*的近似解.逐次迭代法的關鍵和難點：(1)哪一種同解變換能使{xn}收斂于x*?(2)初值x0取何值?(3)收斂速度如何?3.1逐次迭代法3逐次迭代法的收斂性3.1逐次迭代法3.1逐次迭代法推論的用途：用于尋找某一種同解變換收斂時的L系數(shù)。（通過不等式放大的方法）3.1逐次迭代法逐次迭代法的停止計算的條件3.1逐次迭代法3.1.3逐次迭代法的幾何意義求方程f(x)=0的根問題

迭代求解直線y=x與曲線的交點從幾何圖形上：3.1逐次迭代法3.1逐次迭代法3.1逐次迭代法3.1.2收斂階（收斂速度問題）3.1逐次迭代法收斂階的判別方法3.1逐次迭代法3.1.4逐次迭代法的計算實例分析---求解步驟(1)確定有根區(qū)間(2)找有效的同解變形，并確定初值x0(3)作迭代計算3.1逐次迭代法3.1.4逐次迭代法的計算實例練習題:討論下面方程根的情況補充題3.2Newton法3.2.1Newton法的迭代公式1.Newton法的基本思想(1)總體思想：不斷用切線的根代替曲線的根，直到得到滿意解。(2)主要思路：設x0是方程f(x)=0的一個近似解，過曲線y=f(x)上的點(x0,f(x0))作曲線的切線；取此切線與x軸交點的橫坐標x1作為解的一個新近似值；依次繼續(xù)，直到解的新近似值滿足要求為止。3.2Newton法2.Newton法的迭代公式3.2Newton法3.2.2Newton法的幾何意義3.2.3Newton法的收斂條件3.2Newton法3.2Newton法3.2.4Newton法的計算實例[例]Newton法的特點：Newton法是不動點迭代法，公式簡單，使用方便，易于編程是2階收斂的，收斂速度較快。每次迭代都要計算導數(shù)值，計算量大.補充：Newton法對重根的處理1.Newton法有m重根時的收斂階補充：Newton法對重根的處理則Newton法在有m重根時，若不作任何改進，只能保證有1階的收斂階。2.有重根時的改進Newton法方法1：利用m構造新迭代公式此時能達到2階收斂，但通常m很難預先知道。補充：Newton法對重根的處理方法2：構造新函數(shù)F(x)如果x*是f(x)的m重根，則x*也是F(x)的單根。從而對函數(shù)F(x)使用Newton迭代公式，也具有2階收斂性。缺點：要求f(x)的二階導數(shù)。3.3割線法(弦截法)割線法基本思想用割線的根代替曲線的根方法的關鍵：合適的初始點A(x0,y0)和B(x1,y1)割線法：雙點割線法、單點割線法3.3.1單點割線法1.單點割線法的幾何背景不斷作割線:始終固定一個端點x0讓另一個點xi（i=1,2,3,…）不斷改變。3.3.1單點割線法2.過點x0和xn的割線方程3.3.1單點割線法3.單點割線法的迭代公式3.3.1單點割線法3.3.2單點割線法的收斂性3.3.1單點割線法3.3.3

單點割線法的計算實例[例1]3.3.4雙點割線法1.雙點割線法的迭代公式在Newton法的基礎上，用差商代替導數(shù)，得雙點割線法的迭代公式：初始點的選擇：按單點割線法的定理1來確定x0,x1分別為區(qū)間[a,b]的哪個端點。3.3.1雙點割線法2.雙點割線法的收斂性收斂條件與單點割線法的定理1相同。收斂階：3.3.1雙點割線法3.雙點割線法的計算實例[例1]3.4二分法3.4.1二分法的計算公式1.二分法的數(shù)學依據(jù)設函數(shù)f(x)在區(qū)間[a,b]是單調連續(xù)，若f(a)f(b)<0，則f(x)=0在[a,b]上只有一個根x*.2.二分法的基本思想不斷對含有根的區(qū)間[a,b]作平分，判斷x*屬于哪個區(qū)間。3.4二分法3.二分法的計算步驟(嘗試:畫流程圖?)3.4二分法4.二分法的誤差分析5.當計算達到給定精度時，二分法的迭代次數(shù)N的估計3.4二分法3.4.2二分法的計算步驟3.4.3二分法的計算實例[例]注:二分法的特點(1)算法簡單,方法穩(wěn)定.(2)不能求偶次重根和復根.(3)收斂速度較慢,常用于求初始近似值.3.5根的分離和求全部單根設f(x)=0,x∈[a,b]有多個根，求全部根。算法步驟：(1)根的分離：對區(qū)間[a,b]，取適當步長h，將其分離為n個子區(qū)間，若f(xi-1)f(xi)<0，則為有根子區(qū)間；否則為無根子區(qū)間。(2)對有根