計算方法非線性方程求解1課件

第二章非線性方程數(shù)值解§1基礎(chǔ)知識求f(x)=0的根,其中f(x)為非線性函數(shù)。

此類問題

在工程和科學(xué)計算中，此類問題廣泛存在。當(dāng)f(x)為代數(shù)多項(xiàng)式時，稱為代數(shù)方程，否則為超越方程。第二章非線性方程數(shù)值解§1基礎(chǔ)知識求f(x1§2二分法原理：若f

C[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。abx1x2abx*2xx*§2二分法原理：若fC[a,b]，且f(2誤差分析：第1步產(chǎn)生的有誤差第k+1步產(chǎn)生的xk

有誤差對于給定的精度,可估計二分法所需的步數(shù)k：優(yōu)點(diǎn)：①簡單;②對f(x)

要求不高(只要連續(xù)即可).缺點(diǎn)：①無法求復(fù)根及偶重根②收斂慢誤差分析：第1步產(chǎn)生的有誤差第k+1步產(chǎn)生的xk有3計算方法非線性方程求解1課件4計算方法非線性方程求解1課件5

迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。

迭代法是一種重要的逐次逼近方法。這種方法用某個固定公式反復(fù)校正根的近似值，使之逐步精確化，最后得到滿足精度要求的結(jié)果。§2迭代法等價變換為的不動點(diǎn)由此也稱為不動點(diǎn)迭代法，迭代法的一般形式：迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。6,…,,….迭代公式若收斂，即存在x*使得

，且

連續(xù)，則由可知，即是的不動點(diǎn)，也就是f的根。從一個初值

出發(fā)，計算,…,,….迭代公式若收斂，7xyy=xxyy=xxyy=xxyy=xx*x*x*x*x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1y=(x)y=(x)y=(x)y=(x)xyy=xxyy=xxyy=xxyy=xx*8計算方法非線性方程求解1課件9(I)當(dāng)x[a,b]時，(x)[a,b]；(II)0L<1使得

則任取x0[a,b]，由xk+1=(xk)得到的序列收斂于(x)在[a,b]上的唯一不動點(diǎn)。并且有誤差估計式：(k=1,2,…)k考慮方程x=(x),(x)C[a,b],若定理1(I)當(dāng)x[a,b]時，(x)[a,10從一個初值出發(fā)，計算則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。由Taylor展開：對于給定的精度,可估計二分法所需的步數(shù)k：（收斂的充分條件）設(shè)fC2[a,b]，若由Taylor展開：求f(x)=0的根,其中f(x)為非線性函數(shù)。(k=1,2,…)(3)將(x*x0)2看成高階小量，則有：用某個固定公式反復(fù)校正根的近似值，使之逐步精①簡單;三個迭代值組合的方法：迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛?？紤]方程x=(x),(x)C[a,b],若用某個固定公式反復(fù)校正根的近似值，使之逐步精注2注1從一個初值出發(fā)，計算注2注111②不動點(diǎn)唯一反證：若不然，設(shè)還有，則而③當(dāng)k

時，

xk收斂到x*？令有根證明：①(x)在[a,b]上存在不動點(diǎn)②不動點(diǎn)唯一反證：若不然，設(shè)還有12④⑤⑥④⑤⑥13計算方法非線性方程求解1課件14計算方法非線性方程求解1課件15計算方法非線性方程求解1課件16由此也稱為不動點(diǎn)迭代法，(I)當(dāng)x[a,b]時，(x)[a,b]；原理：若fC[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。在整個[a,b]上f”不變號且f’(x)0；三個迭代值組合的方法：引入：將非線性方程線性化——Taylor展開(k=1,2,…)其中，則其中，則在整個[a,b]上f’(x)0,f”(x)0；原理：若fC[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。若收斂，即存在x*使得，在x0和x之間。f(a)f(b)<0；代入公式，令實(shí)、虛部對應(yīng)相等，可得（局部收斂性）設(shè)fC2[a,b]，若x*為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足①無法求復(fù)根及偶重根只要f’(x*)0，則令引入：將非線性方程線性化——Taylor展開由此也稱為不動點(diǎn)迭代法，17連續(xù)連續(xù)18注：事實(shí)上，定理3是充分必要的，即另有結(jié)論：注：事實(shí)上，定理3是充分必要的，即另有結(jié)論：19計算方法非線性方程求解1課件20計算方法非線性方程求解1課件21兩個迭代值組合的方法：兩個迭代值組合的方法：22計算方法非線性方程求解1課件23三個迭代值組合的方法：三個迭代值組合的方法：24取x0x*，將f(x)在x0做一階Taylor展開:將(x*x0)2看成高階小量，則有：f(a)f(b)<0；在整個[a,b]上f’(x)0,f”(x)0；迭代法是一種重要的逐次逼近方法。則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。則任取x0[a,b]，Newton’sMethod產(chǎn)生的序列{xk}從一個初值出發(fā)，計算在整個[a,b]上f’(x)0,f”(x)0；由此也稱為不動點(diǎn)迭代法，，且連續(xù)，則由可知，即是的不動點(diǎn)，也就是f的根。引入：將非線性方程線性化——Taylor展開f(a)f(b)<0；求復(fù)根——Newton公式中的自變量可以是復(fù)數(shù)迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。原理：若fC[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。第二章非線性方程數(shù)值解(3)選取x0[a,b]使得f(x0)f”(x0)>0；由此也稱為不動點(diǎn)迭代法，(k=1,2,…)代入公式，令實(shí)、虛部對應(yīng)相等，可得xyy=xy=g(x)x*x0P(x0,y0)y0

z0P(y0,z0)取x0x*，將f(x)在x0做一階Taylo25計算方法非線性方程求解1課件26計算方法非線性方程求解1課件27計算方法非線性方程求解1課件28§3牛頓法引入：將非線性方程線性化——Taylor展開取x0

x*，將f(x)在x0做一階Taylor展開:，在x0和x之間。將(x*

x0)2看成高階小量，則有：xyx*x0（fC1，f’(x*)

0）單根情形§3牛頓法引入：將非線性方程線性化——Taylor29定理1（收斂的充分條件）設(shè)f

C2[a,b]，若f(a)f(b)<0；在整個[a,b]上f”不變號且f’(x)0；(3)選取x0

[a,b]使得f(x0)f”(x0)>0；則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。定理1（收斂的充分條件）設(shè)fC30計算方法非線性方程求解1課件31定理2（局部收斂性）設(shè)f

C2[a,b]，若x*

為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足定理2（局部收斂性）設(shè)fC2[32證明：Newton’sMethod事實(shí)上是一種特殊的不動點(diǎn)迭代其中，則收斂由Taylor展開：只要f’(x*)0，則令可得結(jié)論。證明：Newton’sMethod事實(shí)上是一種特殊的不動33計算方法非線性方程求解1課件34計算方法非線性方程求解1課件35計算方法非線性方程求解1課件36定理3（全局收斂性定理）設(shè)f

C2[a,b]，若f(a)f(b)<0；在整個[a,b]上f’(x)0,f”(x)0；(3)則任取x0

[a,b]，Newton’sMethod產(chǎn)生的序列{xk}都收斂到f(x)=0在[a,b]的根x*。定理3（全局收斂性定理）設(shè)fC37重根情形重根情形38計算方法非線性方程求解1課件39計算方法非線性方程求解1課件40計算方法非線性方程求解1課件41計算方法非線性方程求解1課件42原理：若由xk得到的xk+1不能使|f|減小，則在xk和xk+1之間找一個更好的點(diǎn)，使得。xkxk+1原理：若由xk得到的xk+1不能使|f|減小43求復(fù)根——Newton公式中的自變量可以是復(fù)數(shù)記z=x+iy,z0為初值，同樣有設(shè)代入公式，令實(shí)、虛部對應(yīng)相等，可得求復(fù)根——Newton公式中的自變量可以是復(fù)數(shù)記z44引入：將非線性方程線性化——Taylor展開(I)當(dāng)x[a,b]時，(x)[a,b]；確化，最后得到滿足精度要求的結(jié)果。代入公式，令實(shí)、虛部對應(yīng)相等，可得證明：①(x)在[a,b]上存在不動點(diǎn)迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。取x0x*，將f(x)在x0做一階Taylor展開:(3)選取x0[a,b]使得f(x0)f”(x0)>0；都收斂到f(x)=0在[a,b]的根x*。由此也稱為不動點(diǎn)迭代法，第k+1步產(chǎn)生的xk有誤差取x0x*，將f(x)在x0做一階Taylor展開:考慮方程x=(x),(x)C[a,b],若將(x*x0)2看成高階小量，則有：都收斂到f(x)=0在[a,b]的根x*。引入：將非線性方程線性化——Taylor展開f(a)f(b)<0；(k=1,2,…)迭代法是一種重要的逐次逼近方法。都收斂到f(x)=0在[a,b]的根x*?！?引入：將非線性方程線性化——Taylor展開§445計算方法非線性方程求解1課件46計算方法非線性方程求解1課件47計算方法非線性方程求解1課件48計算方法非線性方程求解1課件49§5§550計算方法非線性方程求解1課件51將(x*x0)2看成高階小量，則有：第k+1步產(chǎn)生的xk有誤差（局部收斂性）設(shè)fC2[a,b]，若x*為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足（局部收斂性）設(shè)fC2[a,b]，若x*為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足由此也稱為不動點(diǎn)迭代法，(3)(3)選取x0[a,b]使得f(x0)f”(x0)>0；引入：將非線性方程線性化——Taylor展開代入公式，令實(shí)、虛部對應(yīng)相等，可得由Taylor展開：記z=x+iy,z0為初值，同樣有從一個初值出發(fā)，計算由此也稱為不動點(diǎn)迭代法，取x0x*，將f(x)在x0做一階Taylor展開:在整個[a,b]上f”不變號且f’(x)0；三個迭代值組合的方法：由此也稱為不動點(diǎn)迭代法，(3)選取x0[a,b]使得f(x0)f”(x0)>0；迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。取x0x*，將f(x)在x0做一階Taylor展開:在整個[a,b]上f’(x)0,f”(x)0；由此也稱為不動點(diǎn)迭代法，都收斂到f(x)=0在[a,b]的根x*。記z=x+iy,z0為初值，同樣有由此也稱為不動點(diǎn)迭代法，求f(x)=0的根,其中f(x)為非線性函數(shù)。將(x*x0)2看成高階小量，則有：引入：將非線性方程線性化——Taylor展開(k=1,2,…)若收斂，即存在x*使得第二章非線性方程數(shù)值解(k=1,2,…)(3)選取x0[a,b]使得f(x0)f”(x0)>0；引入：將非線性方程線性化——Taylor展開考慮方程x=(x),(x)C[a,b],若兩個迭代值組合的方法：確化，最后得到滿足精度要求的結(jié)果。三個迭代值組合的方法：原理：若fC[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。原理：若由xk得到的xk+1不能使|f|減小，則在xk和xk+1之間找一個更好的點(diǎn)，使得。將(x*x0)2看成高階小量，則有：由此也稱為不動52第二章非線性方程數(shù)值解§1基礎(chǔ)知識求f(x)=0的根,其中f(x)為非線性函數(shù)。

此類問題

在工程和科學(xué)計算中，此類問題廣泛存在。當(dāng)f(x)為代數(shù)多項(xiàng)式時，稱為代數(shù)方程，否則為超越方程。第二章非線性方程數(shù)值解§1基礎(chǔ)知識求f(x53§2二分法原理：若f

C[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。abx1x2abx*2xx*§2二分法原理：若fC[a,b]，且f(54誤差分析：第1步產(chǎn)生的有誤差第k+1步產(chǎn)生的xk

有誤差對于給定的精度,可估計二分法所需的步數(shù)k：優(yōu)點(diǎn)：①簡單;②對f(x)

要求不高(只要連續(xù)即可).缺點(diǎn)：①無法求復(fù)根及偶重根②收斂慢誤差分析：第1步產(chǎn)生的有誤差第k+1步產(chǎn)生的xk有55計算方法非線性方程求解1課件56計算方法非線性方程求解1課件57

迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。

迭代法是一種重要的逐次逼近方法。這種方法用某個固定公式反復(fù)校正根的近似值，使之逐步精確化，最后得到滿足精度要求的結(jié)果。§2迭代法等價變換為的不動點(diǎn)由此也稱為不動點(diǎn)迭代法，迭代法的一般形式：迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。58,…,,….迭代公式若收斂，即存在x*使得

，且

連續(xù)，則由可知，即是的不動點(diǎn)，也就是f的根。從一個初值

出發(fā)，計算,…,,….迭代公式若收斂，59xyy=xxyy=xxyy=xxyy=xx*x*x*x*x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1y=(x)y=(x)y=(x)y=(x)xyy=xxyy=xxyy=xxyy=xx*60計算方法非線性方程求解1課件61(I)當(dāng)x[a,b]時，(x)[a,b]；(II)0L<1使得

則任取x0[a,b]，由xk+1=(xk)得到的序列收斂于(x)在[a,b]上的唯一不動點(diǎn)。并且有誤差估計式：(k=1,2,…)k考慮方程x=(x),(x)C[a,b],若定理1(I)當(dāng)x[a,b]時，(x)[a,62從一個初值出發(fā)，計算則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。由Taylor展開：對于給定的精度,可估計二分法所需的步數(shù)k：（收斂的充分條件）設(shè)fC2[a,b]，若由Taylor展開：求f(x)=0的根,其中f(x)為非線性函數(shù)。(k=1,2,…)(3)將(x*x0)2看成高階小量，則有：用某個固定公式反復(fù)校正根的近似值，使之逐步精①簡單;三個迭代值組合的方法：迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。考慮方程x=(x),(x)C[a,b],若用某個固定公式反復(fù)校正根的近似值，使之逐步精注2注1從一個初值出發(fā)，計算注2注163②不動點(diǎn)唯一反證：若不然，設(shè)還有，則而③當(dāng)k

時，

xk收斂到x*？令有根證明：①(x)在[a,b]上存在不動點(diǎn)②不動點(diǎn)唯一反證：若不然，設(shè)還有64④⑤⑥④⑤⑥65計算方法非線性方程求解1課件66計算方法非線性方程求解1課件67計算方法非線性方程求解1課件68由此也稱為不動點(diǎn)迭代法，(I)當(dāng)x[a,b]時，(x)[a,b]；原理：若fC[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。在整個[a,b]上f”不變號且f’(x)0；三個迭代值組合的方法：引入：將非線性方程線性化——Taylor展開(k=1,2,…)其中，則其中，則在整個[a,b]上f’(x)0,f”(x)0；原理：若fC[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。若收斂，即存在x*使得，在x0和x之間。f(a)f(b)<0；代入公式，令實(shí)、虛部對應(yīng)相等，可得（局部收斂性）設(shè)fC2[a,b]，若x*為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足①無法求復(fù)根及偶重根只要f’(x*)0，則令引入：將非線性方程線性化——Taylor展開由此也稱為不動點(diǎn)迭代法，69連續(xù)連續(xù)70注：事實(shí)上，定理3是充分必要的，即另有結(jié)論：注：事實(shí)上，定理3是充分必要的，即另有結(jié)論：71計算方法非線性方程求解1課件72計算方法非線性方程求解1課件73兩個迭代值組合的方法：兩個迭代值組合的方法：74計算方法非線性方程求解1課件75三個迭代值組合的方法：三個迭代值組合的方法：76取x0x*，將f(x)在x0做一階Taylor展開:將(x*x0)2看成高階小量，則有：f(a)f(b)<0；在整個[a,b]上f’(x)0,f”(x)0；迭代法是一種重要的逐次逼近方法。則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。則任取x0[a,b]，Newton’sMethod產(chǎn)生的序列{xk}從一個初值出發(fā)，計算在整個[a,b]上f’(x)0,f”(x)0；由此也稱為不動點(diǎn)迭代法，，且連續(xù)，則由可知，即是的不動點(diǎn)，也就是f的根。引入：將非線性方程線性化——Taylor展開f(a)f(b)<0；求復(fù)根——Newton公式中的自變量可以是復(fù)數(shù)迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。原理：若fC[a,b]，且f(a)·f(b)<0，則f在(a,b)上必有一根。第二章非線性方程數(shù)值解(3)選取x0[a,b]使得f(x0)f”(x0)>0；由此也稱為不動點(diǎn)迭代法，(k=1,2,…)代入公式，令實(shí)、虛部對應(yīng)相等，可得xyy=xy=g(x)x*x0P(x0,y0)y0

z0P(y0,z0)取x0x*，將f(x)在x0做一階Taylo77計算方法非線性方程求解1課件78計算方法非線性方程求解1課件79計算方法非線性方程求解1課件80§3牛頓法引入：將非線性方程線性化——Taylor展開取x0

x*，將f(x)在x0做一階Taylor展開:，在x0和x之間。將(x*

x0)2看成高階小量，則有：xyx*x0（fC1，f’(x*)

0）單根情形§3牛頓法引入：將非線性方程線性化——Taylor81定理1（收斂的充分條件）設(shè)f

C2[a,b]，若f(a)f(b)<0；在整個[a,b]上f”不變號且f’(x)0；(3)選取x0

[a,b]使得f(x0)f”(x0)>0；則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。定理1（收斂的充分條件）設(shè)fC82計算方法非線性方程求解1課件83定理2（局部收斂性）設(shè)f

C2[a,b]，若x*

為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足定理2（局部收斂性）設(shè)fC2[84證明：Newton’sMethod事實(shí)上是一種特殊的不動點(diǎn)迭代其中，則收斂由Taylor展開：只要f’(x*)0，則令可得結(jié)論。證明：Newton’sMethod事實(shí)上是一種特殊的不動85計算方法非線性方程求解1課件86計算方法非線性方程求解1課件87計算方法非線性方程求解1課件88定理3（全局收斂性定理）設(shè)f

C2[a,b]，若f(a)f(b)<0；在整個[a,b]上f’(x)0,f”(x)0；(3)則任取x0

[a,b]，Newton’sMethod產(chǎn)生的序列{xk}都收斂到f(x)=0在[a,b]的根x*。定理3（全局收斂性定理）設(shè)fC89重根情形重根情形90計算方法非線性方程求解1課件91計算方法非線性方程求解1課件92計算方法非線性方程求解1課件93計算方法非線性方程求解1課件94原理：若由xk得到的xk+1不能使|f|減小，則在xk和xk+1之間找一個更好的點(diǎn)，使得。xkxk+1原理：若由xk得到的xk+1不能使|f|減小95求復(fù)根——Newton公式中的自變量可以是復(fù)數(shù)記z=x+iy,z0為初值，同樣有設(shè)代入公式，令實(shí)、虛部對應(yīng)相等，可得求復(fù)根——Newton公式中的自變量可以是復(fù)數(shù)記z96引入：將非線性方程線性化——Taylor展開(I)當(dāng)x[a,b]時，(x)[a,b]；確化，最后得到滿足精度要求的結(jié)果。代入公式，令實(shí)、虛部對應(yīng)相等，可得證明：①(x)在[a,b]上存在不動點(diǎn)迭代法是數(shù)值計算中的一類重要方法，應(yīng)用廣泛。取x0x*，將f(x)在x0做一階Taylor展開:(3)選取x0[a,b]使得f(x0)f”(x0)>0；都收斂到f(x)=0在[a,b]的根x*。由此也稱為不動點(diǎn)迭代法，第k+1步產(chǎn)生的xk有誤差取x0x*，將f(x)在x0做一階Taylor展開:考慮方程x=(x),(x)C[a,b],若將(x*x0)2看成高階小量，則有：都收斂到f(x)=0在[a,b]的根x*。引入：將非線性方程線性化——Taylor展開f(a)f(b)<0；(k=1,2,…)迭代法是一種重要的逐次逼近方法。都收斂到f(x)=0在[a,b]的根x*?！?引入：