非線性方程與非線性方程組的迭代解法

非線性方程與非線性方程組的迭代解法第四章非線性方程與非線性方程組的迭代解法引言例：假設某一地區(qū)人口的數(shù)量隨時間連續(xù)增長，其增長率與人口數(shù)成正比,若允許移民以某常速率v進入該地區(qū)，則微分方程為：第四章非線性方程與非線性方程組的迭代解法引言若允許移民以某常速率進入該地區(qū)，則微分方程為：其解：第四章非線性方程與非線性方程組的迭代解法

假設某一地區(qū)有100萬初始人口，第一年內有43.5萬移民遷入，第一年末總計人口達156.4萬。根據(jù)上述數(shù)據(jù)推算該地區(qū)的增長率常數(shù)。人口增長模型：引言任玉杰教材32頁求解非線性方程根的MATLAB函數(shù)1、solve函數(shù)（1）求出方程根的解析表達式（2）求方程（組）的數(shù)值解（3）求出多項式方程的全部根2、roots函數(shù)--求解多項式方程（組）的全部根3、fzero函數(shù)--求一維變量的零點求解非線性方程根的MATLAB函數(shù)1、solve函數(shù)（1）求出方程根的解析表達式（2）求方程（組）的數(shù)值解（3）求出多項式方程的全部根2、roots函數(shù)--求解多項式方程（組）的全部根3、fzero函數(shù)--求一維變量的零點4、fsolve函數(shù)—求非線性方程組的解4.1非線性方程的迭代解法1、非線性方程的一般形式其中f(x)是一元非線性函數(shù)。2、非線性方程的分類：復習幾個概念與結論：f(x)=0(4.1)第四章非線性方程與非線性方程組的迭代解法4.1非線性方程的迭代解法1、非線性方程的一般形式2、非線性方程的分類：復習幾個概念與結論：f(x)=0(4.1)第四章非線性方程與非線性方程組的迭代解法4.1非線性方程的迭代解法1、非線性方程的一般形式2、非線性方程的分類：復習幾個概念與結論：f(x)=0(4.1)3、方程的根若存在常數(shù)s使f(s)=0，則稱s是方程(4.1)的根，又稱s是函數(shù)f(x)的零點。第四章非線性方程與非線性方程組的迭代解法4.1非線性方程的迭代解法1、非線性方程的一般形式2、非線性方程的分類f(x)=0(4.1)3、方程的根若存在常數(shù)s使f(s)=0，則稱s是方程(4.1)的根，又稱s是函數(shù)f(x)的零點。4、重根若f(x)能分解為其中則稱s是方程(4.1)的m重根和f(x)的m重零點。當m=1時，s稱為方程(4.1)的單根和f(x)的單零點。4.1非線性方程的迭代解法1、非線性方程的一般形式2、非線性方程的分類f(x)=0(4.1)3、方程的根4、重根5、幾個結論（1）零點存在定理（2）根的唯一性判別：一階導數(shù)不變號且不為零（3）n次代數(shù)方程在復數(shù)域上恰有n個根（4）高于4次的代數(shù)方程沒有求根公式代數(shù)方程求根公式的發(fā)現(xiàn)一元二次方程的求根公式：公元9世紀由中亞細亞的阿爾·花拉子模給出。挪威數(shù)學家.近代數(shù)學發(fā)展的先驅者.1802年8月生于芬島的一個牧師家庭,1829年4月卒于弗魯蘭.13歲入奧斯陸所教會學校學習,1821年在他人資助下入奧斯陸大學進行學習與研究.

1824年他發(fā)表了題為《論代數(shù)方程》證明一般方程的不可解性的論文,解決了困擾數(shù)學界200多年的難題.他在探索求五次方程根式解的過程中,總結前人無數(shù)次的失敗教訓,改變思維角度,證明了一般的五次方程不可能用根式求解的重要結論,在研究過程中,引發(fā)了他對群論的研究,群論中的可交換群,就是以他的名字命名的,稱做阿貝爾群.他的成就為代數(shù)的新學科――群論的誕生奠定的堅實的基礎.

