《非線性方程的數(shù)值解法》由會(huì)員分享，可在線閱讀，更多相關(guān)《非線性方程的數(shù)值解法（19頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、 4 牛 頓 法一 、 牛 頓 迭 代 公 式 的 推 導(dǎo) (Taylor展 開(kāi) 法 )思 想 ： 非 線 性 方 程 線 性 化 （ 以 直 代 曲 ）取 x0 x*， 將 f (x)在 x0 做 一 階 Taylor展 開(kāi) : 20000 )(!2 )()()()( xxfxxxfxfxf ， 在 x0 和 x 之 間將 (x* x0)2 看 成 高 階 小 量 ， 則 有 ：0 0 0( ) ( ) ( )( )f x f x f x x x 00 0( )* ( )f xx x f x 0 0 0( ) ( )( ) 0f x f x x x 1: x令 1 0 1 2( ) , ,
2、,( )kk k kf xx x kf x 注 ： 牛 頓 法 是 一 種 特 殊 的 迭 代 法 。Newton Raphson迭 代 格 式稱(chēng) 之 為 牛 頓 拉 夫 森 方 法 ， 簡(jiǎn) 稱(chēng) 牛 頓 法 .xy x* x 0 0 0 0( ) ( )( )y f x f x x x 與 x軸 交 點(diǎn) 的 橫 坐 標(biāo)1x2x 0 0 0( ) ( )( ) 0f x f x x x 無(wú) 開(kāi) 方 運(yùn) 算 ， 又 無(wú) 除 法 運(yùn) 算 。例 1： 寫(xiě) 出 求 的 Newton迭 代 格 式 ； 寫(xiě) 出 求 的 Newton迭 代 格 式 ,要 求 公 式 中 既0( )a a1 0( )aa 解
3、： 等 價(jià) 于 求 方 程 的 正 根2 0 0( ) ( )f x x a a 1 ( )( )kk k kf xx x f x 解 法 一 ： 等 價(jià) 于 求 方 程 的 正 根21 0 0( ) ( ) ( )f x x aa 12( ) ( )f x x a 21 112( )( )( ) ( )kkk k kk kxf x ax x xf x x a 1 1 0 1 22( ) , , ,kx ka 2 1 0 1 22 2( ) , , ,kk kk kx a ax x kx x 32( )f x x 解 法 二 ： 等 價(jià) 于 求 方 程 的 正 根21 0 0( ) ( )f
4、x a ax 21 312( )( )k kk k kk kaf x xx x xf x x 21 3 0 1 22 ( ) , , ,k kx ax k Th2.7 （ 局 部 收 斂 性 ） 設(shè) x* 為 方 程 f (x) =0的 根 ， 在 包 含 x*的 某 個(gè) 開(kāi) 區(qū) 間 內(nèi) 連 續(xù) ， 且 ， 則 存 在 x* 的 鄰 域 ，使 得 任 取 初 值 ， 由 Newtons Method產(chǎn) 生 的 序 列 以 不 低 于 二 階 的 收 斂 速 度 收 斂 于 x*， 且 ( *) , B x x x *)(0 xBx ( )f x0( )f x kx1 2 2* ( *)lim
5、( * ) ( *)kk kx x f xx x f x 2 21 ( ) ( ) ( )( ) ( )f x f x f xg x f x 證 明 ： Newtons Method 事 實(shí) 上 是 一 種 特 殊 的 不 動(dòng) 點(diǎn) 迭 代 其 中 ， 則)( )()( xf xfxxg f x f xg x f x2( *) ( *)( *) 0( *) 收 斂由 Taylor 展 開(kāi) ： 2)*(!2 )()*)()(*)(0 kkkkk xxfxxxfxfxf 1 2 2 2( )( *)* ( ) ( )=( * ) ( * ) ( )kkk k kk k kf xx xx x f x
6、fx x x x f x 只 要 ， 則 令 可 得 結(jié) 論 。 k0( )f x Th2.51 2 2* ( *)lim ( * ) ( *)kk kx x f xx x f x 有 根 根 唯 一 產(chǎn) 生 的 序 列 單 調(diào) 有界 保 證 收 斂證 明 省 略 。Th2.8 （ 收 斂 的 充 分 條 件 ） 設(shè) f (x) =0 且 f C2a, b， 若(1) f (a) f (b) 0； (2) 在 整 個(gè) a, b上 不 變 號(hào) 且 ；(3) 選 取 x0 a, b 使 得 ；則 Newtons Method產(chǎn) 生 的 序 列 xk 收 斂 于 方 程 的 根 .f 0( )f x
7、 0 0 0( ) ( )f x f x xTh2.9 （ 收 斂 的 另 一 充 分 條 件 ） 設(shè) 在 a, b上 連 續(xù) ， (1) f (a) f (b) 0； (2) 在 整 個(gè) a, b上 且 ；(3) ，則 對(duì) ， Newtons Method產(chǎn) 生 的 序 列 xk 收 斂 于 方程 在 a, b內(nèi) 的 唯 一 實(shí) 根 。 ( )f x 0( )f x x 且0( )f x ( )( )f a b af a ( )( )f b b af b 0 , x a b 0( )f x 證 明 省 略 。 Newtons Method 收 斂 性 依 賴(lài) 于 x0 的 選 取 。x*x0
8、 x0 x0 改 進(jìn) 與 推 廣 （ 補(bǔ) 充 ） 重 根 加 速 收 斂 法 ：Q1: 若 ， Newtons Method 是 否 仍 收 斂 ？0*)( xf設(shè) x* 是 f 的 n 重 根 ， 則 ： 且 。( ) ( ) ( )nf x x x q x ( ) 0q x 因 為 Newtons Method 事 實(shí) 上 是 一 種 特 殊 的 不 動(dòng) 點(diǎn) 迭 代 ,其中 ， 則)( )()( xf xfxxg 2 2( *) ( *) ( *)| ( *) | 1 ( *)f x f x f xg x f x 111 nA1: 有 局 部 收 斂 性 ， 但 重 數(shù) n 越 高 ， 收
9、 斂 越 慢 。Q2: 如 何 加 速 重 根 情 況 時(shí) 的 收 斂 速 度 ？A2: 將 求 f 的 重 根 轉(zhuǎn) 化 為 求 另 一 函 數(shù) 的 單 根 。令 ， 則 f 的 重 根 = 的 單 根 。)( )()( xf xfx 求 復(fù) 根 Newton 公 式 中 的 自 變 量 可 以 是 復(fù) 數(shù)記 z = x + i y, z0 為 初 值 ， 同 樣 有 )( )(1 kkkk zf zfzz kkkkkk DiCzfBiAzf )(,)(設(shè) 代 入 公 式 ， 令 實(shí) 、 虛 部 對(duì) 應(yīng) 相 等 ， 可 得; 221 kk kkkkkk DC DBCAxx .221 kk kk
10、kkkk DC CBDAyy 5 弦 割 法 與 拋 物 線 法 x 0 x1割 線 切 線 斜 率 割 線 斜 率 11( ) ( )( ) k kk k kf x f xf x x x 11 1( )( )( ) ( )k k kk k k kf x x xx x f x f x 需 要 2個(gè) 初 值 x0 和 x1。 Newtons Method每 一 步 要 計(jì) 算 ， 為 了 避 免 計(jì) 算 導(dǎo) 數(shù) 值 ，現(xiàn) 用 的 近 似 ， 得 到 弦 割 法 （ 割 線 法 ） 。ff x 2 一 、 弦 割 法 Th2.10 局 部 收 斂 性 設(shè) 表 示 區(qū) 間 ， x*為 方 程 f (
11、x) =0的 根 ， 函 數(shù) f (x)在 中 有 足 夠 階 連 續(xù) 導(dǎo) 數(shù) ， 且 滿 足 , x x I 0 I則 對(duì) ， 由 割 線 法 產(chǎn) 生 的 序 列 都 收 斂 于 x*， 且(i) (ii) (iii) 0( ) ;f x x I 2 ( ) , ;( )f M If 1d M 0 1,x x I kx其 中 1 1lim k qqk ke Ke 2 *( ) ,( )f xK f x 1 1 5 1 6182( ) . .q 收 斂 速 度 介 于 Newton and Bisection 之 間 Corollary(推 論 ) 設(shè) x* 為 方 程 f (x) =0的 一
12、 個(gè) 根 ， ， 且 在 x* 的 附 近 連 續(xù) ， 則 使 得 由Secant Method產(chǎn) 生 的 序 列 都 收 斂 于 x*。 0 1, , x x x x ( )f x 0( )f x kx 0, xk-2Muller方 法 的 思 想 來(lái) 源 于 弦 割 法 :利 用 3個(gè) 已 知 點(diǎn) 構(gòu) 造 一 條 拋 物線 ,取 其 與 x軸 的 交 點(diǎn) 構(gòu) 造 下 一 次 迭 代 值 .x*二 、 拋 物 線 法 (Muller)幾 何 圖 示 xkxk-1 xk+1 ( )f x2( )p x Muller方 法 的 具 體 實(shí) 現(xiàn) :設(shè) 已 知 三 個(gè) 點(diǎn) 2 2( , ( ),k
13、kx f x 1 1( , ( ),k kx f x ( , ( ).k kx f x則 過(guò) 上 述 三 個(gè) 點(diǎn) 的 拋 物 線 方 程 為 :1 22 2 12 1 2 1 2 1( )( ) ( )( )( ) ( ) ( )( )( ) ( )( )k k k kk kk k k k k k k kx x x x x x x xp x f x f xx x x x x x x x 2 12 1( )( ) ( )( )( )k k kk k k kx x x x f xx x x x 取 該 拋 物 線 與 x軸 的 交 點(diǎn) 作 為 下 一 次 迭 代 值 ,即 2 1 0( )kp x
14、 然 后 取 新 的 相 鄰 的 三 次 迭 代 值 重 復(fù) 上 述 過(guò) 程 ,即 為 Muller方 法 . Muller方 法 中 拋 物 線 根 的 計(jì) 算 方 法 :首 先 要 將 拋 物 線 化 為 規(guī) 范 形 式 : 22( )p x ax bx c 引 入 新 的 變 量 1 13 1 2 23 3 1 21 kk kk kk k k kk k x xx xx xx x x xx x 22 31( )q a b c 其 中 22 3 1 3 3 32 22 3 1 3 3 33( ) ( ) ( ) ,( ) ( ) ( )( ),( ) .k k kk k kka f x f
15、x f xb f x f x f xc f x 2( )q 的 兩 個(gè) 零 點(diǎn) 為 : 21 2 24 22 4, b b ac ca b b ac 2( )p x 可 以 寫(xiě) 為 ： 2( )p 取 的 兩 個(gè) 零 點(diǎn) 中 靠 近 的 那 個(gè) 零 點(diǎn) ,則 有kx4 22 4( )cb sign b b ac 1 4 1k k k kx x x x Muller方 法 的 迭 代 公 式 為 :具 體 計(jì) 算 步 驟 見(jiàn) 教 材 P39. 算 法 : Muller方 法給 定 初 始 近 似 值 x0 ， x1 ， x2 ,求 f(x) =0 的 根 .輸 入 : 初 值 x0 ， x1，
16、x2; 容 許 誤 差 TOL.輸 出 : 近 似 解 x.Step 1 Set i = 1; Step 4 If |t4(x2-x1) | TOLStep 2 do steps 3-7 then Output (x); STOP; Step 3 Compute t 3= (x2 x1)/ (x1 x0); Step 5 Set i +; d3= 1+t3; Step 6 Set x0 = x1 , x1=x2 , x2=x; a=f(x0)t32-f(x1)t3d3+f(x2)t3; Step 7 goto Step 2. b=f(x0)t32-f(x1)d32+f(x2)(t3+d3);
17、c=f(x2)d3 ; t4=-2c/b+sign(b)sqrt(b2-4ac); x= x2+t4(x2-x1); Th2.5.2 （ 局 部 收 斂 性 ） 設(shè) ， 在 x*的 某 鄰 域 內(nèi) 連 續(xù) ， 則 存在 x* 的 一 個(gè) 鄰 域 ， 當(dāng) 時(shí) ,由 拋 物 線 法 產(chǎn) 生 的 序 列 收 斂 于 x*， 且( *) , N x x x 0 1 2, , ( *)x x x N x( )f x0 0( ) , ( )f x f x kx 1 2 1 6 ( )/( )lim ( ) pk pk kx x f xf xx x 其 中 ,是 方 程 的 根 .1 839.p 3 2 1 0( ) Muller法 的 優(yōu) 點(diǎn) ： 初 值 的 選 取 范 圍 比 Newton法 和 弦 割 法 寬 ,但 計(jì) 算 量 比 弦 割 法 大 。 進(jìn) 一 步 研 究 可 知 Muller法 可 求 復(fù) 根 。
非線性方程的數(shù)值解法
