《科學(xué)計(jì)算引論》實(shí)驗(yàn)課 第五章 非線性方程數(shù)值解法

1、科學(xué)計(jì)算引論科學(xué)計(jì)算引論實(shí)驗(yàn)實(shí)驗(yàn)第五章第五章 非線性方程數(shù)值解法非線性方程數(shù)值解法本章內(nèi)容簡(jiǎn)介本章內(nèi)容簡(jiǎn)介 5.1 幾何方法幾何方法 5.2 Picard 迭代法迭代法 5.3 Newton 迭代法迭代法F (X) = 0Matlab解方程函數(shù)解方程函數(shù)roots(p)：多項(xiàng)式的多項(xiàng)式的所有零點(diǎn)所有零點(diǎn)，p 是多項(xiàng)式系數(shù)向量是多項(xiàng)式系數(shù)向量fzero(f,x0)：求求 f(x)=0 在在 x0 附近的一個(gè)根，附近的一個(gè)根，f 是函是函數(shù)句柄，可以通過(guò)內(nèi)聯(lián)函數(shù)，匿名函數(shù)或函數(shù)文件來(lái)定義，數(shù)句柄，可以通過(guò)內(nèi)聯(lián)函數(shù)，匿名函數(shù)或函數(shù)文件來(lái)定義，但不能是方程或符號(hào)表達(dá)式！但不能是方程或符號(hào)表達(dá)式！sol

2、ve(f,v)：求方程關(guān)于指定自變量的解，求方程關(guān)于指定自變量的解，f 是是符號(hào)表達(dá)符號(hào)表達(dá)式式或或符號(hào)方程符號(hào)方程；l solve 也可解方程組也可解方程組 (包含非線性包含非線性)l 得不到解析解時(shí)，給出數(shù)值解得不到解析解時(shí)，給出數(shù)值解linsolve(A,b)：解線性方程組解線性方程組二分法二分法q 二分法的計(jì)算流程：二分法的計(jì)算流程：二分法二分法q 二分法的計(jì)算流程：二分法的計(jì)算流程：算法算法5.1 二分法二分法二分法示例二分法示例解解：弦截法、弦截法、Steffensen 方法方法q 弦截法：弦截法：111()()(, 1,2,.)kkkkkkkxxxxf xkf xf x 當(dāng)當(dāng) 時(shí)

3、，時(shí)，*kxx1()0kkkxxf x 需兩個(gè)初始啟動(dòng)值需兩個(gè)初始啟動(dòng)值q Steffensen方法：方法：改造弦截法得改造弦截法得Steffensen方法方法：21(), 1,2,.()()kkkkkkfxxxkf xf xf x Picard 迭代法迭代法q Picard迭代法迭代法基本思想基本思想l 構(gòu)造構(gòu)造 F (X) = 0 的一個(gè)等價(jià)方程組：的一個(gè)等價(jià)方程組： ()XX 得到一個(gè)迭代序列：得到一個(gè)迭代序列： X0，X1，X2，. . . 其中：其中：l 任取一個(gè)迭代初始值任取一個(gè)迭代初始值 X0 ，計(jì)算，計(jì)算 1()kkXX k = 0, 1, 2, . ( )( )( )12(,

4、)kkkTknXxxx 問(wèn)題非線性方程非線性方程F (X) = 01212(,) , ()(),(),()TTnnnXxxxF XfXfXfXnXDl 迭代終止準(zhǔn)則：迭代終止準(zhǔn)則： （預(yù)設(shè)精度）（預(yù)設(shè)精度）1kkXX 誤差估計(jì)誤差估計(jì)定理定理5.1：設(shè)：設(shè) 于閉凸集于閉凸集 上連續(xù)上連續(xù)可可微微（G-可微），且滿(mǎn)足可微），且滿(mǎn)足這里這里 是從屬于是從屬于 中某向量范數(shù)中某向量范數(shù) 的矩陣范數(shù)，的矩陣范數(shù)， 則方程組則方程組 有有唯一不動(dòng)點(diǎn)唯一不動(dòng)點(diǎn) ，迭代格式，迭代格式 自任意迭代初值自任意迭代初值 出發(fā)出發(fā)收斂收斂于該不動(dòng)點(diǎn)，且有于該不動(dòng)點(diǎn)，且有先驗(yàn)誤差估計(jì)先驗(yàn)誤差估計(jì)及及后驗(yàn)誤差估計(jì)后驗(yàn)誤

