《數(shù)值分析》PPT課件.ppt

《《數(shù)值分析》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)值分析》PPT課件.ppt（112頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1,第7章 非線性方程與方程組的數(shù)值解法,7.1 方程求根與二分法 7.2 不動(dòng)點(diǎn)迭代法及其收斂性 7.3 迭代收斂的加速方法 7.4 牛頓法 7.5 弦截法與拋物線法 7.6 求根問題的敏感性與多項(xiàng)式的零點(diǎn) 7.7 非線性方程組的數(shù)值解法,2,7.1 方程求根與二分法,7.1.1 引言,（1.1）,本章主要討論求解單變量非線性方程,其中 也可以是無窮區(qū)間.,如果實(shí)數(shù) 滿足 ，則稱 是方程(1.1)的 根，或稱 是 的零點(diǎn).,3,若 可分解為,其中 為正整數(shù)，且 則稱 為方程(1.1)的 重根，或 為 的 重零點(diǎn)， 時(shí)為單根.,若 是 的 重零點(diǎn)，且 充分光滑，則,

2、如果函數(shù) 是多項(xiàng)式函數(shù)，即,（1.2）,其中 為實(shí)數(shù)，則稱方程(1.1)為 次代數(shù)方程.,4,它在整個(gè) 軸上有無窮多個(gè)解，若 取值范圍不同，解也 不同，因此討論非線性方程(1.1)的求解必須強(qiáng)調(diào) 的定 義域，即 的求解區(qū)間,時(shí)的求根公式是熟知的， 時(shí)的求根公式 可在數(shù)學(xué)手冊(cè)中查到，但比較復(fù)雜不適合數(shù)值計(jì)算，當(dāng) 時(shí)就不能用公式表示方程的根，所以 時(shí)求根仍用一般 的數(shù)值方法,根據(jù)代數(shù)基本定理可知, 次方程在復(fù)數(shù)域有且只有 個(gè)根（含重根， 重根為 個(gè)根）.,另一類是超越方程，例如,5,迭代法要求先給出根 的一個(gè)近似，若 且 ，根據(jù)連續(xù)函數(shù)性質(zhì)可知 在 內(nèi)至少有一個(gè)實(shí)

3、根，這時(shí)稱 為方程(1.1)的有根區(qū)間.,非線性問題一般不存在直接的求解公式，故沒有直接 方法求解，都要使用迭代法.,通?？赏ㄟ^逐次搜索法求得方程 的有根區(qū)間.,6,例1 求方程 的有根區(qū)間.,解 根據(jù)有根區(qū)間定義，對(duì) 的根進(jìn)行搜索計(jì)算，結(jié)果如下：,由此可知方程的有根區(qū)間為,7,檢查 與 是否同號(hào)， 如果同號(hào)，說明所求的根 在 的右側(cè),這時(shí)令 否則 必在 的左側(cè)， 這時(shí)令 見圖7-1.,考察有根區(qū)間 ，取中點(diǎn) 將它分為 兩半，,7.1.2 二分法,假設(shè)中點(diǎn) 不是 的零點(diǎn)，然后進(jìn)行根的搜索.,圖7-1,不管出現(xiàn)哪一種情況，新的有根區(qū)間 的長(zhǎng)度僅 為 的一半.

4、,8,對(duì)壓縮了的有根區(qū)間 又可施行同樣的手續(xù)，即用 中點(diǎn) 將區(qū)間 再分為兩半，然后通過根 的搜索判定所求的根在 的哪一側(cè)，從而又確定一個(gè)新的 有根區(qū)間 ，其長(zhǎng)度是 的一半.,如此反復(fù)二分下去，即可得出一系列有根區(qū)間,其中每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半，因此 的長(zhǎng)度,當(dāng) 時(shí)趨于零.,9,就是說，如果二分過程無限地繼續(xù)下去，這些區(qū)間最終必收縮于一點(diǎn) ，該點(diǎn)顯然就是所求的根.,作為根的近似，則在二分過程中可以獲得一個(gè)近似根的序列,該序列必以根 為極限.,每次二分后，設(shè)取有根區(qū)間 的中點(diǎn),10,由于,只要二分足夠多次（即 充分大），便有,這里 為預(yù)定的精度.,（1.3）,11,例2

