計算機工程應(yīng)用02-非線性方程2

1計算機工程應(yīng)用第一章代數(shù)方程的計算機方法重點與難點：計算機數(shù)學(xué)概念的理解、計算機數(shù)學(xué)分析方法的應(yīng)用、實際問題的計算機求解算法的實現(xiàn)2第一章代數(shù)方程的計算機方法第一節(jié)問題的引出

在實際工程問題中，我們進行了大量的試驗，從中得到了一個關(guān)于某個現(xiàn)象出現(xiàn)規(guī)律的描述方程，或者說借鑒了前人或其它人的研究成果，即

，其中：來描述某個現(xiàn)象的規(guī)律，并從這種規(guī)律中找出影響該現(xiàn)象最大值或最小值的因素。從數(shù)學(xué)上講，求出某函數(shù)的最大或最小值，就要對某個函數(shù)進行一次微分，即：這時方程就變成了：（1）要想求解出x，就得求解這個方程。

3第一章代數(shù)方程的計算機方法又例如：描述材料的某個性能與因變量的關(guān)系方程式為：我們要從這個規(guī)律中找影響性能最大值的因素，就得求解這個方程的極值，即：

即方程變?yōu)椋?/p>

（2）

解這個方程，求出的x便是這個影響性能極值的因素。以上（1）、（2）這些形式的方程都是典型的代數(shù)方程。從前解法是試算法，即代入一個假設(shè)x值，計算結(jié)果，看是否滿足方程，如果滿足方程，其解就是極值。否則，重新假設(shè)一個x值代入方程進行計算，如此反復(fù)直至達到滿足方程要求為止。這種方法的缺點是：（1）

x值的假設(shè)是隨意的，沒有一個規(guī)律可循。（2）

用手工進行計費時費力。4第一章代數(shù)方程的計算機方法那么什么方法有效呢？這就引出了代數(shù)方程式的計算機解法問題第二節(jié)代數(shù)方程式的計算機解法

1、迭代法迭代法對以上（1）、（2）這些形式的方程的求解特別有效，也是一種常用的方法。對于函數(shù)

求解來說，思路簡單，邏輯嚴密。它是基于使用一個固定的公式，反復(fù)校正根值的近似值，使之逐步精確化，最后，達到滿意的結(jié)果。其具體方法是：對于一般方程首先將其變形為：

（3）式（3）稱為迭代函數(shù)。從式（3）中看出：方程的兩邊都5第一章代數(shù)方程的計算機方法含有未知量x，是一個隱函數(shù)，是不能直接求解的，所以，要事先假設(shè)一個初值x0

，并將其代入（3）中，使方程變?yōu)椋?/p>

(4)式中：x1——為計算值

x0——為假設(shè)初值然后比較

?

(5)或者是否x1充分接近x0

？如果是就結(jié)束計算，則x0或x1就是方程的根，如果不是充分的接近則繼續(xù)按式（4）進行計算。不過，這時代入的初值不是x0而是x1。此時，計算公式為：

如此反復(fù)，其迭代過程中的計算公式就可以用下式表達：

（6）6

并反復(fù)進行檢驗

（7）直到迭代值xn有極限存在，即：

從上面的討論過程看，整個過程用的某一個固定公式的形式就是（6）式，即：

那么，這個公式具有什么意義？如何理解它呢？我們可以試想著將公式（6）看成

:

也就是說有兩個函數(shù)：

（a）

(b)第一章代數(shù)方程的計算機方法7第一章代數(shù)方程的計算機方法圖1迭代法的幾何表示存在，且相等。如果用幾何圖形來表示的話，式（a）、(b)在x-y坐標圖上必然有一個交點，如圖1所示。

x0x1x2x*y=xyx0Q1P0P1P2Q2P*y=φ(x)8交點處的x*就是該迭代方程式的解，其迭代過程如圖中所示。這說明了這種迭代過程的優(yōu)點是：只要迭代函數(shù)選取的得當(dāng)（有效），其迭代過程必然有解，而且迭代值逐漸逼近真值——根，與試算法相比，每一次的初值x0的選取是有規(guī)律可循的，但其缺點和試算是一樣的，要經(jīng)過反復(fù)計算才行。第一章代數(shù)方程的計算機方法那么在什么樣的條件下，才能使迭代函數(shù)有效，也就是說迭代函數(shù)具有收斂性？首先來考察一下迭代函數(shù)為線性時的簡單情況。假設(shè)迭代函數(shù)為：

