課程計算方法第2章方程求根

數(shù)值分析——第二章方程求根第2章方程求根解數(shù)值問題直接法逐次逼近法——規(guī)則：A1

A2…An…精確解其中Ai可以是數(shù)、向量、矩陣或其他兩種形式：迭代法——利用遞推公式搜索法——利用法則（如二分法）直接法——小型問題及特殊問題逐次逼近法——大型問題及非線性問題。2.1非線性方程的迭代法設非線性方程f(x)=0(2.1)若有

，使f(

)=0，則稱

為方程(2.1)的根，或稱

為函數(shù)f(x)的零點。注：(1)代數(shù)方程——5次以上不能用解析公式求根超越方程——求解更難(2)若f(x)=0在區(qū)間[a，b]上僅有一根，則稱[a，b]為方程(2.1)的單根區(qū)間；若f(x)=0在區(qū)間[a，b]上有多個根，則稱[a，b]為方程(2.1)的多根區(qū)間，統(tǒng)稱為有根區(qū)間。2.1非線性方程的迭代法2.1.1根的搜索1.逐步搜索法為明確起見，不妨假定f(a)<0，f(b)>0。我們從有根區(qū)間[a，b]的左端x0=a出發(fā)，某個預定的步長h(譬如取h=(b–a)/N，N為正整數(shù))一步一步地向右跨，每跨一步進行一次根的“搜索”，即檢查節(jié)點xk=a+kh上的函數(shù)值f(xk)的符號，一旦發(fā)現(xiàn)節(jié)點xk與端點a的函數(shù)值異號，即f(xk)>0，則可以確定一個縮小了的有根區(qū)間[xk-1，xk]，其寬度等于預定的步長h.2.1非線性方程的迭代法2.1.1根的搜索1.逐步搜索法【例2-1】考察方程f(x)=x3–x–1=0.注意到f(0)<0，f(2)>0，知f(x)在區(qū)間(0，2)內(nèi)至少有一個實根.

設從x=0出發(fā)，取h=0.5為步長向右進行根的搜索，列表記錄各個節(jié)點上函數(shù)值的符號(表6-1)，我們發(fā)現(xiàn)區(qū)間[1.0，1.5]內(nèi)必有一根.x00.51.01.5f(x)的符號---+2.1非線性方程的迭代法2.1.1根的搜索1.逐步搜索法在具體運用上述方法時，步長h的選擇是個關鍵.很明顯，只要步長h取得足夠小，利用這種方法可以得到具有任意精度的近似根.不過當h縮小時，所要搜索的步數(shù)相應增多，從而使計算量增大。因此，如果精度要求比較高，單用這種逐步搜索方法是不合算的。下述二分法可以看作是逐步搜索方法的一種改進。2.1非線性方程的迭代法2.1.1根的搜索2.二分法考察有根區(qū)間[a，b]，取中點x0=(a+b)/2將它分為兩半,然后進行根的搜索,即檢查f(x0)與f(a)是否同號。如果確系同號，說明所求的根

在x0的右側(cè)，這時令a1=x0，b1=b;否則

必在x0的左側(cè)，這時令a1=a，b1=x0.不管出現(xiàn)哪一種情況，新的有根區(qū)間[a1，b1]的長度僅為[a，b]的一半.2.1非線性方程的迭代法2.1.1根的搜索2.二分法對壓縮了的有根區(qū)間[a1，b1]又可施行同樣的手續(xù)，即用中點x1=(a1+b1)/2將區(qū)間[a1，b1]再分為兩半，然后通過根的搜索判定所求的根在x1的哪一側(cè)，從而又確定一個新的有根區(qū)間[a2，b2]，其長度是[a1，b1]的一半。2.1非線性方程的迭代法2.1.1根的搜索2.二分法如此反復二分下去，即可得出一系列有根區(qū)間[a，b][a1，b1][a2，b2]…[ak，bk]…其中每個區(qū)間都是前一個區(qū)間的一半，因此[ak，bk]的長度bk–ak=(b–a)/2k+1當時趨于零，就是說，如果二分過程無限地繼續(xù)下去，這些區(qū)間最終必收縮于一點