阿貝爾積分、阿貝爾函數(shù)、阿貝爾積分方程、阿貝爾群、阿貝爾級數(shù)、阿貝爾部分和公式、阿貝爾基本定理、阿貝爾極限定理、阿貝爾可和性法國數(shù)學家

Hermite

：

Abel

留下的觀念可以讓數(shù)學家忙上150年。事實上

Hermite

利用橢圓函數(shù)解決了五次方程式公式解的問題。

4.1非線性方程的迭代解法5、幾個結論（1）零點存在定理（2）根的唯一性判別：一階導數(shù)不變號且不為零（3）n次代數(shù)方程在復數(shù)域上恰有n個根（4）高于4次的代數(shù)方程沒有求根公式6、解非線性方程迭代法的收斂性（1）大范圍收斂：在含根區(qū)間任取一初值（2）局部收斂:初值要充分靠近根s才能收斂。求方程根的數(shù)值解的一般步驟：（1）判斷根的存在性。即方程有沒有根？如果有，有幾個？（2）確定根的近似位置。即求出根所在區(qū)間或確定根的近似值。（3）根的精確化即按某種方法將初始近似值逐步精確化，直到滿足所要求的精確度。第四章非線性方程與非線性方程組的迭代解法4.1非線性方程的迭代解法一、初始近似值的搜索二、簡單迭代法及其收斂性三、簡單迭代法的收斂速度四、迭代過程的加速五、Newton法六、求m重根的Newton法七、割線法八、單點割線法4.1非線性方程的迭代解法一、初始近似值的搜索2、逐步搜索法3、區(qū)間二分法第四章非線性方程與非線性方程組的迭代解法1、作圖法（3種方法）參考資料：任玉杰1、作圖法------plot（任玉杰2.2.1）1、作圖法------plot（任玉杰2.2.1）例2.2.1利用作圖法判斷方程在閉區(qū)間[-10,10]上有幾個實根？并確定實根的近似值。一、初始近似值的搜索2、逐步搜索法1、作圖法（3種方法）（1）理論依據(jù)：零點存在定理（任玉杰2.2.2）（2）確定方程根的范圍的步驟（任玉杰44頁）（3）收斂判定準則（任玉杰45頁）自學------plot（任玉杰2.2.1）一、初始近似值的搜索2、逐步搜索法1、作圖法（3種方法）（任玉杰2.2.2）------plot（任玉杰2.2.1）3、區(qū)間二分法（任玉杰2.3）（1）基本思想：①確定方程有根的區(qū)間；將區(qū)間逐次分半縮小，得到一個區(qū)間長度以1/2的比例減小的含根區(qū)間序列，在給定根的誤差界時，利用長度趨于零的特點，可得到在某個區(qū)間中滿足要求的近似根。②3、區(qū)間二分法（1）基本思想將含根區(qū)間逐次分半縮小，得到一個區(qū)間長度以1/2的比例減小的含根區(qū)間序列，在給定根的誤差界時，利用長度趨于零的特點，可得到在某個區(qū)間中滿足要求的近似根。3、區(qū)間二分法（1）基本思想將含根區(qū)間逐次分半縮小，得到一個區(qū)間長度以1/2的比例減小的含根區(qū)間序列，在給定根的誤差界時，利用長度趨于零的特點，可得到在某個區(qū)間中滿足要求的近似根。（2）迭代終止的條件或者輸出根xYNNYY輸出根xN（3）算法：（任玉杰48頁）2、區(qū)間二分法（1）基本思想（3）算法（4）二分法的優(yōu)缺點優(yōu)點：程序簡單，總能求得近似根，對f(x)的要求不高缺點：收斂速度慢，不能求偶重根，復根。二分法一般用于求根的近似值。（2）迭代終止的條件解：所以f(x)在內僅有一根。k0123456721(2,4)(3,4)(3,3.5)(3,3.25)(3.125,3.25)(3.125,3.1875)(3.125,3.15625)(3.140625,3.15625)(3.146192551,3.146193505)3.3.53.253.1253.18753.156253.1406253.14843753.146193028二、簡單迭代法及其收斂性例求方程在x=1.5附近的一個根.迭代法的基本思想二、簡單迭代法及其收斂性例求方程在x=1.5附近的一個根.這種逐步校正的過程稱為迭代過程,所用公式稱為迭代公式.即迭代法的基本思想k0123456781.51.357211.330861.325881.324941.324761.324731.324721.32472迭代結果二、簡單迭代法及其收斂性簡單迭代法又稱不動點迭代法、Picard迭代法.迭代法是一種逐次逼近法,用某個固定公式反復校正根的近似值,使之逐步精確化,最后得到滿足精度要求的解.迭代法的基本思想迭代過程實質上是一個逐步顯示化的過程迭代法的基本思想是將隱式方程的求根問題歸結為計算一組顯式公式二、簡單迭代法及其收斂性1.一般形式：

