计算方法复习新

计算方法总复习第一章误差和有效数字误差的来源及分类绝对误差、相对误差、有效数字的定义误差同有效数字的关系数值计算中应注意的几个问题误差的来源及分类模型误差观测误差截断误差舍入误差绝对误差、相对误差、有效数字的定义绝对误差与绝对误差限相对误差与相对误差限*****xxexxe*********0,rrrxeexxxxxee绝对误差、相对误差、有效数字的定义有效数字的定义nmmnnxxxxxx102110)101010(*2211*kxx1021*误差同有效数字的关系nmxx1021*①　　)1(1**1021nxxxx②　　)1(1*10)1(21nrx③　则x*至少具有n位有效数字四舍五入得到如3.14=0.314×101（X*=±0.X1X2…Xn×10m）n=3,m=1|п–3.14|=|3.1415926…-3.14|=0.0015926….≤0.005=10-2=101-3=10m-n数值计算中应注意的几个问题避免两相近数相减防止大数“吃”小数除数不能太小算法稳定性简化运算步骤，减少运算次数111xxxx...6121112xxxex;xεxεxεx;1lnlnlnxεxεx类似的：小结：1、什么是舍入误差？什么是截断误差？它们的来源是什么？2、什么是绝对误差、相对误差和有效数字？3、绝对误差、相对误差和有效数字之间的关系是什么？4、п=3.141592654…(1)若其近似值取5位有效数字，则该近似值是多少？其绝对、相对误差限是多少？（2）若其近似值取3.1415,绝对误差限是什么？有效数字是什么（3）若其近似值的绝对误差限为0.5×10-5则该近似值是什么？5、下列近似值有几位有效数字，其相对误差限是什么？,绝对误差限是什么?（1)x1=e=2.71828=x1*(2)x2=0.030051x2*=0.0300(3)x3=e/1000.02718=x3*第二章非线性方程的解法对分法迭代法牛顿迭代法对分法条件f(x)在[a,b]上连续，f(a)f(b)0，单调意义对分次数n的计算12lnln)ln(abn迭代法)(1nnxx基本思想）（收敛定理收敛条件11)('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]的一个近似值。几何意义用切线与x轴的交点近似代替取限于x轴的交点。xyx*.牛顿迭代法的几何意义：以f’(x0)为斜率作过(x0,f(x0))点的直线，即作f(x)在点x0的切线方程：x0f(x0)))(()(000xxxfxfy令y=0,则得此切线与x轴的交点x1,即x1)()(0001xfxfxx…)()(1kkkkxfxfxx牛顿迭代法又称切线法收敛性由Φ(x)的表达式得：|Φ′(x)|=因为f(x*)=0所以Φ′(x*)=0也即Φ(x)在根的附近收敛很快（1）局部收敛定理(p30)设f′(x)存在，且f′(x)在方程f(x)=0的根x*附近不为零，=L1,则Newton迭代格式收敛若|Φ′(x)|=])('[|)()(|2xfxfxf])('[|)()(|2xfxfxf(2)全局收敛定理（p31大范围收敛定理）设f(x)在[a,b]上满足①f(a)f(b)0;②f′(x)≠0;③f〞(x)存在且不变号；④取x0∈(a,b),使f〞(x0)f(x0)0则Newton迭代序列收敛于f(x)=0在[a,b]的唯一根------.保证有根------.保证单根------.保证凸凹性不变------.保证收敛牛顿迭代法牛顿迭代公式至少二阶收敛特点在单根附近具有较高的收敛速度。公式)(')(1kkkkxfxfxx牛顿迭代法m重根)(')(1kkkkxfxmfxx011)('*mx第三章线性代数方程组的解法直接法（快速有效）迭代方法（节省内存）向量范数、矩阵范数的定义、性质条件数及其对相对误差的影响（三个证明）直接法Gauss消去法、Gauss列主元消去法（算法描述）追赶法（三对角严格对角占优）平方根法Gauss消去法消元过程),,1(),,1,()1,,2,1()()()1()()()1()()(nkibmbbnkjiamaankaamkkikkikikkjikkijkijkkkkikik回代过程)1,,1()()(1)()()()(nkaxabxabxkkknkjjkkjkkknnnnnn二、算法描述1、消元对k=1…..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)(ik,j=k+1,…,n+1)2、回代第i次回代公式（i=n,n-1….1)Xi(即ain+1(i))=(ain+1(i)-）/aii(i)Gauss列主元消去法关键步骤第k次消元时，在系数矩阵A的第k列元素中选取绝对值最大的元素为主元素。追赶法（条件）解对称正定的平方根法定理2：若n阶方阵A对称正定，则存在唯一的对角元素为正的下三角阵L，使A=LLT(Cholesky分解）即:(i=2,….n,j=1,....i-1)(p543-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()(1ULDCbDf1记，Jacobi迭代法Jacobi迭代收敛条件充分条件(1):迭代矩阵至少存在一种矩阵范数||.||,使||C||1充分条件(2):方程组AX=b的系数矩阵A为严格对角占优阵充要条件：迭代矩阵的谱半径ρ(C)1Gauss-Seidel迭代法分量形式矩阵形式记，),2,1,0;,,2,1(11)()1()1(knidxCxCxijinijkjijkjijkifGXXkk)()1(ULDG1)(bLDf1)(1231231231027.21028.354.2xxxxxxxxx迭代公式为：Gauss-Seidel迭代充分条件：迭代矩阵G的||G||1A对称正定A严格对角占优充要条件：ρ(G)1向量范数、矩阵范数向量范数非负性齐次性三角不等式三种常用的向量范数1—范数2—范数∞—范数0x0,0的充分必要条件是且xx)(为任何实数kxkkx),(nRyxyxyx对任意niixx11niixx12221)(inixx1max向量范数、矩阵范数矩阵范数BAABnBABABAkAkkAAA)4(),()3()((2)0A00)1(；阶方阵为任；为任何实数；的充要条件是，且向量范数、矩阵范数三种常用的矩阵的算子范数的最大特征值为矩阵范数，其中—的称为的列范数；称为的行范数；称为AAAaAaATniijnjnjijnimaxmax2111112AAmaxAmax向量范数、矩阵范数谱半径的谱半径为矩阵个特征值，的为矩阵设AAnRAniininni1max)(),,2,1(条件数及其对相对误差的影响条件数AAACond1)(Cond(A)的值越大，方程组的病态就越严重。条件数的性质条件数及其对相对误差的影响常用的条件数AAACond1)(1）（（2）A的谱条件数当A为对称正定矩阵时，nACond12)(其中λ1，λn为矩阵A的最大和最小特征值。第四章插值与拟合Lagrange插值Newton插值差商、差分定义、性质差商、差分表的构造、使用样条函数插值、条件、意义曲线拟合与最小二乘法(使用环境和步骤）Lagrange插值Lagrange插值多项式线性插值及其余项抛物插值（二次插值）iniinyxlxL)()(0nijjjijixxxxxl0)()()(jijixlji01)(Lagrange插值Lagrange插值余项li(x)的性质njjnnbaxxnfxR0)1(],[)()!1()()(njjxl01)(njjCxlC0)(Lagrange插值njnnkjjnkxxxnkkxl010)(1)1(,,2,1001)0(njkjkjxxlx0)()()(次数不超过n次的代数多项式的插值函数等于它本身。Newton插值公式)())(](,,,[))(](,,[)](,[)()(11010102100100nnnxxxxxxxxxfxxxxxxxfxxxxfxfxNNewton插值差商的定义)())(()()(')()())(()()(],,,[100011010nniiininiiiiiiinxxxxxxxxxfxxxxxxxxxfxxxf其中()()[,]jiijjifxfxfxxxx差商表的构造及使用Nn(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)++f[x0,x1,x2,x3](x-x0)(x-x1)(x-x2)….+f[x0,x1,….xn](x-x0)(x-x1)…(x-xn-1)牛顿插值多项式的余项：Rn（x）=f[x,x0,x1….xn]ω(n+1)(x)(n1)1()(x)(n1)!nf样条函数插值、条件、意义给定函数表求一个函数s(x)满足（1）s(xi)=yi(i要=0,1,,,n)（2）s′(x)s(x)在内节点xi(i=1,n-1)上连续（3）在每个小区间上，s(x)为三次多项式此时，称s(x)为三次样条插值函数xx0x1…xny=f(x)y0y1…yn常见的边界条件有：（1）第一类边界条件：给定端点处的一阶导数值s′(x0)=y′(x0)（m0=y′(x0))s′(xn)=y′(xn)(mn=y′(xn))（2）第二类边界条件：给定端点处的二阶导数值s(x0)=y(x0)(M0=y(x0))s(xn)=y(xn)(Mn=y(xn))特别情况下：M0=Mn=0称为自然边界条件，满足自然边界条件的样条函数叫做自然样条曲线拟合问题的提法已知一组（二维）数据，即平面上n个点（xi,yi)i=1,…n,寻求一个函数（曲线）y=p(x),使p(x)在某种准则下与所有数据点最为接近，即曲线拟合的最好。+++++++++xyy=p(x)(xi,yi)ii为点（xi,yi)与曲线y=p(x)的距离所谓”曲线拟合”,是指根据给定的数据表,寻找一个简单的表达式来”拟合”该组数据,此处的”拟合”的含义为:不要求该表达式对应的近似曲线完全通过所有的数据点,只要求该近似曲线能够反映数据的基本变化趋势.第五章数值积分与微分插值型求积公式Newton-Cotes求积公式复化求积公式Gauss型求积公式数值微分插值型求积公式定义求积公式nkkkbaxfAdxxf0)()(其系数时，则称求积公式为插值求积公式。bakkdxxlA)(例1给定求积公式如下：4322141231)(10fffdxxf试证此求积公