5、求方程,在區(qū)間 內(nèi)的一個(gè)實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后第2位.,解 這里 ，而,取 的中點(diǎn) ，將區(qū)間二等分，由于 ， 即 與 同號(hào)，故所求的根 必在 右側(cè)，這時(shí)應(yīng)令 ，而得到新的有根區(qū)間,如此反復(fù)二分下去, 按誤差估計(jì)（1.3）式,欲使,只需 ，即只要二分6次，便能達(dá)到預(yù)定的精度.,12,計(jì)算結(jié)果如表7-2.,13,二分法是計(jì)算機(jī)上的一種常用算法，計(jì)算步驟為：,步驟1 準(zhǔn)備 計(jì)算 在有根區(qū)間 端點(diǎn)處的值,步驟2 二分 計(jì)算 在區(qū)間中點(diǎn) 處的值,步驟3 判斷 若 ，則 即是根， 計(jì)算過程結(jié)束，否則檢驗(yàn).,若 ，則以 代替 ，否則以,代替 .,14,此時(shí)中

6、點(diǎn) 即為所求近似根.,15,7.2 不動(dòng)點(diǎn)迭代法及其收斂性,7.2.1 不動(dòng)點(diǎn)與不動(dòng)點(diǎn)迭代法,將方程（1.1）改寫成等價(jià)的形式,（2.1）,若 滿足 ，則 ；反之亦然，稱 為函數(shù) 的一個(gè)不動(dòng)點(diǎn).,求 的零點(diǎn)就等價(jià)于求 的不動(dòng)點(diǎn).,選擇一個(gè)初始近似值 ，將它代入(2.1)右端，即可求得,16,如此反復(fù)迭代計(jì)算,（2.2）,稱為迭代函數(shù).,如果對(duì)任何 ，由（2.2）得到的序列 有極限,則稱迭代方程(2.2)收斂，且 為 的不動(dòng)點(diǎn)， 故稱（2.2）為不動(dòng)點(diǎn)迭代法.,17,方程 的求根問題在 平面上就是要確定曲 線 與直線 的交點(diǎn),對(duì)于 的某個(gè)近似值 ，在曲線

7、上可確定 一點(diǎn) ，它以 為橫坐標(biāo)，而縱坐標(biāo)則等于,就是說，迭代過程實(shí)質(zhì)上是一個(gè)逐步顯示化的過程.,過 引平行 軸的直線，設(shè)此直線交直線 于點(diǎn) ，,然后過 再作平行于 軸的直線，,與曲線 的交點(diǎn),上述迭代法是一種逐次逼近法，其基本思想是將隱式 方程 歸結(jié)為一組顯式的計(jì)算公式 .,18,則點(diǎn) 的橫坐標(biāo)為 ，,圖7-2,記作 ，,縱坐標(biāo)則等于,按圖7-2中箭頭所示的路徑繼續(xù)做下去.,在曲線 上得到點(diǎn)列，,其橫坐標(biāo)分別為,19,例3 求方程,（2.3）,在 附近的根,解 設(shè)將方程（2.3）改寫成下列形式,依公式 求得的迭代值,如果點(diǎn)列 趨向于點(diǎn) ，則相應(yīng)的迭代值 收斂 到所求的根

8、,據(jù)此建立迭代公式,20,各步迭代的結(jié)果見表7-3.,這時(shí)可以認(rèn)為 實(shí)際上已滿足方程(2.3)，即為所求的根.,如果僅取6位數(shù)字，那么結(jié)果 與 完全相同，,21,但若采用方程（2.3）的另一種等價(jià)形式,建立迭代公式,仍取迭代初值 ，則有,結(jié)果會(huì)越來越大，不可能趨于某個(gè)極限.,這種不收斂的迭代過程稱作是發(fā)散的.如圖7-3.,一個(gè)發(fā)散的迭代過程，縱使進(jìn)行了千百次迭代，其結(jié)果也是毫無價(jià)值的.,圖7-3,22,7.2.2 不動(dòng)點(diǎn)的存在性與迭代法的收斂性,首先考察 在 上不動(dòng)點(diǎn)的存在唯一性.,定理1 設(shè) 滿足以下兩個(gè)條件：,1. 對(duì)任意 有,2. 存在正常數(shù) ，使對(duì)任意 都有,（2

