数值计算方法与算法

数值计算方法与算法第0章绪论•误差•范数|)(|max)(maxmax)(sup,,1120/11AAρaAaAAAAAxxiijjiiijijpppppnpp谱半径，，，矩阵范数向量范数xxxxxxFxxFyxxFyxFydddddxdxdxdxxx)(')(')(')(，相对误差，绝对误差，近似值精确值例题1•计算矩阵的范数•计算矩阵的谱半径1101A3113B225112AAA，4)(2421B，，第1章插值•多项式插值•Lagrange插值•Newton插值)(010000010nnnnnnnnnyyxxxxaaxaxaaxp，],,[)()(00iiniijjinxxfiaxxaxp阶差商，)()()(00ijjiiiniiiniinxxywxxwxxxp，第1章插值•差商•插值函数误差•Runge现象0101000],,[],,[],,[)(][xxxxfxxfxxfxfxfkkkk，)()!1())(()()(0)1(niinnxxnxfxpxf。，则，，一般地，若)()(|)()()()()(1)()(xpxfxxxfxpxfxpkiikikii第1章插值•三次样条函数•M关系式•m关系式113330))(,0max()(niiiiiixxaxaxS11111113111131)()())(()(6))(()(6)(iiiiiiiiiiiiiiiiiiiiiiiiixxxxxxxyxxxxyxxxxxxxxMxxxxxxxxMxS，1111111211112111)()()()())(()(iiiiiiiiiiiiiiiiiiiiiiiiiiiiixxxxxxxyxxxxyxxxxxxmxxyyxxxxxxxxyymxS，第1章插值21111111021120112111111111111012112011211222211110)(/00/3)(2)(2)(2006)(2)(2)(21222211110iiiiiiiiiiiiinnnnnhhhhhhhhhhnnnnnnnnnxxyyexxyydxxhhmhmeeeeeemmmMhMhddddddMMMhhhhhhhhhhnnnn，，其中例题2•给定f(-1)=3,f(2)=5,f(3)=7,f(4)=5，作出差商表，写出Newton插值公式。x-1234Δ03575Δ12/32-2Δ21/3-2Δ3-7/15)3)(2)(1()2)(1()1(3)(1573132xxxxxxxp例题3•给定数据f(0),f(1),f(3),f'(3),作出插值多项式，并写出插值余项。3)(0)3)(1(!4))(()()()3(6)3)(1()3(6))3(1)(1()1(4)3()0(9)3)(1()(2)4(6522xxxxxfxpxffxxxfxxxfxxfxxxp，第2章数值微分和数值积分•数值微分)()!1()()()(6)(2)()()(2)()()()(2)()()()()1(2321ijjininixxnfxpxfhfhhxfhxfxfhfhhxfxfxfhfhxfhxfxf插值型微分中心差商向后差商向前差商第2章数值微分和数值积分•数值积分5)4(230)2(0)1()(2880)()(6)()(4)()(12)()(2)()()()!2()()()!1()()()()(],[abfabbffafabfabbfafndxxxxnfndxxxnfdxxpdxxfabniaxnbababaniinbaniinbanbai为偶数为奇数等分，将区间第2章数值微分和数值积分•复化数值积分•Romberg积分54)4(1023210)(2880)()(3)(2)(6)()()()(12)()()(2)()()()(],[1abnfabfxfafbfdxxfabnfabxfafbfdxxfabniaxnbanixxibaniibaiii等分，将区间ijRRRRRjjijijijiii11421,11,1,,0,，个分点的梯形积分，例题4•构造积分的数值积分公式I(f)=a0f(-h)+a1f(0)+a2f(2h)。)2(43)0(49)()()2(6)()0(2)2)(()(3)2()(2222hfhfhdxxpfIhfhxhxfhhxhxhfhhxxxphhhhdxxffI2)()(例题5•用Romberg公式计算积分：Ri,j01205/2119/87/3275/327/37/3212)(dxxfI第3章曲线拟合的最小二乘法•最小二乘原理设A为m×n列满秩实矩阵，b为列向量，则使函数取最小值。•多项式拟合2)(bxxAQbxAAA1)(mnnmmnnyyyaaaxxxxxx10101100111例题6•给定数据用最小二乘法求形如y=aebx的经验公式。x-0.70-0.500.250.75y0.991.212.574.2300198.199724.100198.1691769.0lnlnlnbabaxbay第4章非线性方程求根•对分法求实根原理：若f(a)f(b)0则f在[a,b]中至少有一零点。收敛步数：O(log(1/ε))•迭代法原理：若|f'(x)|≤L1，则xk+1=f(xk)收敛。收敛步数：O(log(1/ε))第4章非线性方程求根•Newton迭代法原理：f(x)≈f(xk)+f'(xk)(x-xk)公式：xk+1=xk－f(xk)／f'(xk)收敛步数：O(loglog(1/ε))•弦截法原理：f(x)≈f(xk)+(x-xk)(f(xk)-f(xk-1))／(xk-xk-1)收敛步数：O(loglog(1/ε))第4章非线性方程求根•方程组的Newton迭代法原理：F(X)≈F(Xk)+J(Xk)(X－Xk)公式：Xk+1=Xk－J(Xk)-1F(Xk)收敛步数：O(loglog(1/ε))•同时逼近一元多项式的所有根Weierstrass-Durand-Kerner方法：ijjiiiixxxfxx)()(~例题7•用Newton迭代法求解非线性方程组取(x0,y0)=(0.8,0.6)，误差控制量10-3。yxyxxyxyxyx3221211322~~001322yxyxk0123xk0.80.8270490.8260320.826031yk0.60.5639340.5636240.563624第5章解线性方程组的直接法•Gauss消元法原理：通过初等行变换，化方程组Ax=b为上三角。由此得到Dolittle分解和Courant分解A=LU。条件：A的顺序主子式非零。运算量：O(n3)nnnnnnnnaaaaaaaaA~~~~~~~~111111111第5章解线性方程组的直接法•列主元消元法原理：在Gauss消元过程中，先选取一列中模最大元素，将其换行至左上角位置，再作消元。由此得到分解A=PLU，P为置换方阵，L中各元素的模都≤1。条件：A行列式非零。运算量：O(n3)第5章解线性方程组的直接法•全主元消元法原理：在Gauss消元过程中，先选取所有元素模最大者，将其换行至左上角位置，再作消元。由此得到分解A=PLUQ，P和Q为置换方阵，L中各元素的模都≤1，U中各元素的模都≤同行对角元素的模。条件：A行列式非零。运算量：O(n3)第5章解线性方程组的直接法•Dolittle分解：A=LU，L为单位下三角方阵。•Crout分解：A=LU，U为单位上三角方阵。•对称阵的LDLT分解：L为单位下三角方阵，D为对角方阵。•追赶法：将Gauss消元法应用于三对角方阵。第5章解线性方程组的直接法•Givens旋转消元法原理：通过Givens旋转，化方程组Ax=b为上三角。由此得到分解A=QR，Q为正交阵，R为上三角阵。运算量：O(n3)1112521525121151351411A例题8•库朗分解矩阵532131215A5321312155321215575145215135751421215211513575142121511111234xxxx，，，例题9•用追赶法求解三对角方程组568272372372314321xxxx57263728372231572637243123157223143123111231431231第6章解线性方程组的迭代法•Jacobi迭代原理：设D为A的对角方阵。若ρ(I－AD-1)1，则Ax(k+1)－b=(I－AD-1)(Ax(k)－b)趋于0，x(k+1)=x(k)－D-1(Ax(k)－b)趋于A-1b。运算量：O(n2log(1/ε))充分条件：A列(行)对角优第6章解线性方程组的迭代法•Gauss-Seidel迭代原理：设D+L为A的下三角方阵。若ρ(I－A(D+L)-1)1则Ax(k+1)－b=(I－A(D+L)-1)(Ax(k)－b)趋于0，x(k+1)=x(k)－(D+L)-1(Ax(k)－b)趋于A-1b。运算量：O(n2log(1/ε))充分条件：A列(行)对角优或A正定第6章解线性方程组的迭代法•松弛迭代原理：x(k+1)=x(k)－(w-1D+L)-1(Ax(k)－b)，w为松弛因子必要条件：|w－1|1•Newton迭代法求逆矩阵原理：设I－AX(k+1)=(I－AX(k))2。若ρ(I－AX(0))1，则X(k+1)=2X(k)－X(k)AX(k)收敛到A-1。运算量：O(n3loglog(1/ε))例题10•雅可比迭代求解401211263115321xxx)()(1)()1(bAXDXXkkkk01220x10−0.20.20.0