计算方法大作业

作业一：线性方程组的数值解法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa............22112222212111212111两类方法，第一是直接解法，得到其精确解；第二是迭代解法，得到其近似解。一、Gauss消去法1．顺序Gauss消去法记方程组为：)1()1(2)1(21)1(1)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11............nnnnnnnnnnbxaxaxabxaxaxabxaxaxa消元过程：经n－1步消元，化为上三角方程组)()(2)(21)(1)2(22)2(221)2(21)1(11)1(11......nnnnnnnnnnbxaxaxabxaxabxa第k步若0)(kkkankjinkbaabbaaaaakkkkkkikkikikkjkkkkikkijkij,....,1,1,...1)()()()()1()()()()()1(回代过程：nijiiijiijiiinnnnnnnniaxabxabx1)()()()()()1,...2,1(/)(/2．Gauss—Jordan消去法避免回代，消元时上下同时消元3．Gauss列主元消去法Gauss列主元消去法原理：每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵(1)ijnnAba表示。消元过程：对k=1,2,n-1,选主元，找{,1,,}kikkn使得,maxkikikkinaa如果,0kika，则矩阵A奇异，程序结束；否则执行3。如果kik，则交换第k行与第ki行对应的元素位置，,,,1.kkjijaajkn消元，对i=k+1,,n,计算,ikikkkala对j=L+1,,n+1,计算ijijikkjaala回代过程：1．若0,nna则矩阵A奇异，程序结束；否则执行。2．,1;1,,2,1,nnnnnaxina对计算,11ninijjjiiiiaaxxa二、LU分解法1．求解原理线性方程组写成矩阵形式为：AX=b若A=LU，则LUX=b，记UX=Y则LY=b若L、U为特殊矩阵，则求解线性方程组变为解两个特殊线性方程组问题。2．Doolittle分解L为下三角矩阵,U为上三角矩阵,不一定能分解,分解也不一定唯一;设L或U是单位三角矩阵,若能分解,则可分解唯一.L是单位下三角矩阵,称为Doolittle分解;U是单位上三角矩阵,称为Crout分解；定理:n阶矩阵A有唯一分解的充要条件为A的前n-1阶主子式都不为0.Doolittle分解算法：nnnnnnnnnnnnuuuuuulllaaaaaaaaa............1............11.....................222112112121212222111211由矩阵乘法：nkkjikijula1得到：11;,...1,krrjkrkjkjnkkjulaunkkiuulalkrkkrkirikik,...1,/)(11算法特点：先计算U的行，再计算L的列，交替进行；存储时可用紧凑格式。矩阵分解后，解两个三角方程组：LY=b，UX=Y1111,...3,2ikkikiiniylbybynikiikikiinniuxuyx11,...1,/)(3．Crout分解若L为下三角矩阵，U是单位上三角矩阵，则称Crout分解；算法特点：先计算L的列，再计算U的行，交替进行。线性方程组的迭代解法一、Jacobi迭代公式一般地，对线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa............22112222212111212111若0iia，则可从第i个方程中解出ix,得到Jacobi迭代公式：nnknnnknnkniikninkiikiknnkkaxaxabxaxaxabxaxaxabx/)...(.../).......(.../)...()(1)(11)1()()(11)1(11)(1)(2121)1(1简记为：niaxabxiinijjkjijiki,...,2,1/)(1)()1(二、Gauss--Seidel迭代公式niaxaxabxiiijnijkjijkjijiki,...,2,1/)(111)()1()1(非线性方程的数值解法一、二分法1．根的存在性定理：函数f(x)在区间[a，b]连续，且f(a).f(b)0,则方程f(x)=0在区间[a，b]有根。方程的根存在，不一定唯一，若在区间[a，b]上有唯一根，称区间[a，b]为根隔离区间。2．二分法（区间逐次分半法）原理：通过计算根隔离区间中点，将区间分半，缩小区间，得到方程近似根数列{}nx。...,....,,11nnbababakkkabab2/)(取2/)(*nnbax二、迭代法1．迭代原理迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。方程f(x)=0变形为)(xx，得到递推公式)(1kkxx--------简单迭代公式称)(x为迭代函数给初值计算，得到数列{}nx，若*limxxkk，则称迭代收敛，否则发散。2．迭代收敛性判定收敛性定理：设方程)(xx的迭代函数)(x在[a，b]满足：（1）当],[bax时，)(x],[ba；（2）)(x在[a，b]可导，且1)(Lx，],[bax，则（1）方程)(xx在[a，b]有唯一根*x；（2）迭代公式)(1kkxx收敛，即*limxxkk；（3）误差估计01*1xxLLxxkk。说明可根据迭代函数)(x的导数判断迭代收敛性。3．Newton迭代法Newton切线公式：几何作法迭代公式)()('1kkkkxfxfxx例：利用解二次方程,02cx推导近似计算c的公式。由Newton切线公式)(211kkkxcxxNewton弦截公式：Newton切线公式的缺点及改进几何作法迭代公式)()()()(111kkkkkkkxxxfxfxfxxNewton弦截公式是两步公式。插值与拟合一、插值法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)(i,j=0,1,···,n)。不难验证，这样构造出的Ln(x)满足插值条件。因此问题归结为求li(x)(i=0,1,···,n)的表达式。因xj(j6=i)是n次多项式li(x)的n个根，故可设再由得故有称为n阶拉格朗日插值公式，其中li(x)(i=0,1,···,n)称为n阶拉格朗日插值的基函数。2．Hermite插值拉格朗日插值仅考虑节点的函数值约束，而一些插值问题还需要在某些节点具有插值函数与被插值函数的导数值的一致性。具有节点的导数值约束的插值称为Hermite插值。3．牛顿插值法由于拉格朗日插值公式计算缺少递推关系，每次新增加节点需要重新计算，高次插值无法利用低次插值的结果。通过引进差商的概念，可以给出一种在增加节点时可对拉格朗日插值多项式进行递推计算的方法。该方法称为牛顿插值法。设已知x0,x1,···,xn及yi=f(xi)(i=0,1,···,n)，由差商的定义，当x6=xi(i=0,1,···,n)时，由从而f(x)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x](x−x0)(x−x1)依此类推，得到f(x)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)+···+f[x0,x1,···,xn](x−x0)(x−x1)···(x−xn−1)+f[x0,···,xn,x](x−x0)···(x−xn−1)(x−xn)其中=Nn(x)+Rn(x),Nn(x)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)及+···+f[x0,···,xn](x−x0)(x−x1)···(x−xn−1)由于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的牛顿插值多项式。4.样条插值法从拉格朗日插值余项公式的分母部分可以发现，节点数的增加对提高插值精度是有利的，但这只是问题的一个方面。以下讨论的著名例子揭示了问题的另一方面，即并非插值节点越多精度越高。设已知x0x1···xn及yi=f(xi)(i=0,1,···,n)，插值函数S(x)在每个小区间[xi−1,xi]上是不超过3次的多项式且具有2阶连续导数，则称S(x)为三阶样条插值。具体地说，三阶样条插值是满足下列条件的分段三次多项式：(1)插值条件：S(xi)=yi(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)称为被拟合函数。y≈ϕ(x)近似反映了变量x与y之间的函数关系y=f(x)，称为经验公式或数学模型。数值微积分一、Newton-Cotes公式1．公式推导由Lagrange插值多项式)(xLn代替函数f(x)babaninibaiiiinbaxfdxxldxxfxldxxLdxxfI00)())(()()()()(记baiidxxlA)(则niiibaxfAdxxfI0)()(求积系数iA的计算：)(00)()()()!(!)1(ninnijjiniCabdtjiitininabA-)(niC为Cotes系数；niininiiibaxfCabxfAdxxfI0)(0)()()()(---------Newton-Cotes求积公式2．Cotes系数性质对称性：)()(ninniCC权性：niniC0)(13．常用公式n=1梯形公式：))()((2)(bfafabdxxfIban=2Simpson,抛物公式：))()2(4)((6)(bfbafafabdxxfIban=4Cotes公式：))(7)(32)(12)(32)(7(90)(43210xfxfxfxfxfabdxxfIba4abiaxi二、Gauss型求积公式1．代数精确度定义：若求积公式niiibaxfAdxxfI0)()(对任意≤m次代数多项式精确成立，而对m+1次代数多项式不精确成立，称求积公式具有m次代数精确度。判定：求积公式具有m次代数精确度求积公式对mxxxxf,...,,,1)(2精确成立；而对1)(mxxf不精确成立。例：梯形公式具有1次代数精确度；定理