9、.4）,則 在 上存在唯一的不動(dòng)點(diǎn),23,因 ，,以下設(shè) 及 ，,若 或 ，則不動(dòng)點(diǎn)為 或 ，,存在性得證.,定義函數(shù),顯然 ，,由連續(xù)函數(shù)性質(zhì)可知存在 ,,且滿足,使 ,,即,即為 的不動(dòng)點(diǎn).,證明 先證不動(dòng)點(diǎn)存在性.,24,再證唯一性.,設(shè) 都是 的不動(dòng)點(diǎn)，,引出矛盾.故 的不動(dòng)點(diǎn)只能是唯一的.,則由(2.4)得,25,（2.5）,定理2 設(shè) 滿足定理1中的兩個(gè)條件，則 對(duì)任意 ，由（2.2）得到的迭代序列 收斂到 的不動(dòng)點(diǎn) ，并有誤差估計(jì),證明 設(shè) 是 在 上的唯一不動(dòng)點(diǎn)， 由條件，可知 ，再由（2.4）得,因 ，故

10、當(dāng) 時(shí)序列 收斂到 .,26,再證明估計(jì)式（2.5），,由（2.4）有,（2.6）,反復(fù)遞推得,于是對(duì)任意正整數(shù) 有,27,在上式令 ，注意到 即得式（2.5）.,迭代過程是個(gè)極限過程.,在用迭代法實(shí)際計(jì)算時(shí)，必須按精度要求控制迭代次數(shù).,原則上可以用誤差估計(jì)式（2.5）確定迭代次數(shù)，但由 于它含有信息 而不便于實(shí)際應(yīng)用.,根據(jù)式（2.6），對(duì)任意正整數(shù) 有,在上式中令 知,28,對(duì)定理1和定理2中的條件2，如果 且對(duì)任意 有,（2.7）,則由中值定理可知對(duì) 有,表明定理中的條件2可用（2.7）代替.,29,例3中，當(dāng) 時(shí)， , 在區(qū)間 中， ，故

11、（2.7）成立.,又因 ，故定理1中條件1也成立. 所以迭代法是收斂的.,而當(dāng) 時(shí)， ，在區(qū)間 中 不滿足定理?xiàng)l件.,30,7.2.3 局部收斂性與收斂階,上面給出了迭代序列 在區(qū)間 上的收斂性，,定理的條件有時(shí)不易檢驗(yàn)，實(shí)際應(yīng)用時(shí)通常只在不動(dòng)點(diǎn) 的鄰近考察其收斂性，即局部收斂性.,定義1 設(shè) 有不動(dòng)點(diǎn) ，如果存在 的某個(gè)鄰域 對(duì)任意 ，迭代（2.2）產(chǎn)生的序列 且收斂到 ，則稱迭代法（2.2）局部收斂.,通常稱為全局收斂性.,31,證明 由連續(xù)函數(shù)的性質(zhì)，存在 的某個(gè)鄰域 使對(duì)于任意 成立,定理3 設(shè) 為 的不動(dòng)點(diǎn)， 在 的某個(gè)鄰 域連續(xù)，

12、且 ，則迭代法（2.2）局部收斂.,此外，,對(duì)于任意 ，,總有 ，,于是依據(jù)定理2可以斷定迭代過程 對(duì)于任意 初值 均收斂.,這是因?yàn)?32,討論迭代序列的收斂速度.,例4 用不同方法求方程 的根,解 這里 ，可改寫為各種不同的等價(jià)形式 其不動(dòng)點(diǎn)為 由此構(gòu)造不同的迭代法：,33,取 ，對(duì)上述4種迭代法，計(jì)算三步所得的結(jié)果如下表.,34,從計(jì)算結(jié)果看到迭代法（1）及（2）均不收斂，且它們均不滿足定理3中的局部收斂條件.,注意 .,迭代法（3）和（4）均滿足局部收斂條件，且迭代法（4）比（3）收斂快，因在迭代法（4）中 .,35,定義2 設(shè)迭代過程

13、收斂于方程 的根 ，如果迭代誤差 當(dāng) 時(shí)成立下列 漸近關(guān)系式,則稱該迭代過程是 階收斂的.,特別地, 時(shí)稱線性收斂，,時(shí)稱超線性收斂，,時(shí)稱平方收斂.,36,定理4 對(duì)于迭代過程 ，如果 在所 求根 的鄰近連續(xù)，并且,則該迭代過程在點(diǎn) 鄰近是 階收斂的.,（2.8）,證明 由于 ，據(jù)定理3立即可以斷定迭代 過程 具有局部收斂性.,再將 在根 處做泰勒展開，利用條件（2.8），,則有,37,注意到 ，,因此對(duì)迭代誤差，,當(dāng) 時(shí)有,（2.9）,這表明迭代過程 確實(shí)為 階收斂.,由上式得,上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù) 的選取.,如果當(dāng)

