计算方法大作业

1、作业一：线性方程组的数值解法两类方法，第一是直接解法，得到其精确解；第二是迭代解法，得到其近似解。一、Gauss消去法1顺序Gauss消去法记方程组为：消元过程：经n1步消元，化为上三角方程组第k步若回代过程：2GaussJordan消去法避免回代，消元时上下同时消元3Gauss列主元消去法Gauss列主元消去法原理：每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵表示。消元过程：对k=1,2,n-1,选主元，找 如果，则矩阵A奇异，程序结束；否则执行3。如果，则交换第k行与第行对应的元素位置， 消元，对i=k+1, ,n,计算 对j=L+1, ,n+1,计算 回代过程：1若则矩阵A奇

2、异，程序结束；否则执行。2二、LU分解法1求解原理线性方程组写成矩阵形式为：AX=b若A=LU，则LUX= b，记UX=Y则LY= b若L、U为特殊矩阵，则求解线性方程组变为解两个特殊线性方程组问题。2Doolittle分解L为下三角矩阵, U为上三角矩阵,不一定能分解,分解也不一定唯一;设L或U是单位三角矩阵, 若能分解,则可分解唯一.L是单位下三角矩阵,称为Doolittle分解; U是单位上三角矩阵,称为Crout分解；定理: n阶矩阵A有唯一分解的充要条件为A的前n-1阶主子式都不为0.Doolittle分解算法：由矩阵乘法：得到：算法特点：先计算U的行，再计算L的列，交替进行；存储时

3、可用紧凑格式。矩阵分解后，解两个三角方程组：LY= b，UX=Y3Crout分解若L为下三角矩阵，U是单位上三角矩阵，则称Crout分解；算法特点：先计算L的列，再计算U的行，交替进行。线性方程组的迭代解法一、Jacobi迭代公式一般地，对线性方程组若，则可从第i个方程中解出,得到Jacobi迭代公式：简记为：二、 Gauss-Seidel迭代公式非线性方程的数值解法一、 二分法1根的存在性定理：函数f(x)在区间a，b连续，且f(a).f(b)<0,则方程f(x)=0在区间a，b有根。方程的根存在，不一定唯一，若在区间a，b上有唯一根，称区间a，b为根隔离区间。2 二分法（区间逐次分半

4、法）原理：通过计算根隔离区间中点，将区间分半，缩小区间，得到方程近似根数列。 取 二、迭代法1迭代原理迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。方程f(x)=0变形为，得到递推公式-简单迭代公式称为迭代函数给初值计算，得到数列，若，则称迭代收敛，否则发散。2迭代收敛性判定收敛性定理：设方程的迭代函数在a，b满足：（1）当时，；（2）在a，b可导，且，则（1）方程在a，b有唯一根； （2）迭代公式收敛，即；（3）误差估计。说明可根据迭代函数的导数判断迭代收敛性。3Newton 迭代法Newton切线公式：几何作法迭代公式例：利用解二次方程推导近似计算的公式。由Ne

5、wton切线公式 Newton弦截公式：Newton切线公式的缺点及改进几何作法迭代公式Newton弦截公式是两步公式。插值与拟合一、插值法1拉格朗日插值设已知 x0,x1,··· ,xn 及 yi = f(xi)(i = 0,1,··· ,n)，Ln(x) 为不超过 n 次的多项式，且满足插值条件 Ln(xi) = yi (i = 0,1,··· ,n)。由对 L2(x) 的构造经验，可设,其中，li(x)(i = 0,1,··· ,n) 均为 n 次多项式且满足 (4.9

6、)(i,j = 0,1,··· ,n)。不难验证，这样构造出的 Ln(x) 满足插值条件。因此问题归结为求 li(x)(i = 0,1,··· ,n) 的表达式。因 xj(j 6= i) 是 n 次多项式 li(x) 的 n 个根，故可设再由得故有称为 n 阶拉格朗日插值公式，其中 li(x)(i = 0,1,··· ,n) 称为 n 阶拉格朗日插值的基函数。2Hermite 插值拉格朗日插值仅考虑节点的函数值约束，而一些插值问题还需要在某些节点具有插值函数与被插值函数的导数值的一致性。具有节点的导数值约

