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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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