14、時(shí) ，則該迭代過程只可能是線性收斂.,38,在例4中，迭代法（3）的 ，故它只是線性 收斂.,而迭代法（4）的 ，而 由定理4知 ，該迭代過程為2階收斂.,39,7.3 迭代收斂的加速方法,7.3.1 埃特金加速收斂方法,設(shè) 是根 的某個(gè)近似值，用迭代公式迭代一次得,由微分中值定理，有,其中 介于 與 之間.,假定 改變不大，近似地取某個(gè)近似值 ，,（3.1）,則有,40,由于,將它與（3.1）式聯(lián)立，消去未知的 ，,由此推知,在計(jì)算了 及 之后，可用上式右端作為 的新近 似，記作 .,若將校正值 再迭代一次，又得,有,41,一般情形是由 計(jì)算 ，,(3.2)稱為埃

15、特金（Aitken） 加速方法.,可以證明,它表明序列 的收斂速度比 的收斂速度快.,（3.2）,記,42,7.3.2 斯蒂芬森迭代法,埃特金方法不管原序列 是怎樣產(chǎn)生的，對(duì) 進(jìn) 行加速計(jì)算，得到序列 .,如果把埃特金加速技巧與不動(dòng)點(diǎn)迭代結(jié)合，則可得到 如下的迭代法：,稱為斯蒂芬森(Steffensen)迭代法.,（3.3）,43,它的理解為，要求 的根 ，,已知 的近似值 及 ，其誤差分別為,過 及 兩點(diǎn)做線性插值函數(shù).,它與 軸交點(diǎn)就是（3.3）中的 ，即方程,的解,令,44,實(shí)際上（3.3）是將不動(dòng)點(diǎn)迭代法（2.2）計(jì)算兩步合 并成一步得到的，可將它寫成另一種不動(dòng)點(diǎn)迭代,（3.

16、4）,其中,（3.5）,45,定理5 若 為（3.5）定義的迭代函數(shù) 的不動(dòng)點(diǎn)， 則 為 的不動(dòng)點(diǎn).反之，若 為 的不動(dòng)點(diǎn)， 設(shè) 存在， ，則 是 的不動(dòng)點(diǎn)， 且斯蒂芬森迭代法（3.3）是2階收斂的.,解 例3中已指出, 下列迭代,是發(fā)散的，現(xiàn)用(3.3)計(jì)算，取 .,例5 用斯蒂芬森迭代法求解方程,計(jì)算結(jié)果如下表.,46,至于原來已收斂的迭代法（2.2），由定理5可知它可達(dá)到2階收斂.,計(jì)算表明它是收斂的，這說明即使迭代法（2.2）不收 斂，用斯蒂芬森迭代法（3.3）仍可能收斂.,47,例6 求方程 在 中的解.,解 由方程得等價(jià)形式 ，取對(duì)數(shù)得,由此構(gòu)造迭代法,

17、且當(dāng) 時(shí)， ，,由于 ,,根據(jù)定理2此迭代法是收斂的.,48,若取 迭代16次得 ，有六位有效數(shù) 字.,若用（3.3）進(jìn)行加速，計(jì)算結(jié)果如下 ：,這里計(jì)算2步（相當(dāng)于（2.2）迭代4步）結(jié)果與 相同，,說明用迭代法（3.3）的收斂速度比迭代法（2.2）快得多.,49,7.4 牛頓法,7.4.1 牛頓法及其收斂性,設(shè)已知方程 有近似根 （假定 )，,將函數(shù) 在點(diǎn) 展開，有,于是方程 可近似地表示為,（4.1）,牛頓法是一種線性化方法，其基本思想是將非線性方程 逐步歸結(jié)為某種線性方程來求解.,50,這是個(gè)線性方程，記其根為 ，,則 的計(jì)算公式為,（4.2）,

18、這就是牛頓(Newton)法.,牛頓法的幾何解釋.,方程 的根 可解釋為,曲線 與 軸的交點(diǎn)的橫坐標(biāo),圖7-4,（圖7-4).,51,設(shè) 是根 的某個(gè)近似值，過曲線 上橫坐標(biāo)為 的點(diǎn) 引切線，并將該切線與 軸的交點(diǎn)的橫坐標(biāo) 作為 的新的近似值.,注意到切線方程為,這樣求得的值 必滿足（4.1），從而就是牛頓公式 （4.2）的計(jì)算結(jié)果.,由于這種幾何背景，牛頓法亦稱切線法.,由定理4，可以直接得到牛頓法的收斂性，,52,由于,假定 是 的一個(gè)單根，即 ， 則由上式知 于是依據(jù)定理4可以斷定，牛頓法 在根 的鄰近是平方收斂的.,(4.2)的迭代函數(shù)為,又因,53,故由（

