计算方法复习新

1、计算方法总复习第一章第一章 误差和有效数字误差和有效数字误差的来源及分类误差的来源及分类绝对误差、相对误差、有效数字的定义绝对误差、相对误差、有效数字的定义误差同有效数字的关系误差同有效数字的关系数值计算中应注意的几个问题数值计算中应注意的几个问题误差的来源及分类误差的来源及分类模型误差模型误差观测误差观测误差截断误差截断误差舍入误差舍入误差绝对误差、相对误差、有效数字的定义绝对误差、相对误差、有效数字的定义绝对误差与绝对误差限绝对误差与绝对误差限相对误差与相对误差限相对误差与相对误差限*xxexxe*0,rrrxeexxxxxee绝对误差、相对误差、有效数字的定义绝对误差、相对误差、有效数字

2、的定义有效数字的定义有效数字的定义nmmnnxxxxxx102110)101010(*2211*kxx1021*误差同有效数字的关系误差同有效数字的关系nmxx1021*)1(1*1021nxxxx)1(1*10) 1(21nrx则则x*至少具有至少具有n位有效数字位有效数字四舍五入得到四舍五入得到如如 3.14= 0.314101 （X * =0.X1X2Xn 10m）n = 3 , m = 1| 3.14| =|3.1415926 - 3.14| =0.0015926. 0.005= 10-2 = 101-3 = 10 m-n数值计算中应注意的几个问题数值计算中应注意的几个问题避免两相近数

3、相减避免两相近数相减防止大数防止大数“吃吃”小数小数除数不能太小除数不能太小算法稳定性算法稳定性简化运算步骤，减少运算次数简化运算步骤，减少运算次数111xxxx .6121112xxxex;xxxx ;1lnlnln xxx类似的：类似的：小结小结：1、什么是舍入误差？什么是截断误差？它们、什么是舍入误差？什么是截断误差？它们的来源是什么？的来源是什么？2、什么是绝对误差、相对误差和有效数字？、什么是绝对误差、相对误差和有效数字？3、绝对误差、相对误差和有效数字之间的关、绝对误差、相对误差和有效数字之间的关系是什么？系是什么？4、 =3.141592654 (1) 若其近似值取若其近似值取5

4、位有效数字，则该近似位有效数字，则该近似值是多少？其绝对、相对误差限是多少？值是多少？其绝对、相对误差限是多少？ （2）若其近似值取）若其近似值取3.1415, 绝对误差限是什绝对误差限是什么？有效数字是什么么？有效数字是什么 （3）若其近似值的绝对误差限为）若其近似值的绝对误差限为0.5 10-5 则该近似值是什么？则该近似值是什么？5、下列近似值有几位有效数字，其相对误、下列近似值有几位有效数字，其相对误差限是什么？差限是什么？,绝对误差限是什么绝对误差限是什么?（1) x1=e= 2.71828=x1* (2) x2=0.030051 x2*=0.0300 (3)x3=e/100 0.0

