計算方法第七章print課件

本章討論非線性方程的求根問題，其中一類特殊的問題就是多項式方程的求根。方程的根又稱為的零點，它使若可表示為，其中為正整數(shù)，且。當時，稱為單根，若稱為重根，或的重零點。若是的重零點，且充分光滑，則7.1

方程求根與二分法7.1

方程求根與二分法當為代數(shù)多項式時，根據(jù)代數(shù)基本定理可知，次方程在復數(shù)域有且只有個根，因此可利用迭代法求代數(shù)方程的根。二分法若，且，根據(jù)連續(xù)函數(shù)性質可知在內至少有一個實根，此時稱為方程的有根區(qū)間。例：求方程的有根區(qū)間。解：通過計算部分點的函數(shù)值，得到如下結果：由此得到方程的有根區(qū)間為：。7.1

方程求根與二分法二分算法設已找到有根區(qū)間，滿足，且在上只有一個零點，步驟如下：

(1)先設對于一般的區(qū)間，設其中點為：

(2)檢驗的符號，若與同號，就取，否則取這樣必有所以就是新的有根區(qū)間，繼續(xù)此過程，即可得到結果。算法：(1)令(2)若或，則輸出，結束(3)若，則令，否則令(4)轉向1)7.1

方程求根與二分法這樣，我們得到了一個序列，為確定的收斂性我們有如下的定理：定理：設則二分算法產生的序列滿足其中為方程的根。證明：因為由對分得到，所以對區(qū)間長度而，且，所以故當時，，且有誤差估計式7.1

方程求根與二分法例：已知在有一個零點，，，用二分法計算的結果如下：7.1

方程求根與二分法，，另外，如果要求，可以從令，可得，即計算17次即可。7.2

迭代法及其收斂性不動點迭代法將方程改寫成等價的形式，則的根也滿足方程，反之亦然。稱為的不動點。而求的根的問題就成為求的不動點問題。選取初值，以公式進行迭代，稱為迭代函數(shù)，若收斂到，則就是的不動點，這種方法就稱為不動點迭代法。將轉化為的方法可以是多種多樣的，例：在上可有以下方法：(1)(2)(3)(4)取，有的收斂，有的發(fā)散，有的快，有的慢。7.2

迭代法及其收斂性迭代過程的幾何表示方程的求根問題在平面上就是要確定曲線與直線的交點，對于的某個近似值，在曲線上可確定一點，它的橫坐標為而縱坐標為，過引軸的平行線，交于，然后過再作軸的平行線，它與的交點記作，則的橫坐標為，而縱坐標為，按圖中箭頭所示路經繼續(xù)做下去，在曲線上得到點列其橫坐標分別為按公式求得的迭代值如果點列趨向于點，則相應的迭代值收斂到所求的根。7.2

迭代法及其收斂性7.2

迭代法及其收斂性例3：求方程在附近的根。解：將方程改寫為，由此建立迭代公式：計算結果如下表：這是一個收斂的例子，也有不收斂的迭代公式，如我們對于同樣的問題，如果將方程改寫為令一種迭代公式，仍取初值，則迭代發(fā)散。為此，我們要研究存在性及迭代法的收斂性。7.2

迭代法及其收斂性定理1：(存在性)設滿足以下兩個條件：(1)對任意的，有(2)存在，使對任意都有則在上存在唯一的不動點。證明：先證不動點的存在性。若或，則或就是不動點。因此由可設及，定義函數(shù)，顯然且滿足由函數(shù)的連續(xù)性可知存在使，即，即為的不動點。7.2

迭代法及其收斂性再證唯一性。設及都是的不動點，則由定理的條件(2)，得到矛盾，故的不動點是唯一的。證畢。定理2：(收斂的充分條件)設滿足定理1的兩個條件，則對任意，由得到的迭代序列收斂到的不動點，并有誤差估計證明：設是在上的唯一不動點，由條件1可知，再由條件2得因，故當時，序列收斂到。7.2

迭代法及其收斂性由迭代公式可得據(jù)此反復遞推，得到于是對任意正整數(shù)，有在上式令，注意到即得到結果。證畢。7.2

