數(shù)值分析方法 課件 第五章 非線性方程的數(shù)值解法

數(shù)值分析方法面向“四新”人才培養(yǎng)普通高等教育系列教材第五章非線性方程的數(shù)值解法目錄/Contents5.1-1非線性方程的近似求根

5.2非線性方程組的數(shù)值解

5.3非線性方程近似求根計(jì)算機(jī)實(shí)驗(yàn)

5.1-2非線性方程的迭代法的加速引言

在科學(xué)研究和工程設(shè)計(jì)中，經(jīng)常會(huì)遇到一類求解非線性方程：方程的根，亦稱為函數(shù)的零點(diǎn).一般地，若為多項(xiàng)式，稱方程

為n次代數(shù)方程，當(dāng)n＞1時(shí)，方程顯然是非線性的；而稱三角方程、指數(shù)方程、對(duì)數(shù)方程等為超越方程.通常

3次以上的代數(shù)方程或超越方程，很難甚至無(wú)法求得精確解，數(shù)值解法可以借助于計(jì)算機(jī)完成求解.

求非線性方程的根的方法分為兩步：計(jì)算根的近似值

確定方程的有根區(qū)間:由零點(diǎn)定理設(shè)，且，則方程在區(qū)間上至少有一個(gè)根。如果在上恒正或恒負(fù)，則此根唯一。5.1非線性方程的近似求根5.1.1二分法二分法的基本思想是將有根區(qū)間二等分，通過(guò)判斷的符號(hào)，逐步對(duì)半縮小有根區(qū)間，直至有根區(qū)間縮小到容許誤差范圍之內(nèi)，然后取區(qū)間的中點(diǎn)為根的近似值.第一步令計(jì)算有根區(qū)間的中點(diǎn)

若

，則為有根區(qū)間，否則為有根區(qū)間，記新的有根區(qū)間為，則第二步對(duì)重復(fù)上述做法得，設(shè)所求的根為，則取為的近似解.且有誤差估計(jì)式：對(duì)于預(yù)先給定的精度，只要，即便有，這時(shí)就是滿足精度要求的近似值.求方程f(x)=0的根的二分法算法python實(shí)現(xiàn)可以編寫(xiě)函數(shù)bisection來(lái)實(shí)現(xiàn)二分算法，代碼如下：defbisection(f,a,b,ep=1e-8):#首先判斷搜索區(qū)間是否包括所求根

iff(a)*f(b)>0:raiseException("區(qū)間端點(diǎn)處函數(shù)值符號(hào)不應(yīng)相同！")#進(jìn)入迭代

whileTrue:x0=(a+b)/2iff(x0)==0:returnx0iff(x0)*f(a)<0:b=x0else:a=x0ifabs(b-a)<ep:returnx0.例5.1.1證明方程在區(qū)間[1.0,1.5]內(nèi)有且只有一個(gè)實(shí)根，且使用二分法求誤差不超過(guò)0.005根至少迭代6次.解：因?yàn)椋苑匠痰挠懈鶇^(qū)間為[1.0,1.5],對(duì)給定的誤差不超過(guò)0.005，有故只要迭代n=6次便能達(dá)到所要求的精度.任取初值，代入中的右端得到

，再以為初值代入方程（1），得到，反復(fù)迭代得如下數(shù)列：5.1.2不動(dòng)點(diǎn)迭代法非線性方程的等價(jià)方程（1）其中為x的連續(xù)函數(shù).方程（1）的解稱為函數(shù)的不動(dòng)點(diǎn).

（2）稱式(2)為求解非線性方程的不動(dòng)點(diǎn)迭代法，稱為迭代函數(shù).

若收斂，即則得是的一個(gè)根迭代法的幾何意義

交點(diǎn)的橫坐標(biāo)解：由

建立迭代

計(jì)算結(jié)果如下:

