第7章 非線性方程與方程組的數(shù)值解法《數(shù)值分析》

2023年2月1日1第7章非線性方程與方程組的數(shù)值解法7.1方程求根與二分法7.1.1引言方程求根的一般形式：其中，如果實(shí)數(shù)滿足，

則稱是方程的根，或稱是函數(shù)的零點(diǎn)。2023年2月1日2若可分解為：其中為正整數(shù)，且則稱為方程的重根，或?yàn)榈闹亓泓c(diǎn)。時(shí)為單根。若為的重零點(diǎn)，且充分光滑，則2023年2月1日3方程性質(zhì)不同，求解方法也有很大差異。如果函數(shù)是多項(xiàng)式：其中，為實(shí)數(shù)，則稱方程為次代數(shù)方程。

次代數(shù)方程在復(fù)數(shù)域有且只有個(gè)根（含重根）。當(dāng)時(shí)不能用公式表示方程的根，只能數(shù)值求解。2023年2月1日4有根區(qū)間：設(shè)函數(shù)在上連續(xù)，則方程在區(qū)間內(nèi)一定有實(shí)根，稱為方程的有根區(qū)間。對(duì)于超越方程，例如：在整個(gè)軸上有無窮多個(gè)解，取值范圍不同，解也不同。超遠(yuǎn)方程只能通過數(shù)值求解。2023年2月1日5逐次搜索法：設(shè)連續(xù)函數(shù)存在有根區(qū)間①將等分，步長(zhǎng)；②端點(diǎn)；③檢查節(jié)點(diǎn)函數(shù)值④若，則可確定有根區(qū)間。2023年2月1日6P213例1求方程的有根區(qū)間。解：，在區(qū)間內(nèi)至少有一個(gè)實(shí)根。取步長(zhǎng)，進(jìn)行搜索計(jì)算：方程的有根區(qū)間為，，2023年2月1日77.1.2二分法計(jì)算方法：②計(jì)算區(qū)間中點(diǎn)函數(shù)值

③若，則根為，

①計(jì)算區(qū)間端點(diǎn)函數(shù)值、否則：時(shí)，；

時(shí)，；

2023年2月1日8④反復(fù)計(jì)算，直到，（——預(yù)定的精度）最終取值：。誤差：取有根區(qū)間的中點(diǎn)（——二分次數(shù)）作為近似根，則：特點(diǎn)：算法簡(jiǎn)單，可保證收斂，但收斂太慢。用于求近似解。2023年2月1日9P214例2求方程在區(qū)間內(nèi)的一個(gè)實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后的第二位。解：注：，即，2023年2月1日107.2不動(dòng)點(diǎn)迭代法及其收斂性7.2.1不動(dòng)點(diǎn)與不動(dòng)點(diǎn)迭代法將方程改寫成等價(jià)形式：若要求滿足，則；反之亦然?！Q為函數(shù)的一個(gè)不動(dòng)點(diǎn)。因此，求的零點(diǎn)就等價(jià)于求的不動(dòng)點(diǎn)。2023年2月1日11①選擇一個(gè)初始近似值，代入迭代函數(shù)：②將新值作為近似值，再次代入迭代函數(shù)：③反復(fù)迭代，迭代方程：，④迭代存在極限：不動(dòng)點(diǎn)迭代法：則稱迭代方程收斂，且為的不動(dòng)點(diǎn)。2023年2月1日12實(shí)質(zhì)：將隱式方程，通過迭代逐步顯式化——逐次逼近法。幾何意義：直線與曲線其交點(diǎn)橫坐標(biāo)就是方程的根。逐次逼近：（迭代收斂）2023年2月1日13P215例3求方程在附近的根。解：迭代公式，注意：如果迭代公式為，則迭代發(fā)散。2023年2月1日147.2.2不動(dòng)點(diǎn)的存在性與迭代法的收斂性定理1設(shè)函數(shù)滿足以下兩個(gè)條件：（1）

對(duì)于任意，有（2）

