解非線性方程

解非線性方程第一頁，共三十八頁，2022年，8月28日本章目的：講述用于實際計算中求f(x)=0的根的近似值的幾種常用方法。方程根的數(shù)值計算大致可以分為三個步驟：

(1)判斷根的存在性；

(2)確定根的分布范圍(根的隔離)；

(3)根的精確化。根的隔離1.分析法：利用對函數(shù)f(x)的各種性質(zhì)的分析來確定根的分布范圍。例：試確定f(x)=x3-6x2+9x-1=0各根的分布范圍。隔根區(qū)間為(0,1)、(1,3)、(3,4)第二頁，共三十八頁，2022年，8月28日2.逐步搜索法：

先確定方程f(x)=0的所有實根所在的區(qū)間[a,b]，再按照選定的步長h=(b–a)/n，取點xk=a+kh(k=0,1,2,….,n)，逐步計算函數(shù)值f(xk),依據(jù)函數(shù)值異號及實根的個數(shù)確定隔根區(qū)間.必要時可以調(diào)整步長h,總可以把隔根區(qū)間全部找出.代數(shù)方程根的模上下界定理：定理：設(shè)代數(shù)方程

f(x)=xm+am-1xm-1+…+a1x+a0=0則:(1)若μ=max{|am-1|,…,|a1|,|a0|},方程根的模小于μ+1；(2)若v=1/|a0|max{1,|am-1|,…,|a1|},方程根的模大于1/(v+1).例：求方程x3-3.2x2+1.9x+0.8=0的隔根區(qū)間。解：設(shè)方程的根為α

由

μ=max{|-3.2|,|1.9|,|0.8|}=3.2;

v=(1/0.8)max{1,|-3.2|,|1.9|}=4

第三頁，共三十八頁，2022年，8月28日得：0.2<|α|<4.2即：-4.2<α<-0.2,0.2<α<4.2取n=8,h=0.5,計算f(xk)xk…-0.7-0.20.2……f(xk)…-2.440.281.06…0.20-0.310.14…由上表可知隔根區(qū)間為[-0.7,-0.2],[1.2,1.7],[1.7,2.2]3.圖解法：

由函數(shù)圖像來確定根的大體位置。第四頁，共三十八頁，2022年，8月28日§4.1二分法(對分區(qū)間法)(BisectionMethod)原理：若f(x)C[a,b]單調(diào)，且f(a)·f(b)<0，則f(x)

在(a,b)上有且僅有一實根?；舅枷耄和ㄟ^計算隔根區(qū)間的中點，逐步將隔根區(qū)間縮小，從而得到方程的近似根數(shù)列{xn}。第五頁，共三十八頁，2022年，8月28日abx1x2a1b2x*b1a2(1)先將[a,b]等分為兩個小區(qū)間,分點記為x0=(a+b)/2,判斷根屬于哪個小區(qū)間,舍去無根區(qū)間保留有根區(qū)間[a1,b1].即,若f(x0)=0,則x0=x*.設(shè)f(x0)≠0,若f(a)f(x0)<0,則x*∈

(a,x0),這時令a1=a,b1=x0;否則,x*∈(x0,b),此時令a1=x0,b1=b.總之,可以得到x*所在的新區(qū)間[a1,b1],其長度為[a,b]的一半.二分法的步驟：對區(qū)間[a1,b1]實施上述同樣的過程,得中點x1=(a1+b1)/2和x*的新區(qū)間[a2,b2],如此繼續(xù)下去,則得一系列有根區(qū)間:[a0,b0]=[a,b],[a1,b1],[a2,b2],….,[ak,bk],…第六頁，共三十八頁，2022年，8月28日其中bk-ak=(bk-1-ak-1)/2.因此bk-ak=(b-a)/2k,當(dāng)k→+∞時,有根區(qū)間[ak,bk]最終必收斂于一點,該點就是所求方程的根x*.把每次二分后的有根區(qū)間[ak,bk]的中點xk=(ak+bk)/2作為根x*的近似值,則可得一個根的近似值序列

