第五非線性方程求根演示文稿

第五非線性方程求根演示文稿現(xiàn)在是1頁\一共有64頁\編輯于星期四（優(yōu)選）第五非線性方程求根現(xiàn)在是2頁\一共有64頁\編輯于星期四圖5.1.1衛(wèi)星定位示意圖

美國和前蘇聯(lián)的GPS都包括有24顆衛(wèi)星,它們不斷地向地球發(fā)射信號報告當前位置和發(fā)出信號的時間,衛(wèi)星分布如圖所示。它的基本原理是:在地球的任何一個位置，至少同時收到4顆以上衛(wèi)星發(fā)射的信號。發(fā)射的信號，

設地球上一個點R，同時收到衛(wèi)星

現(xiàn)在是3頁\一共有64頁\編輯于星期四假設接收的信息如表所示。請設法確定R點的位置。圖5.1.2衛(wèi)星分布圖表GPS導航問題可歸結為求解非線性代數(shù)數(shù)方程組,當時就是單個方程.現(xiàn)在是4頁\一共有64頁\編輯于星期四.其中可以是代數(shù)方程，也可以是超越方程。使成立的x值稱為方程的根，或稱為的零點。科學與工程計算中，如電路和電力系統(tǒng)計算、非線性力學、非線性微（積分）方程、非線性規(guī)劃（優(yōu)化）等眾多領域中，問題的求解和模擬最終往往都要解決求根或優(yōu)化問題。前一種情形要求出方程（組）的根；后一種情形則要求找出函數(shù)取最大或最小的點。即使是對實驗數(shù)據進行擬合或數(shù)值求解微分方程，也總是將問題簡化成上述兩類問題。上述除少數(shù)特殊方程外，大多數(shù)非線性代數(shù)方程（組）很難使用解析法求解精確解，一般需要通過一些數(shù)值方法逼近方程的解。這里主要介紹單個方程的數(shù)值解法，方程組也可以采用類似的方法，將放在后面討論。現(xiàn)在是5頁\一共有64頁\編輯于星期四1．根的存在性。方程有沒有根？如果有，有幾個根？2．根的搜索。這些根大致在哪里？如何把根隔離開？3．根的精確化。

f(x)=0（）現(xiàn)在是6頁\一共有64頁\編輯于星期四1.根的存在性定理1：設函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，如果f(a)

f(b)<0，

則方程f(x)=0在[a,b]內至少有一實根x*。

定義：如果存在使得，則稱為方程（）的根或函數(shù)的零點。若其中為正整數(shù)，則當m=1時，稱為方程（5.1.1）的單根或函數(shù)的單零點。當時，稱為方程（5.1.1）的m重根或函數(shù)的m重零點?，F(xiàn)在是7頁\一共有64頁\編輯于星期四2.根的搜索(1)圖解法（利用作圖軟件如Matlab)(2)解析法(3)近似方程法(4)定步長搜索法現(xiàn)在是8頁\一共有64頁\編輯于星期四（1）畫出f(x)的略圖，從而看出曲線與x軸交點的位置。（2）從左端點x=a出發(fā)，按某個預先選定的步長h一步一步地向右跨，每跨一步都檢驗每步起點x0和終點x0+h的函數(shù)值，若那么所求的根x*必在x0與x0+h之間，這里可取x0或作為根的初始近似。x*abf(x)現(xiàn)在是9頁\一共有64頁\編輯于星期四

開始讀入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印結束否是繼續(xù)掃描

例1：考察方程

x00.51.01.5f(x)的符號－－－＋現(xiàn)在是10頁\一共有64頁\編輯于星期四ab或不能保證

x

的精度abx0x1x*§2二分法現(xiàn)在是11頁\一共有64頁\編輯于星期四

執(zhí)行步驟1．計算f(x)在有解區(qū)間[a,b]端點處的值，f(a)，f(b)。2．計算f(x)在區(qū)間中點處的值f(x0)。3．判斷若f(x0)=0，則x0即是根，否則檢驗：（1）若f(x1)與f(a)異號，則知解位于區(qū)間[a,x0]，

b1=x0,a1=a;（2）若f(x0)與f(a)同號，則知解位于區(qū)間[x0,b]，

a1=x0,b1=b。反復執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：

現(xiàn)在是12頁\一共有64頁\編輯于星期四4、當時，停止；即為根的近似。當時，，即這些區(qū)間必將收縮于一點，也就是方程的根。在實際計算中，只要的區(qū)間長度小于預定容許誤差就可以停止搜索，即然后取其中點作為方程的一個根的近似值。注：