為了直觀，將函數(shù)用圖示的方法來表示，先令：

然后，在x-y坐標上通過改變φ(x)中的系數(shù)k做出不同的y=x

、y=φ(x)兩條直線

,見下頁圖9第一章代數(shù)方程的計算機方法K<-1圖ay=xy=φ(x)yx0x0x2x1X*圖byy=φ(x)x0y=x-1<K<0X*x1x0x2yy=φ(x)x0y=x0<K<1圖cX*x0x1x2yy=φ(x)x0y=xK>1圖dx0x1x2X*圖2發(fā)散收斂收斂發(fā)散10第一章代數(shù)方程的計算機方法由圖2可以看出，若使y=φ(x)在迭代過程中有近似根存在，須使。進而，我們考察一般情況，設(shè)x*為方程x=φ(x)根，如果有根值存在的話，在迭代過程中會有：

x*-xn+1=φ(x*)-φ(xn)(8)根據(jù)微分中值定理，上式可以用下式進行表示：

x*-xn+1=φ(x*)-φ(xn)=φ’(ξ)（

x*-xn）（9）式中：ξ——是x*與x之間的某一值由此得知，如果存在一個正數(shù)L<１，那么對于任意x∈［a，b］成立：

φ’(x)≤L則有：│x*-xn+1│

=Ｌ│x*-xn│

(10)11第一章代數(shù)方程的計算機方法對用en=│x*-xn│表示迭代誤差時其迭代誤差有：en

=Lne所以，當(dāng)n→∞時，en→0，迭代收斂。需要指出的是：在上述的論證過程中，應(yīng)當(dāng)保證一切迭代值xn全部落在[a,b]內(nèi)，為此，要求對任意x∈[a,b]，總有：

φ（x）∈[a,b]綜上所述，我們有結(jié)論：定理1

設(shè)φ（x）在[a,b]上具有連續(xù)的一階導(dǎo)數(shù)，且（1）對任意x∈[a,b]，總有φ（x）∈[a,b]

（2）存在0≤L<1，使對任意x∈[a,b]成立

│φˊ

(x*)│<L12第一章代數(shù)方程的計算機方法則迭代過程xn+1=φ（xn）對任意初值x∈[a,b]均收斂于方程x=φ（xn）的根x*。且有下列估計式：

│x*-xn+1│≤│xn+1-xn│

（11）

│x*-xn│≤│x1-x0│

（12）（證明從略）據(jù)估計式（11、12）只要相鄰兩次迭代值xn,xn+1的偏差充分小就能保證迭代值xn(或xn+1)足夠精確，因此，可用│xn+1-xn│來控制迭代過程是否結(jié)束。迭代法的一個突出優(yōu)點就是算法邏輯結(jié)構(gòu)簡單，圖3詳細的描述了迭代過程。圖3中x0，x1分別表示每次迭代的初值和終值。ε為精度，N為最大迭代次數(shù)。13第一章代數(shù)方程的計算機方法開始讀入x0

、ε、Nn=n+1(初值為0)輸出迭代失敗標記xn+1=φ(xn)?|xn+1-xn|????<εn等于N？結(jié)束輸出xn+1YNNY圖3迭代法的計算機解法流程圖14第一章代數(shù)方程的計算機方法

迭代法的另一個關(guān)鍵是如何尋找一個迭代函數(shù)。具體的做法是根據(jù)定理1要求去做。即，保證：│φˊ

(x*)│<L例1：求x3-x-1=0的唯一正根。解：首先要考察這個方程式的根存在的范圍。從圖4可以看出，要找出根值存在的范圍，必需使f(x)的值出現(xiàn)異號。在這個例子中，根值存在于x∈[1,2]圖4函數(shù)根值存在的示意圖yxy=f(x)x*15第一章代數(shù)方程的計算機方法其次是尋找適當(dāng)?shù)牡瘮?shù)。根據(jù)迭代函數(shù)的要求，要將原函數(shù)變成迭代函數(shù)。對于這個問題，則要變x3-x-1=0成為能夠迭代的形式。有下面幾種變法：

a變成：x=x3-1，根據(jù)收斂定理要求這個迭代函數(shù)在x∈[1,2]內(nèi)，其導(dǎo)數(shù)要小于1，則有：φˊ(x)=(x3-1)ˊ=3x2