，該點顯然就是所求的根.2.1非線性方程的迭代法2.1.1根的搜索2.二分法每次二分后，設取區(qū)間[ak，bk]的中點xk=(bk+ak)/2作為根的近似值，則在二分過程中可以獲得一個近似根的序列x0，x1，x2，…，xk…該序列必以根為極根。由于|–xk|≤(bk–ak)/2=(b–a)/2k+1

只要二分足夠多次(即k充分大)，便有|–xk|<，這里為預定的精度.2.1非線性方程的迭代法2.1.1根的搜索2.二分法【例2-2】求方程f(x)=x3–x–1=0在區(qū)間[1.0，1.5]內(nèi)的一個實根，要求準確到小數(shù)點后的第2位.

解：這里a=1.0，b=1.5，而f(a)<0，f(b)>0。取[a，b]的中點x0=1.25，將區(qū)間二等分，由于f(x0)<0，即f(x0)與f(a)同號，故所求的根必在x0右側(cè)，這時應令a1=x0=1.25，b1=b=1.5，而得到新的有根區(qū)間[a1，b1].

如此反復二分下去。2.1非線性方程的迭代法2.1.1根的搜索2.二分法【例2-2】求方程f(x)=x3–x–1=0在區(qū)間[1.0，1.5]內(nèi)的一個實根，要求準確到小數(shù)點后的第2位.

我們現(xiàn)在預估所要二分的次數(shù)，按誤差估計(1.1)式，只要二分6次(k=6)，便能達到預定的精度|–x6|≤0.005.二分法的計算結(jié)果如表2-2.Kakbkxkf(xk)符號01.01.51.25-11.25l.375+21.3751.3125-31.3125l.3438+41.34381.3281+51.32811.3203-61.32031.3242-2.1非線性方程的迭代法2.1.1根的搜索2.二分法二分法是電子計算機上一種常用算法，下面列出計算步驟：步1準備計算f(x)在有根區(qū)間[a，b]端點處的值，f(a)，f(b).

步2二分計算f(x)在區(qū)間中點(a+b)/2處的值f((a+b)/2).2.1非線性方程的迭代法2.1.1根的搜索2.二分法二分法是電子計算機上一種常用算法，下面列出計算步驟：步3判斷若f((a+b)/2)=0則(a+b)/2即是根，計算過程結(jié)束。否則檢驗：若f((a+b)/2)與f(a)異號，則根位于區(qū)間[a，(a+b)/2]內(nèi)，這時以(a+b)/2代替b；若f((a+b)/2)與f(a)同號，則根位于區(qū)間[(a+b)/2，b]內(nèi)，這時以(a+b)/2代替a.2.1非線性方程的迭代法2.1.1根的搜索2.二分法二分法是電子計算機上一種常用算法，下面列出計算步驟：反復執(zhí)行步2和步3，直到區(qū)間[a，b]長度縮小到允許誤差范圍之內(nèi)，此時區(qū)間中點(a+b)/2即可作為所求的根.

上述二分法的優(yōu)點是算法簡單，而且收斂性總能得到保證，但是不能用來求重根。2.1非線性方程的迭代法2.1.1根的搜索2.二分法

2.1非線性方程的迭代法2.1.2簡單迭代法1.定義設方程x=

(x)(2.2)與(2.1)同解，即f(x)=0x=

(x)。任取初值x0，令x1=

(x0)，x2=

(x1)，…，一般地xk+1=

(xk)k=0，1，2，…(2.3)稱(2.3)為迭代法(迭代過程、迭代格式)，

(x)稱為迭代函數(shù)，xk稱為第k步迭代值。若{xk}收斂，稱迭代法收斂，否則稱迭代法發(fā)散。2.1非線性方程的迭代法2.1.2簡單迭代法1.定義設方程x=

(x)(2.2)與(2.1)同解，即f(x)=0x=

(x)。任取初值x0，令x1=

(x0)，x2=

(x1)，…，一般地xk+1=

(xk)k=0，1，2，…(2.3)

若xk

，則=

()，從而f()=0，即為方程(2.1)的根。2.1非線性方程的迭代法2.1.2簡單迭代法【例2-3】求方程x3–x–1=0在x=1.5附近的根。解：方程化為等價方程，取初值x0=1.5，則