5、2718=x3*第二章第二章 非线性方程的解法非线性方程的解法对分法对分法迭代法迭代法牛顿迭代法牛顿迭代法对分法对分法条件条件f(x)在在a,b上连续，上连续，f(a)f(b)0，单调单调意义意义对分次数对分次数n的计算的计算12lnln)ln(abn迭代法迭代法)( 1nnxx基本思想）（收敛定理收敛条件1 1)( x 收敛阶阶收敛记P )0(lim1*Ceexxepkkkkk迭代法迭代法一阶收敛 0)( *x二阶收敛 0)( 0)( *xx牛顿迭代法牛顿迭代法条件条件设设f(x)在在a,b上连续，上连续，f(a) f(b)0，且，且x0为为a,b上根上根x*a, b 的一个近似值。的一个近

6、似值。 几何意义几何意义用切线与用切线与x轴的交点近似代替取限于轴的交点近似代替取限于x轴的交轴的交点。点。 xyx*.牛顿迭代法的几何意义牛顿迭代法的几何意义：以以f (x0)为斜率作过为斜率作过(x0 , f (x0)点的直线，即作点的直线，即作f(x)在在点点x0 的切线方程：的切线方程：x0f (x0)()(000 xxxfxfy 令令 y=0, 则得此切线与则得此切线与x轴轴的交点的交点x1, 即即x1)()(0001xfxfxx )()(1kkkkxfxfxx 牛顿迭代法又牛顿迭代法又称切线法称切线法收敛性收敛性 由 (x) 的表达式得：| (x) | = 因为因为 f (x*)

7、= 0 所以所以 (x*) = 0 也即也即 (x)在根的附近收敛很快在根的附近收敛很快（1）局部收敛定理）局部收敛定理(p30) 设设 f (x) 存在，存在， 且且 f (x) 在方程在方程f(x)=0 的根的根x*附近不为零附近不为零 ， = L 1 , 则则Newton迭代格式收敛迭代格式收敛若若| (x) | =)( | )( )(|2xfxfxf)( | )( )(|2xfxfxf(2) 全局收敛定理（全局收敛定理（p31大范围收敛定理）大范围收敛定理） 设设 f( x) 在在 a ,b 上满足上满足 f(a)f(b) 0 则则Newton迭代序列收敛于迭代序列收敛于f(x) =0

8、 在在 a, b的唯一根的唯一根 -.保证有根保证有根-.保证单根保证单根-.保证凸凹性不变保证凸凹性不变-.保证收敛保证收敛牛顿迭代法牛顿迭代法牛顿迭代公式至少二阶收敛牛顿迭代公式至少二阶收敛特点特点在单根附近具有较高的收敛速度。在单根附近具有较高的收敛速度。 公式公式)( )(1kkkkxfxfxx牛顿迭代法牛顿迭代法m重根重根)( )(1kkkkxfxmfxx011)( *mx第三章第三章 线性代数方程组的解法线性代数方程组的解法直接法（快速有效）直接法（快速有效）迭代方法（节省内存）迭代方法（节省内存）向量范数、矩阵范数的定义、性质向量范数、矩阵范数的定义、性质条件数及其对相对误差的影

9、响（三个证条件数及其对相对误差的影响（三个证明）明）直接法直接法Gauss消去法、消去法、Gauss列主元消去法（算列主元消去法（算法描述）法描述）追赶法（三对角严格对角占优）追赶法（三对角严格对角占优）平方根法平方根法Gauss消去法消去法消元过程消元过程), 1( ), 1,( ) 1, 2 , 1( )()()1()()()1()()(nkibmbbnkjiamaankaamkkikkikikkjikkijkijkkkkikik回代过程回代过程) 1 , 1( )()(1)()()()(nkaxabxabxkkknkjjkkjkkknnnnnn二、算法描述二、算法描述1、消元 对k=1.

10、n-1 消元因子： C= aik(k)/ akk(k) ( i= k+1.n ） 系数变化： aij(k+1) = aij(k) （i k) aij(k+1) = aij(k) - C. akj(k) ( i k , j=k+1,n+1 )2、回代第 i次回代公式 （ i=n,n-1.1)Xi(即a in+1(i)=(a in+1(i) - ）/aii(i) Gauss列主元消去法列主元消去法关键步骤关键步骤第第k次消元时，在系数矩阵次消元时，在系数矩阵A的第的第k列列元素中选取绝对值最大的元素为主元元素中选取绝对值最大的元素为主元素。素。追赶法（条件）追赶法（条件）解对称正定的平方根法定理2

11、：若 n阶方阵A对称正定，则存在唯一的对角元素为正的下三角阵L，使A=LLT (Cholesky分解） 即:(i=2,.n, j=1,.i-1) (p54 3-25)-按行计算公式按行计算公式按列计算公式：按列计算公式：对j=1,2,ni=j+1,j+2,.n迭代方法迭代方法Jacobi迭代法迭代法 A=D-L-UGauss-Seidel迭代法迭代法公式及收敛条件（充分条件、充要条件）公式及收敛条件（充分条件、充要条件）Jacobi迭代法迭代法分量形式分量形式矩阵形式矩阵形式), 2 , 1 , 0 ;, 2 , 1( 1)()1(knidxCxnijjikjijkifCXXkk)()1()(

12、1ULDCbDf1记记 ，Jacobi迭代法迭代法Jacobi迭代收敛条件迭代收敛条件充分条件充分条件(1) :迭代矩阵至少存在一种矩阵范数迭代矩阵至少存在一种矩阵范数|.|,使使 | C | 1充分条件充分条件(2) : 方程组方程组 AX=b的系数矩阵的系数矩阵A为为 严格对角占优阵严格对角占优阵充要条件：迭代矩阵的谱半径充要条件：迭代矩阵的谱半径(C) 1Gauss-Seidel迭代法迭代法分量形式分量形式矩阵形式矩阵形式记记 ，), 2 , 1 , 0 ;, 2 , 1( 11)()1()1(knidxCxCxijinijkjijkjijkifGXXkk)()1(ULDG1)(bLDf

13、1)(1231231231027.21028.354.2xxxxxxxxx迭代公式为迭代公式为：Gauss-Seidel迭代迭代充分条件：充分条件：迭代矩阵迭代矩阵G的的|G|1A对称正定对称正定A严格对角占优严格对角占优充要条件：充要条件：(G)=3.706 取取n=4即能达到这个精度即能达到这个精度52102112ne52106en85.212n213n相应的复化梯形公式为相应的复化梯形公式为: 2121213)1()(2)0(4261kkfxffT2131nabhRomberg求积公式求积公式nnnTTS1411442nnnSSC1411442222nnnCCR1411443233Gau

14、ss型求积公式型求积公式Gauss型求积公式的定义，判断型求积公式的定义，判断 具有具有2n+12n+1次代数精度的插值型次代数精度的插值型求积公式求积公式数值微分数值微分两点公式及其截断误差两点公式及其截断误差三点公式及其截断误差三点公式及其截断误差两点公式两点公式hyyxfxf0110)()(截断误差截断误差)(2)()(2)()!1()()( 11 0)1(01fhxRfhxnfxRn三点公式三点公式hyyyxLxfhyyxLxfhyyyxLxf434)()(2)()(243)()(21022221121210020三点公式三点公式截断误差截断误差)( 3)()( )()( 6)()(

15、)()( 3)()( )(222222212112202002fhxLxfxRfhxLxfxRfhxLxfxR第六章第六章 常微分方程初值问题的数值解法常微分方程初值问题的数值解法欧拉法欧拉法欧拉法、改进欧拉法、预报欧拉法、改进欧拉法、预报-校正公式校正公式截断误差截断误差精度精度显式（隐式）、单步（多步）显式（隐式）、单步（多步）绝对稳定区间的求法绝对稳定区间的求法龙格龙格-库塔方法库塔方法思想、精度思想、精度显式（隐式）、单步（多步）显式（隐式）、单步（多步）欧拉法欧拉法, 2 , 1 , 0 ),(1iyxhfyyiiii, 2 , 1 , 0 ),(111iyxhfyyiiii后退欧拉

16、法后退欧拉法梯形公式梯形公式,.2 , 1 , 0),(),(2111iyxfyxfhyyiiiiii预报预报-校正公式校正公式),(),(2),(1111iiiiiiiiiiyxfyxfhyyyxhfyy预报预报-校正公式校正公式121112(,)(,)()20,1,2,iiiiiikf x ykf xh yhkhyykki龙格龙格-库塔公式库塔公式),()2/, 2/()2/, 2/(),()22(61342312143211kyhxhfkkyhxhfkkyhxhfkyxhfkkkkkyyiiiiiiiiii补充定义2：用单步法解模型方程 得到解满足稳定性方程 若 方法是绝对稳定的0)Re

17、(,yyiiyhEy)(11|)(|hE的交称为绝对稳定区间在实轴为实数时，此区域与（当h)0例例证明证明解常微分方程解常微分方程初值问题的初值问题的梯形方法梯形方法精度精度是是二阶二阶的，并求其局部截断误差的，并求其局部截断误差主项主项而局部截断误差按定义是：而局部截断误差按定义是： y(x i+1)-yi+1= y(x i+h)- yi+1先将先将y(x i+h)在在x=xi处处tailor展开展开分析：分析：证明精度是二阶，即证明其局部截断误差是证明精度是二阶，即证明其局部截断误差是o(h3）111 (,)(,)2iiiiiihyyf x yf xy这里：证明证明:23( )( )(h)

18、( )( ).2!3!iiiiiyxyxy xy xhy xhh再来看再来看 yi+11111(,)(,)2()()2iiiiiiiiihyyf xyf xyhyy xy x123(4)()()(h)()()().2!3!iiiiiiiy xy xhxxtailorhhy xy xhyxyxy将在处展开代入上式代入上式 yi+111123(4)234(4)(,)(,)2 ()()()().22!3!()()().2412iiiiiiiiiiiiiiihyyf xyf xyhhhyy xy xhyxyxyhhhyhy xyxyxy23()()(h)()().2!3!iiiiiyxyxy xy xhy xhh注意到：例求Euler法的绝对稳定区间 yyxfy),(解：),(1iii