當(dāng)x=1，迭代函數(shù)φˊ(x)

=3>1，當(dāng)x=2時，迭代函數(shù)為=12>1，所以這樣的變換是不行的。

b變成：x3=x+1即：x=(x+1)1/3,

則：φˊ(x)=((x+1)1/3)ˊ=1/3(x+1)-2/3根據(jù)收斂定理要求，這個迭代函數(shù)在x∈[1,2]內(nèi)當(dāng)x=1時，迭代函數(shù)φˊ(1)

=0.20999<1，當(dāng)x=2時，迭代函數(shù)φˊ(2)

=0.16025<1。即符合定理要求，所以，選取這個作為迭代函數(shù)是合理的。

16第一章代數(shù)方程的計算機方法在這個迭代函數(shù)的基礎(chǔ)上，按照圖3的流程圖用VB及C語言進行編程取初值為1.5運算，所得到的結(jié)果見表1nxnnxnnxn01.531.3258861.3247311.3572141.3249471.3247221.3308651.3247681.3247217第一章代數(shù)方程的計算機方法求x3-x-1=0的唯一正根，迭代公式用

x=(x+1)1/3

VBA程序演示：18第一章代數(shù)方程的計算機方法C程序清單：19在實際應(yīng)用迭代法時，通常首先在根x*的鄰近考察，如果存在鄰域，迭代過程對于任意初值

均收斂，這種在根的鄰近具有的收斂性稱作局部收斂性

定理2

設(shè)在根鄰近有連續(xù)的一階導(dǎo)數(shù)，且：

則迭代過程

具有局部收斂性。例2：求方程在x=0.5附近一個根，要求e=10-5。所求的準確值為0.567143。第一章代數(shù)方程的計算機方法20第一章代數(shù)方程的計算機方法解:在x=0.5附近一個根，要求e=10-5，VBA程序演示：21第一章代數(shù)方程的計算機方法例2的C程序清單：22第一章代數(shù)方程的計算機方法nxnnxnnxn00.50000060.564863120.56706710.60653170.568438130.56718620.54523980.566409140.56711930.57970390.567560150.56715740.560065100.566907160.56713550.571172110.5670277170.56714823第一章代數(shù)方程的計算機方法例3：為求方程在x0=1.5附近的一個根，現(xiàn)將方程改寫成下列等價形式，且建立相應(yīng)的迭代公式：試分析每一種迭代公式的收斂性；任取一種收斂的迭代公式計算1.5附近的根，要求|xk+1-xk|<10-624第一章代數(shù)方程的計算機方法

分析判斷一個迭代公式是否收斂，可用迭代法的局部收斂性定理或整體收斂性定理．若有幾個迭代式都收斂，應(yīng)取中L較小的那個迭代法進行計算。解：取x0=1.5的鄰域[1.3，1.6]來考察。25第一章代數(shù)方程的計算機方法＞26第一章代數(shù)方程的計算機方法取第二種迭代式，x0=1.5，計算結(jié)果如下表：kxkkxk01.581.46563446511.48124803491.46559999621.472705730101.46558431631.468817314111.46557718441.467047973121.46557393951.466243010131.46557246361.465876820141.46557179271.46571024115由于|x14-x13|=0.671*10-6<10-6,故可取x*≈x14=1.46557179227第一章代數(shù)方程的計算機方法例4對方程3x2-ex=0,確定迭代函數(shù)φ(x)及區(qū)間[a，b]，使對均收斂，并求該解，要求|xk+1-xk|<10-5分析這樣的題有難度，一般應(yīng)知道函數(shù)f(x)的圖形及根x*的大概位置，才能確定有根區(qū)間及該區(qū)間上的迭代函數(shù).因為,f(x)可能在其定義域內(nèi)有多個根，所以,在沒有指明求哪個根的情況下，就應(yīng)全部求出.根據(jù)3x2和ex的圖形知f(x)=3x2-ex=0有三個根，分別位于區(qū)間(-1,0)，(0,1)，(3,4)內(nèi)28第一章代數(shù)方程的計算機方法29代數(shù)方程的計算機方法取x0=-0.5，計算結(jié)果如下表：kXkKxk0-0.54-0.4590751311-0.4496408415-0.4589363682-0.4611063516-0.4589682113-0.4584705047-0.45896090330第一章代數(shù)方程的計算機方法kxkkxk10.74133242080.90937571820.83640700690.90972012130.877127740100.90987679040.895169427110.90994806850.903281143120.90998049860.906952162130.90999525370.908618410140.91000196731第一章代數(shù)方程的計算機方法3x3x32第一章代數(shù)方程的計算機方法kxkkxk13.60413822693.73217014823.662777674103.73259203633.695055862113.73281810543.712603634123.73293923453.722079126133.73300413263.727177123143.73303890273.729914576153.73305753183.731382952163.73306751133第一章代數(shù)方程的計算機方法2牛頓法牛頓法也是一種求解代數(shù)方程式的數(shù)學(xué)迭代方法。它的基本思想是：為了把根夾住，先找到兩個異號的值在兩個異號的值之間選取方程f(x)=0根的一個估計值x0

