統(tǒng)計(jì)計(jì)算 課件 第1章第二節(jié)牛頓法

11.2方程求根和優(yōu)化算法1.2.1方程求根與二分法1.2.2不動(dòng)點(diǎn)迭代法及其收斂性1.2.3牛頓法1.2.4優(yōu)化算法21.2.1

方程求根與二分法

（1）

主要討論求解單變量非線性方程其中也可以是無窮區(qū)間.

如果實(shí)數(shù)滿足，則稱是方程(1)的根，或稱是的零點(diǎn).1、方程求根3若可分解為其中為正整數(shù)，且則稱為方程(1)的重根，或?yàn)榈闹亓泓c(diǎn)，時(shí)為單根.

若是的重零點(diǎn)，且充分光滑，則

如果函數(shù)是多項(xiàng)式函數(shù)，即（2）其中為實(shí)數(shù)，則稱方程(1)為次代數(shù)方程.4

根據(jù)代數(shù)基本定理可知,n次方程在復(fù)數(shù)域有且只有n

個(gè)根（含重根，m重根為m個(gè)根）.

n=1,2時(shí)的求根公式是熟知的，n=3,4時(shí)的求根公式可在數(shù)學(xué)手冊中查到，但比較復(fù)雜不適合數(shù)值計(jì)算，當(dāng)時(shí)就不能用公式表示方程的根，所以時(shí)求根仍用一般的數(shù)值方法

另一類是超越方程，例如它在整個(gè)軸上有無窮多個(gè)解，若取值范圍不同，解也不同，因此討論非線性方程(1)的求解必須強(qiáng)調(diào)的定義域，即的求解區(qū)間5

非線性問題一般不存在直接的求解公式，故沒有直接方法求解，都要使用迭代法.

迭代法要求先給出根的一個(gè)近似，若且，根據(jù)連續(xù)函數(shù)性質(zhì)可知在內(nèi)至少有一個(gè)實(shí)根，這時(shí)稱為方程(1)的有根區(qū)間.

通常可通過逐次搜索法求得方程的有根區(qū)間.6例1求方程的有根區(qū)間.

解根據(jù)有根區(qū)間定義，對的根進(jìn)行搜索計(jì)算，結(jié)果如下：

由此可知方程的有根區(qū)間為7a=[]deff(x):y=x**3-11.1*x**2+38.8*x-41.77returnyforiinrange(10):s=f(i)a.append(s)print(a)[-41.77,-13.070000000000007,-0.5700000000000074,1.7299999999999969,-0.1700000000000088,-0.2700000000000031,7.430000000000014,28.929999999999986,70.22999999999999,137.32999999999996]8

2、二分法

考察有根區(qū)間，取中點(diǎn)將它分為兩半，假設(shè)中點(diǎn)不是的零點(diǎn)，然后進(jìn)行根的搜索.

檢查與是否同號，如果同號，說明所求的根在的右側(cè),這時(shí)令否則必在的左側(cè)，這時(shí)令

不管出現(xiàn)哪一種情況，新的有根區(qū)間的長度僅為的一半.9

對壓縮了的有根區(qū)間又可施行同樣的手續(xù)，即用中點(diǎn)將區(qū)間再分為兩半，然后通過根的搜索判定所求的根在的哪一側(cè)，從而又確定一個(gè)新的有根區(qū)間，其長度是的一半.

如此反復(fù)二分下去，即可得出一系列有根區(qū)間其中每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半，因此的長度

當(dāng)時(shí)趨于零.10

就是說，如果二分過程無限地繼續(xù)下去，這些區(qū)間最終必收縮于一點(diǎn)，該點(diǎn)顯然就是所求的根.作為根的近似，則在二分過程中可以獲得一個(gè)近似根的序列

該序列必以根為極限.

每次二分后，設(shè)取有根區(qū)間的中點(diǎn)11

由于只要二分足夠多次（即充分大），便有這里為預(yù)定的精度.（3）12

例2求方程

在區(qū)間內(nèi)的一個(gè)實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后第2位.

解這里，而