現(xiàn)在是13頁\一共有64頁\編輯于星期四例1證明方程存在唯一的實根用二分法求出此根，要求誤差不超過。解：記，則對任意

，因而，是嚴格單調的，最多有一個根，所以，有唯一實根又因為

現(xiàn)在是14頁\一共有64頁\編輯于星期四用二分法求解，要使，只要解得，取。所以只要二等分7次，即可求得滿足精度要求的根。計算過程如表所示k

f(ak)及符號f(xk)及符號f(bk)及符號012345670(－)0(－)0(－)0(－)0.0625(－)0.0625(－)0.078125(－)0.0859375(－)0.5(+)0.25(+)0.125(+)0.0625(－)0.09375(+)0.078125(－)0.0859375(－)1(+)0.5(+)0.25(+)0.125(+)0.125(+)0.09375(+)0.09375(+)0.09375(+)表所以，現(xiàn)在是15頁\一共有64頁\編輯于星期四①簡單;②對f(x)

要求不高(只要連續(xù)即可).①無法求復根及偶重根②收斂慢

二分法的優(yōu)缺點現(xiàn)在是16頁\一共有64頁\編輯于星期四

問題雖然二分法計算簡單，能夠保證收斂，但是它對于方程單根存在區(qū)域信息要求太高，一般情況下很難實現(xiàn)，并且不能求重根、復根和虛根。在實際應用中，用來求解方程根的主要方法是迭代法。使用迭代法求解非線性代數(shù)方程的步驟為：(1)迭代格式的構造；(2)迭代格式的收斂性分析；(3)迭代格式的收斂速度與誤差分析?！?

迭代法現(xiàn)在是17頁\一共有64頁\編輯于星期四1．簡單迭代法f(x)=0x=

(x)等價變換其中

(x)是連續(xù)函數(shù)。方程（）稱為不動點方程，滿足（）式的點稱為不動點，這樣就將求（）的零點問題轉化為求的不動點問題。稱這種迭代格式為不動點迭代。以不動點方程為原型構造迭代格式現(xiàn)在是18頁\一共有64頁\編輯于星期四例3：求方程的一個根.構造迭代格式x1=0.4771x2=0.3939 …x6=0.3758x7=0.3758解：給定初始點現(xiàn)在是19頁\一共有64頁\編輯于星期四xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1現(xiàn)在是20頁\一共有64頁\編輯于星期四定理2如果

(x)滿足下列條件 （1）當x[a,b]時，(x)[a,b]

（2）當任意x[a,b]，存在0<L<1，使 則方程x=

(x)在[a,b]上有唯一的根x*,且對任意初值

x0[a,b]時，迭代序列xk+1=

(xk)

(k=0,1,…)收斂于

x*，且有如下誤差估計式：(5.3.2)2．迭代過程的收斂性與誤差估計停機準則。（）現(xiàn)在是21頁\一共有64頁\編輯于星期四求方程在內的根例：。解：原方程可以等價變形為下列三個迭代格式現(xiàn)在是22頁\一共有64頁\編輯于星期四由迭代格式（1）

取初值得

結果是發(fā)散的？！現(xiàn)在是23頁\一共有64頁\編輯于星期四由迭代格式（2）

取初值得

結果精確到四位有效數(shù)字，迭代到得到收斂結果。

十步才能得到收斂的結果！現(xiàn)在是24頁\一共有64頁\編輯于星期四

由迭代格式（3）

取初值得

結果精確到四位有效數(shù)字，迭代到得到收斂結果。四步就能得到收斂的結果了！現(xiàn)在是25頁\一共有64頁\編輯于星期四迭代格式（1）的迭代函數(shù)為

求導得

當時故迭代格式（1）是發(fā)散的。分析:現(xiàn)在是26頁\一共有64頁\編輯于星期四當時，

迭代格式（2）的迭代函數(shù)為

由知當時，

所以迭代格式（2）是收斂的。現(xiàn)在是27頁\一共有64頁\編輯于星期四迭代格式（3）的迭代函數(shù)為當時，由時，

知當所以迭代格式（3）也是收斂的?，F(xiàn)在是28頁\一共有64頁\編輯于星期四結論:

通過以上算例可以看出對迭代函數(shù)所得到的若小于1，則收斂；且上界越小收斂速度越快。求導，的上界若是大于1，則迭代格式發(fā)散；現(xiàn)在是29頁\一共有64頁\編輯于星期四

3.加速收斂技術

