牛頓法拋物線法課件

第七章

非線性方程(組)的數(shù)值解法計(jì)算方法——Newton法——弦截法、拋物線法1第七章

非線性方程(組)的數(shù)值解法計(jì)算方法——Newton本講內(nèi)容

Newton法及其收斂性牛頓下山法弦截法與拋物線法2本講內(nèi)容Newton法及其收斂性2Newton法基本思想將非線性方程線性化設(shè)xk

是f(x)=0的近似根，將f(x)在xk

處Taylor展開(kāi)令：條件：

f’(x)03Newton法基本思想將非線性方程線性化設(shè)xk是Newton法xyx*xkxk+14Newton法xyx*xkxk+14Newton法算法：(Newton法)(1)任取迭代初始值

x0(2)對(duì)k=1,2,...,maxit，計(jì)算判斷收斂性，若收斂，則停止計(jì)算，輸出近似解5Newton法算法：(Newton法)(1)任取收斂性k=0,1,2,...迭代函數(shù)牛頓法至少二階局部收斂6收斂性k=0,1,2,...迭代函數(shù)牛頓舉例例：用Newton法求f(x)=xex

–1=0

的解ex75.m7舉例例：用Newton法求f(x)=xex–1舉例例：用Newton法求f(x)=x2

–C=0

的正根解：對(duì)任意x0>0，總有|q|<1，即牛頓法收斂8舉例例：用Newton法求f(x)=x2–C=牛頓法

牛頓的優(yōu)點(diǎn)牛頓法是目前求解非線性方程(組)的主要方法至少二階局部收斂，收斂速度較快，特別是當(dāng)?shù)c(diǎn)充分靠近精確解時(shí)。

牛頓的缺點(diǎn)

對(duì)重根收斂速度較慢（線性收斂）

對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解先用其它算法獲取一個(gè)近似解，然后使用牛頓法

需要求導(dǎo)數(shù)！9牛頓法牛頓的優(yōu)點(diǎn)牛頓法是目前求解非線性方程(組)的主要簡(jiǎn)化的Newton法線性收斂簡(jiǎn)化的Newton法

基本思想：用f’(x0)

替代所有的f’(xk)10簡(jiǎn)化的Newton法線性收斂簡(jiǎn)化的Newton法基本思Newton下山法下山因子的取法：

從=1開(kāi)始，逐次減半，直到滿足下降條件基本思想：要求每一步迭代滿足下降條件具體做法：加下山因子

Newton下山法保證全局收斂11Newton下山法下山因子的取法：

從=1開(kāi)重根情形且

解法一：直接使用Newton法線性收斂

解法二：改進(jìn)的Newton法二階收斂缺點(diǎn)：需要知道m(xù)

的值重根情形12重根情形且解法一：直接使用Newton法線性收斂解法重根情形令x*是(x)=0的單重根

解法三：用Newton法解(x)=0迭代格式：13重根情形令x*是(x)=0的單重根解法三：用N舉例例：求x4-4x2＋

4=0

的二重根(1)普通Newton法ex76.m(2)改進(jìn)的Newton法(3)用Newton法解(x)=014舉例例：求x4-4x2＋4=0的二重根(1)弦截法與拋物線法弦截法與拋物線法

目的：避免計(jì)算Newton法中的導(dǎo)數(shù)，且具有較高的收斂性（超線性收斂）

弦截法（割線法）：用差商代替微商拋物線法：用二次多項(xiàng)式近似f(x)15弦截法與拋物線法弦截法與拋物線法目的：避免計(jì)算Newto弦截法弦截法迭代格式：k=1,2,3,...注：弦截法需要提供兩個(gè)迭代初始值16弦截法弦截法迭代格式：k=1,2,3,...收斂性定理：設(shè)x*是f(x)

的零點(diǎn)，

f(x)在x*

的某鄰域U(x,)

內(nèi)有二階連續(xù)導(dǎo)數(shù)，且f’(x)0，若初值x0，x1U(x,)，則當(dāng)U(x,)充分小時(shí)，弦截法具有p

階收斂性，其中17收斂性定理：設(shè)x*是f(x)的零點(diǎn)，f(x)在弦截法幾何含義xyx*xk-1xkxk+118弦截法幾何含義xyx*xk-1xkxk+118拋物線法基本思想：

用二次曲線與x

軸的交點(diǎn)作為x*的近似值

拋物線法19拋物線法基本思想：

用二次曲線與x軸的交點(diǎn)作為拋物線法yxk-2xk-1xkxk+120拋物線法yxk-2xk-1xkxk+120拋物線法計(jì)算過(guò)程二次曲線方程(三點(diǎn)Newton插值多項(xiàng)式)

問(wèn)題：p2(x)與x

軸有兩個(gè)交點(diǎn)，取哪個(gè)點(diǎn)？解決方法：取靠近xk的那個(gè)點(diǎn)!21拋物線法計(jì)算過(guò)程二次曲線方程(三點(diǎn)Newton插值拋物線法取靠近xk的那個(gè)點(diǎn)22拋物線法取靠近xk的那