迭代法及其收斂性根據(jù)定理2的結論，對于給定的計算精度，迭代次數(shù)是可以預先確定的，但由于公式中含有常數(shù)，使得計算迭代次數(shù)較為復雜，根據(jù)估計式我們得到：令，得到由此可知，只要相鄰兩次計算結果的偏差足夠小即可保證近似值有足夠的精度。7.2

迭代法及其收斂性對于定理中的條件2，在實際使用時，如果且對任意的有則由中值定理可知有它表明定理中條件2可由替代。7.2

迭代法及其收斂性局部收斂性前面討論的收斂性稱為全局收斂性，現(xiàn)在我們討論局部收斂性。定義1：設有不動點，如果存在的某個領域，對任意，迭代公式產生的序列且收斂到，則稱該迭代法局部收斂。定理3：設為的不動點，在的某個領域連續(xù)，且，則迭代法收斂。證明：由連續(xù)函數(shù)的性質，存在的某個領域，使對任意成立，此外，對于任意，總有，這是因為于是依據(jù)定理2可斷定迭代過程對于任意的初值收斂7.2

迭代法及其收斂性關于收斂速度問題的例用不同的方法求方程的根。解：這里，可改寫為各種不同的等價形式：(1)(2)(3)(4)取，對上述4種迭代法，計算三步所得結果如下7.2

迭代法及其收斂性注意，從計算結果看到迭代法(1)和(2)均不收斂，且它們均不滿足定理3種的局部收斂條件迭代法(3)和(4)均滿足局部收斂條件，且(4)比(3)快，這是因為(4)的。為了衡量收斂速度，可以給出如下的定義。7.2

迭代法及其收斂性定義2設迭代過程收斂于方程的根，如果迭代誤差當時成立下列漸進關系式則稱該迭代過程是階收斂的，特別地，時稱線性收斂，時稱超線性收斂，時稱平方收斂。定理4對于迭代過程，如果在所求根的鄰近連續(xù)，并且

(*)則該迭代過程在點鄰近是階收斂的。證明：由于，據(jù)定理3立即可以斷定迭代過程具有局部收斂性。再將在根處做泰勒展開，利用條件(*)，得到7.2

迭代法及其收斂性在與之間，注意到由上式得到因此對迭代誤差，當時有這表明迭代過程確實為階收斂。證畢。定理說明，迭代過程的收斂速度依賴于迭代函數(shù)的選取，如果，則迭代過程只可能時線性收斂。在例4中，迭代法(3)的，故它只是線性收斂，迭代法(4)的，但，故為2階。7.3

迭代法收斂的加速方法埃特金加速收斂方法有的迭代過程雖然收斂，但速度很慢，因此迭代過程的加速是一個重要課題。設是根的某個近似值，用迭代公式校正一次得，而有微分中值定理，有其中介于與之間。假設改變不大，近似地取某個近似，則有若將校正值再校正一次，又得，由于

在兩式中消去，得到，由此推得：7.3

迭代法收斂的加速方法在計算了及之后，可用上式右端作為的新近似，記作，一般情形是由計算，，記該方法稱為埃特金加速方法?？梢宰C明：它表明序列的收斂速度比的收斂速度快。7.3

迭代法收斂的加速方法斯蒂芬森迭代法埃特金方法不管原序列是怎樣產生的，對進行加速計算，得到序列，如果把埃特金加速技巧與不動點迭代結合，則得到如下的迭代法：稱為斯蒂芬森迭代法，它可以這樣理解：我們要求的根，令已知的近似值及，其誤差分別為通過把誤差外推到零，即過及兩點做線性插值函數(shù)，它與軸的交點就是迭代法的結果。7.3

迭代法收斂的加速方法即方程的解：實際上就是將兩個步驟合成一個步驟，如果把它看成一個不動點迭代，則

(*)關于上述不動點迭代法有以下的局部收斂性：定理5若為(*)定義的迭代函數(shù)的不動點，則為的不動點。反之，若為的不動點，設存在，，則是的不動點，且斯法是2階的。7.3

迭代法收斂的加速方法證明：設是的不動點，即，則有：即，所以，即是的不動點。反之，若是的不動點，且設，則故與有相同的不動點?，F(xiàn)設且，則此時，若收斂，且只是一階的，但卻可以是二階的。7.3

迭代法收斂的加速方法因為：取，即有：故：回到一般的，即有：所以：即具有二階收斂性。證畢。7.3