例5.1.1試用迭代法求方程在區(qū)間(1，2)內(nèi)的實(shí)根。格式k=0,1,2,3…….精確到小數(shù)點(diǎn)后五位但如果由建立迭代公式仍取，則有，,顯然結(jié)果越來(lái)越大，是發(fā)散序列.迭代函數(shù)滿足什么條件，才能保證迭代過(guò)程

是收斂的？迭代法的收斂性定理5.1（壓縮映像原理）設(shè)迭代函數(shù)在閉區(qū)間上滿足以下兩個(gè)條件：（1）對(duì)任意的（2）在上滿足Lipschitz條件：即存在常數(shù)L，是對(duì)有且Lipschitz常數(shù);壓縮映像原理則（1）在上存在唯一解；（2）對(duì)，由產(chǎn)生的序列收斂于，即；（4）（誤差事后估計(jì)式）（誤差事前估計(jì)式）（3）證明：（1）首先證明不動(dòng)點(diǎn)的存在性.構(gòu)造函數(shù)則由連續(xù)函數(shù)介值條件，存在，使得

（3）由Lipschitz條件及遞推關(guān)系得

所以壓縮映像原理在應(yīng)用中定理5.1的條件保證了迭代格式收斂，但Lipschitz條件驗(yàn)證起來(lái)有時(shí)稍顯困難，事實(shí)上，比Lipschitz條件更強(qiáng)的條件是在(a，b)內(nèi)可導(dǎo)，且，Lipschitz常數(shù)L可取的最大值.區(qū)間[a,b]上的收斂性稱為全局收斂性不動(dòng)點(diǎn)迭代法的局部收斂性斂的.

證畢的迭代結(jié)果謝謝數(shù)值分析方法主編

李冬果李林高磊面向“四新”人才培養(yǎng)普通高等教育系列教材第五章非線性方程的數(shù)值解法目錄/Contents5.1-1非線性方程的近似求根

5.2非線性方程組的數(shù)值解

5.3非線性方程近似求根計(jì)算機(jī)實(shí)驗(yàn)

5.1-2非線性方程的迭代法的加速5.1.3迭代法的加速(1)(2)(3)

,稱為Aitken加速法.

Aitken加速：比收斂得略快。將視為新的初值，重復(fù)上述步驟xyy=xy=

(x)x*x0P(x0,x1)x1x2P(x1,x2)P(,)

Steffensen迭代格式幾何解釋：

斯蒂芬森加速可使原本不收斂的迭代改進(jìn)到收斂.

幾何意義：xyx*x0Newton迭代法收斂性(4)例牛頓法求方程在附近的一個(gè)根.

設(shè)取迭代初值，用牛頓法公式計(jì)算迭代3次得到的結(jié)果有6位有效數(shù)字.取這個(gè)結(jié)果反而比更偏離了所求的根.x*x0

x0

x0保證函數(shù)值穩(wěn)定下降滿足這項(xiàng)要求的算法稱下山法.牛頓法的計(jì)算結(jié)果前一步的近似值作加權(quán)平均得其中稱為下山因子，此迭代格式稱為牛頓下山法.xkxk+1下山因子的選取從開(kāi)始，逐次將減半進(jìn)行試算，直到能使下降條件成立為止.

通過(guò)逐次取半進(jìn)行試算，當(dāng)時(shí)可求得當(dāng)時(shí)求得

，不滿足條件此時(shí)有

，而顯然

.

由作為初始值計(jì)算時(shí),均能使下山條件成立.計(jì)算結(jié)果：

即為的近似.（2）計(jì)算較困難.（1）每步迭代要計(jì)算及.缺點(diǎn)1、

弦截法

設(shè)是的近似根，利用

構(gòu)造一次插值多項(xiàng)式，并用的根作為新的近似根.由有

牛頓公式中的導(dǎo)數(shù)用差商取代的結(jié)果.(5)幾何意義

曲線上橫坐標(biāo)為的點(diǎn)分別記為，則弦線的斜率等于差商值,其方程為求得的實(shí)際上是弦線與軸交點(diǎn)的橫坐標(biāo).這種算法因此而稱為弦截法.弦截法與Newton法的區(qū)別

