數(shù)值分析第7章非線性方程與方程組的數(shù)值解法講義課件

1、第7章 非線性方程與方程組的數(shù)值解法7.1 方程求根與二分法7.1.1 引言方程求根的一般形式：其中 ， 如果實數(shù) 滿足 ， 則稱 是方程的根，或稱 是函數(shù) 的零點。2022年8月22日1若 可分解為：其中 為正整數(shù)，且則稱 為方程的 重根，或 為 的 重零點。 時為單根。若 為 的 重零點，且 充分光滑，則2022年8月22日2方程性質(zhì)不同，求解方法也有很大差異。如果函數(shù) 是多項式：其中 ， 為實數(shù)，則稱方程為 次代數(shù)方程。 次代數(shù)方程在復數(shù)域有且只有 個根（含重根）。當 時不能用公式表示方程的根，只能數(shù)值求解。2022年8月22日3有根區(qū)間：設(shè)函數(shù) 在 上連續(xù)，則方程 在區(qū)間 內(nèi)一定有實根

2、，稱 為方程 的有根區(qū)間。對于超越方程，例如：在整個 軸上有無窮多個解， 取值范圍不同，解也不同。超遠方程只能通過數(shù)值求解。2022年8月22日4逐次搜索法：設(shè)連續(xù)函數(shù) 存在有根區(qū)間 將 等分，步長 ； 端點 ； 檢查節(jié)點函數(shù)值 若 ，則可確定有根區(qū)間 。2022年8月22日5P213 例1 求方程 的有根區(qū)間。解： ， 在區(qū)間 內(nèi)至少有一個實根。取步長 ，進行搜索計算：方程的有根區(qū)間為 ， ， 2022年8月22日67.1.2 二分法計算方法： 計算區(qū)間中點函數(shù)值 若 ，則根為 ， 計算區(qū)間端點函數(shù)值 、 否則： 時 ， ； 時 ， ； 2022年8月22日7 反復計算，直到 ，（ 預定的精

3、度） 最終取值： 。 誤差：取有根區(qū)間 的中點 （ 二分次數(shù)）作為近似根，則：特點：算法簡單，可保證收斂，但收斂太慢。用于求近似解。2022年8月22日8P214例2 求方程 在區(qū)間 內(nèi)的一個實根，要求準確到小數(shù)點后的第二位。解：注： ，即，2022年8月22日97.2 不動點迭代法及其收斂性7.2.1 不動點與不動點迭代法將方程 改寫成等價形式：若要求 滿足 ，則 ；反之亦然。稱 為函數(shù) 的一個不動點。因此，求 的零點就等價于求 的不動點。2022年8月22日10 選擇一個初始近似值 ，代入迭代函數(shù) ： 將新值 作為近似值，再次代入迭代函數(shù)： 反復迭代，迭代方程：， 迭代存在極限：不動點迭代

4、法：則稱迭代方程收斂，且 為 的不動點。2022年8月22日11實質(zhì)：將隱式方程 ，通過迭代逐步顯式化逐次逼近法。幾何意義：直線 與曲線其交點橫坐標就是方程的根。逐次逼近：（迭代收斂）2022年8月22日12P215例3 求方程 在 附近的根 。解：迭代公式，注意：如果迭代公式為 ，則迭代發(fā)散。2022年8月22日137.2.2 不動點的存在性與迭代法的收斂性定理1 設(shè)函數(shù) 滿足以下兩個條件：（1） 對于任意 ，有（2） 存在正常數(shù) ，使對任意 都有（迭代函數(shù)在 上）（迭代函數(shù)的增量小于自變量的增量）則 在 上存在唯一的不動點 。2022年8月22日14證明：先證不動點存在性。若 ，或 ：則