存在正常數(shù)，使對(duì)任意都有（迭代函數(shù)在上）（迭代函數(shù)的增量小于自變量的增量）則在上存在唯一的不動(dòng)點(diǎn)。2023年2月1日15證明：先證不動(dòng)點(diǎn)存在性。若，或：則在上存在不動(dòng)點(diǎn)。（不動(dòng)點(diǎn)特點(diǎn)）因，以下設(shè)及，定義：顯然，且滿足，由連續(xù)函數(shù)性質(zhì)可知：存在使即，為的不動(dòng)點(diǎn)。2023年2月1日16再證唯一性。設(shè)及都是的不動(dòng)點(diǎn)，則：引出矛盾。故的不動(dòng)點(diǎn)只能是唯一的。在的不動(dòng)點(diǎn)唯一的情況下，可得到迭代法收斂的充分條件。收斂到的不動(dòng)點(diǎn)，并有誤差估計(jì)2023年2月1日17定理2設(shè)函數(shù)滿足以下兩個(gè)條件：（1）

對(duì)于任意，有（2）

存在正常數(shù)，使對(duì)任意都有則對(duì)任意：由得到的迭代序列2023年2月1日18證明：設(shè)是在上的唯一不動(dòng)點(diǎn)。由定理?xiàng)l件（1）可知：由定理?xiàng)l件（2）可得：反復(fù)應(yīng)用上述結(jié)論：因：故當(dāng)時(shí)，序列收斂到。2023年2月1日19再由定理?xiàng)l件（2）得：如此反復(fù)遞推得：于是對(duì)于任意正整數(shù)有：在上式令，注意到：2023年2月1日20討論一：因正常數(shù)未知，上述誤差估計(jì)無法使用。對(duì)于任意正整數(shù)有：令可得：即：只要相鄰兩次計(jì)算結(jié)果的偏差足夠小，

就能保證近似值具有足夠的精度。2023年2月1日21討論二：在某些情形下可求得。如果且對(duì)任意有則，由中值定理可得：對(duì)有因此，可將上述定理

