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

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

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

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

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

5、差估計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簡化簡化Newton法法 & Newton下山法下山法q 簡化的簡化的Newton迭代法迭代法q Newton下山法下山法101(), 0,2)1, ,(kkkXXFFXXk l基本思想：減少導(dǎo)數(shù)的計算基本思想：減少導(dǎo)

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

8、,0,1,2,.kkkkXXFXF Xk l 下山因子的取法：下山因子的取法： 從從 =1 開始，逐次減半，直到滿足下山條件開始，逐次減半，直到滿足下山條件l 基本思想：要求每一步迭代滿足基本思想：要求每一步迭代滿足下山條件下山條件 1kkF XF X :01 l 具體做法：加具體做法：加下山因子下山因子保證全局收斂保證全局收斂Jacobi矩陣的計算矩陣的計算q 計算計算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 % 依次計算依次計算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