…取6位數(shù)字時x7與x8相同，即可認為x7是方程的根，x7=1.32472。2.1非線性方程的迭代法2.1.2簡單迭代法【例2-3】求方程x3–x–1=0在x=1.5附近的根。解：方程化為等價方程，取初值x0=1.5，則

取6位數(shù)字時x7與x8相同，即可認為x7是方程的根，

x7=1.32472。2.1非線性方程的迭代法2.1.2簡單迭代法應當指出，迭代法的效果并不是總能令人滿意的。譬如，方程化為另一種等價形式：x=x3–1，建立迭代公式xk+1=xk3–1。迭代初值仍取x0=1.5，則有x1=2.375，x2=12.39，x3=1904.…。繼續(xù)迭代下去已經(jīng)沒有必要，因為結(jié)果顯然會越來越大，不可能趨于某個極限。這種不收斂的迭代過程稱作是發(fā)散的。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【定理2-1】假定迭代函數(shù)(x)滿足下列兩項條件：

1.對任意x∈[a，b]有a

(x)b；

2.存在正數(shù)L<1,使對任意x∈[a，b]有|'(x)|L<1.則迭代過程xk+1=

(xk)對于任意初值x0∈[a，b]均收斂于方程x=

(x)的根。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性證明：由微分中值定理xk+1–=

(xk)–

()='(

)(xk–)式中

是與xk之間某一點,當xk∈[a，b]時

∈[a，b]，因此利用條件可以斷定|xk+1–|L|xk–|據(jù)此反復遞推有|xk–|Lk|x0–|，故當k

時，迭代值xk將收斂到所求的根。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【定理2-1】假定迭代函數(shù)

(x)滿足下列兩項條件：

1.對任意x∈[a，b]有a

(x)b；

2.存在正數(shù)L<1,使對任意x∈[a，b]有|'(x)|L<1.則迭代過程xk+1=

(xk)對于任意初值x0∈[a，b]均收斂于方程x=

(x)的根。檢驗：,[，][1，2]，

,所以迭代法收斂2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性說明：(1)條件是充分的而非必要的.如方程x3–2x=0,

取，則，在[–1，1]上不滿足|'(x)|<1，但實際上=0，取初值x0在0附近，迭代法有可能收斂。

(2)通?？上扔枚ɡ砼袛?，若不滿足，則改變迭代公式使之滿足，然后迭代。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性說明：(3)若|'(x)|1，則|xk+1–xk|=|

(xk)–

(xk–1)|=|'(

)||xk–xk-1||xk–xk-1|…|x1–x0|，故迭代法必發(fā)散。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性左圖表示收斂的序列，右圖表示發(fā)散的序列。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【推論】在定理條件下，有如下誤差估計：

(2.4)(2.5)

證明:∵|xk+1–|=|

(xk)–

()|=|'(

)||xk–|L|xk–||xk+1–xk|=|

(xk)–

(xk–1)|=|'(

)||xk–xk–1|L|xk–xk–1|∴|xk–||xk–xk+1|+|xk+1–|L|xk–xk–1|+L|xk–|從而2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【推論】在定理條件下，有如下誤差估計：

(2.4)(2.5)

證明:從而又因為|xk–xk–1|L|xk–1–xk–2|…Lk–1|x1–x0|所以 2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性

(2.4)(2.5)說明：(1)(2.4)用于控制迭代過程：(2.5)用于事先估計迭代次數(shù)：由求出k。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性說明：(2)定理是以[a，b]中任一點作初值，迭代都收斂，稱為全局收斂。此要求較難滿足，故考慮在的某一鄰域內(nèi)—局部收斂性【定理2-1'】若方程有根,|'()|<1，且

'在的某鄰域U()內(nèi)連續(xù),則存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收斂。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【定理2-1'】若方程有根,|'()|<1，且

'在的某鄰域U()內(nèi)連續(xù),則存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收斂。證明：∵|'()|<1，及

'(x)在U()內(nèi)連續(xù)，存在

>0，使[–

，+

]U()，且x[–

，+

]有|'(x)|L<1.x[–

，+

]，|

(x)–|=|

(x)–

()|=|‘(

)||x–|L|x–|<

，即

(x)[–

，+

]1.對任意x∈[a，b]有a

(x)b；2.存在正數(shù)L<1,使對任意x∈[a，b]有|'(x)|L<1.則迭代過程xk+1=