L越小迭代法的收斂速度越快，因此，可以從尋找較小的L來改進迭代格式以加快收斂速度。思路(1)松弛法引入待定參數(shù)，將

作等價變形為（）將方程右端記為，則得到新的迭代格式現(xiàn)在是30頁\一共有64頁\編輯于星期四由定理2知為了使新的迭代格式比原來迭代格式收斂得更快，只要滿足且越小，所獲取的L就越小，迭代法收斂的就越快，因此我們希望。現(xiàn)在是31頁\一共有64頁\編輯于星期四可取

，若記則（）式可改寫為稱為松弛因子，這種方法稱為松弛法。為使迭代速度加快，需要邊計算邊調整松弛因子。由于計算松弛因子需要用到微商，在實際應用中不便使用，具有一定局限性。若迭代法是線性收斂的，當計算不方便時，可以采用埃特金加速公式?，F(xiàn)在是32頁\一共有64頁\編輯于星期四(2)埃特金加速公式設迭代法是線性收斂，由定義知成立，故當時有由此可得的近似值（）現(xiàn)在是33頁\一共有64頁\編輯于星期四由此獲得比和更好的近似值，利用（）序列的方法稱為(3)Steffensen加速法

將Aitken加速公式與不動點迭代相結合，可得（）式構造埃特金（Aitken）加速方法。利用（）式構造序列的方法稱為Steffensen加速方法。即每進行兩次不動點迭代，就執(zhí)行一次Aitken加速?，F(xiàn)在是34頁\一共有64頁\編輯于星期四例2試用簡單迭代法和Steffensen加速法求方程在附近的根，精確至四位有效數(shù)。解：記，簡單迭代法公式為：計算得kxkkxkkxk00.570.55844140.5671210.6065380.56641150.5671620.5452490.56756160.5671430.57970100.5669140.56006110.5672850.57117120.5670760.56486130.56719現(xiàn)在是35頁\一共有64頁\編輯于星期四Aitken加速公式計算得所以,?，F(xiàn)在是36頁\一共有64頁\編輯于星期四4．迭代過程的局部收斂定義1：

若存在的某一鄰域，迭代過程對任意初值均收斂，則稱迭代過程在根鄰近具有局部收斂性。定理3設為方程的根，在的鄰近連續(xù)，且，則迭代過程在的鄰近具有局部收斂性?，F(xiàn)在是37頁\一共有64頁\編輯于星期四5．迭代過程的收斂速度

設由某方法確定的序列{xk}收斂于方程的根x*，如果存在正實數(shù)p，使得

（C為非零常數(shù)）定義2則稱序列{xk}收斂于x*的收斂速度是p階的，或稱該方法具有p階收斂速度。當p=1時，稱該方法為線性（一次）收斂；當p=2時，稱方法為平方（二次）收斂；當1<p<2或C=0,p=1時，稱方法為超線性收斂。

現(xiàn)在是38頁\一共有64頁\編輯于星期四定理4

如果在附近的某個領域內有()階連續(xù)導數(shù)，且則迭代格式在

附近是階局部收斂的，且有現(xiàn)在是39頁\一共有64頁\編輯于星期四§3牛頓法一、牛頓法的迭代公式考慮非線性方程原理：將非線性方程線性化—Taylor展開取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0

和x

之間。現(xiàn)在是40頁\一共有64頁\編輯于星期四將(x*

x0)2

看成高階小量，則有：只要f

C1，且每步迭代都有，而且則

x*就是f(x)的根。公式（）稱為牛頓迭代公式。(9.4.1)構造迭代公式現(xiàn)在是41頁\一共有64頁\編輯于星期四x*x0x1x2xyf(x)二、牛頓法的幾何意義現(xiàn)在是42頁\一共有64頁\編輯于星期四三、牛頓法的收斂性定理4：

設f(x)在[a,b]上存在二階連續(xù)導數(shù)且滿足下列條件： （1）f(a)

f(b)<0； （2）f’(x)0； （3）f(x)在區(qū)間[a,b]上不變號； （4）取x0[a,b]，使得f(x)f(x0)>0則由（）確定的牛頓迭代序列{xk}二階收斂于f(x)在[a,b]上的唯一單根x*?，F(xiàn)在是43頁\一共有64頁\編輯于星期四現(xiàn)在是44頁\一共有64頁\編輯于星期四注：Newton法的收斂性依賴于x0

的選取。x*x0x0x0現(xiàn)在是45頁\一共有64頁\編輯于星期四四.牛頓迭代法的局部收斂性與收斂速度

