數(shù)值計算方法 (第2章 非線性方程與方程組的數(shù)值解法)

第2章非線性方程與方程組的數(shù)值解法1

本章重點介紹求解非線性方程的幾種常見和有效的數(shù)值方法,同時也對非線性方程組求解,簡單介紹一些最基本的解法.無論在理論上,還是在實際應用中,這些數(shù)值解法都是對經典的解析方法的突破性開拓和補充,許多問題的求解,在解析方法無能為力時,數(shù)值方法則可以借助于計算機出色完成.2二分法求非線性方程

確定方程的有根區(qū)間(等長掃描法)

計算根的近似值（二分法）的根的方法分為兩步：3概念：有根區(qū)間：存在根隔根區(qū)間：唯一根4首先確定有限區(qū)間：依據(jù)零點定理。設，且，則方程在區(qū)間上至少有一個根。如果在上恒正或恒負，則此根唯一。5等步長掃描法求有根區(qū)間

用計算機求有根區(qū)間：等步長掃描法。設h>0是給定的步長，取，若則掃描成功；否則令，繼續(xù)上述方法，直到成功。如果則掃描失敗。再將h縮小，繼續(xù)以上步驟。6等步長掃描算法

算法：（求方程的有根區(qū)間）(1)輸入；(2)；(3)，若輸出失敗信息，停機。(4)若。輸出，已算出方程的一個根，停機。7等步長掃描算法(5)若。輸出為有根區(qū)間，停機(6)，轉3）注：如果對足夠小的步長h掃描失敗。說明：在內無實根或8二分法

用二分法(將區(qū)間對平分)求解。令若，則為有根區(qū)間，否則為有根區(qū)間記新的有根區(qū)間為，則且9二分法對重復上述做法得且

10二分法設所求的根為，則即取為的近似解

11求方程f(x)=0的根的二分法算法12求方程f(x)=0的全部實根的二分法算法13求方程f(x)=0的全部實根的二分法算法14例題例1設方程解：取h=0.1,掃描得：又即在有唯一根。15一般迭代法2.2.1迭代法及收斂性

對于有時可以寫成形式如：16迭代法及收斂性考察方程。這種方程是隱式方程，因而不能直接求出它的根。

但如果給出根的某個猜測值，代入中的右端得到，再以為一個猜測值，代入的右端得反復迭代得17迭代法及收斂性若收斂，即則得是的一個根18迭代法的幾何意義交點的橫坐標y=x19簡單迭代法

將變?yōu)榱硪环N等價形式。選取的某一近似值，則按遞推關系產生的迭代序列。這種方法算為簡單迭代法。20例題例2.2.1試用迭代法求方程在區(qū)間(1，2)內的實根。解：由建立迭代關系

k=0,1,2,3…….計算結果如下:21例題精確到小數(shù)點后五位22例題但如果由建立迭代公式仍取，則有，顯然結果越來越大，是發(fā)散序列23迭代法的收斂性定理（壓縮映像原理）設迭代函數(shù)在閉區(qū)間上滿足（1）（2）滿足Lipschitz條件即有且。24壓縮映像原理則在上存在唯一解，且對，由產生的序列收斂于。

25壓縮映像原理證明：不失一般性,不妨設否則a或b為方程的根。首先證明根的存在性令

26壓縮映像原理則，即由條件2）是上的連續(xù)函數(shù)是上的連續(xù)函數(shù)。故由零點定理在上至少有一根27壓縮映像原理再證根的唯一性假設有均為方程的根則因為0<L<1，所以只可能，即根是唯一的。28壓縮映像原理最后證迭代序列的收斂性

與n無關，而0<L<1即29壓縮映像原理誤差估計若滿足定理條件，則

這是事后估計，也就是停機標準。L越小，收斂速度越快。

這是事前估計。選取n，預先估計迭代次數(shù)。

3031例題例證明函數(shù)在區(qū)間[1，2]上滿足迭代收斂條件。證明：32例題

33例題若取迭代函數(shù)，不滿足壓縮映像原理，故不能肯定收斂到方程的根。34簡單迭代收斂情況的幾何解釋35362.2.2Steffensen加速收斂法對收斂緩慢的迭代格如何加快收斂速度？一個簡便易行，而又能大幅度提高收斂速度的方法。372.2.2Steffensen加速收斂法此部分主要有兩個內容1.Aitken加速收斂迭代法2.Steffensen加速收斂方法38Aitken加速收斂迭代法概述39Aitken加速收斂迭代法概述40對選取的gi(x)，取初始近似值x0=1.5，迭代計算結果列在表。（a）(b)(c)(d)(e)01．51．51．51．51．51-0.8750.81651.286953771.348399731.373333326.7322.99691.402540801.367376371.365262013-469.71.345458381.36495701.3652300141.03×1081.375170251.3652647581.365916731.3652300291.364878221.36523001231.36522998251.3652300141簡單觀察迭代過程，(a)(b)不定，(c)(d)(e)都收斂，但收斂速度相差很大。例：對g4(x)產生的迭代序列（表中(d)對應列）進行Aitken加速。解:利用計算公式得比較可得，與x8的誤差差不多。