，然后將f(x)=0在x0處進行泰勒展開：

f(x1)=f(x0)+f’(x0)(x1-x0)+1/2f”(x0)(x1-x0)2+…=0

因為x0是在f(x0)的根值附近，所以，令：h=x1-x0是一個很小值則h2更是一個極小值，所以將泰勒展開式的右邊的第三項以后的項都有忽略（作為誤差來處理）34第一章代數(shù)方程的計算機方法也即： 移項得：得到35第一章代數(shù)方程的計算機方法yxy=f(x)x*x0x1x2圖4牛頓法的幾何解釋36第一章代數(shù)方程的計算機方法寫成通式，從而得到牛頓迭代公式：

(13)這里xn+1是在x=xn

處曲線的切線與x軸的交點。由于曲線f(x)不是直線，f(xn+1)就不可能是真正的零。因此，就必須以xn=xn+1作為新的基點，重復(fù)以上步驟，直至f(xn+1)充分小牛頓法的實質(zhì)是沿著曲線上的一點切線作外推，而不是在兩個函數(shù)之間作內(nèi)插。這可以從圖4中看出:？切線與X軸的交點37第一章代數(shù)方程的計算機方法從圖4中很明顯的看出，起點位置的選擇會顯著的影響收斂速度。另外，這種方法的缺點是：

1、在迭代過程中，一但曲線的斜率f’(x)=0，就無法迭代下去了。

2、還可以證明當(dāng)f’’(x)趨于無窮大時，牛頓法也將失效。其證明可以直接從函數(shù)的泰勒展示式中得到。即：當(dāng)f’’(x)趨于無窮大時

f(x1)=f(x0)+f’(x0)(x1-x0)+1/2f”(x0)(x1-x0)2+…=0就不能簡化成為：

f(x1)=f(x0)+f’(x0)(x1-x0)=038第一章代數(shù)方程的計算機方法也就不能有：

存在。

牛頓法的好處在于，不用對原函數(shù)f(x)的代數(shù)方程進行迭代變換，所用的固定公式簡單。所以，用牛頓法進行編程時，編程也簡單，這可從圖5的流程圖中看出：

39第一章代數(shù)方程的計算機方法選擇初值xn=x0計算Xn+1和f(Xn+1)Xn+1=x0?f(xn+1)充分?。客Ｖ筜N圖5牛頓法的計算機解法流程圖40第一章代數(shù)方程的計算機方法41第一章代數(shù)方程的計算機方法KXkKXk02.031.32580134511.54545454541.32471890521.35961491651.324717957計算結(jié)果如下表：此時以達到誤差要求，即x*≈x5=1.324717957比較P16頁42第一章代數(shù)方程的計算機方法43第一章代數(shù)方程的計算機方法44第一章代數(shù)方程的計算機方法注意雖然在單根附近牛頓法比一般迭代法有更快的收斂速度．但是，應(yīng)該注意的是：首先牛頓法求根對迭代初值選取要求較嚴，初值選取不好，可能導(dǎo)致迭代不收斂。其次，牛頓法每迭代一次要計算f’(xk)的值.這無疑會增加很多計算量，為回避這個問題，通常并不是每次都去計算f’(xk)的值，而是用一個固定的f’(xk)迭代若干步后再求一次f’(xk)。顯然這樣做減少了工作量，但以降低收斂速度為代價。最后，若方程f(x)＝0中的非線性函數(shù)f(x)僅僅連續(xù)而不可微，顯然不可對其求導(dǎo)數(shù)，即或有時f(x)雖然可求導(dǎo)數(shù)，但導(dǎo)數(shù)計算比較復(fù)雜。對于這兩種情形，都可用函數(shù)在已知點xk和xk+1的差商來代替導(dǎo)數(shù)，這便是下節(jié)要介紹的割線法45第一章代數(shù)方程的計算機方法