x0,x1,x2,….,xk,….該序列的極限即為x*.定理1.設(shè)x*是f(x)=0在[a,b]內(nèi)的唯一根,且f(a)·f(b)<0,則二分法計算過程中,各隔根區(qū)間的中點數(shù)列

滿足:|xn–x*|≤(b–a)/2n+1第七頁，共三十八頁，2022年，8月28日誤差分析：第1步產(chǎn)生的有誤差第k+1

步產(chǎn)生的xk

有誤差(1)對于給定的精度,可估計二分法所需的步數(shù)k：停機條件（terminationcondition）或誤差控制方法：(2)事后估計誤差.先對分,再判斷所得中點是否滿足(3)用不等式控制誤差。第八頁，共三十八頁，2022年，8月28日例1用二分法求在(1,2)內(nèi)的根，要求絕對誤差不超過

解：

f(1)=-5<0有根區(qū)間中點

f(2)=14>0-(1,2)+

f(1.5)>0(1,1.5)

f(1.25)<0(1.25,1.5)

f(1.375)>0(1.25,1.375)

f(1.313)<0(1.313,1.375)

f(1.344)<0(1.344,1.375)

f(1.360)<0(1.360,1.375)

f(1.368)>0(1.360,1.368)

第九頁，共三十八頁，2022年，8月28日例2:求方程f(x)=x

3–e-x=0的一個實根。解：因為f(0)<0,f(1)>0.故f(x)在(0,1)內(nèi)有根.(a,b)=(0,1),計算結(jié)果如表：k a bk xk

f(xk)符號 0 0 1 0.5000 － 1 0.5000 － 0.7500－ 2 0.7500 － 0.8750 ＋ 3 － 0.8750 0.8125 ＋ 4 － 0.8125 0.7812 ＋ 5 － 0.7812 0.7656 － 6 0.7656 － 0.7734 ＋ 7 － 0.7734 0.7695 － 80.7695－ 0.7714 － 9 0.7714 － 0.7724 － 10 0.7724 － 0.7729 ＋ 取x10=0.7729，誤差為|x*-x10|≤1/211.第十頁，共三十八頁，2022年，8月28日Remark1：求奇數(shù)個根

Findsolutionstotheequationx3-6x2+10x–4=0ontheintervals[0,4]，Usethebisectionmethodtocomputeasolutionwithanaccuracyof10－7.Determinethenumberofiterationstouse..[0,1],[1.5,2.5]and[3,4]，利用前面的公式可計算迭代次數(shù)為k=23.

第十一頁，共三十八頁，2022年，8月28日Remark2:要區(qū)別根與奇異點Considerf(x)=tanxontheinterval(0,3).Usethe20iterationsofthebisectionmethodandseewhathappens.Explaintheresultsthatyouobtained.（如右圖）Remark3:二分法不能用來求重根,且收斂速度較慢.優(yōu)點:對函數(shù)的性質(zhì)要求低,程序簡單,易操作.第十二頁，共三十八頁，2022年，8月28日§4.2簡單迭代法基本思想：先將方程f(x)=0改寫成某種等價形式,由等價形式構(gòu)造相應(yīng)的迭代公式,然后選取方程的某個初始近似根x0,代入迭代公式反復(fù)校正根的近似值,直到滿足精度要求為止.具體做法：(1)

把f(x)=0改寫成下列等價形式f(x)=0x=(x)等價變換f(x)的根

(x)的不動點第十三頁，共三十八頁，2022年，8月28日(2)

構(gòu)造迭代格式：

,k=0,1,2,…(3)

從給定的初始值x0出發(fā),按照迭代公式即可得一個數(shù)列

x0,x1,x2,…,xk,…(4)

若有極限,則迭代公式收斂,此時數(shù)列極限即為原方程的根,即這里

(x)稱為迭代函數(shù)注：

f(x)=0化為等價方程x=