---迭代函數(shù)。

2.收斂性若由迭代公式產(chǎn)生的序列收斂于，則為原方程的根在D收斂3.幾何意義

y=xsoxyxyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1x2x2x2x2簡單迭代法哪一個收斂？4.收斂條件a、非局部收斂定理（3）成立誤差估計式（4.4）

（4.5）

(1)迭代終止的條件：說明:迭代法框圖開始讀入輸出迭代失敗標志結束輸出=算法4.1（簡單迭代法算法）1、取初始點、最大迭代次數(shù)N和精度要求，置k=0；2、計算；3、若，則停止計算；4、若k=N，則停止計算；否則置k=k+1，轉2.1f(x)在[2，4]內有唯一根等價方程：1f(x)在[2，4]內有唯一根等價方程：迭代公式：取為方程的近似根.例3求方程的一個正根.解確定正根所在區(qū)間取用試湊法確定如下：xf(x)0123-5-6-116思考：應該選取哪一個函數(shù)作為迭代函數(shù)？思考：應該選取哪一個函數(shù)作為迭代函數(shù)？k01234562.52.15442.10362.09592.09482.09462.0946b、局部收斂定理證明思路:找滿足Th4.1的區(qū)間[a,b]

在的根s附近有連續(xù)的一階

導數(shù)，且則迭代法具有局部收斂性．三、簡單迭代法的收斂速度觀察：當時，哪個趨于零的速度快？如何衡量趨于零的速度的快慢？三、簡單迭代法的收斂速度1.r階收斂速度的定義成立，成立，r=1時，稱序列是線性收斂的；r=2時，稱序列是平方收斂的;(接近收斂時迭代誤差的下降速度)例P80體驗一階、二階收斂的速度一階收斂二階收斂2、簡單迭代法的收斂速度(1)線性收斂的條件證明思路：由Taylor公式，2、簡單迭代法的收斂速度(1)線性收斂的條件證明思路：由Taylor公式，2、簡單迭代法的收斂速度(1)線性收斂的條件2、簡單迭代法的收斂速度(1)線性收斂的條件思考:二階收斂的條件?2、簡單迭代法的收斂速度(1)線性收斂的條件思考:二階收斂的條件?(2)m階收斂的條件證明思路：由Taylor公式，例6四、迭代過程的加速加權迭代法2.埃特金(Aitken)加速法四、迭代過程的加速加權迭代法四、迭代過程的加速加權迭代法四、迭代過程的加速加權迭代法或者:例7用加權法加速技術求方程在0.5附近的一個根.例7用加權法加速技術求方程在0.5附近的一個根.k00.510.56658220.56713230.56714340.567143思考：若取迭代函數(shù)要達到同樣精度需要幾次迭代？答：18次。四、迭代過程的加速加權迭代法或者:加權迭代法的缺點:L值的確定需要迭代函數(shù)的導數(shù)信息，因此不便于實際應用。2.埃特金(Aitken)加速法（教材）設序列{xk}線性收斂到s，則斯蒂芬森（Steffensen）迭代法迭代公式：將一般迭代與Aitken加速技術結合起來即得到:8P114(74)表4-2，4-3不收斂！算法4.2（Steffensen迭代法算法）1、取初始點、最大迭代次數(shù)N和精度要求，置k=0；2、計算：3、若，則停止計算；4、若k=N，則停止計算；否則置k=k+1，轉2.例用斯蒂芬森（Steffensen）算法求在（1，1.5）內的根。課后練習五、Newton法（切線法）1.基本思想2.迭代函數(shù)3.迭代公式4.幾何意義6.牛頓下山法5.收斂性7.牛頓法的缺點五、Newton法（切線法）1.基本思想:(1)構造法:推導?。何?、Newton法（切線法）2.迭代函數(shù)：3.迭代公式：（4.7）4.幾何意義1.基本思想:(2)幾何上:逐步線性化方法(1)構造法:(3)Taylor展開推導5.收斂性（1）局部收斂定理證明思路:驗證迭代函數(shù)滿足定理4.2的三個條件關鍵證明：（2）非局部收斂定理證明思路：

