第二章非線性方程的數(shù)值解法第一頁，共十九頁，編輯于2023年，星期四取滿足因此，選取迭代函數(shù)Newton–Raphson迭代格式稱之為牛頓—拉夫森方法，簡稱牛頓法原理：將非線性方程線性化取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0

和x

之間2、Taylor展開法/*Taylor’sexpansionMethod*/第二頁，共十九頁，編輯于2023年，星期四將(x*

x0)2

看成高階小量，則有：xyx*x0只要f

C1，每一步迭代都有而且，則

x*就是f

的根。與x軸交點的橫坐標(biāo)第三頁，共十九頁，編輯于2023年，星期四無開方運算，又無除法運算。例1：寫出求的Newton迭代格式；寫出求的Newton迭代格式,要求公式中既解：等價于求方程的正根等價于求方程的正根第四頁，共十九頁，編輯于2023年，星期四Th2.7

（局部收斂性）設(shè)x*

為方程f(x)=0的根，在包含x*的某個開區(qū)間內(nèi)連續(xù)，且，則存在x*的鄰域，使得任取初值，由Newton’sMethod產(chǎn)生的序列以不低于二階的收斂速度收斂于x*，且第五頁，共十九頁，編輯于2023年，星期四證明：Newton’sMethod

事實上是一種特殊的不動點迭代其中，則收斂由Taylor展開：在單根

/*simpleroot*/

附近收斂快只要，則令可得結(jié)論。第六頁，共十九頁，編輯于2023年，星期四有根根唯一產(chǎn)生的序列單調(diào)有界保證收斂Th2.8

（收斂的充分條件）設(shè)f(x)=0

且f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整個[a,b]上不變號且

；(3)選取x0

[a,b]

使得；則Newton’sMethod產(chǎn)生的序列{xk}

收斂于方程的根,且第七頁，共十九頁，編輯于2023年，星期四注：Newton’sMethod

收斂性依賴于x0

的選取。x*x0x0x0Th2.9

（收斂的另一充分條件）設(shè)

在[a,b]上連續(xù)，(1)

f(a)f(b)<0；(2)

在整個[a,b]上且

；(3)

，則對，Newton’sMethod產(chǎn)生的序列{xk}

收斂于方程在[a,b]內(nèi)的唯一實根。且第八頁，共十九頁，編輯于2023年，星期四Th2.9中條件（3）的幾何意義保證數(shù)列單調(diào)遞增且有上界第九頁，共十九頁，編輯于2023年，星期四改進(jìn)與推廣（補充）

/*improvementandgeneralization*/重根

/*multipleroot*/

加速收斂法：Q1:

若，Newton’sMethod

是否仍收斂？設(shè)x*是f

的n

重根，則：且。因為Newton’sMethod

事實上是一種特殊的不動點迭代，其中，則A1:

有局部收斂性，但重數(shù)n

越高，收斂越慢。Q2:

如何加速重根情況時的收斂速度？A2:

將求

f

的重根轉(zhuǎn)化為求另一函數(shù)的單根。令，則f

的重根=

的單根。第十頁，共十九頁，編輯于2023年，星期四

§5弦割法與拋物線法

/*SecantMethodandParabolaMethod

*/x0x1割線

/*secantline*/切線斜率

割線斜率需要2個初值x0

和x1。Newton’sMethod

每一步要計算f

和，為了避免計算導(dǎo)數(shù)值，現(xiàn)用f

的值近似，從而得到弦割法（割線法）。x2一、弦割法第十一頁，共十九頁，編輯于2023年，星期四Th2.10

局部收斂性設(shè)表示區(qū)間，x*為方程f(x)=0的根，函數(shù)f(x)在

中有足夠階連續(xù)導(dǎo)數(shù)，且滿足則對，由割線法產(chǎn)生的序列都收斂于x*，且(i)(ii)(iii)

其中收斂速度介于NewtonandBisection

之間

第十二頁，共十九頁，編輯于2023年，星期四xk-2Muller方法的思想來源于弦割法:利用3個已知點構(gòu)造一條拋物線,取其與x軸的交點構(gòu)造下一次迭代值.x*二、拋物線法(Muller)幾何圖示xkxk-1xk+1第十三頁，共十九頁，編輯于2023年，星期四

Muller方法的具體實現(xiàn):設(shè)已知三個點則過上述三個點的拋物線方程為:取該拋物線與x軸的交點作為下一次迭代值,即然后取新的相鄰的三次迭代值重復(fù)上述過程,即為Muller方法.第十四頁，共十九頁，編輯于2023年，星期四

Muller方法中拋物線根的計算方法:首先要將拋物線化為規(guī)范形式:引入新的變量第十五頁，共十九頁，編輯于2023年，星期四將上述變量代入前面的拋物線方程,得其中的兩個零點為:第十六頁，共十九頁，編輯于2023年，星期四取的兩個零點中靠近的那個零點,則有

Muller方法的迭代公式為:具體計算步驟見教材P39.第十七頁，共十九頁，編輯于2023年，星期四

算法:Muller方法給定初始近似值

x0

，x1

，

x2,求f(x)

=0的根.輸入:

初值

x0，x1，x2;容許誤差

TOL.輸出:

近似解x.Step1Seti=1;Step4If|t4(x2-x1)|<TOLStep2

dosteps3-7

thenOutput(x);

STOP;

Step3

Compute

t3=(x2x1)/(x1x0);Step5Seti++;

d3=1+t3;Step6Setx0=x1,x1=x2,x2=x; a=f(x0)t32-f(x1)t3d3+f(x2)t3;Step7

gotoStep2.b=f(x0)t32-f(x1)d32+f(x2)(t3+d3);

c=f(x2)d3;

t4=-2c/[b+sign(b)sqrt(b2-4ac)];

x=x2+t4(x2-x1);第十八頁，共十九頁，編輯于2023年，星期四Th2.5.2

（局部收斂性）設(shè)，在x*的某鄰域內(nèi)連續(xù)，則存在x*的一個鄰域