5、差估計(jì)000():sup()1, ,XDDDqX :nnDRR 0DD *101,2 ,1kkqXXXXqk *11,2, ,1kkkqXXXXqk nR()XX 00XD 1()kkXX *0XD 注：注： q (局部考察局部考察q*)越小，迭代收斂越快。越小，迭代收斂越快。加速迭代法加速迭代法Aitken 加速迭代公式加速迭代公式1()kkxx 11(),kkxx 2111111(),2kkkkkkkxxxxxxx q 方程組的加速迭代公式：方程組的加速迭代公式：11() ()kkkXIPXPX k = 0, 1, 2, . . q 標(biāo)量方程的加速迭代公式：標(biāo)量方程的加速迭代公式：Newt

6、on迭代法迭代法f (x) = 0111(), 1,2,.()kkkkf xxxkfx q Newton迭代法：迭代法：l 迭代終止準(zhǔn)則：迭代終止準(zhǔn)則： （預(yù)設(shè)精度）（預(yù)設(shè)精度） kkXX1| 或或 （預(yù)設(shè)精度）（預(yù)設(shè)精度） kF X|()| 11()(), 0,1,2,kkkkXXFXF Xk q 非線性方程組的非線性方程組的Newton迭代法迭代法：F (X) = 0簡(jiǎn)化簡(jiǎn)化Newton法法 & Newton下山法下山法q 簡(jiǎn)化的簡(jiǎn)化的Newton迭代法迭代法q Newton下山法下山法101(), 0,2)1, ,(kkkXXFFXXk l基本思想：減少導(dǎo)數(shù)的計(jì)算基本思想：減少導(dǎo)

7、數(shù)的計(jì)算 11()(),0,1,2,.kkkkXXFXF Xk l 下山因子的取法：下山因子的取法： 從從 =1 開(kāi)始，逐次減半，直到滿(mǎn)足下山條件開(kāi)始，逐次減半，直到滿(mǎn)足下山條件l 基本思想：要求每一步迭代滿(mǎn)足基本思想：要求每一步迭代滿(mǎn)足下山條件下山條件 1kkF XF X :01 l 具體做法：加具體做法：加下山因子下山因子保證全局收斂保證全局收斂簡(jiǎn)化簡(jiǎn)化Newton法法 & Newton下山法下山法q 簡(jiǎn)化的簡(jiǎn)化的Newton迭代法迭代法q Newton下山法下山法101(), 0,2)1, ,(kkkXXFFXXk l基本思想：減少導(dǎo)數(shù)的計(jì)算基本思想：減少導(dǎo)數(shù)的計(jì)算 11()()

8、,0,1,2,.kkkkXXFXF Xk l 下山因子的取法：下山因子的取法： 從從 =1 開(kāi)始，逐次減半，直到滿(mǎn)足下山條件開(kāi)始，逐次減半，直到滿(mǎn)足下山條件l 基本思想：要求每一步迭代滿(mǎn)足基本思想：要求每一步迭代滿(mǎn)足下山條件下山條件 1kkF XF X :01 l 具體做法：加具體做法：加下山因子下山因子保證全局收斂保證全局收斂Jacobi矩陣的計(jì)算矩陣的計(jì)算q 計(jì)算計(jì)算Jacobi矩陣矩陣的函數(shù)的函數(shù)% 求函數(shù)求函數(shù)fun在在x處的處的Jacobi矩陣矩陣function J=Jacobi(fun,x)m=length(x); % 確定變量的維度確定變量的維度n=length(fun(x);

9、 % 確定函數(shù)的維度確定函數(shù)的維度J=zeros(m,n); % 初始化初始化Jacobi矩陣矩陣epsnew=1.d-12; % 小增量小增量I=eye(m,n); % 保存單位向量的矩陣保存單位向量的矩陣for k=1:n % 依次計(jì)算依次計(jì)算Jacobi矩陣的第矩陣的第k列列 J(:,k)=(fun(x+epsnew*I(:,k)-fun(x)/epsnew;end例：例： f=(x) sin(x(1);cos(x(2); J=jacobi(f,0;0)標(biāo)量方程的標(biāo)量方程的Newton迭代算法迭代算法% fun和和dfun以字符串的形式輸入即可以字符串的形式輸入即可function xv

10、ect,xdif,fx,nit=newton(x0,nmax,tol,fun,dfun)err=tol+1; nit=0; xvect=x0; x=x0; fx=eval(fun); xdif=;while (nit tol), nit=nit+1; x=xvect(nit); dfx=eval(dfun); if (dfx = 0), nit=nmax; disp(Stop for vanishing dfun); else, xn=x-fx(nit)/dfx; err=abs(xn-x); xdif=xdif; err; x=xn; xvect=xvect;x; fx=fx;eval(fun); end;end;例：例： xvect,xdif,fx,ni