19、2.9）可得,（4.3）,例7 用牛頓法解方程,（4.4）,解 這里牛頓公式為,取迭代初值 ，迭代結(jié)果列于表7-6中.,所給方程（4.4）實(shí)際上是方程 的等價(jià)形式.,54,牛頓法的計(jì)算步驟：,步驟1 準(zhǔn)備 選定初始近似值 ，計(jì)算,步驟2 迭代 按公式,迭代一次，,得新的近似值 ，,若用不動(dòng)點(diǎn)迭代到同一精度,可見牛頓法的收斂速度是很快的.,要迭代17次.,計(jì)算,55,此處 是允許誤差，而,其中 是取絕對(duì)誤差或相對(duì)誤差的控制常數(shù)，,步驟4 修改 如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù) ，,步驟3 控制 如果 滿足 或 ， 則終止迭代，以 作為所求的根；否則轉(zhuǎn)步驟4.,一般可取,56,或者 ，則

20、方法失??；,否則以 代替 轉(zhuǎn)步驟2繼續(xù)迭代.,57,7.4.2 牛頓法應(yīng)用舉例,對(duì)于給定的正數(shù) ，應(yīng)用牛頓法解二次方程,可導(dǎo)出求開方值 的計(jì)算程序,（4.5）,這種迭代公式對(duì)于任意初值 都是收斂的.,事實(shí)上，對(duì)（4.5）式施行配方手續(xù)，易知,58,以上兩式相除得,據(jù)此反復(fù)遞推有,（4.6）,記,59,解 取初值 ，對(duì) 按(4.5)式迭代3次便得到精度為 的結(jié)果（見表7-8).,對(duì)任意 ，總有 ，故由上式推知，當(dāng) 時(shí) ，即迭代過程恒收斂.,例8 求 .,整理（4.6）式，得,60,由于公式（4.5）對(duì)任意初值 均收斂，并且收 斂的速度很快，因此可取確定的初值如 編成通

21、用程序.,61,7.4.3 簡(jiǎn)化牛頓法與牛頓下山法,牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計(jì)算 及 ，計(jì)算量較大且有時(shí) 計(jì)算較困難，,為克服這兩個(gè)缺點(diǎn)，通?？捎孟率龇椒?,（1） 簡(jiǎn)化牛頓法，也稱平行弦法.其迭代公式為,（4.7）,迭代函數(shù),62,若在根 附近成立 ，即取,則迭代法（4.7）局部收斂.,在（4.7）中取 ，則稱為簡(jiǎn)化牛頓法，,這類方法計(jì)算量省，但只有線性收斂，,其幾何意義是用平行弦與 軸交 點(diǎn)作為 的近似.,如圖7-5所示.,圖7-5,即,63,（2） 牛頓下山法.,牛頓法收斂性依賴初值 的選取.,如果 偏離所求根 較遠(yuǎn)，則牛頓法可能發(fā)散.,例如，用牛

22、頓法求方程,（4.8）,在 附近的一個(gè)根 .,設(shè)取迭代初值 ，用牛頓法公式,（4.9）,計(jì)算得,64,迭代3次得到的結(jié)果 有6位有效數(shù)字.,但如果改用 作為迭代初值，則依牛頓法公式 （4.9）迭代一次得,這個(gè)結(jié)果反而比 更偏離了所求的根 .,為了防止迭代發(fā)散，對(duì)迭代過程再附加一項(xiàng)要求，即 具有單調(diào)性：,（4.10）,滿足這項(xiàng)要求的算法稱下山法.,65,將牛頓法與下山法結(jié)合起來使用，即在下山法保證函 數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度.,將牛頓法的計(jì)算結(jié)果,與前一步的近似值 適當(dāng)加權(quán)平均作為新的改進(jìn)值,（4.11）,其中 稱為下山因子，,（4.12）,(4.12)稱為牛頓