5、在 上存在不動點。（不動點特點 ）因 ，以下設(shè) 及 ，定義：顯然 ，且滿足，由連續(xù)函數(shù)性質(zhì)可知：存在 使即 ， 為 的不動點。2022年8月22日15再證唯一性。設(shè) 及 都是 的不動點，則：引出矛盾。故 的不動點只能是唯一的。在 的不動點唯一的情況下，可得到迭代法收斂的充分條件。2022年8月22日16收斂到 的不動點 ，并有誤差估計定理2 設(shè)函數(shù) 滿足以下兩個條件：（1） 對于任意 ，有（2） 存在正常數(shù) ，使對任意 都有則對任意 ：由 得到的迭代序列 2022年8月22日17證明：設(shè) 是 在 上的唯一不動點。由定理條件（1）可知：由定理條件（2）可得：反復應(yīng)用上述結(jié)論：因 ：故當 時，序列

6、 收斂到 。2022年8月22日18再由定理條件（2）得：如此反復遞推得：于是對于任意正整數(shù) 有：在上式令 ，注意到 ：2022年8月22日19討論一：因正常數(shù) 未知，上述誤差估計無法使用。對于任意正整數(shù) 有：令 可得：即：只要相鄰兩次計算結(jié)果的偏差 足夠小， 就能保證近似值 具有足夠的精度。2022年8月22日20討論二：在某些情形下可求得 。如果 且對任意 有則，由中值定理可得：對 有因此，可將上述定理 和定理 中的條件（2）改為：2022年8月22日21P215例3 求方程 在 附近的根 。例如：（1）當 時，在區(qū)間 有：由定理2可得：迭代法是收斂的。（2）當 時，在區(qū)間 有：不滿足定理

7、的條件，無法保證迭代收斂。2022年8月22日227.2.3 局部收斂性與收斂階對于區(qū)間 上的任意 ，所產(chǎn)生的迭代序列 都收斂，稱為全局收斂。實際應(yīng)用時，通常只在不動點 鄰居考察其收斂性，稱為局部收斂。定義1 設(shè) 有不動點 ，如果存在 的某個領(lǐng)域 ：對任意 ，迭代產(chǎn)生序列 ，且收斂到 ，則稱迭代法局部收斂。2022年8月22日23且 ，則迭代法 局部收斂。定理3 設(shè) 為 的不動點， 在 的某個領(lǐng)域連續(xù)，證明：由連續(xù)函數(shù)的性質(zhì)，存在 的某個領(lǐng)域 ：使對于任意 有下式成立：此外，對于任意 ，總有 ，這是因為：依據(jù)定理2 ：迭代過程對于任意 均收斂。2022年8月22日24P218題4 用不同方法求

8、方程 的根 。解：這里 ，可改寫成不同的等價形式 ，其不動點為（1），（2），2022年8月22日25（3），（4），取 ，對上述4種迭代法，計算三步的結(jié)果如下表。2022年8月22日26說明： 精確值 ，迭代法（1）和（2）不收斂，迭代法（3）和（4）收斂； 迭代法（4）中 比迭代法（3）小，迭代法（4）比迭代法（3）收斂速度快。2022年8月22日27定義2 設(shè)迭代過程 收斂于方程 的根 ， 如果當 時迭代誤差 滿足漸進關(guān)系式，常數(shù)則稱該迭代過程是 階收斂的。特別地， 時稱為線性收斂， 時為超線性收斂， 時為平方收斂。2022年8月22日28定理4 對于迭代過程 及正整數(shù) ，如果 在所求根

9、 的鄰近連續(xù)，且則該迭代過程在點 鄰近是 階收斂的。證明：由于 ，根據(jù)定理3可得：迭代過程 具有局部收斂性。2022年8月22日29再將 在根 處泰勒展開，利用定理條件：， 在 與 之間注意到 ， ：因此對迭代誤差，當 時有：這表明迭代過程 確實為 階收斂。2022年8月22日30迭代過程的收斂速度依賴于迭代函數(shù) 的選取。說明 定理表明： 如果 時 ：則該迭代過程只可能是線性收斂的。 在例4中：迭代法（3）的 ，故它只能是線性收斂；迭代法（4）的 ， ，迭代為二階收斂。2022年8月22日317.3 迭代收斂的加速方法7.3.1 埃特金加速收斂方法設(shè) 是根 的某個近似值，用迭代公式迭代一次：由