(x)的方式是不唯一的,故迭代格式也不唯一,有的收斂,有的發(fā)散.第十四頁，共三十八頁，2022年，8月28日(1)如果將原方程化為等價方程由此可見，這種迭代格式是發(fā)散的

取初值Forexample：2x3–x–1=0(2)如果將原方程化為等價方程仍取初值第十五頁，共三十八頁，2022年，8月28日依此類推,得

x3=0.9940

x4=0.9990

x5=0.9998

x6=1.0000

x7=1.0000已經(jīng)收斂,故原方程的解為x=1.0000

同樣的方程?不同的迭代格式有不同的結(jié)果什么形式的迭代法能夠收斂呢?收斂性分析定義:

若存在常數(shù)(0≤<1),使得對一切x1,x2[a,b],成立不等式|g(x1)-

g(x2)|≤|x1

-

x2|則稱g(x)是[a,b]上的一個壓縮映射,稱為壓縮系數(shù)第十六頁，共三十八頁，2022年，8月28日

考慮方程x=

(x)

,

(x)

C[a,b],若(I)當(dāng)x[a,b]時，

(x)

[a,b]；(II)在[a,b]上成立不等式:

|

(x1)

-

(x2)

≤|x1-

x2|,(0≤<1)則(1)

(x)在[a,b]上存在惟一不動點x*(2)任取x0[a,b]，由xk+1=

(xk)得到的序列{xk}([a,b])收斂于x*

。(3)k次迭代所得到的近似不動點xk與精確不動點x*有誤差估計式：定理4.2第十七頁，共三十八頁，2022年，8月28日證明：①

(x)在[a,b]上存在不動點？②不動點唯一？③當(dāng)k

時，

xk收斂到x*？|x*-

x'|=|

(x*)-