弦截法在求時(shí)要用到前面兩步的結(jié)果，稱為多點(diǎn)迭代法.

切線法在計(jì)算時(shí)只用到前一步的值,故稱之為單點(diǎn)迭代.

例5.1.8用Newton迭代法和弦截法解方程

取作為開(kāi)始值，解弦截法的收斂速度也是相當(dāng)快的Newton迭代格式為：弦截法迭代格式為：——密勒（Müller）法2、

拋物線法

設(shè)已知方程的三個(gè)近似根，以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次

幾何上，這種方法的基本思想是用拋物線與軸的交點(diǎn)作為所求根的近似位置，如圖.插值多項(xiàng)式，

的一個(gè)零點(diǎn)作為新的近似根。并適當(dāng)選取插值多項(xiàng)式其中，有兩個(gè)零點(diǎn)：

式中

問(wèn)題是該如何確定.

假定在三個(gè)近似根中，更接近所求的根，為了保證精度，選較接近的一個(gè)值作為新的近似根.

為此，只要取根式前的符號(hào)與的符號(hào)相同.

例5.1.9用拋物線法求解方程計(jì)算得

取初始值

解故

代入式中求得

在一定條件下可以證明：謝謝數(shù)值分析方法主編

李冬果李林高磊面向“四新”人才培養(yǎng)普通高等教育系列教材第五章非線性方程的數(shù)值解法目錄/Contents5.1-1非線性方程的近似求根

5.2非線性方程組的數(shù)值解

5.3非線性方程近似求根計(jì)算機(jī)實(shí)驗(yàn)

5.1-2非線性方程的迭代法的加速5.2非線性方程組的數(shù)值解非線性方程組的數(shù)值解法在實(shí)際問(wèn)題中有廣泛的應(yīng)用，特別是在許多工程問(wèn)題、經(jīng)濟(jì)學(xué)問(wèn)題、數(shù)學(xué)建模、動(dòng)力學(xué)問(wèn)題等方面，經(jīng)常會(huì)遇到求解如下多元非線性方程組：（1）方程組（1）可表示成向量方程（1）（2）

通常非線性方程組（1）的數(shù)值解法主要包括兩種方法：