10、微分中值定理：（ 在 與 之間 ）假定 變化不大：，2022年8月22日32將校正值 再迭代一次：因而有：消去 ：可推得：注意： 上式是對兩次迭代值加權(quán)平均后的結(jié)果，可加速迭代； 適用任何求根序列 ，不只局限于不動點迭代序列。 2022年8月22日33已知求根序列 ，其三個相鄰值為埃特金加速法（ 加速法）：加速計算，得到新值，點 的一階差分；點 的二階差分；可以證明：新序列 的收斂速度比 的收斂速度快2022年8月22日347.3.2 斯特芬森迭代法把埃特金加速法與不動點迭代結(jié)合，就可得到斯特芬森迭代法：斯特芬森迭代法是將兩步迭代合成一步得到的：2022年8月22日35斯特芬森迭代法思路：為求

11、解 的根 ，令 ： 已知 的近似值 及 ，其誤差分別為：把誤差 “外推到零”：即過 及 兩點做線性插值函數(shù)，它與 軸交點就是 。 2022年8月22日36即求解方程：其解為：即：2022年8月22日37定理5 對于斯特芬森迭代法若 為迭代函數(shù) 的不動點，則 也為 的不動點。反之，若 為 的不動點，設(shè) 存在，則 也是 的不動點，且斯特芬森迭代法是二階收斂的。2022年8月22日38P221例5 用斯特芬森法求解方程 。解：用迭代公式 求解方程是發(fā)散的。改進上述迭代公式，斯特芬森迭代法：，2022年8月22日39因 ， ，P222例6 求方程 在 中的解 。解：由方程得 ，并取對數(shù)可構(gòu)造迭代法且

12、時， ，由定理2此迭代法是收斂的。若取 迭代16次得 ，有六位有效數(shù)字。若用斯特芬森迭代法加速：2022年8月22日407.4 牛頓法7.4.1 牛頓法及其收斂性牛頓法基本思想：將非線性方程轉(zhuǎn)化線性方程求解。設(shè)已知方程 有近似根 ，將函數(shù) 在點 展開于是方程 可近似表示為這是個線性方程，其根為 （牛頓法）2022年8月22日41牛頓法的幾何解釋：方程 的根 為曲線 與 軸交點的橫坐標。設(shè) 是根 的某個近似值，過曲線 上點 引切線，切線與 軸交點的橫坐標 作為新解切線方程：（ 點斜式方程）其根為牛頓法的近似解切線法。2022年8月22日42討論：牛頓法的收斂性。，假定 是 的一個單根：，代入上式

13、，可得：，因此：牛頓法在根 鄰近是平方收斂的。2022年8月22日43P223例7 用牛頓法解方程 。解：牛頓公式為取迭代初值2022年8月22日44牛頓法計算步驟：第一步 準備：選定初值 ，計算 ，第二步 迭代：迭代一次 ，計算 ， 第三步 控制：計算迭代誤差 ，（ 控制常數(shù)），當 時，當 時2022年8月22日45否則以 代替 ，或者 ，則方法失敗；第四步 修改：如果迭代次數(shù)達到預先指定的次數(shù) ，如果 滿足：或 （ 、 允許誤差）則迭代收斂，以 作為所求的根，否則轉(zhuǎn)第四步。轉(zhuǎn)第二步繼續(xù)迭代。2022年8月22日467.4.2 牛頓法應(yīng)用舉例對于給定正數(shù) ，開方計算 轉(zhuǎn)變?yōu)閼?yīng)用牛頓法解方程

14、。 ， 可以證明：對于任意初值 迭代都收斂。 2022年8月22日47證明：由迭代公式：兩式相除：反復遞推：2022年8月22日48假設(shè)：解出：因此：對于任意 ，總有 ，當 時， ，即迭代過程恒收斂。2022年8月22日49迭代函數(shù)為 ，要求7.4.3 簡化牛頓法與牛頓下山法牛頓法缺點： 每次迭代都要計算 及 ，有時計算 困難。 初始值 在根 附近才能保證收斂，取值不合適可能不收斂。（1）簡化牛頓法（平行弦法）迭代公式為其中常量 ，并保證迭代收斂 ，即若上式在根 附近成立，則該迭代法局部收斂。2022年8月22日50若 取為 處之值 ，則有簡化牛頓法特點：節(jié)省了計算量，但只有線性收斂。幾何意義