取的中點(diǎn)，將區(qū)間二等分，由于，即與同號，故所求的根必在右側(cè)，這時(shí)應(yīng)令，而得到新的有根區(qū)間

如此反復(fù)二分下去,按誤差估計(jì)（3）式,欲使只需，即只要二分6次，便能達(dá)到預(yù)定的精度.13

計(jì)算結(jié)果如下表.141.2.2

不動(dòng)點(diǎn)迭代法及其收斂性

1、

不動(dòng)點(diǎn)與不動(dòng)點(diǎn)迭代法

將方程（1）改寫成等價(jià)的形式（4）若滿足，則；反之亦然，稱為函數(shù)的一個(gè)不動(dòng)點(diǎn).

求的零點(diǎn)就等價(jià)于求的不動(dòng)點(diǎn).

選擇一個(gè)初始近似值，將它代入(4)右端，即可求得15如此反復(fù)迭代計(jì)算（5）

稱為迭代函數(shù).

如果對任何，由（5）得到的序列有極限則稱迭代方程(5)收斂，且為的不動(dòng)點(diǎn)，故稱（5）為不動(dòng)點(diǎn)迭代法.16

方程的求根問題在平面上就是要確定曲線與直線的交點(diǎn)

對于的某個(gè)近似值，在曲線上可確定一點(diǎn)，它以為橫坐標(biāo)，而縱坐標(biāo)則等于過引平行軸的直線，設(shè)此直線交直線于點(diǎn)，然后過再作平行于軸的直線，與曲線的交點(diǎn)

上述迭代法是一種逐次逼近法，其基本思想是將隱式方程歸結(jié)為一組顯式的計(jì)算公式.17圖2則點(diǎn)的橫坐標(biāo)為，記作，縱坐標(biāo)則等于

按圖2中箭頭所示的路徑繼續(xù)做下去.在曲線上得到點(diǎn)列，其橫坐標(biāo)分別為18

例3求方程

（6）在附近的根

解設(shè)將方程（6）改寫成下列形式依公式求得的迭代值

如果點(diǎn)列趨向于點(diǎn)，則相應(yīng)的迭代值收斂到所求的根據(jù)此建立迭代公式19各步迭代的結(jié)果見下表.這時(shí)可以認(rèn)為實(shí)際上已滿足方程(6)，即為所求的根.

如果僅取6位數(shù)字，那么結(jié)果與完全相同，20但若采用方程（6）的另一種等價(jià)形式建立迭代公式仍取迭代初值，則有結(jié)果會越來越大，不可能趨于某個(gè)極限.

這種不收斂的迭代過程稱作是發(fā)散的.如圖3.圖3212、不動(dòng)點(diǎn)的存在性與迭代法的收斂性

首先考察在上不動(dòng)點(diǎn)的存在唯一性.

定理1設(shè)滿足以下兩個(gè)條件：1.對任意有2.存在正常數(shù)，使對任意都有（7）則在上存在唯一的不動(dòng)點(diǎn)22

因，以下設(shè)及，

若或，則不動(dòng)點(diǎn)為或，存在性得證.定義函數(shù)顯然，由連續(xù)函數(shù)性質(zhì)可知存在,且滿足使,即即為的不動(dòng)點(diǎn).

證明先證不動(dòng)點(diǎn)存在性.

23

再證唯一性.

設(shè)都是的不動(dòng)點(diǎn)，引出矛盾.故的不動(dòng)點(diǎn)只能是唯一的.

則由(7)得24

定理2設(shè)滿足定理1中的兩個(gè)條件，則對任意，由（5）得到的迭代序列收斂到的不動(dòng)點(diǎn)，并有誤差估計(jì)（8）

證明設(shè)是在上的唯一不動(dòng)點(diǎn)，由條件，可知，再由（7）得因，故當(dāng)時(shí)序列收斂到.25

再證明估計(jì)式（8），由（7）有（9）反復(fù)遞推得于是對任意正整數(shù)有26在上式令，注意到即得式（8）.

在用迭代法實(shí)際計(jì)算時(shí)，必須按精度要求控制迭代次數(shù).

