數(shù)值計(jì)算chapter2 非線性方程求根.ppt

1、1,第二章 非線性方程求根,序,求方程根的近似值，需要解決的問(wèn)題：, 根的存在性 方程有無(wú)根，有幾個(gè)；,2,從11000這1000個(gè)自然數(shù)隨機(jī)抽出個(gè)數(shù)，誰(shuí)能根據(jù)提示“大了”“小了”“對(duì)了”先猜出這個(gè)數(shù)？,猜數(shù)字游戲，看誰(shuí)先猜中：,10次以內(nèi)能猜出嗎 ？,二分法的廣泛應(yīng)用,3,復(fù)習(xí)：零點(diǎn)定理（根的存在性定理）,如果函數(shù)y=f(x)在區(qū)間a,b上的圖象是連續(xù)的不斷的一條曲線，并且有f(a)f(b)0,那么，函數(shù)y=f(x)在區(qū)間(a,b)內(nèi)有零點(diǎn)， 即存在c(a,b)，使f(c)=0 ， 這個(gè)c也就是方程f(x)=0的根.,4,1 二分法,設(shè)函數(shù) 在區(qū)間 上連續(xù)且,不妨設(shè) 在 內(nèi)只有一個(gè)實(shí)根 。,

2、取 中點(diǎn) 將其二分，,若,否則，若,則,若,令,則,令,對(duì)有根區(qū)間,再取 中點(diǎn) 將其二分，,首先,則,其次,否則，便得到一組不斷縮小的有根區(qū)間,5,其中每一個(gè)有根區(qū)間的長(zhǎng)度都是前一個(gè)有根區(qū)間的一半，,當(dāng) 時(shí)，上式極限為零，即這些區(qū)間最終必收縮于一點(diǎn),該點(diǎn)即為所求的根。,區(qū)間 的中點(diǎn) 形成一個(gè)序列,顯然,實(shí)際計(jì)算中，對(duì)于給定的根的允許誤差,只要,就可確定得到滿足精度要求的近似根,上述求非線性方程的實(shí)根的近似值的方法稱為二分法。,同時(shí)也得到所需二分次數(shù)k.,6,解,這里,所以 是 的有根區(qū)間。,用二分法計(jì)算結(jié)果如下表：,7,（可求得根的精確值為 ）。,解,如圖，可確定,故方程只有一個(gè)非零實(shí)根,由,

3、用二分法計(jì)算結(jié)果如下表：,8,所以可取,注,9,例,不能求出所有根,(即有可能漏根)。,例,如圖,2.不能用于求偶重根、復(fù)根；不能推廣到多元方程組求解；,缺點(diǎn):,的等比級(jí)數(shù)的收斂速度,相同。,1.收斂速度不快,僅與公比為,即是線性收斂的。,10,2 迭 代 法,一、簡(jiǎn)單迭代法,作迭代計(jì)算,1、一般形式（具體做法）：,即序列 的極限 就是方程 的根。,11,這種求方程近似根的方法稱為簡(jiǎn)單迭代法（逐次迭代法）。,稱為迭代公式或迭代過(guò)程,稱為根的初始近似值,稱為根的k次近似值；,稱為迭代函數(shù)；,稱為迭代序列,其中：,12,解,將方程轉(zhuǎn)化為等價(jià)方程,得相應(yīng)的迭代公式,若取初值,計(jì)算結(jié)果如下表,從表中可

4、以看出，,迭代序列是收斂的，,13,若取初值,計(jì)算結(jié)果圖像（MATLAB）,注：該方程的3個(gè)根,1.89328919630450,-0.94664459815225 + 0.82970355286240i （復(fù)數(shù)根）,-0.94664459815225 - 0.82970355286240i （復(fù)數(shù)根）,14,注,很明顯，將方程改寫成等價(jià)方程的形式是不唯一的，,例如,上例中, 原方程也可改寫成,此時(shí)相應(yīng)的迭代公式,可見(jiàn),所得迭代序列趨于無(wú)窮大,即發(fā)散.,2、迭代法的幾何意義,15,16,二、簡(jiǎn)單迭代法收斂的充分條件,定理1,則,17,證明,令,則 在 上也連續(xù)，,由條件，有,即,再證 的唯一性

5、,設(shè)方程 在 上存在兩個(gè)實(shí)根,則由拉格朗日定理，有,即,（其中 在 之間）,最后證明迭代法的收斂性,由條件（2）知道，,當(dāng) 時(shí)，,先證方程 在 上存在實(shí)根,18,（ 在 之間）,反復(fù)遞推，有,得證,再由式，有,得證,得證,再由拉格朗日定理，有,19,注,20,解,設(shè),顯然 在 內(nèi)可導(dǎo)，且有,對(duì),又因?yàn)?所以 在 上單增，所以,所以 在 上滿足定理?xiàng)l件，,由,得,故需迭代7次即可。,21,迭代點(diǎn)圖形,函數(shù)圖形,方程的解,1.32471795724475 -0.66235897862237 + 0.56227951206230i -0.66235897862237 - 0.562279512062

