數值分析方程求根的迭代法

數值分析方程求根的迭代法第1頁，共30頁，2023年，2月20日，星期六方程求根需要考慮的問題求

f(x)=0的根

代數方程：f(x)=a0+a1x+...+anxn超越方程：f(x)含超越函數，如sin(x),ex,lnx等

實根與復根

根的重數f(x)=(x–x*)m

·

g(x)且

g(x*)

0,則x*為f(x)的m重根

有根區(qū)間：[a,b]上存在f(x)=0

的一個實根在有根的前提下求出方程的近似根。研究內容：第2頁，共30頁，2023年，2月20日，星期六迭代法的基本思想基本思路同解迭代公式給定初值存在等價于迭代函數？轉換是否唯一幾何意義第3頁，共30頁，2023年，2月20日，星期六轉換例子(1)x=1(x)=x3-6x2+10x-2;(2)

;(3)

;(4)

;例：已知方程

x3-6x2+9x-2=0

在

[3,4]

內有一根，考慮迭代？哪種轉換方法好第4頁，共30頁，2023年，2月20日，星期六幾何含義xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1第5頁，共30頁，2023年，2月20日，星期六幾何含義xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1第6頁，共30頁，2023年，2月20日，星期六壓縮映像定理定理設(x)C[a,b]

且可導，若(2)0L<1，使得|’(x)|L

對x[a,b]

成立(1)a(x)b對一切x[a,b]

都成立則有(a)對任意x0[a,b]，由

xk+1

=

(xk)

產生的迭代序列均收斂到(x)在[a,b]

中的唯一不動點x*。(b)有如下的誤差估計可用|xk+1-xk

|來控制收斂精度L

越小收斂越快第7頁，共30頁，2023年，2月20日，星期六壓縮映像定理證明(a)由壓縮映像定理可知，不動點x*

存在且唯一。第8頁，共30頁，2023年，2月20日，星期六壓縮映像定理證明(b)又第9頁，共30頁，2023年，2月20日，星期六全局收斂與局部收斂定理的條件保證了不動點迭代的全局收斂性。即迭代的收斂性與初始點的選取無關。這種在x*的鄰域內具有的收斂性稱為局部收斂性。定理中的條件|’(x)|L

<1可以適當放寬(2’)’(x)

在x*

的某個鄰域內連續(xù)，且|’(x*)|<1由’(x)

的連續(xù)性及|’(x*)|<1即可推出：存在x*的某個

鄰域

N(x*)

=[x*-,x*+],

使得對

xN(x*)都有|’(x)|L

<1,則由x0N(x*)開始的迭代都收斂。第10頁，共30頁，2023年，2月20日，星期六迭代過程的收斂速度定義則稱該迭代為r階收斂。(1)當r=1時稱為線性收斂，此時C<1；(2)當r=2時稱為二次收斂，或平方收斂；(3)當r>1時稱為超線性收斂。二分法線性收斂不動點迭代中，若

’(x*)0，則取極限得(C為常數)線性收斂第11頁，共30頁，2023年，2月20日，星期六P階收斂設迭代xk+1=(xk)

，若(p)(x)

在x*的某鄰域內連續(xù)，則該迭代法具有p階收斂的充要條件是定理并且有證明：充分性.根據泰勒展開有第12頁，共30頁，2023年，2月20日，星期六必要性的證明必要性.設迭代xk+1=(xk)是p階收斂。迭代兩邊取極限

，由(x)的連續(xù)性可知x*=(x*)

。設p0是滿足的最小正整數。由充分性的證明過程可知迭代p0階收斂。又若

p0<p，

與迭代p

階收斂矛盾p0=p第13頁，共30頁，2023年，2月20日，星期六迭代過程的加速

設有不動點迭代：設：缺點：每次迭代需計算第14頁，共30頁，2023年，2月20日，星期六埃特金算法設：Aitken加速當x

收斂到x*時，修正項分子趨于零。

第15頁，共30頁，2023年，2月20日，星期六一點注記第16頁，共30頁，2023年，2月20日，星期六Newton迭代

基本思想：將非線性方程線性化設xk

是f(x)=0

的近似根，將f(x)

在

xk

一階Taylor展開:，在xk

和x

之間。xyx*xkxk+1條件：

f’(x)0第17頁，共30頁，2023年，2月20日，星期六Newton迭代

Newton法可以看作下面的不動點迭代：其中’(x*)=0Newton法至少二階局部收斂定理設f(x)

在其零點x*的某個鄰域內二階連續(xù)可導且f’(x)0，則存在

x*的某個

鄰域

N(x*)

=[x*-,x*+],

使得對

x0N(x*)，Newton法產生的序列以不低于二階的收斂速度收斂到x*

。第18頁，共30頁，2023年，2月20日，星期六Newton迭代

Newton法也可以看作一類特殊的加速迭代取(x)=x-f(x)第19頁，共30頁，2023年，2月20日，星期六收斂性定理定理設f

C2[a,b]，且

f

滿足

(1)f(a)f(b)<0(2)對

x[a,b]，f’(x)0

且f”(x)

0

；(3)初始點x0

[a,b]

滿足f(x0)f”(x0)>0；則Newton法產生的序列收斂到f在[a,b]

的唯一零點x*。第20頁，共30頁，2023年，2月20日，星期六全局收斂性定理定理設f

C2[a,b]，且

f

滿足

(1)f(a)f(b)<0(2)對

x[a,b]，f’(x)0

且f”(x)

0

；則對任意初始點x0

[a,b]，Newton法產生的序列收斂到f在[a,b]

的唯一零點x*。(3)第21頁，共30頁，2023年，2月20日，星期六舉例（一）例：設計一個二階收斂算法計算(a>0)。解：轉化為求x2-a=0的正根Newton迭代：二階收斂mynewton.m第22頁，共30頁，2023年，2月20日，星期六重根情形

設x*

是f(x)

的m(m2)

重根，Newton法是否收斂？Taylor展式Newton迭代：線性收斂。且重數m

越高，收斂越慢。第23頁，共30頁，2023年，2月20日，星期六提高收斂階提高收斂速度但m通常無法預先知道！法一：取二階收斂法二：將求f(x)的重根轉化為求另一個函數的單根。構造針對(x)的具有二階收斂的Newton迭代：令，則x*是(x)的單重根。第24頁，共30頁，2023年，2月20日，星期六降低初始點的要求例：求

sin(x)-x/6=0的正根。mynewton.m

Newton下山法：kk

為數列中滿足的最大數。

算法7.2

(Newton下山法)給定初始點x0，精度要求1.如果|f(xk)|<

,停機，輸出xk2.計算，=13.如果|f(xk+dk)|<|f(xk)|，令xk+1=xk+dk

，返回第1步；

否則折半，重新計算第3步Newton法的收斂依賴于初始點的選取。第25頁，共30頁，2023年，2月20日，星期六割線法

Newton法的缺點：每步迭代都要計算導數值

只需計算函數值，避免計算導數；切線斜率割線斜率xk-1xkxk+1xk+1切線割線需要兩個初始點；

收斂比Newton法稍慢，但對初始點要求同樣高。第26頁，共30頁，2023年，2月20日，星期六割線法公式兩點割線法單點割線法第27頁，共30頁，2023年，2月20日，星期六誤差估計引理設f(x)在其零點x*的某個鄰域

N(x*)

=[x*-,x*+]內存在連續(xù)的二階導數，且f’(x)0，又設xk-1,xkN(x*)\{x*}，且互不相等，則由兩點割線法的誤差

ek=xk-x*

滿足其中第28頁，共30頁，2023年