原則上可以用誤差估計(jì)式（8）確定迭代次數(shù)，但由于它含有信息而不便于實(shí)際應(yīng)用.

根據(jù)式（9），對任意正整數(shù)有在上式中令知27

由此可見，只要相鄰兩次計(jì)算結(jié)果的偏差足夠小即可保證近似值具有足夠精度.

對定理1和定理2中的條件2，如果且對任意有（10）則由中值定理可知對有表明定理中的條件2可用（10）代替.28

例3中，當(dāng)時(shí)，,在區(qū)間中，，故（10）成立.

又因，故定理1中條件1也成立.所以迭代法是收斂的.

而當(dāng)時(shí)，，在區(qū)間中不滿足定理?xiàng)l件.29

3、

局部收斂性與收斂階

上面給出了迭代序列在區(qū)間上的收斂性，

定理的條件有時(shí)不易檢驗(yàn)，實(shí)際應(yīng)用時(shí)通常只在不動(dòng)點(diǎn)的鄰近考察其收斂性，即局部收斂性.

定義1設(shè)有不動(dòng)點(diǎn)，如果存在的某個(gè)鄰域?qū)θ我?，迭代?）產(chǎn)生的序列且收斂到，則稱迭代法（5）局部收斂.通常稱為全局收斂性.30

證明由連續(xù)函數(shù)的性質(zhì)，存在的某個(gè)鄰域使對于任意成立

定理3設(shè)為的不動(dòng)點(diǎn)，在的某個(gè)鄰域連續(xù)，且，則迭代法（5）局部收斂.此外，對于任意，總有，于是依據(jù)定理2可以斷定迭代過程對于任意初值均收斂.這是因?yàn)?1

討論迭代序列的收斂速度.

例4用不同方法求方程的根

解這里，可改寫為各種不同的等價(jià)形式其不動(dòng)點(diǎn)為由此構(gòu)造不同的迭代法：32取，對上述4種迭代法，計(jì)算三步所得的結(jié)果如下表.

注意.33

從計(jì)算結(jié)果看到迭代法（1）及（2）均不收斂，且它們均不滿足定理3中的局部收斂條件.

迭代法（3）和（4）均滿足局部收斂條件，且迭代法（4）比（3）收斂快，因在迭代法（4）中.34importnumpyasnpx0=2n=10foriinrange(n):x1=x0**2+x0-3ifnp.abs(x1-x0)<10**(-4):breakx0=x1print(x1)35

定義2設(shè)迭代過程收斂于方程的根，如果迭代誤差當(dāng)時(shí)成立下列漸近關(guān)系式則稱該迭代過程是階收斂的.

特別地,時(shí)稱線性收斂，時(shí)稱超線性收斂，時(shí)稱平方收斂.36

定理4對于迭代過程，如果在所求根的鄰近連續(xù)，并且

則該迭代過程在點(diǎn)鄰近是階收斂的.（11）37注意到，因此對迭代誤差，當(dāng)時(shí)有（12）這表明迭代過程確實(shí)為階收斂.

上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù)的選取.

如果當(dāng)時(shí)，則該迭代過程只可能是線性收斂.38

在例4中，迭代法（3）的，故它只是線性收斂.

而迭代法（4）的，而由定理4知，該迭代過程為2階收斂.

39

1.2.3

牛頓法及其收斂性

設(shè)已知方程有近似根（假定)，將函數(shù)在點(diǎn)展開，有于是方程可近似地表示為（13）

牛頓法是一種線性化方法，其基本思想是將非線性方程逐步歸結(jié)為某種線性方程來求解.

1、

牛頓法及其收斂性40這是個(gè)線性方程，記其根為，則的計(jì)算公式為（14）這就是牛頓(Newton)法.

牛頓法的幾何解釋.

方程的根可解釋為曲線與軸的交點(diǎn)的橫坐標(biāo)41

設(shè)是根的某個(gè)近似值，過曲線上橫坐標(biāo)為的點(diǎn)引切線，并將該切線與軸的交點(diǎn)的橫坐標(biāo)作為的新的近似值.