42Steffensen加速收斂法概述在Aitken加速中，只要有三個相鄰點就可以進行加速。把簡單迭代與Aitkn加速方法結合起來，建立稱之為Steffenson方法的迭代過程。43Steffensen加速收斂法概述由上式產生的序列稱為Steffensen迭代序列。44Steffensen加速收斂法概述Steffenson方法不必計算導函數(shù)，每迭代步的工作量略多于二步簡單迭代的工作量，而收斂速度達二階。45一般迭代法求解46Steffensen加速收斂472.2.2Steffensen加速收斂法自學為主。不做要求。482.2.2Steffensen加速收斂法迭代法收斂的階定義設序列收斂到，若有實數(shù)和非零常數(shù)C，使得其中，，則稱該序列是p階收斂的，C稱為漸進誤差常數(shù)。

49迭代法收斂的階當p=1時，稱為線性收斂；當p>1時，稱為超線性收斂；當p=2時，稱為平方收斂或二次收斂。50迭代法收斂的階定理設是方程的不動點，若為足夠小的正數(shù)。如果且，則從任意出發(fā)，由產生的序列收斂到，當時斂速是線性的。

51迭代法收斂的階證明：滿足壓縮映像原理52迭代法收斂的階

斂速是線性的線性收斂到。53Steffensen迭代格式由線性收斂知當n充分大時有

即54Steffensen迭代格式展開有：55Steffensen迭代格式已知，則，改成

n=0，1，2，…56Steffensen迭代格式也可以改寫成其中迭代函數(shù)57Steffensen迭代法收斂的充要條件定理2.2.358Steffensen迭代法收斂的充要條件證明：必要性59Steffensen迭代法收斂的充要條件充分性60Steffensen算法的收斂速度

61Steffensen算法的收斂速度定理2.2.5在定理假設下，若

產生的序列至少平方收斂到。

62Steffensen算法的收斂速度63Steffensen算法的收斂速度

64Steffensen算法的收斂速度

65Steffensen算法的收斂速度由定理知至少以平方速度收斂到。也就是說：簡單迭代法是線性收斂；Steffensen迭代至少平方以上收斂（加速收斂）。66例題例試用Steffensen算法求解方程解法一、取，由

n=0，1，2，…67例題取初值，計算結果如下：NXnYnZn01.51.3572088081.33086095911.3248991811.3247523791.32472449621.3247179571.3247179571.32471795768例題解法二、取，由對于該迭代函數(shù)在一般迭代法中是發(fā)散的，而Steffensen格式卻是收斂的。

n=0，1，2，…69例題取初值，計算結果如下：NXnYnZn01.52.3751.23964843711.4162929751.8409219155.23887276921.3556504421.4913982792.31727069931.3289487771.3470628831.44435122441.3248044891.3251735441.32711728151.3247179441.3247181521.32471898061.32471795770Steffensen迭代格式幾何解釋

71Steffensen迭代算法

72Steffensen迭代算法

732.3Newton迭代法設x*是方程f(x)=0的根，又x0為x*附近的一個值，將f(x)在x0附近做泰勒展式：令，則

74Newton迭代法

去掉的二次項，有：即以x1代替x0重復以上的過程，繼續(xù)下去得：75Newton迭代法

以此產生的序列{Xn}得到f(x)=0的近似解，稱為Newton法，又叫切線法。76Newton迭代法幾何解釋

牛頓迭代法的幾何意義77Newton迭代法幾何解釋類似，過點x1再做切線….78當做曲線上的點的引切線，該切線與x軸的交點橫坐標即為牛頓迭代公式求得的xn+1，因此牛頓迭代法也稱為牛頓且切線法。79例題例2.3.1用Newton法求的近似解。解：由零點定理。80例題81例設a>0，試用Newton法計算,并求的值。解：82Newton迭代法算法框圖83Newton迭代法算法84Newton迭代法收斂性定理2.3.1設函數(shù)，且滿足若初值滿足時，由Newton法產生的序列收斂到方程在[a,b]上的唯一根。85Newton迭代法收斂性證明：根的存在性根的唯一性86Newton迭代法收斂性收斂性87Newton迭代法收斂性

88Newton迭代法收斂性89注：牛頓法的平方收斂是在根X*附近的性質，因此迭代初值必須足夠靠近X*。應用中常把隔根區(qū)間取的如此之小，使其f(x)f”(x)>0，就能保證收斂。9091Newton迭代法收斂性推論在定理條件下，Newton迭代法具有平方收斂速度。92代數(shù)方程的Newton迭代法代數(shù)方程的Newton迭代法推導設n次代數(shù)方程用Newton迭代法求有限區(qū)間的實根，則要計算，一般采用秦九韶算法。93代數(shù)方程的Newton迭代法由Taylor展式94代數(shù)方程的Newton迭代法

9596代數(shù)方程的Newton迭代法同理

97代數(shù)方程的Newton迭代法比較x的同次冪系數(shù)得：故代數(shù)方程的Newton迭代公式98代數(shù)方程的Newton迭代法算法99

100弦截法Newton迭代法有一個較強的要求是且存在。因此，用弦的斜率近似的替代。101弦截法令y=0，解得弦與x軸的交點是坐標x2102弦截法103弦截法的幾何解釋(a)定端點弦截法