和定理中的條件（2）改為：2023年2月1日22P215例3求方程在附近的根。例如：（1）當(dāng)時(shí)，在區(qū)間有：由定理2可得：迭代法是收斂的。（2）當(dāng)時(shí)，在區(qū)間有：不滿足定理的條件，無法保證迭代收斂。2023年2月1日237.2.3局部收斂性與收斂階對(duì)于區(qū)間上的任意，所產(chǎn)生的迭代序列都收斂，——稱為全局收斂。實(shí)際應(yīng)用時(shí)，通常只在不動(dòng)點(diǎn)鄰居考察其收斂性，——稱為局部收斂。定義1設(shè)有不動(dòng)點(diǎn)，如果存在的某個(gè)領(lǐng)域：對(duì)任意，迭代產(chǎn)生序列，且收斂到，則稱迭代法局部收斂。且，則迭代法局部收斂。定理3設(shè)為的不動(dòng)點(diǎn)，在的某個(gè)領(lǐng)域連續(xù)，2023年2月1日24證明：由連續(xù)函數(shù)的性質(zhì)，存在的某個(gè)領(lǐng)域：使對(duì)于任意有下式成立：此外，對(duì)于任意，總有，這是因?yàn)椋阂罁?jù)定理2：迭代過程對(duì)于任意均收斂。2023年2月1日25P218題4用不同方法求方程的根。解：這里，可改寫成不同的等價(jià)形式，其不動(dòng)點(diǎn)為（1），，（2），，2023年2月1日26（3），，（4），，取，對(duì)上述4種迭代法，計(jì)算三步的結(jié)果如下表。2023年2月1日27說明：①精確值，迭代法（1）和（2）不收斂，迭代法（3）和（4）收斂；②迭代法（4）中比迭代法（3）小，迭代法（4）比迭代法（3）收斂速度快。2023年2月1日28定義2設(shè)迭代過程收斂于方程的根，如果當(dāng)時(shí)迭代誤差滿足漸進(jìn)關(guān)系式，常數(shù)則稱該迭代過程是階收斂的。特別地，時(shí)稱為線性收斂，時(shí)為超線性收斂，時(shí)為平方收斂。2023年2月1日29定理4對(duì)于迭代過程及正整數(shù)，如果在所求根的鄰近連續(xù)，且則該迭代過程在點(diǎn)鄰近是階收斂的。證明：由于，根據(jù)定理3可得：迭代過程具有局部收斂性。再將在根處泰勒展開，利用定理?xiàng)l件：2023年2月1日30，在與之間注意到，：因此對(duì)迭代誤差，當(dāng)時(shí)有：這表明迭代過程確實(shí)為階收斂。迭代過程的收斂速度依賴于迭代函數(shù)的選取。2023年2月1日31說明①定理表明：②如果時(shí)：則該迭代過程只可能是線性收斂的。③在例4中：迭代法（3）的，故它只能是線性收斂；迭代法（4）的，，迭代為二階收斂。2023年2月1日327.3迭代收斂的加速方法7.3.1埃特金加速收斂方法設(shè)是根的某個(gè)近似值，用迭代公式迭代一次：由微分中值定理：（在與之間）假定變化不大：，2023年2月1日33將校正值再迭代一次：因而有：消去：可推得：注意：①上式是對(duì)兩次迭代值加權(quán)平均后的結(jié)果，可加速迭代；②適用任何求根序列，不只局限于不動(dòng)點(diǎn)迭代序列。已知求根序列，其三個(gè)相鄰值為2023年2月1日34埃特金加速法（加速法）：加速計(jì)算，得到新值，，——點(diǎn)的一階差分；——點(diǎn)的二階差分；可以證明：新序列的收斂速度比的收斂速度快2023年2月1日357.3.2斯特芬森迭代法把埃特金加速法與不動(dòng)點(diǎn)迭代結(jié)合，就可得到斯特芬森迭代法：斯特芬森迭代法是將兩步迭代合成一步得到的：2023年2月1日36斯特芬森迭代法思路：為求解的根，令：已知的近似值及，其誤差分別為：把誤差“外推到零”：即過及兩點(diǎn)做線性插值函數(shù)，它與軸交點(diǎn)就是。2023年2月1日37即求解方程：其解為：即：2023年2月1日38定理5對(duì)于斯特芬森迭代法若為迭代函數(shù)的不動(dòng)點(diǎn)，則也為的不動(dòng)點(diǎn)。反之，若為的不動(dòng)點(diǎn)，設(shè)存在，則也是的不動(dòng)點(diǎn)，且斯特芬森迭代法是二階收斂的。2023年2月1日39P221例5

用斯特芬森法求解方程。解：用迭代公式求解方程是發(fā)散的。改進(jìn)上述迭代公式，斯特芬森迭代法：，因，，2023年2月1日40P222例6

求方程在中的解。解：由方程得，并取對(duì)數(shù)可構(gòu)造迭代法且時(shí)，，由定理2此迭代法是收斂的。若取迭代16次得，有六位有效數(shù)字。若用斯特芬森迭代法加速：2023年2月1日417.4牛頓法7.4.1牛頓法及其收斂性牛頓法基本思想：將非線性方程轉(zhuǎn)化線性方程求解。設(shè)已知方程有近似根，將函數(shù)在點(diǎn)展開于是方程可近似表示為這是個(gè)線性方程，其根為（牛頓法）2023年2月1日42牛頓法的幾何解釋：方程的根為曲線與軸交點(diǎn)的橫坐標(biāo)。設(shè)是根的某個(gè)近似值，過曲線上點(diǎn)引切線，切線與軸交點(diǎn)的橫坐標(biāo)作為新解切線方程：（點(diǎn)斜式方程）其根為牛頓法的近似解——切線法。2023年2月1日43討論：牛頓法的收斂性。，假定是的一個(gè)單根：，代入上式，可得：，因此：牛頓法在根鄰近是平方收斂的。2023年2月1日44P223例7