注意到切線方程為這樣求得的值必滿足（13），從而就是牛頓公式（14）的計(jì)算結(jié)果.

由于這種幾何背景，牛頓法亦稱切線法.

由定理4，可以直接得到牛頓法的收斂性，42由于假定是的一個(gè)單根，即，則由上式知于是依據(jù)定理4可以斷定，牛頓法在根的鄰近是平方收斂的.

(14)的迭代函數(shù)為43

例7用牛頓法解方程

（17）

解這里牛頓公式為

取迭代初值，迭代結(jié)果列于表中.44

若用不動(dòng)點(diǎn)迭代到同一精度

可見牛頓法的收斂速度是很快的.要迭代17次.

所給方程（17）實(shí)際上是方程的等價(jià)形式.45牛頓法應(yīng)用舉例

對于給定的正數(shù)，應(yīng)用牛頓法解二次方程可導(dǎo)出求開方值的計(jì)算程序（18）這種迭代公式對于任意初值都是收斂的.

事實(shí)上，對（18）式施行配方手續(xù)，易知46以上兩式相除得據(jù)此反復(fù)遞推有（19）記47

解取初值，對按(18)式迭代3次便得到精度為的結(jié)果（見表).

對任意，總有，故由上式推知，當(dāng)時(shí)，即迭代過程恒收斂.

例8求.

整理（19）式，得48

由于公式（18）對任意初值均收斂，并且收斂的速度很快，因此可取確定的初值如編成通用程序.493、

簡化牛頓法與牛頓下山法

牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計(jì)算及，計(jì)算量較大且有時(shí)計(jì)算較困難，

為克服這兩個(gè)缺點(diǎn)，通?？捎孟率龇椒?

（1）簡化牛頓法，也稱平行弦法.其迭代公式為

（20）迭代函數(shù)

二是初始近似只在根附近才能保證收斂，如給的不合適可能不收斂.50

若在根附近成立，即取則迭代法（20）局部收斂.

在（20）中取，則稱為簡化牛頓法，這類方法計(jì)算量省，但只有線性收斂，

其幾何意義是用平行弦與軸交點(diǎn)作為的近似.即51

（2）牛頓下山法.

牛頓法收斂性依賴初值的選取.

如果偏離所求根較遠(yuǎn)，則牛頓法可能發(fā)散.

例如，用牛頓法求方程（21）在附近的一個(gè)根.

設(shè)取迭代初值，用牛頓法公式（22）計(jì)算得52迭代3次得到的結(jié)果有6位有效數(shù)字.

但如果改用作為迭代初值，則依牛頓法公式（22）迭代一次得這個(gè)結(jié)果反而比更偏離了所求的根.

為了防止迭代發(fā)散，對迭代過程再附加一項(xiàng)要求，即具有單調(diào)性：（23）滿足這項(xiàng)要求的算法稱下山法.53

將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度.

將牛頓法的計(jì)算結(jié)果與前一步的近似值適當(dāng)加權(quán)平均作為新的改進(jìn)值（24）其中稱為下山因子，（25）(25)稱為牛頓下山法.（24）即為54

選擇下山因子時(shí)從λ=1開始，逐次將

λ

減半進(jìn)行試算，直到能使下降條件（4.23）成立為止.

若用此法解方程（21），當(dāng)時(shí)由（22）求得

，它不滿足條件（23）.

通過λ逐次取半進(jìn)行試算，當(dāng)λ=1/32時(shí)可求得顯然.此時(shí)有，而

由計(jì)算時(shí),均能使條件（23）成立.計(jì)算結(jié)果如下：55

即為的近似.一般情況只要能使條件（4.10）成立，則可得到，從而使收斂.

56定理5（全局收斂定理）函數(shù)在區(qū)間[a,b]上滿足如下條件：且一階導(dǎo)數(shù)和二階導(dǎo)數(shù)在區(qū)間[a,b]上符號保持不變；y=f(x)在區(qū)間[a,b]上有一個(gè)根，由牛頓法得到的近似解收斂于方程f(x)=