23、下山法.,（4.11）即為,66,選擇下山因子時(shí)從 開始，逐次將 減半進(jìn)行試算，,若用此法解方程（4.8），當(dāng) 時(shí)由（4.9）求得,直到能使下降條件（4.10）成立為止.,，它不滿足條件（4.10）.,通過 逐次取半進(jìn)行試算，當(dāng) 時(shí)可求得,此時(shí)有 ，,顯然 .,而,由 計(jì)算 時(shí) , 均能使條件（4.10） 成立. 計(jì)算結(jié)果如下 ：,67,即為 的近似.一般情況只要能使條件（4.10）成立， 則可得到 ，從而使 收斂.,68,7.4.4 重根情形,設(shè) ，整數(shù) ， 則 為方程 的 重根，此時(shí)有,只要 仍可用牛頓法（4.2）計(jì)算，此時(shí)迭代函數(shù),

24、的導(dǎo)數(shù)為,且 ，所以牛頓法求重根只是線性收斂.,69,則 .,（4.13）,求 重根，則具有2階收斂，但要知道 的重?cái)?shù) .,構(gòu)造求重根的迭代法，還可令 ，,若 是 的 重根，則,若取,用迭代法,70,從而可構(gòu)造迭代法,（4.14）,它是二階收斂的.,故 是 的單根.,對(duì)它用牛頓法，其迭代函數(shù)為,71,例9 方程 的根 是二重根， 用上述三種方法求根.,解,（1） 牛頓法,先求出三種方法的迭代公式：,（2） 用（4.13）式,（3） 用（4.14）式,取初值 ，計(jì)算結(jié)果如表7-9.,,72,從結(jié)果看出，經(jīng)過三步計(jì)算，方法（2）及（3）均達(dá)到 10位有效數(shù)字，而由

25、于牛頓法只有線性收斂，所以要達(dá)到同 樣精度需迭代30次.,73,7.5 弦截法與拋物線法,當(dāng)函數(shù) 比較復(fù)雜時(shí)，計(jì)算 往往較困難，,74,7.5.1 弦截法,（5.1）,由于,因此有,（5.2）,75,（5.2）可以看做將牛頓公式,中的導(dǎo)數(shù) 用差商 取代的結(jié)果.,接著討論幾何意義.,曲線 上橫坐標(biāo)為 的點(diǎn)分別記為 ，,則弦線 的斜率等于差商值 ,,（5.2）,76,按（5.2)式求得的 實(shí)際上是弦線 與 軸交點(diǎn)的橫坐標(biāo).,表7-6,這種算法因此而稱為弦截法.,其方程為,77,而弦截法（5.2），在求 時(shí)要用到前面兩步的結(jié)果 ，,弦截法與切線法（牛頓法）都是線性化方法

26、，但兩者 有本質(zhì)的區(qū)別.,切線法在計(jì)算 時(shí)只用到前一步的值 .,因此使用這種方法必須先給出兩個(gè)開始值 .,例10 用弦截法解方程,解 設(shè)取 作為 開始值，用弦截法求得的結(jié)果見表7-10，,78,實(shí)際上，弦截法具有超線性的收斂性.,比較例7牛頓法的計(jì)算結(jié)果可以看出，弦截法的收斂速度也是相當(dāng)快的.,定理6 假設(shè) 在根 的鄰域 內(nèi) 具有二階連續(xù)導(dǎo)數(shù)，且對(duì)任意 有 ，又初值 那么當(dāng)鄰域充分小時(shí)，弦截法（5.2）將按 階收斂到根 .,這里 是方程 的正根.,79,7.5.2 拋物線法,設(shè)已知方程 的三個(gè)近似根 ，,幾何上，這種方法的基本思想 是用拋物線與 軸

27、的交點(diǎn) 作為 所求根 的近似位置（圖7-7).,圖7-7,這樣確定的迭代過程稱為拋 物線法，亦稱密勒（Mller）法.,80,插值多項(xiàng)式,有兩個(gè)零點(diǎn)：,（5.3）,式中,問題是該如何確定 .,假定在 三個(gè)近似根中， 更接近所求的根 .,81,為了保證精度，選（5.3）中較接近 的一個(gè)值作為新的近似根 .,為此，只要取根式前的符號(hào)與 的符號(hào)相同.,例11 用拋物線法求解方程,解 設(shè)用表7-10的前三個(gè)值,作為開始值，計(jì)算得,,82,故,代入（5.3）式求得,以上計(jì)算表明，拋物線法比弦截法收斂得更快.,在一定條件下可以證明，對(duì)于拋物線法，迭代誤差有 下列漸近關(guān)系式,83,可見拋物線法也是超線性