，,且設在包含的一個區(qū)間二階連續(xù)可導，則Newton迭代法至少二階收斂，即值得注意的是，當充分光滑且是的重根時，牛頓法在的附近是線性收斂的。且Newton迭代法在上的收斂性依賴于初值的選取。即初值的選取充分靠近時，一般可保證Newton迭代法收斂?，F(xiàn)在是46頁\一共有64頁\編輯于星期四并得出了是該方程的一個根，無人知道他用什么方法得出的，在當時這是一個非常有名的結果，試用牛頓法求出此結果。解：記則當時，，又所以有唯一實根，并改寫例3Leonardo于1225年研究了方程現(xiàn)在是47頁\一共有64頁\編輯于星期四用牛頓迭代格式所以，?，F(xiàn)在是48頁\一共有64頁\編輯于星期四五、求m重根的牛頓法1、迭代格式(9.4.2)2、重數(shù)m的確定3、迭代格式（9.4.2)的收斂階（至少2階收斂）現(xiàn)在是49頁\一共有64頁\編輯于星期四由于Newton迭代法的收斂性依賴于初值的選取，如果離方程的根較遠，則Newton迭代法可能發(fā)散。為了防止迭代發(fā)散，可以將Newton迭代法與下山法結合起來使用，放寬初值的選取范圍，即將（）式修改為：其中，稱為下山因子，選擇下山因子時，希望滿足下山法具有的單調性，即這種算法稱為Newton下山法。在實際應用中，可選擇。六、牛頓法的變形1、牛頓下山法現(xiàn)在是50頁\一共有64頁\編輯于星期四牛頓下山法的計算步驟：（1）選取初始近似值x0；（2）取下山因子

=1；（3）計算（4）計算f(xk+1)，并比較與的大小，分以下二種情況 1）若，則當時，取x*

xk+1，計算過程結束；當時，則把xk+1作為新的近似值，并返回到（3）。

2）若，則當≤且|f(xk+1)|<，取x*

xk，計算過程結束；否則若≤，而時，則把xk+1加上一個適當選定的小正數(shù)，即取xk+1+作為新的xk值，并轉向（3）重復計算；當＞；且時，則將下山因子縮小一半，取/2代入，并轉向（3）重復計算。現(xiàn)在是51頁\一共有64頁\編輯于星期四例5：求方程f(x)=x3

–

x

–1=0的根。kxk010.611/251.14063211.36681311.32628411.32472牛頓下山法的計算結果：現(xiàn)在是52頁\一共有64頁\編輯于星期四牛頓迭代法每迭代一次都需計算函數(shù)值和導數(shù)值計算量比較大；且迭代過程中計算時，僅利用了點的信息，而沒有充分利用已經求出的；在導數(shù)計算比較麻煩或難以求出時，

迭代格式構造

(2)構造方法：將Newton迭代格式中的導數(shù)用差商代替。2、割線法：(1)構造思想：用割線的斜率代替牛頓迭代法中切線的斜率；設法避開導數(shù)值的計算，因此可以采用離散牛頓法（割線法）。

一個自然的想法就是在充分利用“舊信息”的同時，現(xiàn)在是53頁\一共有64頁\編輯于星期四割線法的幾何意義x0x1切線

割線

切線斜率

割線斜率x2割線法迭代格式：現(xiàn)在是54頁\一共有64頁\編輯于星期四割線法的局部收斂性與收斂速度

設，在,且的某一鄰域內二階連續(xù)可微，當時，由割線法產生的序列收斂于，且收斂階至少為1.618?，F(xiàn)在是55頁\一共有64頁\編輯于星期四3、雙點弦截法：切線斜率

割線斜率初值x0

和x1。x0x1x2現(xiàn)在是56頁\一共有64頁\編輯于星期四§4非線性方程組的數(shù)值解法(1)構造思想：用線性方程組近似非線性方程組，由線性方程組解得的向量序列，逐步逼近非線性方程組的解向量。

(2)構造方法：若記一、

非線性方程組的牛頓迭代法則非線性方程組現(xiàn)在是57頁\一共有64頁\編輯于星期四其中

，且中至少有一個是的非線性函數(shù)。類似于的情況，可將單變量方程求根的方法推廣到非線性方程組。若已給出方程組的一個近似根。將函數(shù)的分量在用多元函數(shù)泰勒展開，并取其線性部分可表示為（）令上式右端為零，得到線性方程組（）其中現(xiàn)在是58頁\一共有64頁\編輯于星期四稱為

的