(xk)對于任意初值x0∈[a，b]均收斂于方程x=

(x)的根。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【定理2-1'】若方程有根,|'()|<1，且

'在的某鄰域U()內(nèi)連續(xù),則存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收斂。證明：x[–

，+

]有|'(x)|L<1.

x[–

，+

]，

(x)[–

，+

]由定理6-1知，任意x0[–

，+

]，迭代法xk+1=

(xk)收斂。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【定理2-1'】若方程有根,|'()|<1，且

'在的某鄰域U()內(nèi)連續(xù),則存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收斂。說明：只要x0充分接近，且|'(x0)|明顯小于1，則{xk}收斂于

。2.1非線性方程的迭代法2.1.2簡單迭代法2.收斂性【例2-4】求方程x=e–x在x=0.5附近的一個根，要求精度

<10–3。分析：記f(x)=x–e–x，則f(0.5)<0，f(1)>0，即根∈[0.5，1]，要驗證定理6-1的條件很麻煩，只須驗證定理6-1'的條件，或|'(x)|<1于[0.5，1]上。解：因為

(x)=e–x，

'(x)=–e–x，|

'(x)|=e–x<1于[0.5，1]上。(當然有|

'()|<1)。所以取x0=0.5，迭代法必收斂。計算結(jié)果如表kxkkxk00.570.56843810.60653180.56640920.54523990.5675630.579703100.56690740.560065110.56727750.571172120.56706760.564863130.5671862.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階一種迭代格式要具有實用意義，不但需要肯定是收斂的，還要求它收斂得比較快，就是說要有一定的收斂速度，否則未必有實際意義。那么，何謂收斂速度呢？下面就來介紹這個概念.2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階【定義2-1】設由某方法確定的序列{xk}收斂于方程的根，如果存在正實數(shù)p，使得

(C為非零常數(shù))則稱序列{xk}收斂于的收斂速度是p階的，或稱該方法具有p階斂速。2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階【定義6-1】設由某方法確定的序列{xk}收斂于方程的根，如果存在正實數(shù)p，使得

(C為非零常數(shù))當p=1時，稱該方法為線性(一次)收斂；當p>1時，稱方法為超線性收斂。特別當p=2時，稱方法為平方(二次)收斂；2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階【定義6-1】設由某方法確定的序列{xk}收斂于方程的根，如果存在正實數(shù)p，使得

(C為非零常數(shù))由定義易見，一個方法的收斂速度實際就是絕對誤差的收縮率，斂速的階p越大，絕對誤差縮減得越快，也就是該方法收斂得越快。2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階在定理2-2中，若

'(x)連續(xù)，且

'()0，則迭代格式xk+1=

(xk)必為線性收斂。因為由如果

'()=0，則收斂速度就不止是線性的了。進一步有2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階【定理2-2】設方程方程x=

(x)，正整數(shù)p2，若

(p)在根的某鄰域內(nèi)連續(xù)，且滿足

(6.6)則{xk}p階局部收斂。證明：∵

'()=0(<1)，∴xk局部收斂。設

(x)在處展開為2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階

(2.6)則{xk}p階局部收斂。證明：由(2.6)知，所以即{xk}p階局部收斂。2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階

【例2-5】設fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

為f的單重零點。試確定未知函數(shù)r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三階局部收斂的。解：由定理2-2知，應有

'()=

"()=0，因為

'(x)=1–r1'(x)f(x)–r1(x)f'(x)–r2'(x)f2(x)–2r2(x)f(x)f'(x)而f()=0，f

'()≠0（單重零點）,令

'()=0有1–r1'()f

'()=0.取,則有

'()=02.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階

【例2-5】設fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

為f的單重零點。試確定未知函數(shù)r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三階局部收斂的。解：此時有

'(x)=–r1'(x)f(x)–r2'(x)f

2(x)–2r2(x)f(x)f'(x)

"(x)=–r1"(x)f(x)–r1'(x)f'(x)–r2"(x)f

2(x)–4r2'(x)f(x)f'(x)–2r2(x)[f'(x)]2–2r2'(x)f(x)f

"(x)其中

2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階

【例2-5】設fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

為f的單重零點。試確定未知函數(shù)r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三階局部收斂的。解：

"(x)=–r1"(x)f(x)–r1'(x)f'(x)–r2"(x)f

2(x)–4r2'(x)f

(x)f

'(x)–2r2(x)[f

'(x)]2–2r2'(x)f

(x)f

"(x)令

"(

)=0，有即取