迭代法收斂的加速方法例5用斯蒂芬森迭代法求解方程。解：前面的例3中已經指出迭代格式是發(fā)散的，現(xiàn)用斯蒂芬森迭代法，取，則有迭代公式：取，得到：書上的方法是通過得到的，結果一致。特別注意：對于發(fā)散的算法，斯蒂芬森迭代法仍可能收斂。進一步還可證明斯蒂芬森迭代法的收斂階可以高一階。7.4

牛頓法牛頓法對于方程，如果是線性函數(shù)，則它的求根是容易的，牛頓法就是一種將非線性方程逐步線性化的方法。設已知方程有近似根(假定)，將函數(shù)在點展開，有，于是方程可近似地表示為，這是一個線性方程，記其根為，則的計算公式為這就是牛頓迭代法。7.4

牛頓法牛頓法的幾何意義方程的根在幾何上就是曲線與軸的交點的橫坐標。設是根的某個近似值，通過曲線上橫坐標為的點引切線，切線方程為：令，解得，將其作為下一個近似值就得到牛頓法。因此，牛頓法在幾何上可以解釋為將近似值處曲線上對應點的切線與軸的交點作為的新的近似值，注意到切線方程的形式，我們可以將牛頓法稱為切線法。7.4

牛頓法關于牛頓法的收斂性，由于迭代函數(shù)為：由于假定是的一個單根，即，，則由上式知，于是可得牛頓法在根的附近是平方收斂的。又因故可得7.4

牛頓法例：用牛頓法解方程解：迭代公式為：取初值，迭代結果為：如果用格式，采用不動點迭代法，則要17次迭代才能得到同樣的結果。7.4

牛頓法牛頓法的計算步驟(1)準備：確定初始值，計算(2)迭代：按公式迭代一次，得到新的近似值，計算(3)控制：如果滿足或，則終止迭代，以作為所求的根，否則轉步驟4，此處的是允許誤差，而(4)修改：若，或，則停止，否則轉(2)7.4

牛頓法牛頓法應用舉例：應用牛頓法解二次方程：計算公式為：可以證明，這個迭代公式對于任意的初值均收斂。求，應用上述公式，取，計算3次即得到較高精度。7.4

牛頓法簡化牛頓法與牛頓下山法牛頓法需要計算，計算量較大?？赡懿皇諗?。為克服這兩個缺點，通常采用下述方法：(1)簡化牛頓法迭代函數(shù)：若，即取在根附近成立，則該迭代法局部收斂。若取，則稱為簡化牛頓法。這類算法計算量小，單只有線性收斂。7.4

牛頓法(2)牛頓下山法牛頓法收斂依賴于初始值，因此可能發(fā)散，為防止迭代發(fā)散，我們對迭代過程附加一個要求，即滿足這項要求的算法稱為下山法。我們將牛頓法和下山法結合起來，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快速度，為此我們構造迭代公式：即：，稱為牛頓下山法。其中稱為下山因子。下山因子的選擇取進行試算，逐次減半，直到下山條件成立。7.4

牛頓法重根情形設，整數(shù)，，則為方程的重根，此時有：只要，就可以用牛頓迭代法繼續(xù)計算，此時迭代函數(shù)的導數(shù)為，且，所以牛頓迭代法求重根只是線性收斂。改進方案一取，則，用迭代法求重根，則具有2階收斂，但需要預先知道重數(shù)。7.4

牛頓法改進方案二令，若是的重根，則對于它用牛頓法，其迭代函數(shù)為：從而可構造迭代法它是一個2階的方法。7.4

牛頓法例9：方程的根是二重根，用上述三種方法求根。解：三種方法的迭代公式分別為：

(1)(2)(3)取初值，得到如下結果：(1)為線性收斂，精度不高，(2)(3)為2階收斂，精度高已有10位有效數(shù)字，而方法(1)要30次才達同樣精度7.5

弦截法與拋物線法為回避在牛頓法中需計算的，設法用函數(shù)值來代替，下面介紹兩種常用方法：弦截法設是的近似根，我們利用構造一次插值多項式，并用的根作為的新的近似根，由于因此有：這個結果其實可以看成牛頓公式中導數(shù)用差商來代替7.5

弦截法與拋物線法弦截法的幾何意義7.5

弦截法與拋物線法拋物線法設已知方程的三個近似根，構造二次插值多項式