區(qū)間迭代法和不動(dòng)點(diǎn)算法1.不動(dòng)點(diǎn)迭代法把方程組(2)改寫(xiě)成下面便于迭代的等價(jià)形式：（3）連續(xù)函數(shù).則的不動(dòng)點(diǎn)，是迭代函數(shù)即滿足)(),(****xxxxxGG=的是自變量,,,21xxxnL收斂，若由此生成的序列是連續(xù)的,即且)(,),(),()(21xxxxnGGKGG的解。是方程組從而*x（2）且有誤差估計(jì)式（5）定理的證明較為復(fù)雜，我們將略去其證明。例5.2.1設(shè)有非線性方程組（6）把它寫(xiě)成等價(jià)形式

由此構(gòu)造不動(dòng)點(diǎn)迭代法公式（7）解從而取初始點(diǎn)，由迭代公式（7）計(jì)算結(jié)果如表，可見(jiàn)迭代收斂到方程的解2.Newton迭代法對(duì)于非線性方程組，也可以構(gòu)造于一元方程的Newton迭代法。

在用多元函數(shù)泰勒展開(kāi)，并取其線性部分，則可表示為令上式右端為零，得到線性方程組（8）（9）若矩陣非奇異，則由使（8）右端為零的向量作為新的一個(gè)近似值，記為，于是得到Newton迭代格式（10）如果寫(xiě)成一般不動(dòng)點(diǎn)迭代的形式，則Newton迭代函數(shù)為

（11）事實(shí)上，在實(shí)際計(jì)算過(guò)程中由于矩陣的逆求解十分耗時(shí)，因此通常通過(guò)求解線性方程組來(lái)替代.如第k步可令先解線性方程組其中包括了計(jì)算向量及Jacobi矩陣.例5.2.2用Newton法解例5.2.1的方程組解

對(duì)該方程組有取初始向量，解方程組，即求出后，。同理計(jì)算結(jié)果如表，可見(jiàn)迭代4次可得精確解，顯然Newton法的收斂速度比例5.2.1中的迭代法要快的多。k0123400.800.9917872210.9999752291.0000000000.880.9917117370.9999685241.00000000例5.2.3用牛頓法解方程組解先計(jì)算Jacobi矩陣由Newton迭代格式（10）得取初始值，則迭代6次可得精度為

=10-6的解

(3.000000，2.645751)T.解線性方程組例5.2.4用修正牛頓法解方程組在附近的解.解先計(jì)算Jacobi矩陣從出發(fā)計(jì)算解線性方程組，即，得于是得新的近似值為反復(fù)迭代結(jié)果如下：修正牛頓法的每一步迭代所用的計(jì)算時(shí)間較少，但迭代的收斂速度減低.為了提高收斂速度，可以在求出后，引入修正因子

i(

i為大于1的正數(shù))，對(duì)求出的新解采用進(jìn)行修正.3.最速下降法最速下降法又稱梯度法.由著名數(shù)學(xué)家Cauchy于1847年提出.該方法是求解n元函數(shù)無(wú)約束最小化問(wèn)題的一種重要解析方法，用于求解實(shí)系數(shù)非線性方程組(1)的一組根.該方法使用函數(shù)的梯度（一階導(dǎo)數(shù)）或Hesse矩陣（二階導(dǎo)數(shù)）對(duì)算法進(jìn)行優(yōu)化.即在射線進(jìn)行搜索，（14）最速下降法計(jì)算步驟如下：例5.2.5用最速下降法求解問(wèn)題：取初始值為.解(1)目標(biāo)函數(shù)的梯度函數(shù)為由得令

，(2)從初始值出發(fā)進(jìn)行一維搜索：t為最優(yōu)步長(zhǎng)，則有（3）從出發(fā)進(jìn)行第二次迭代，計(jì)算令，則有故（4）進(jìn)一步從出發(fā)進(jìn)行第三次迭代，計(jì)算，令，則有此時(shí)，達(dá)到要求的精度，所以問(wèn)題的最優(yōu)解為謝謝數(shù)值分析方法主編

李冬果李林高磊面向“四新”人才培養(yǎng)普通高等教育系列教材第五章非線性方程的數(shù)值解法目錄/Contents5.1-1非線性方程的近似求根

5.2非線性方程組的數(shù)值解

5.3非線性方程近似求根計(jì)算機(jī)實(shí)驗(yàn)

5.1-2非線性方程的迭代法的加速5.3非線性方程近似求根計(jì)算機(jī)實(shí)驗(yàn)根據(jù)5.1.1節(jié)的介紹可以知道，二分法是一種搜索算法，算法需要計(jì)算函數(shù)在搜索區(qū)域中點(diǎn)處的函數(shù)值，并將其與端點(diǎn)值進(jìn)行比較和替換，從而達(dá)到縮小搜索區(qū)間的目的，將這一操作迭代進(jìn)行，直到搜索區(qū)間的大小小于給定的閾值，即可以得到符合精度要求的近似解。由此，可以編寫(xiě)函數(shù)bisection來(lái)實(shí)現(xiàn)二分算法。1.二分法算法實(shí)現(xiàn)例解2.Newton法算法實(shí)現(xiàn)牛頓算法是一種迭代算法，需要首先需要定義函數(shù)function1和它的導(dǎo)函數(shù)dfunction1。function1=lambdax:x**3-x-1

dfunction1=lambdax:3*x**2–1將函數(shù)及其導(dǎo)函數(shù)代入牛頓法函數(shù)，定義初值為1.0，其他參數(shù)采用默認(rèn)值，即：x2=newton_method(function1,dfunction1,1.0)得到方程近似解為1.67169988。3.非線性方程組的牛頓迭代法

importnumpyasnp

fromscipyimportlinalgasla

defnewton_equations(fun,