條件(1),(2)共有四種情形:只就情形(1)進行定理的證明(見圖4-2),其余三種情形的證明方法是類似的.

證明思路:單調增加收斂于s。首先證明:其次證明:歸納假設：推出從而數(shù)列單調增加必有極限。只就情形(1)進行定理的證明(見圖4-2),其余三種情形的證明方法是類似的.

證明:單調增加收斂于s。首先證明:其次證明:歸納假設：推出從而數(shù)列單調增加必有極限。3P78算法4.3（Newton法）1、取初始點、最大迭代次數(shù)N和精度要求，置k=0；2、如果，則停止計算。否則計算：3、若，則停止計算；4、若k=N，則停止計算；否則置k=k+1，轉2.牛頓法程序框圖讀入輸出迭代失敗標志結束輸出=輸出奇異標志=例用牛頓切線法求方程在1.5附近的一個根.k01.511.3478321.3252031.3247241.32472若結果如何？------下山法Newton迭代格式：6.牛頓下山法}其中稱為下山因子通過適當選取下山因子保證：下山因子的選擇是逐步進行的，從開始反復將的值減半進行試算，一旦單調下降條件成立，則稱下山成功，反之，如果在上述過程中找不到使單調下降條件成立的下山因子，則稱下山失敗，這時需另選初值重算。牛頓下山法程序框圖讀入重選下山成功>輸出YN

作為初值進行牛頓迭代例用牛頓切線法求方程在1.5附近的一個根.取k010.6-1.3841117.95716否?9.25781否?4.925117否1/82.762517.319否1/161.681252.0709否1/321.140625-0.625是211.366810.1866311.326280.00667411.32472511.324727、牛頓法的缺點7、牛頓法的缺點六、求m重根的Newton法設S是方程（4.1）的m重根（m2），f(x)在s的某鄰域內有m階連續(xù)導數(shù)，則（1）（2）考察：結論：但只是線性收斂

方程（4.1）的m重根s仍然是其等價方程（4.2）的根六、求m重根的Newton法設S是方程（4.1）的m重根（m2），f(x)在s的某鄰域內有m階連續(xù)導數(shù)，則（1）（2）結論：

線性收斂

（3）變形的Newton法令則至少平方收斂缺點:不知道重根的重數(shù)m。（3）變形的Newton法令則至少平方收斂缺點:不知道重根的重數(shù)m。（4）若S是方程（4.1）的m重根，則s為的單根.迭代函數(shù)迭代函數(shù)迭代公式：優(yōu)點：至少二階收斂；缺點；計算工作量大。例P80（4）若S是方程（4.1）的m重根，則s為的單根.（4）若S是方程（4.1）的m重根，則s為的單根.迭代公式：例P80例P80六、求m重根的Newton法設S是方程（4.1）的m重根（m2），f(x)在s的某鄰域內有m階連續(xù)導數(shù)，則（2）

線性收斂（3）變形的Newton法至少平方收斂（4）若S是方程（4.1）的m重根，則s為的單根.至少二階收斂七、割線法基本思想用割線代替切線2.迭代公式3.幾何意義4.收斂性9P83例4k-12.000000000-0.69314718004.0000000000.61370563813.066788438-0.05788410423.141738781-0.00303761733.1462221340.000019723431461932210.八、單點割線法基本思想2.迭代公式（4.13）3.幾何意義4.收斂性9P85例5割線法的