第二章非線性方程組數(shù)值解法

§6

非線性方程組的解法

/*TheSolutionsforSystemsofNonlinearEquations*/一、基本概念(/*BasicConcepts*/)n個方程的n元非線性方程組的一般形式：其中是定義在區(qū)域上的n元實值函數(shù)，且中至少有一個是非線性函數(shù)。如是向量n個方程的n元非線性方程組的向量形式：令方程組(*)可表示成向量形式

其中是定義在區(qū)域上的n維實向量值函數(shù)如果使則稱是方程組（*）的解。設

若存在向量，滿足則稱在處可微，向量稱為在處的導數(shù)，記為若是開區(qū)域且

在

內(nèi)每點處都可微，則稱

在

可微。（n元實值函數(shù)的可微性

）/*RealValuedFunctionofnvariables*/證明：令Th2.11

（導數(shù)的求法）

若在處可微，則在處關于各自變量的偏導數(shù)存在，且有/*Differentiate*/

Frechet導數(shù)注：多元實值函數(shù)的導數(shù)實際上就是函數(shù)的梯度。（n元向量函數(shù)的可微性

）記，若存在矩陣，滿足則稱在處可微，矩陣稱為在處的導數(shù)，記為。若是開區(qū)域且在內(nèi)每點都可微，則稱在可微

。/*Functionofnvariables*/Gateaux導數(shù)（定義詳見[3]）Th2.12

（Frechet導數(shù)的計算）設，在處可微的充要條件是的所有分量在處可微；若在處可微，則證明：

在處可微所以存在向量等價于其中即是在處可微的充要條件

在處可微Th2.11所以稱為Jacobi矩陣（收斂階/*theorderofConvergence*/)設向量序列收斂于向量，，若存在實數(shù)

及常數(shù)，滿足或者滿足當（某個正整數(shù)）時，則稱序列是階收斂的。當且時，稱為線性收斂，為超線性收斂，時為平方或二次收斂二、Newton迭代法令設方程組（*）存在解

在的某個開鄰域內(nèi)可微設是方程組（*）的第次近似解Taylor公式展開1、Newton迭代格式寫成向量形式用該線性方程組的解作為非線性方程組（*）的第k+1次近似解從而得到Newton迭代格式：注：Newton迭代格式中每迭代一步都要求矩陣的逆運算，計算量大，應該想辦法避免。Newton迭代方法在實際計算時，轉(zhuǎn)化為求方程組的解缺陷每迭代一次需要計算Jacobi矩陣，計算量仍然很大

需要進一步改進

算法:Newton迭代給定初始近似值

x(0)

，求非線性方程F(x)=0

的解.輸入:

初始近似值

x(0)

;容許誤差

TOL;最大迭代次數(shù)

Nmax.輸出:

近似解x*

或失敗信息.Step1Setk=1;Step2While(k

Nmax)dosteps3-7

Step3

計算和

Step4

求解線性方程組

Step5If||x

x(0)||/||x(0)||<TOLthenOutput(x);

/*成功*/STOP;

Step6Setk++;

Step7Setx(0)=x;/*更新x(0)

*/Step8Output(Themethodfailedafter

Nmax

iterations);/*不成功*/ STOP.Newton迭代格式：解：例5：

用Newton迭代法求解下列方程組，要求選取解方程組即最終結(jié)果見教材P35表2-62、Newton迭代的局部收斂性Th2.13（壓縮映射原理/*CompressionMappingPrinciple*/）設為中的一個閉集，為壓縮映射，即它滿足條件：則下列結(jié)論成立：（1）對任意的，由Newton法產(chǎn)生的迭代序列都有（2）在上有唯一的不動點，，且；（3），即至少線性收斂；（4）有估計式證明詳見[3]證明見P124引理1（Lemma1）引理2（Lemma2

）設，且，則

非奇異且。設，為開凸集，在上可導。若存在常數(shù)，使得對，都有則成立證明：Th2.14（Newton迭代的局部收斂性）設是方程組（*）的解，在包含的某個開區(qū)間內(nèi)連續(xù)可微，且非奇異，則存在閉球

使對任意的，由Newton法產(chǎn)生的序列超線性收斂于；若還有常數(shù)使得則牛頓迭代序列至少二階收斂于。思路2、收斂條件:1、超線性收斂：

映內(nèi)性

壓縮性證明詳見[3]收斂速度快，可以達到二次收斂（但效率并不高）。①每迭代一次需要計算Jacobi矩陣，計算量大；②每迭代一次需要求解線性方程組，當n很大時，工作量巨大。另外：一方面，用Newton迭代求非線性方程組的解，初值的選擇往往比較困難；另一方面，迭代過程中如果出現(xiàn)Jacobi矩陣非奇異的情況，則Newton迭代無法進行下去。優(yōu)點缺點3、Newton格式的變形（/*ModifiedNewtonMethod*/）①帶阻尼因子的Newton格式/*DampedNewtonMethod*/避免Jacobi矩陣的奇異性或病態(tài)程度思想措施在迭代格式中引入阻尼因子注：的選擇要保證每次迭代產(chǎn)生的Jacobi矩陣非奇異且病態(tài)程度不十分嚴重；適當?shù)目墒棺枘酦ewton法是線性收斂的。例6：用Newton法和阻尼Newton法求解方程解：方程的精確解為計算結(jié)果見P38表2-7

下降Newton格式（/*DescentNewtonMethod*/）減小對初始向量值的嚴格限制引入下降因子思想措施的選取原則：優(yōu)點：具有大范圍收斂性。

簡化Newton格式/*SimplifiedNewtonMethod*/

修正的Newton方法(/*ModifiedNewtonMethod*/)每次迭代要調(diào)用簡化Newton格式m次

離散的Newton方法(/*DiscreteNewtonMethod*/)思想避免Jacobi矩陣中導數(shù)的計算方法

擬Newton方法(/*Quasi-NewtonMethod*/)一、基本思想和擬牛頓方程前面所討論的牛頓法的這些變形，都可以寫成如下形式：如Newton方法中為非奇異矩陣其中為了提高計算效率，令或者稱之為擬Newton方程如果取為一元函數(shù)則上式中表示過兩點的割線斜率割線法假設已知，上述方程為n個變量、n2個未知數(shù)的方程，需要添加輔助條件才能得到.的計算方法其中是秩為m的增量矩陣由此得到的迭代法(*)稱為擬Newton法二、Broyden秩