7、束的插值称为 Hermite 插值。3牛顿插值法由于拉格朗日插值公式计算缺少递推关系，每次新增加节点需要重新计算，高次插值无法利用低次插值的结果。通过引进差商的概念，可以给出一种在增加节点时可对拉格朗日插值多项式进行递推计算的方法。该方法称为牛顿插值法。设已知 x0,x1,··· ,xn 及 yi = f(xi)(i = 0,1,··· ,n)，由差商的定义，当 x 6= xi (i =0,1,··· ,n) 时，由从而f(x) = f(x0) + fx0,x1(x x0) + fx0,x1,x(x x0

8、)(x x1)依此类推，得到f(x)=f(x0) + fx0,x1(x x0) + fx0,x1,x2(x x0)(x x1)+··· + fx0,x1,··· ,xn(x x0)(x x1)···(x xn1)+ fx0,··· ,xn,x(x x0)···(x xn1)(x xn)其中=Nn(x) + Rn(x),Nn(x)=f(x0) + fx0,x1(x x0) + fx0,x1,x2(x x0)(x x1)及+··&

9、#183; + fx0,··· ,xn(x x0)(x x1)···(x xn1)由于 Nn(x) 为不超过 n 次的多项式，且满足Nn(xi) = f(xi) Rn(xi) = f(xi) = yi, i = 0,1,··· ,n,故由插值多项式的唯一性知，Nn(x) = Ln(x) 恰为 f(x) 关于节点 x0,x1,··· ,xn 的拉格朗日插值多项式。再由,即得从而有Nn(x) 称为 f(x) 关于节点 x0,x1,··· ,xn 的牛

10、顿插值多项式。4.样条插值法从拉格朗日插值余项公式的分母部分可以发现，节点数的增加对提高插值精度是有利的，但这只是问题的一个方面。以下讨论的著名例子揭示了问题的另一方面，即并非插值节点越多精度越高。设已知 x0 < x1 < ··· < xn 及 yi = f(xi)(i = 0,1,··· ,n)，插值函数 S(x) 在每个小区间 xi1,xi 上是不超过 3 次的多项式且具有 2 阶连续导数，则称 S(x) 为三阶样条插值。具体地说，三阶样条插值是满足下列条件的分段三次多项式：(1) 插值条件：S(xi) = y

11、i (i = 0,1,··· ,n)(2) 连接条件：二、最小二乘拟合假定通过观测得到函数 y = f(x) 的 m 个函数值：yi f(xi), i = 1,2,··· ,m所谓最小二乘法就是求 f(x) 的简单近似式 (x)，使 (xi) 与 yi 的差（称为残差或偏差）ei = (xi) yi, (i = 1,2,··· ,m)的平方和最小，即使最小。(x) 称为 m 个数据 (xi,yi), i = 1,2,··· ,n, 的最小二乘拟合函数，f(x) 称为被拟合函数

12、。y (x) 近似反映了变量 x 与 y 之间的函数关系 y = f(x)，称为经验公式或数学模型。数值微积分一、 Newton-Cotes公式1公式推导由Lagrange插值多项式代替函数f(x)记则求积系数的计算：-为Cotes系数；- Newton-Cotes求积公式2Cotes系数性质对称性：权性：3常用公式n=1梯形公式：n=2Simpson,抛物公式：n=4Cotes公式： 二、Gauss型求积公式1代数精确度定义：若求积公式对任意m次代数多项式精确成立，而对m+1次代数多项式不精确成立，称求积公式具有m次代数精确度。判定：求积公式具有m次代数精确度求积公式对精确成立；而对 不精确

13、成立。例：梯形公式具有1次代数精确度；定理1：n+1个节点的插值型求积公式代数精确度至少为n；定理2；Newton-Cotes公式代数精确度至少为n；当n为偶数时，可达n+1次代数精确度。2Gauss型求积公式定义：若n+1个节点求积公式具有2n+1次代数精确度，则称为Gauss型求积公式，节点为Gauss点。作业二：计算方法的应用1数值实例下面给定的是某城市最近1个月早晨7：00左右的天气预报所得到的温度，按照数据找出任意次曲线拟合方程和它的图像。天数12345678910温度910111213141312119天数11121314151617181920温度1011121314121110

14、98天数21222324252627282930温度78911976531下面用Matlab编程对上述数据进行最小二乘拟合2Matlab源程序x=1:1:30;y=9,10,11,12,13,14,13,12,11,9,10,11,12,13,14,12,11,10,9,8,7,8,9,11,9,7,6,5,3,1;a1=polyfit(x,y,3) %三次多项式拟合%a2= polyfit(x,y,9) %九次多项式拟合%a3= polyfit(x,y,15) %十五次多项式拟合%b1= polyval(a1,x)b2= polyval(a2,x)b3= polyval(a3,x)r1= sum(y-b1).2) %三次多项式误差平方和%r2= sum(y-b2).2) %九次次多项式误差平方和%r3= sum(y-b3).2) %十五次多项式误差平方和%plot(x,y,'*') %用*画出x,