28、收斂的，其收斂的階 ,,從（5.3）看到，即使 均為實(shí)數(shù)， 也 可以是復(fù)數(shù)，所以拋物線法適用于求多項(xiàng)式的實(shí)根和復(fù)根.,收斂速度比弦截法更接近于牛頓法.,84,7.6 求根問題的敏感性與多項(xiàng)式的零點(diǎn),85,7.6.1 求根問題的敏感性與病態(tài)代數(shù)方程,方程求根的敏感性與函數(shù)求值是相反的，若 ， 則由 求 的病態(tài)性與由 求 的病態(tài)性相反，光滑函數(shù) 在根 附近函數(shù)絕對(duì)誤差與自變量誤差之比 若 ，則求根為反問題，即輸入 滿足 若找到一個(gè) 使 ,則解的誤差 與 之比為 ，即 誤差將 達(dá)到 ，如果 非常小，這個(gè)值就非常大，直 觀的可用圖7-8表示.,86,圖7-8,87

29、,對(duì)多項(xiàng)式方程,若系數(shù)有微小擾動(dòng)其根變化很大，這種根對(duì)系數(shù)變化的敏 感性成為病態(tài)的代數(shù)方程.,若多項(xiàng)式 的系數(shù)有微小變化，可表示為,其中 是一個(gè)多項(xiàng)式，次數(shù)不大于 的零點(diǎn) 表示為 ，令 為 的零點(diǎn)，即 ，將（6.2）對(duì) 求 導(dǎo)，可得,（6.1）,（6.2）,88,于是當(dāng) 時(shí)有,當(dāng) 充分小時(shí)，利用 在 處的泰勒展開得,它表明系數(shù)有微小變化 時(shí)引起根變化的情況.,當(dāng) 很大時(shí)代數(shù)方程（6.1）就是病態(tài)的.,（6.3）,（6.4）,89,例12 多項(xiàng)式,解 取 的根,由（6.4）可得,實(shí)際上，方程 的根 分別為,這說明方程是嚴(yán)重病態(tài)的.,90,

30、7.6.2 多項(xiàng)式的零點(diǎn),很多問題要求多項(xiàng)式的全部零點(diǎn)，即方程（6.1）的 全部根，它等價(jià)于求,的全部根.,前面討論的任一種方法都可用于求出一個(gè)根 ，但通常使用牛頓法最好，可利用秦九韶算法計(jì)算 及 的值.,（6.5）,91,再求 的一個(gè)根 ， ,如此反 復(fù)直到求出全部 個(gè)根.,由牛頓法 計(jì)算到 ，則得到 .,由于 ，即 ，將 的次數(shù)降低一階.,一般地， ，這里 為二次多項(xiàng)式，在此過程中當(dāng) 增加時(shí) 不精確性也增加，為了解決此困難可通過原方程 的牛頓法改進(jìn) 的結(jié)果.,92,由于 可能是復(fù)根，因此使用拋物線法對(duì)求復(fù)根更有利

31、.,若 為復(fù)根，記 ，則 也是一個(gè)根， 于是 是 的一個(gè)二次因 子，于是 是 階多項(xiàng)式，可 降低二階.,即使不是復(fù)根，也可通過拋物線法求出兩個(gè)實(shí)根，它 比牛頓法更優(yōu)越.,93,例13 求 的全部零點(diǎn).,解 先用拋物線法求方程的根，取 計(jì)算到 為止.結(jié)果見表7-11.,94,求得根為 ，從而可得,再由 可求得另外兩根為,可對(duì)原方程 ，以此兩根為初值，用牛頓法迭代一次 可得到更精確的根,95,令一種求多項(xiàng)式零點(diǎn)的方法是將其轉(zhuǎn)化為求矩陣的特征 值問題.,由于方程（6.5）是矩陣,的特征多項(xiàng)式，利用計(jì)算矩陣特征值方法求矩陣

32、的全部 特征值，則可得到方程（6.5)的全部根，MATLAB中的roots 函數(shù)使用的就是這種方法.,此外還有專門針對(duì)求多項(xiàng)式全部零點(diǎn)的專門方法.,96,7.7 非線性方程組的數(shù)值解法,97,考慮方程組,（7.1）,其中 均為 的多元函數(shù).,用向量記號(hào)記 ,,（7.2）,(7.1）就可寫成,7.7.1 非線性方程組,98,例14 求 平面上兩條拋物線 及 的交點(diǎn)，這就是方程組（7.1)中 的情形.,解 當(dāng) 時(shí)無解. 當(dāng) 時(shí)有唯一解,當(dāng) 時(shí)有兩個(gè)解. 及 當(dāng) 時(shí)有4個(gè)解,99,求方程組（7.1）的根可直接將單個(gè)方程 的求根 方法加以推廣，實(shí)際