(x')|≤|x*-

x'|.因0≤

<1,故必有x'=x*若有x'[a,b],滿足

(x')=x'，則|xk-x*|=|

(xk-1)-

(x*)|≤|xk-1-x*|≤2|xk-2-x*|≤…≤k|x0-x*|0.令G(x)=

(x)-x,x∈[a,b]，由條件知G(a)=

(a)-

a≥0,G(b)=

(b)-

b≤0.由條件知G(x)在[a,b]上連續(xù)，又由介值定理知存在x*[a,b]，使G(x*)=0，即x*=

(x*).第十八頁，共三十八頁，2022年，8月28日可用來控制收斂精度越小,收斂越快(4)|xk-x*|=|(xk-1)-

(x*)|≤|xk-1-x*|≤

(|xk-xk-1|+|xk-x*|),故有|xk-

x*|≤/(1-)|xk-

xk-1|.這就證明了第一個估計式.

(5)|xk-

xk-1|=|(xk-1)-(xk-2)|≤|xk-1-xk-2|≤…≤

k-1|x1-x0|結(jié)合上一估計式可得|xk-x*|≤k-1/(1-)|x1-x0|.即第二個估計式成立第十九頁，共三十八頁，2022年，8月28日Remark：定理條件非必要條件，而且定理4.2中的壓縮條件不好驗證，一般來講

若知道迭代函數(shù)(x)

C1[a,b],并且滿足|

'(x)|≤

≤1,對任意的x[a,b],則

(x)是[a,b]上的壓縮映射.第二十頁，共三十八頁，2022年，8月28日例3:

已知方程2x–7-lgx＝0，求方程的含根區(qū)間，考查用迭代法解此方程的收斂性。第二十一頁，共三十八頁，2022年，8月28日解：在這里我們考查在區(qū)間[3.5,4]的迭代法的收斂性很容易驗證：f(3.5)<0,f(4)>0將方程變形成等價形式：x＝(lgx+7)/2由定理4.2知，迭代格式xk+1＝(lgxk+7)/2在[3.5,4]內(nèi)收斂.第二十二頁，共三十八頁，2022年，8月28日局部收斂Def:(局部收斂)

設(shè)x*為的不動點,若存在x*的一個閉鄰域U(x*,δ)=[x*-δ,x*+δ](δ>0),使得對任意x0

U(x*,δ),由迭代格式xk+1=(xk)(k=0,1,2,…)產(chǎn)生的序列{xk}都收斂于x*,則稱迭代過程xk+1=(xk)在的閉鄰域U(x*,δ)內(nèi)是局部收斂的.定理4.3:設(shè)x*為的不動點,(x)與

'

(x)在包含x*的某鄰域U(x*)(即開區(qū)間)內(nèi)連續(xù),且|

'

(x*)|≤

L<1,則迭代格式xk+1=(xk)(k=0,1,2,…)具有局部收斂性.證明略Wedon’tknowx*,howdoweestimatetheinequality？

第二十三頁，共三十八頁，2022年，8月28日例4:

用一般迭代法求x3-x-1=0的正實根x*解:將方程改寫成則迭代函數(shù)為易知:

'

(x)在包含x*的某鄰域U(x*)內(nèi)連續(xù),且|

'

(x*)|<1.因此迭代格式在x*附近收斂.例5:用一般迭代法求方程x–lnx＝2在區(qū)間(2,)內(nèi)的根,要求|xk-xk-1|/|xk|≤10-8第二十四頁，共三十八頁，2022年，8月28日解：令f(x)=x-lnx-2f(2)<0,f(4)>0,故方程在(2,4)內(nèi)至少有一個根

因此方程在(2,∞)內(nèi)僅有一個根x*,且x*(2,4)將方程化為等價方程：x＝2＋lnx因此,

x0(2,),xk+1＝2＋lnxk產(chǎn)生的序列xk收斂于x*取初值x0＝3.0,計算結(jié)果如下：第二十五頁，共三十八頁，2022年，8月28日k

xi83146188209103.146191628113.146192714123.146193060133.146193169143.146193204

k

xi03.00000000013.098612289231413378664314570220963146143611第二十六頁，共三十八頁，2022年，8月28日另一種迭代格式：

03.0000000001314619344133.146193221注：由此可見,對同一個非線性方程的迭代格式,在收斂的情形下,有的收斂快,有的收斂慢.第二十七頁，共三十八頁，2022年，8月28日

Def:設(shè)序列{xk}收斂于x*,記ek=xk-x*,若存在p≥1和正數(shù)C，使得成立則稱{xk}為p階收斂的.特別地

p=1,且0<C<1,稱線性收斂;p>1,稱超線性收斂;

p=2,稱平方收斂.迭代法的收斂階(收斂速度)注：收斂階p反映了迭代格式收斂的快慢,p越大收斂越快.第二十八頁，共三十八頁，2022年，8月28日定理4.4:設(shè)x*為的不動點,p>1為正整數(shù),在x*的某鄰域Ｕ(x*)內(nèi)p階連續(xù)可微,且

'(x*)="(x*)=…=

(p-1)(x*)=0,而

(p)(x*)≠0

則存在>0,當(dāng)x0[x*-,x*+](x0≠x*)時,由迭代格式產(chǎn)生的序列{xk}以p階收斂速度收斂于x*.Prove:(1)由(x*)=0必存在>0,當(dāng)x0[x*-,x*+]

U(x*)時,由迭代格式產(chǎn)生的序列{xk}收斂于x*,并有xk[x*-,x*+]由泰勒公式有第二十九頁，共三十八頁，2022年，8月28日由條件知(2)由于在x*處p階連續(xù)可微且

(p)(x*)≠0,知必存在x*的某鄰域Ｕ(x*),當(dāng)x

U(x*)時,有

(p)(x)≠0.由于

[x*-,x*+]U(x*),故

(p)()≠0,k=0,1,2,…可見,當(dāng)初值x0≠x*時,xk≠x*.于是有即{xk}有p階收斂速度.第三十頁，共三十八頁，2022年，8月28日§4.3

迭