ch07b非線(xiàn)性方程組的數(shù)值解法newton法弦截法拋物線(xiàn)法

1、1第七章非線(xiàn)性方程(組)的數(shù)值解法數(shù)值分析 Newton 法法 弦截法、拋物線(xiàn)法弦截法、拋物線(xiàn)法2Newton 法法q 基本思想基本思想將非線(xiàn)性方程將非線(xiàn)性方程線(xiàn)性化線(xiàn)性化2( )( )()()()()2!kkkkff xf xfxxxxx l 設(shè)設(shè) xk 是是 f (x)=0 的近似根，將的近似根，將 f(x) 在在 xk 處處 Taylor 展開(kāi)展開(kāi)令：令：( )0P x 1()()kkkkf xxxfx ( )P x()()()kkkf xfxxx 條件：條件： f(x) 03Newton 法法xyx*xkxk+14Newton 法法算法算法 ：( Newton 法法 )(1) 任取迭代

2、初始值任取迭代初始值 x0(2) 對(duì)對(duì) k = 1, 2, . , maxit，計(jì)算，計(jì)算判斷收斂性，若收斂，則停止計(jì)算，輸出近似解判斷收斂性，若收斂，則停止計(jì)算，輸出近似解1()()kkkkf xxxfx 5收斂性收斂性1()()kkkkf xxxfx k = 0, 1, 2, . . . l 迭代函數(shù)迭代函數(shù)( )( )( )f xxxfx ( *)( *)0,( *)2( *)fxxxfx牛頓法至少二階牛頓法至少二階局部收斂局部收斂12*( *)( *)lim(*)2!2( *)kkkxxxfxxxfx 6舉例舉例例：例：用用 Newton 法求法求 f(x) = x2 C=0 的正根的

3、正根112kkkCxxx 解：解： 2112kkkxCxCx 2112kkkxCxCx 211kkkkxCxCxCxC 2200kkkkxCxCqxCxC 2221kkkqxCCq 對(duì)任意對(duì)任意 x00，總有總有 |q|1，即牛頓法收斂即牛頓法收斂7牛頓牛頓法法q 牛頓牛頓的的優(yōu)點(diǎn)優(yōu)點(diǎn)牛頓牛頓法是目前求解非線(xiàn)性方程法是目前求解非線(xiàn)性方程 (組組) 的主要方法的主要方法至少二階局部收斂，收斂速度較快，特別是當(dāng)?shù)c(diǎn)至少二階局部收斂，收斂速度較快，特別是當(dāng)?shù)c(diǎn)充分靠近精確解時(shí)。充分靠近精確解時(shí)。q 牛頓牛頓的缺點(diǎn)的缺點(diǎn)l 對(duì)重根收斂速度較慢（線(xiàn)性收斂）對(duì)重根收斂速度較慢（線(xiàn)性收斂）l 對(duì)初值的選

4、取很敏感，要求初值相當(dāng)接近真解對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解先用其它算法獲取一個(gè)近似解，然后使用牛頓法先用其它算法獲取一個(gè)近似解，然后使用牛頓法l 需要求導(dǎo)數(shù)！需要求導(dǎo)數(shù)！8簡(jiǎn)化的簡(jiǎn)化的Newton法法10()()kkkfxf xxx 線(xiàn)性收斂線(xiàn)性收斂簡(jiǎn)化的簡(jiǎn)化的 Newton 法法l 基本思想：基本思想：用用 f(x0) 替代所有的替代所有的 f(xk)9Newton下山法下山法1()()kkkkf xxxfx l 下山因子的取法：下山因子的取法： 從從 =1 開(kāi)始，逐次減半，直到滿(mǎn)足下降條件開(kāi)始，逐次減半，直到滿(mǎn)足下降條件l 基本思想：基本思想：要求每一步迭代滿(mǎn)足下降條件要求每一

5、步迭代滿(mǎn)足下降條件 1kkfxfx l 具體做法：具體做法：加加下山因子下山因子 Newton下山法下山法保證全局收斂保證全局收斂10重根情形重根情形( )(*)( )mf xxxg x ( *)0g x 且且l 解法一解法一：直接使用：直接使用 Newton 法法( )( )( )f xxxfx 1( *)1xm 線(xiàn)性收斂線(xiàn)性收斂l 解法二解法二：改進(jìn)的：改進(jìn)的 Newton 法法( )( )( )f xxxmfx ( *)0 x 二階收斂二階收斂缺點(diǎn)：缺點(diǎn)：需要知道需要知道 m 的值的值重根情形重根情形11重根情形重根情形( )( )( )f xxfx 令令x* 是是 (x)=0 的的單重

6、根單重根l 解法三解法三：用：用 Newton 法解法解 (x) = 02( )( ) ( )( )( ) ( )( ) ( )xf x fxxxxxfxf x fx 12() () ()() ()kkkkkkkf xfxxxfxf xfx 迭代格式：迭代格式：12舉例舉例例：例：求求 x4 - 4x2 4=0 的二重根的二重根 *2x 212( )4xxxx (1) 普通普通 Newton 法法(2) 改進(jìn)的改進(jìn)的 Newton 法法(3) 用用 Newton 法解法解 (x) = 0222( )2xxxx 232(2)( )2x xxxx 13弦截法與拋物線(xiàn)法弦截法與拋物線(xiàn)法弦截法與拋物線(xiàn)

7、法弦截法與拋物線(xiàn)法l 目的目的：避免計(jì)算：避免計(jì)算 Newton 法中的導(dǎo)數(shù)，且具有較法中的導(dǎo)數(shù)，且具有較高的收斂性（超線(xiàn)性收斂）高的收斂性（超線(xiàn)性收斂）l 弦截法（割線(xiàn)法）：弦截法（割線(xiàn)法）：用差商代替微商用差商代替微商l 拋物線(xiàn)法：拋物線(xiàn)法：用二次多項(xiàng)式近似用二次多項(xiàng)式近似 f(x)14弦截法弦截法l 弦截法迭代格式：弦截法迭代格式：111()()(),kkkkkkkf xf xfxf xxxx 111()()()kkkkkkkxxxxf xf xf x k = 1, 2, 3, . . .l 注：弦截法需要提供注：弦截法需要提供兩個(gè)迭代初始值兩個(gè)迭代初始值15收斂性收斂性定理：定理：設(shè)設(shè)

8、 x* 是是 f(x) 的零點(diǎn)的零點(diǎn)， f(x) 在在 x* 的某鄰域的某鄰域 U(x, ) 內(nèi)有二階連續(xù)導(dǎo)數(shù)，且內(nèi)有二階連續(xù)導(dǎo)數(shù)，且 f(x) 0，若初值，若初值 x0，x1 U(x, )，則當(dāng)則當(dāng) U(x, ) 充分小時(shí)，弦截法具有充分小時(shí)，弦截法具有 p 階收斂性，其中階收斂性，其中152p 2(10)pp16弦截法幾何含義弦截法幾何含義xyx*xk-1xkxk+117拋物線(xiàn)法拋物線(xiàn)法l 基本思想：基本思想： 用二次曲線(xiàn)與用二次曲線(xiàn)與 x 軸的交點(diǎn)作為軸的交點(diǎn)作為 x* 的近似值的近似值 拋物線(xiàn)法拋物線(xiàn)法18拋物線(xiàn)法拋物線(xiàn)法21( )(),()kkkkpxf xf xxxx 121,()()kkkkkf xxxxxxx12122 ()4 () ,kkkkkkkf xxxf xf xxx 1121,()kkkkk