数值计算方法论文
论文名称:数值计算方法期末总结
学 号:
姓 名:
完成时间:
摘要:数值计算方法是数学的一个重要分支,以用计算机求解数学问题的理论和方法为研究对象。本文是我对本学期数值分析这门课程中所学到的内容以及所作的工作的总结。通过一学期的学习,我深入学习了线性方程组的解法,非线性方程的求根方法,矩阵特征值与特征向量的计算,函数的插值方法,最佳平方逼近,数值积分与数值微分,常微分方程初值问题的数值解法。通过陶老师课堂上的讲解和课下的上机训练,对以上各个章节的算法有了更深刻的体会。
最后做了程序的演示界面,使得程序看起来清晰明了,便于查看与修改。通过本学期的学习。
关键词:数值计算方法、演示界面
第一章 前言
随着电子计算机的普及与发展,科学计算已成为现代科学的重要组成部分,因而数值计算方法的内容也愈来愈广泛和丰富。通过本学期的学习,主要掌握了一些数值方法的基本原理、具体算法,并通过编程在计算机上来实现这些算法。
第二章 基本概念
2.1算法
算法是指由基本算术运算及运算顺序的规定构成的完整的解题步骤。 算法可以使用框图、算法语言、数学语言、自然语言来进行描述。具有的特征:正确性、有穷性、适用范围广、运算工作量少、使用资源少、逻辑结构简单、便于实现、计算结果可靠。
2.2 误差
计算机的计算结果通常是近似的,因此算法必有误差,并且应能估计误差。误差是指近似值与真正值之差。绝对误差是指近似值与真正值之差或差的绝对值;相对误差:是指近似值与真正值之比或比的绝对值。误差来源见表2.1
表2.1
第三章 泛函分析
2.1泛函分析概要
泛函分析(Functional Analysis)是研究“函数的函数”、函数空间和它们之间变换(映射)的一门较新的数学分支,隶属分析数学。它以各种学科为具体背景,在集合的基础上,把客观世界中的研究对象抽象为元素和空间。如:距离空间,赋范线性空间,内积空间。
2.2 范数
范数,是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域,泛函是一个函数,其为矢量空间内的所有矢量赋予非零的正长度或大小。
这里以Cn空间为例,Rn空间类似。最常用的范数就是p-范数。若,那么
当p取1,2,∞的时候分别是以下几种最简单的情形:
1-范数:║x║1=│x1│+│x2│+…+│xn│
2-范数:║x║2=(│x1│2+│x2│2+…+│xn│2)1/2
∞-范数:║x║∞=max(│x1│,│x2│,…,│xn│)
其中2-范数就是通常意义下的距离。
对于这些范数有以下不等式:║x║∞ ≤ ║x║2 ≤ ║x║1 ≤ n1/2║x║2 ≤ n║x║∞
另外,若p和q是赫德尔(Hölder)共轭指标,即1/p+1/q=1,那么有赫德尔不等式:
|<x,y>| = ||xH*y| ≤ ║x║p║y║q
当p=q=2时就是柯西-许瓦兹(Cauchy-Schwarz)不等式
一般来讲矩阵范数除了正定性,齐次性和三角不等式之外,还规定其必须满足相容性:║XY║≤║X║║Y║。所以矩阵范数通常也称为相容范数。
如果║·║α是相容范数,且任何满足║·║β≤║·║α的范数║·║β都不是相容范数,那么║·║α称为极小范数。对于n阶实方阵(或复方阵)全体上的任何一个范数║·║,总存在唯一的实数k>0,使得k║·║是极小范数。
注:如果不考虑相容性,那么矩阵范数和向量范数就没有区别,因为mxn矩阵全体和mn维向量空间同构。引入相容性主要是为了保持矩阵作为线性算子的特征,这一点和算子范数的相容性一致,并且可以得到Mincowski定理以外的信息。
第四章 算法总结
本学期讲解过的主要算法列举如下:线性方程组的解法(高斯消元法,列主消元法,Doolittle分解法,追赶法,LDL'分解法,Jacobi分解法,Seidel迭代法);非线性方程的求根方法(二分法,简单迭代法,Newton迭代法,Newton+下山因子,Newton迭代法2,Newton非线性方程);矩阵特征值与特征向量的计算(householder矩阵,反幂法,幂法,QR分解);函数的插值方法(三次样条插值,Lagrange插值法,Newton差商插值法);最佳平方逼近(chebyshev最小二乘法,曲线拟合最小二乘法);数值积分与数值微分(simpson求积分式算法,Romberg算法,外推法);常微分方程初值问题的数值解法(欧拉改进法、龙格库塔法和修正的Adams法)。下面对主要算法进行分析。
4.1线性方程组的解法
本章学习了一些求解线性方程组的常用方法,其中Gauss消元法,列主元消元法,LU分解法,追赶法和LDL’分解法都是解线性方程组的直接方法;而Jacobi迭代法和SOR法则是解线性方程组的基本迭代法。求解线性方程组时,应该注意方程组的性态,对病态方程组使用通常求解方程组的方法将导致错误。迭代求精法可用于求解某些病态方程。
4.1.1高斯列主元LU分解法求解线性方程组
高斯消元法和LU分解法是直接法求解线性方程组中的两种方法。其中高斯消元法的基本思想是将线性方程组(1.1)通过消元,逐步化为同解的三角形方程组,然后用回代法解出n个解。高斯列主元消元法则是在高斯消元法的基础上提出的先选主元再消元的方法,避免了时消元无法进行或者是当的绝对值与其下方的元素的绝对值之比很小时,引起计算机上溢或产生很大的舍入误差而导致所求出的解失真的问题。LU分解法是将矩阵用一个下三角矩阵和一个上三角矩阵之积来表示,即,然后由,,得,将线性方程组的求解化为对两个三角形方程组和的求解,由此可解出线性方程组(1.1)的n个解。这两种求解线性方程组的方法在处理单个线性方程组时没有差别,只是方法的不同,但在处理系数矩阵相同,而右端项不同的一组线性方程组时,LU分解法就有明显的优势,因为它是将系数矩阵和右端项分开处理的,这样就可以只进行一次分解。例如,求解线性方程组,用高斯消元法求解的计算量大约为,而用LU分解求解的计算量约为,后者计算量显然小很多。但是LU分解法同样有可能由于的绝对值很小而引起计算机上溢或产生很大的舍入误差而导致所求出的解失真。因此提出了结合高斯列主元消元的LU分解法。
我们采用的计算方法是先将A矩阵进行高斯列主元消元,然后再计算相应的L矩阵和U矩阵(U矩阵就是经过n-1步消元后的A矩阵)。但要注意,第k步消元时会产生,从而可以得到L矩阵的第k列元素,但在下一步消元前选取列主元时可能会交换方程的位置,因此与方程位置对应的L矩阵中的元素也要交换位置。
4.2非线性方程组的求根方法
本章学习的二分法简单迭代法、Newton迭代法等方法,代表着求解非线性方程所采用的两类方法。大范围收敛方法的初值x0选取没有多少限制,只要在含根区间任选其一即可,二分法就是这类方法。局部收敛法要求x0要充分靠近根x*才能保证收敛,以简单迭代法为基础,Newton迭代法为代表的各类迭代法都属这类方法。
4.2.1Newton迭代法
牛顿迭代法的构造过程是这样的:设是的一个近似根,将在处作Taylor展开得,若取其前两项来近似代替,得近似方程的根,然后再对做上述同样处理,继续下去,一般若,则可以构造出迭代格式
此格式称为牛顿迭代格式,用它来求解的方法称为牛顿迭代法。
牛顿迭代法的几何意义是用在处的切线与轴得交点作为下一个迭代点的。由于这一特点,牛顿迭代法也常称为切线法。
牛顿迭代法虽然收敛很快,但它通常过于依赖初值的选取,如果选择不当,将导致迭代发散或产生无限循环。
4.3 矩阵特征值与特征向量的计算
本章学习了计算矩阵特征值和特征向量的三种常用的有效方法。
幂法是求矩阵的主特征值和对应特征向量的一种迭代方法。它在计算过程中原始举证A始终不变。这种方法简单方便,适用于任意类型的矩阵,特别适用于高阶稀疏矩阵。
QR算法是计算任意矩阵A的全部特征值的一种正交相似变换方法。它利用Househoder变换把矩阵A约化成一种上三角阵,所得三角阵的对角线的元就是所求矩阵的特征值。
Jacobi方法是另一种求矩阵特征值的变换法。它是把实对称阵A经过一系列正交旋转变换化为一个对角阵。对角阵的对角元就是A的特征值。
4.3.1 QR法求特征值
QR算法是目前求一般矩阵全部特征值最有效的方法。
其以基本步骤如下:
(1)令,对作QR分解: (4-1)
(2)将(4-1)右端逆序相乘,得到 (4-2)
(3)(4-2)式中对作QR分解,有,,以此类推
(4)得到矩阵序列,容易证明与相似,因而具有相同特征值。在一定条件下,收敛于上三角阵(或分块上三角阵),其对角元(或分块)有确定的极限。如果收敛于上三角阵,则主对角元就是的特征值;如果收敛于分块,则这些分块的特征值也就是的特征值。
4.4 函数的插值法
本章学习了插值多项式与样条插值函数的构造与误差,主要构造方法是利用插值基函数。插值多项式的两种形式各有特点,Lagrange插值适用于不等距节点的插值和导出数值计算公式。Newton插值使用与等距节点的插值及在插值中增加节点。由于高次插值的效果不好,实践中常用分段低次插值,特别是样条插值。样条函数是当前函数逼近中最活跃的一个分支,它在函数插值、数值积分、微分方程求解中都有重要应用。
4.4.1Hermite插值
设,。已知它在个互异点()上的函中求数值: 。
求解插值问题就是从函数类中求使:
这里称为被插函数,称为插值区间,称为插值结点,称为插值函数,称为插值函数类。误差函数称为插值余项,并以作为的估值,称为插值点,当属于包含结点的最小闭区间时,相应的插值称为内插,否则称为外插。
在附近,可用在处的阶Taylor展开式来近似函数
显然它与在处具有相同的函数值,以及1到阶导数值,即有
(4.31)
故可将阶的Taylor公式视为在处满足插值条件(4.31)的一种插值方法.
为在较大的范围内能更好的近似被插值函数,在实际应用中,不但要求在节点上插值函数与被插值函数有相同的函数值,而且要求在部分或者全部节点上一阶甚至更高阶的导数值也相同.这类插值称为Hermite插值。在一点处两个函数的函数值和一阶导数值相同,在几何上表现为两条曲线在该点有相同的切线;如果直至二阶导数值相同,则两条曲线在该点具有相同的凹凸性及曲率。可见,Hermite插值是一类更广泛的插值方法,Taylor公式可视为在处的Hermite插值。
在构造Hermite插值时,如给出的插值条件有个,则可以构造一个不超过次的插值多项式。
4.5最佳平方逼近
最小二乘曲线拟合是处理实验数据的常用方法。通常选取多项式为拟合函数,但此种拟合对应的法方程当阶数较高时,往往出现病态。为避免上述问题,可采用正交多项式。样条函数亦是一个很好的拟合模型,它既能保证有良好的逼近效果,又比较便于计算。
4.5.1Legendre最小二乘曲线拟合
曲线拟合问题就是从在实验中得到的对数据中找到一个经验公式。曲线拟合的最小二乘法实际上是离散数据下的最佳平方逼近,其提法为:给定对数据和一组权系数。设
是曲线拟合函数类,其中是线性无关的基函数。求
使得,若满足此式的解存在,则称为数据的最小二乘拟合函数。
常规的最小二乘拟合通常取,并取权系数,而Legendre最小二乘拟合是以Legendre正交多项式为基函数的,即,可解得
(5.1)
其中是带权内积,而可由如下递推公式得到:
(5.2)
则拟合的结果为,最小平方误差为
若所给区间不是[-1,1],而是[a,b],则可通过变换x=(a+b)/2+[(b-a)/2]t将其转换为-1<=t<=1上的情形处理,具体是现在程序中有所体现。
4.6 数值积分与数值微分
本章学习了数值积分与数值微分的计算方法,这些近似方法都是基于对函数作插值逼近,用插值函数的积分或微分近似原来函数的积分或微分。等距结点求积公式及其复合公式算法比较简单,程序易实现,特别是Romberg求积公式,当节点加密提高积分近似程度时,前面的结果可以为后面的计算使用,因此对减少计算量有好处。Gauss型求积公式是高精度求积公式,其节点是不规则的。通常在具有相同数目结点的情况下,它将大大优于其他等距节点求积公式。特别是计算无穷积分与旁义积分是其它方法不能比的。但使用gauss型求积公式要在计算机中存储节点和求积系数,计算过程也较麻烦。
4.6.1 数值积分
所谓数值积分方法,就是用一个足够精度的简单函数去近似被积函数,从而有
(1-6-1)
一般取为的插值多项式或分段插值多项式,因此得到
(1-6-2)
式(1-6-1)称为数值求积公式。称为求积数,它仅与有关,与被积函数无关。称为求积结点。
4.6.2 数值微分
根据函数在一些离散点的函数值,推算它在某点的导数或高阶导数的近似值的方法。通常用差商代替微商,或者用一个能够近似代替该函数的较简单的可微函数(如多项式或样条函数等)的相应导数作为能求导数的近似值。例如一些常用的数值微分公式(如两点公式、三点公式等)就是在等距步长情形下用插值多项式的导数作为近似值的。此外,还可以采用待定系数法建立各阶导数的数值微分公式,并且用外推技术来提高所求近似值的精确度。当函数可微性不太好时,利用样条插值进行数值微分要比多项式插值更适宜。如果离散点上的数据有不容忽视的随机误差,应该用曲线拟合代替函数插值,然后用拟合曲线的导数作为所求导数的近似值,这种做法可以起到减少随机误差的作用。数值微分公式是微分方程数值解法的重要依据。
4.7 常微分方程初值问题的数值解法
本章主要学习了求解常微分方程初值问题的两类数值解法:单步法与线性多步法。单步法中最常用的是R-K方法。它的特点是易于编程,易于调整步长,且稳定性好,不用提供辅助值,是自开始方法;但是它的精度的提高依赖于计算f(x,y)的次数。因此R-K方法适用于计算函数值不太复杂且精度要求不很高的问题。线性多步法具有计算函数值次数少,精度高的优点,并且它还宜于估计误差。所以在计算比较复杂时,推荐使用线性多步法。本章介绍了变步长的单步法,误差控制方法,它要求计算中固定方法的阶,若想在计算过程中提高方法的阶,则要用外推法。
4.7.1改进的Euler方法
利用原有的Euler方法,利用其结果,再利用梯形公式迭代一次就得到,这样的计算公式就是改进的Euler方法。其计算格式为
按上面第一个式子算出初值称为预测,按第二式迭代一次求出称为校正,这两个式子构成一个预测-校正公式。它可以改写成一个显示公式:
4.7.2 Runge-Kutta 方法
将改进Euler法改写成如下形式:
此为一单步、2阶、显式公式(比较梯形:2阶隐式)。若注意此处的,它们是两个不同的增量,Heun 方法则是从出发加上若干个增量的加权平均值后得到,将此推广到一般形式,出发加上个增量的加权平价取得,便有:-级Runge-Kutta公式
二级Runge-Kutta公式为:
常用的四阶四级Runge-Kutta公式(称为经典、古典或标准Runge-Kutta公式——Classical Runge-Kutta)
几何意义:若将上述公式改写为:
其中为分别为原式中中相应的函数值。比较在区间 上的数值积分Simpson公式
其中 分别表示在区间 的左、中、右端点的值;它们分别有:;因此可简略地得到该公式的误差公式是
第五章 算法界面制作
学期末,我运用VB环境制作界面,如图5.1所示
图5.1总结界面
由上图可以很直观地看到总结界面综合了本学期所有编写的程序,并且,在该界面环境下,根据程序设计的要求,允许修改程序及输入数据文件,支持修改后的编译连接,并可以在这个图形界面下面运行这学期编写的所有程序。对本学期所做工作做了一个很好的总结。
第六章 总结
通过对《数值计算方法》这门课程的理论学习以及以上一系列的程序编写,我不仅对数值计算方法的原理和和算法应用有了更近一步的了解,同时还对C语言的程序编写,编译和链接等方面有了进一步的掌握,对规模稍大的程序编写也积累了一定的经验。通过学习我已经对数值计算方法这门课程有了一定的了解,我相信有了这样实用的数学工具,在今后的学习生活中一定会给我带来狠多的帮助,我也会更加努力,争取更大的进步!!
这门课程分工合作的性质,增进了我与其他同学之间相互协作的能力。相信这些都会对我以后的自身发展有很大的帮助。在此,对陶老师课堂上的悉心指导表示衷心的感谢!
第七章 参考文献
[1]刘钦圣 张晓丹 王兵团. 数值计算方法教程. 北京:冶金工业出版社,2005.