，則有

"(

)=0。2.1非線性方程的迭代法2.1.2簡單迭代法3.收斂階

【例2-5】設fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

為f的單重零點。試確定未知函數(shù)r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三階局部收斂的。解：從而只要同時取和迭代法至少具有三階局部收斂性。2.1非線性方程的迭代法2.1.3Newton迭代法及其變形1.Newton迭代法取

(x)=x+k(x)f(x),(k(x)0).則x=

(x)與f(x)=0同解.由

'(x)=1+k'(x)f(x)+k(x)f'(x).令

'()=0k()f'()=–1.若f'()0,則有即迭代法：稱為牛頓迭代法。如何構造

(x)使迭代法收斂？令x=x+f(x)？不妥!2.1非線性方程的迭代法2.1.3Newton迭代法及其變形1.Newton迭代法幾何意義：給定非線性方程f(x)=0的解

的近似值xn用過點Pn(xn,f(xn))的切線：y=f(xn)+(x-xn)f'(xn)近似表示曲線y=f(x)并將該切線與x軸的交點的橫坐標xn+1作為

的新的近似值。2.1非線性方程的迭代法2.1.3Newton迭代法及其變形【例2-6】用牛頓法計算方程x3–x–1=0在x=1.5附近的根.解：f(x)=x3–x–1，f'(x)=3x2–1在x=1.5附近不為零.

k=0，1，2，…從x(0)=1.5出發(fā)，迭代3次即有6位有效數(shù)字.2.1非線性方程的迭代法2.1.3Newton迭代法及其變形【例2-7】用Newton法求非線性方程f(x)=xex–1=0在(0，1)內(nèi)的根，取x(0)=0.5。解：因為f

'(x)=(1+x)ex，故其Newton迭代公式為k=0，1，2，…從x(0)=0.5出發(fā)，計算結(jié)果2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性(1)若是f(x)的單重根：f()=0，f'()≠0因為一般不為0所以，在f'()0,f"(x)連續(xù)的條件下，牛頓迭代法至少是平方收斂的.<'()=0>.2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性(2)若是f(x)的重根，即有f(x)=(x–)mg(x)其中g()≠0，m2因為f'(x)=m(x–)m-1g(x)+(x–)mg'(x)，記x=+h，則

2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性(2)若是f(x)的重根，即有f(x)=(x–)mg(x)其中g()≠0，m2，記x=+h，則

2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性(2)若是f(x)的重根，即有f(x)=(x–)mg(x)當m2時，

'(

)≠0，由|

'(

)|<1，知Newton迭代法一階收斂。2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性(3)若是f(x)的重根，即有f(x)=(x–)mg(x)(2)的改進：

取

，易知有

'(

)=0，所以，若事先知道的重數(shù)，則可改迭代公式為此時，迭代序列{xk}是二階收斂的。2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性(3)若是f(x)的重根，即有f(x)=(x–)mg(x)或令則是u(x)的單重零點。2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性(3)若是f(x)的重根，即有f(x)=(x–)mg(x)或令，則是u(x)的單重零點。應用Newton法于u(x)，有此時，迭代序列也是二階收斂的

2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性【例2-8】是方程x4–4x2+4=0的二重根(1)采用Newdon法即

2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性【例6-8】是方程x4–4x2+4=0的二重根(2)采用(3.15)2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性【例2-8】是方程x4–4x2+4=0的二重根(3)采用，即2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性【例2-8】是方程x4–4x2+4=0的二重根分別采用2.1非線性方程的迭代法2.1.3Newton迭代法及其變形2.收斂性【例2-9】計算的近似值分析：是方程x3–7=0的根Newton迭代公式：2.1非線性方程的迭代法2.1.3Newton迭代法及其變形3.弦截法牛頓迭代計算導數(shù)f'(x)不方便，代入(2.10)中有2.1非線性方程的迭代法2.1.3Newton迭代法及其變形3.弦截法牛頓迭代計算導數(shù)f'(x)不方便，即

(2.11)稱(2.11)為弦截法.2.1非線性