33、上只要把單變量函數(shù) 看成向量函 數(shù) ，將方程(7.1）改寫為方程組(7.2)，就可將前面 討論的求根方法用于求方程組（7.2）的根.,為此設(shè)向量函數(shù) 定義在區(qū)域 若 ，則稱 在 連續(xù)，這意味著對(duì)任 意實(shí)數(shù) ，存在實(shí)數(shù) ，使得對(duì)滿足 的 ，有,如果 在 上每點(diǎn)都連續(xù)，則稱 在域 上連續(xù).,100,向量函數(shù) 的導(dǎo)數(shù) 稱為 的雅可比矩陣，它表 示為,（7.3）,101,7.7.2 多變量方程的不動(dòng)點(diǎn)迭代法,為了求解方程組（7.2），可將它改寫為便于迭代的形式,（7.4）,其中向量函數(shù) ，且在定義域 上連續(xù)，如果 ，滿足 ，稱 為函數(shù) 的不動(dòng)點(diǎn)， 也就是方

34、程組（7.2）的一個(gè)解.,根據(jù)（7.4）構(gòu)造的迭代法,稱為不動(dòng)點(diǎn)迭代法， 稱為迭代函數(shù).,（7.5）,102,如果由它產(chǎn)生的向量序列 滿足 ，對(duì) （7.5）取極限，由 的連續(xù)性可得 ，故 是 的不動(dòng)點(diǎn)，也就是方程組（7.2）的一個(gè)解.,103,類似于 時(shí)單個(gè)方程有下面的定理.,定理7 函數(shù) 定義在區(qū)域 ，假設(shè)：,（1）存在閉集 及實(shí)數(shù) ，使,（2）對(duì)任意 ，有 .,則 在 有唯一不動(dòng)點(diǎn) ，且對(duì)任意 ，由迭代法 （7.5）生成的序列 收斂到 ，并有誤差估計(jì),定理的條件（1）稱為 的壓縮條件.,（7.6）,（7.7）,104,若 是壓縮的，則它也是連續(xù)的.條件（2）表明

35、把區(qū) 域 映入自身，此定理也稱壓縮映射原理.它是迭代法在域 的全局收斂性定理.,類似于單個(gè)方程還有以下局部收斂定理.,定理8 設(shè) 在定義域內(nèi)有不動(dòng)點(diǎn) 的分量函數(shù)有 連續(xù)偏導(dǎo)數(shù)且,則存在 的一個(gè)鄰域 ，對(duì)任意 ，迭代法（7.5）產(chǎn) 生的序列 收斂于,（7.8）中的 是指函數(shù) 的雅可比矩陣的譜半徑.,（7.8）,105,類似于一元方程迭代法也有向量序列 收斂階的 定義，設(shè) 收斂于 ，若存在常數(shù) 及 ，使,則稱 為 階收斂.,（7.9）,106,設(shè) ，不難驗(yàn)證 ，故有 時(shí) .,例15 用不動(dòng)點(diǎn)迭代法求解方程組,解 將方程組化為（7.4）的形式，其中,1

36、07,又對(duì)一切 ，,于是有 ，即 滿足條件（7.6）. 根據(jù)定理7， 在域 中存在唯一不動(dòng)點(diǎn) 內(nèi)任意點(diǎn)出 發(fā)的迭代法收斂于 .,今取 ，用迭代法（7.5）可求得,108,由于,對(duì)一切 都有 ，故 ，從而有 ，滿足定理7的條件.,此外還可看到 故 ，即滿足定理8條件.,109,7.7.3 非線性方程組的牛頓迭代法,將單個(gè)方程的牛頓法直接用于方程組（7.2）則可得到 解非線性方程組的牛頓迭代法,這里 是（7.3）給出的雅可比矩陣的逆矩陣.,求出向量 ，再令 .每步包括了計(jì)算向 量函數(shù) 及矩陣,（7.10）,具體計(jì)算時(shí)記 ，先解方程組,110,定理9 設(shè) 的定義域?yàn)? 滿足 在 的開鄰域 上 存在且連續(xù)， 非奇異， 則牛頓法生成的序列 在閉域 上超線性收斂于 ， 若還存在常數(shù) ，使,則 至少平方收斂.,牛頓法有以下收斂性定理.,111,例16 用牛頓法解例15的方程組,解,選 ，解線性方程組 ，即,112,解得 ，按牛頓迭代法（7.10）計(jì)算結(jié)果 如表7-12.,