15、：用斜率為 的平行弦與 軸的交點作為 的近似。2022年8月22日51（2）牛頓下山法問題：牛頓法的收斂性依賴于初值 。例如：用牛頓法求解方程 公式：如果：取迭代初值，如果：取迭代初值，結(jié)果偏離了根2022年8月22日52為防止迭代發(fā)散，要求迭代過程具有單調(diào)性下山法牛頓下山法：下山法保證函數(shù)值穩(wěn)定下降，牛頓法加速收斂先用牛頓法初步迭代在將近似值 與 加權(quán)平均其中下山因子 ：2022年8月22日53下山因子選擇：從 開始，逐次減半試算，直到滿足下山法要求例如：求解方程 ，牛頓下山法公式為當 ， 時，求得 ，且結(jié)果不滿足下山法要求，無法繼續(xù)迭代，需改進 值。2022年8月22日54逐次對 減半試算

16、：當 時，求得以 為初值，取 ，迭代收斂注意：下山因子減半試算，只為確定使迭代收斂的初值 。2022年8月22日557.4.4 重根情形設(shè) ，整數(shù) ，則 為方程 的 重根，此時有：方法1：只要 仍可用牛頓法此時迭代函數(shù)為 ，其導數(shù)為，且所以牛頓法求重根只是線性收斂。2022年8月22日56改進迭代函數(shù)此時有因此，用改進的迭代公式求重根具有二階收斂性。改進的迭代公式為缺點：需要知道 的重根數(shù) 。2022年8月22日57方法2：重新構(gòu)造求重根的迭代法令 ，若 是 的 重根故 是 的單根。由此應(yīng)用牛頓法，迭代函數(shù)為從而可構(gòu)造二階收斂的迭代法特點：無需知道 值，但要計算 。2022年8月22日58P2

17、27例9 方程 的根 是二重根 。 用上述三種方法求根。解：三種方法的迭代公式為（1）牛頓法（2）改進法（3）重構(gòu)法2022年8月22日59取初值 ，計算結(jié)果如下:注意：方法（2）和（3)均達到10位有效數(shù)字，而牛頓法達到同樣精度需迭代30次。2022年8月22日607.5 弦截法與拋物線法7.5.1 弦截法牛頓法問題：每步需計算 ，當函數(shù)復雜時較困難。設(shè) 、 是 的近似根由 、 構(gòu)造一次插值多項式用 的根作為 的新的近似根2022年8月22日61代入牛頓公式，即得弦截法結(jié)果：用差商取代導數(shù)：弦截法幾何意義：過曲線 上橫坐標為 的兩點作弦線 ，其方程為弦線 與 軸交點的橫坐標即為 2022年8

18、月22日62P229例10 用弦截法解方程 。解：迭代公式為選取開始值為注意： 弦截法比牛頓法收斂速度快； 計算時要用到前兩步的結(jié)果 。2022年8月22日63弦截法具有超線性的收斂性定理6 假設(shè) 在根 的鄰域 ： 內(nèi)具有二階連續(xù)導數(shù)，且對任意 有又初值 ，那么當鄰域 充分小時，弦截法將按階 收斂到 。這里 是方程 的正根。2022年8月22日647.5.2 拋物線法設(shè)已知方程 的三個近似根 、 、以這三點為節(jié)點構(gòu)造二次插值多項式適當選取 的一個零點 作為新的近似根拋物線法（密勒法）幾何意義：過節(jié)點 、 、 作拋物線拋物線與 軸的交點即為根 的近似值2022年8月22日65二次插值多項式為有兩個零點在三個近似根 、 、 中，往往 更接近所求根需選取零點中較接近 的一個值作為新的近似根為此，只要取根號前的符號與 的符號相同即可2022年8月22日66P229例11 用拋物線法求解方程 。解：選用例10中迭