3

弦割法

牛頓法的優(yōu)點就是收斂速度快。但是其明顯的缺點就是先要求出f’(x)的值來，如果求導(dǎo)不容易，這時牛頓法就變得不方便了。遇到就種情況時，我們就采用：（14）來代替導(dǎo)數(shù)f’(xn)，這時相應(yīng)的公式就變成了：

（15）46所以，47第一章代數(shù)方程的計算機方法因為；f’(x)=如果將這個極限不讓

，而是有一個微小的范圍，那么上式就變?yōu)椋?所以，在x變化的微小范圍內(nèi)，可以認為：

s(xn)≈f’(x)這種方法的幾何解釋如圖6所示。48第一章代數(shù)方程的計算機方法yxy=f(x)x*xn+1xnxn-1圖6弦割法的幾何示意圖pnpn-149第一章代數(shù)方程的計算機方法yxy=f(x)x*xn+1xnxn-1圖6弦割法的幾何示意圖pnpn-1xn+2pn+150第一章代數(shù)方程的計算機方法其推導(dǎo)過程是：從圖6看，在三角形Pn

、Xn-1

及Xn+1

中,

有:移項，將放在等式的左邊，即：變?yōu)椋簝蛇呁缘茫?1第一章代數(shù)方程的計算機方法弦割法和牛頓法計算機邏輯流程是一樣的，思路簡單，如下圖所示選擇初值xn,xn-1計算Xn+1和f(Xn+1)Xn+1=xnXn=xn-1?f(xn+1)充分小？停止YN圖6弦割法的計算機解法流程圖52第一章代數(shù)方程的計算機方法53第一章代數(shù)方程的計算機方法取初值x0=0.5，x1=0.1,計算結(jié)果如下：KXk-1xk10.50.120.10.36059530.3605950.34823740.3482370.34729150.3472910.34729660.3472960.34729654第一章代數(shù)方程的計算機方法4

二元搜索法二元搜索法是求解一元非線性方程根的常用的方法之一。這種方法也是迭代法的一種。它求解的過程是：首先按x的等距離間隔求出它的函數(shù)值f(x),直到相鄰的兩個函數(shù)值f(xn)和f(xn+1)具有相反的符號為止。即：f(xn)f(xn+1)<0因為對于連續(xù)的函數(shù)而言，這種函數(shù)值的不同就指明了根值的存在。這時用下列式子求出xn和xn+1的中間值xmid

(16)然后，再求出點xmid的函數(shù)值f(xmid)，若f(xmid)與f(xn)同號就以f(xmid)代替f(xn)，否則就以f(xmid)代替f(xn+1)于是含根區(qū)間就縮小為：55第一章代數(shù)方程的計算機方法（xmid，xn+1）或（xn，xmid）。當(dāng)f(xmid)足夠小時就終止這個過程，不然就重復(fù)以上步驟。這種迭代過程的幾何意義可由圖7表示。yxy=f(x)x*xn+1xnxn-1圖7二元搜索法的幾何示意圖pnpn-1Pn+156第一章代數(shù)方程的計算機方法二元搜索法適用于：迭代函數(shù)不好找，牛頓法的f

‘(x)不好求等情況下。二元搜索法的特點是：簡單、直觀。二元搜索法的計算機編程流程見圖857第一章代數(shù)方程的計算機方法在x的等分距上求使f(xn)到f(xn+1)異號的函數(shù)值f(xmid)與f(xn)同號？YNNY圖8二元搜索法的計算機解法流程圖計算xmid和f(xmid)xn+1=xmid

f(xn+1)=f(xmid)xn=xmid，f(xn)=f(xmid)f(xmid)足夠?。拷Y(jié)束58第一章代數(shù)方程的計算機方法59第一章代數(shù)方程的計算機方法n(a,b)Xnf(xn)0(0,1)0.54.6487212181(0,0.5)0.251.7840254312(0,0.25)0.1250.3831484623(0,0.125)0.0625-0.3105055394(0.0625,0.125)0.0937500.0357851395(0.0625,0.093750)0.078125-0.1374921956(0.078125,0.093750)0.0859375-0.0508867847(0.0859375,0.093750)0.089843750-0.0075591688(0.089843750,0.093750)0.0917968750.01