用牛頓法解方程。解：牛頓公式為取迭代初值2023年2月1日45牛頓法計(jì)算步驟：第一步準(zhǔn)備：選定初值，計(jì)算，第二步迭代：迭代一次，計(jì)算，第三步控制：計(jì)算迭代誤差，（控制常數(shù)），當(dāng)時(shí)，當(dāng)時(shí)2023年2月1日46否則以代替，或者，則方法失?。坏谒牟叫薷模喝绻螖?shù)達(dá)到預(yù)先指定的次數(shù)，如果滿足：或（、允許誤差）則迭代收斂，以作為所求的根，否則轉(zhuǎn)第四步。轉(zhuǎn)第二步繼續(xù)迭代。2023年2月1日477.4.2牛頓法應(yīng)用舉例對(duì)于給定正數(shù)，開方計(jì)算轉(zhuǎn)變?yōu)閼?yīng)用牛頓法解方程。，可以證明：對(duì)于任意初值迭代都收斂。2023年2月1日48證明：由迭代公式：兩式相除：反復(fù)遞推：2023年2月1日49假設(shè)：解出：因此：對(duì)于任意，總有，當(dāng)時(shí)，，即迭代過程恒收斂。迭代函數(shù)為，要求2023年2月1日507.4.3簡(jiǎn)化牛頓法與牛頓下山法牛頓法缺點(diǎn)：①每次迭代都要計(jì)算及，有時(shí)計(jì)算困難。②初始值在根附近才能保證收斂，取值不合適可能不收斂。（1）簡(jiǎn)化牛頓法（平行弦法）迭代公式為其中常量，并保證迭代收斂，即若上式在根附近成立，則該迭代法局部收斂。2023年2月1日51若取為處之值，則有簡(jiǎn)化牛頓法特點(diǎn)：節(jié)省了計(jì)算量，但只有線性收斂。幾何意義：用斜率為的平行弦與軸的交點(diǎn)作為的近似。2023年2月1日52（2）牛頓下山法問題：牛頓法的收斂性依賴于初值。例如：用牛頓法求解方程公式：如果：取迭代初值，，如果：取迭代初值，，結(jié)果偏離了根2023年2月1日53為防止迭代發(fā)散，要求迭代過程具有單調(diào)性——下山法牛頓下山法：下山法保證函數(shù)值穩(wěn)定下降，牛頓法加速收斂先用牛頓法初步迭代在將近似值與加權(quán)平均其中下山因子：2023年2月1日54下山因子選擇：從開始，逐次減半試算，直到滿足下山法要求例如：求解方程，牛頓下山法公式為當(dāng)，時(shí)，求得，且結(jié)果不滿足下山法要求，無法繼續(xù)迭代，需改進(jìn)值。2023年2月1日55逐次對(duì)減半試算：當(dāng)時(shí)，求得以為初值，取，迭代收斂注意：下山因子減半試算，只為確定使迭代收斂的初值。2023年2月1日567.4.4重根情形設(shè)，整數(shù)，則為方程的重根，此時(shí)有：方法1：只要仍可用牛頓法此時(shí)迭代函數(shù)為，其導(dǎo)數(shù)為，且所以牛頓法求重根只是線性收斂。2023年2月1日57改進(jìn)迭代函數(shù)此時(shí)有因此，用改進(jìn)的迭代公式求重根具有二階收斂性。改進(jìn)的迭代公式為缺點(diǎn)：需要知道的重根數(shù)。2023年2月1日58方法2：重新構(gòu)造求重根的迭代法令，若是的重根故是的單根。由此應(yīng)用牛頓法，迭代函數(shù)為從而可構(gòu)造二階收斂的迭代法特點(diǎn)：無需知道值，但要計(jì)算。2023年2月1日59P227例9

方程的根是二重根。

用上述三種方法求根。解：三種方法的迭代公式為（1）牛頓法（2）改進(jìn)法（3）重構(gòu)法2023年2月1日60取初值，計(jì)算結(jié)果如下:注意：方法（2）和（3)均達(dá)到10位有效數(shù)字，而牛頓法達(dá)到同樣精度需迭代30次。2023年2月1日617.5弦截法與拋物線法7.5.1弦截法牛頓法問題：每步需計(jì)算，當(dāng)函數(shù)復(fù)雜時(shí)較困難。設(shè)、是的近似根由、構(gòu)造