6、30i,22,定理2（迭代法的局部收斂性定理）,證,因?yàn)?在 內(nèi)連續(xù)且,取,顯然 在 上滿足定理1的條件（1）。,23,又當(dāng) 時(shí)，,其中 介于 之間，,這又說(shuō)明 在 上滿足定理1的條件（2）。,解,設(shè),顯然在 內(nèi)， 連續(xù)且,只要 取得充分靠近 ，迭代過(guò)程必收斂。,24,迭代點(diǎn)圖形,函數(shù)圖形,25,解, 構(gòu)造迭代公式,方程等價(jià)形式為,相應(yīng)的迭代公式為, 判斷迭代法的收斂性,而,在 內(nèi)有實(shí)根,所以由定理2知，迭代法收斂。, 列表計(jì)算如下：,26,所以,27,3 Newton迭代法,28,29,2、Newton 法的幾何意義,30,31,本定理不證，其幾何意義明顯，如圖。,32,33,解,相應(yīng)的牛頓

7、迭代過(guò)程為,(k=0、1、2)收斂，,計(jì)算結(jié)果如下表：,得,34,解,令,則 的正根就是,故相應(yīng)的牛頓迭代公式為,(k=0、1、2),當(dāng) 時(shí)，,由定理4知，,對(duì)于任取的初始近似值,即上式即為所求。,證明收斂性：,不妨取區(qū)間,有,由迭代公式產(chǎn)生的序列 必收斂于平方根,35,解,令,(k=0、1、2),36,例3 用牛頓法求方程 實(shí)根，準(zhǔn)確到,解,方程 有唯一實(shí)根 。,37,38,39,例4 用弦割法求方程 在區(qū)間 內(nèi)的一個(gè)根.,解,故相應(yīng)的弦割法迭代過(guò)程為,得,40,41,4 迭代法的收斂階 與加速收斂方法,一、收斂階的概念,序,定義,設(shè)序列 收斂于,則稱序列 是P階收斂的。,當(dāng) 且 時(shí)稱為線性

8、收斂；,當(dāng) 時(shí)稱為超線性收斂。,特別地，,當(dāng) 時(shí)稱為二次收斂或平方收斂。,42,顯然，收斂階越高（即p越大），收斂速度就越快，因此，收斂,階的高低是衡量迭代法的優(yōu)劣的一個(gè)重要指標(biāo)。,定理5,證,把 在 處按泰勒公式展開(kāi)，有,（ 在 和 之間）,（ 在 x和 之間）,43,由定理2，知，,因此，當(dāng)初始近似值 充分接近 時(shí)，有,所以，有,44,例1,分析簡(jiǎn)單迭代法與牛頓迭代法的收斂速度。,解,（一）、簡(jiǎn)單迭代法,由拉格朗日中值定理，有,（ 在 和 之間）,（二）、牛頓迭代法,即有,由牛頓迭代法的迭代函數(shù),有,45,又,這說(shuō)明牛頓迭代法在求解有單根的方程時(shí)至少是二階收斂的。,則,46,這說(shuō)明直接用牛

9、頓迭代法求有重根的方程時(shí)只具有線性收斂速度.,如果把方程 在有重根的情形下，改寫成,則 就是 的單根，,可以證明弦截法的收斂速度為1.618.,而單點(diǎn)弦截法的收斂速度為線性收斂.,47,二、加速收斂方法（埃特肯Aitken算法）,只介紹一種一般的線性收斂序列 的收斂的加速方法。,48,設(shè) 是方程的根的某個(gè)近似值，,則,由迭代公式，,相臨兩次迭代的迭代值為,由中值定理，有,（ 在 和 之間， 在 和 之間）,假定 在x變化時(shí)改變不大，,可令,所以,49,就有可能產(chǎn)生一個(gè)收斂速度較快的新序列,這種加速方法稱為埃特肯（Aitken）加速方法。,50,將埃特肯加速方法使用于迭代法，得計(jì)算公式如下：,（迭代）,（迭代）,（加速）,上式稱為埃特肯算法。,解,51,得,52,方程等價(jià)形式為,相應(yīng)的迭代公式為,下面利用埃特肯算法求：,埃特肯算法為,計(jì)算結(jié)果列表如下：,53,0 1 2,所以,54,解,下面我們分別用：,簡(jiǎn)單迭代法,牛頓迭代法,埃特肯算法,三種方法求滿足精度要求的近