数值计算方法教案

PAGE13《计算方法》教案课程名称：计算方法适用专业：医学信息技术适用年级：二年级任课教师：张利萍编写时间：2011年8月新疆医科大学工程学院张利萍教案目录TOC\o"1-3"\u《计算方法》教学大纲 3一、课程的性质与任务 3二、课程的教学内容、基本要求及学时分配 3三、课程改革与特色 4四、推荐教材及参考书 4《计算方法》教学日历 5第一章绪论 6第1讲绪论有效数字 6第2讲误差………………第二章线性方程组的直接法 12第3讲直接法、高斯消去法 13第4讲高斯列主元消去法 21第5讲平方根法、追赶法 27第三章插值法与最小二乘法 30第6讲机械求积、插值型求积公式 30第7讲牛顿柯特斯公式、复化求积公式 35第8讲高斯公式、数值微分 41第9讲第10讲第12讲第四章数值积分与数值微分 46第11讲欧拉公式、改进的欧拉公式 46第12讲龙格库塔方法、亚当姆斯方法 51第13讲收敛性与稳定性、方程组与高阶方程 54第14讲第15讲第五章微分常微分方程的差分方法 57第16讲迭代收敛性与迭代加速 58第17讲牛顿法、弦截法 62第18讲第19讲第20讲第六章线性方程组的迭代法 65第21讲迭代公式的建立 66第22讲第23讲第24讲向量范数、迭代收敛性 69第25讲《计算方法》教学大纲课程名称：计算方法/ComputerNumericalAnalysisB学时/学分：54/4先修课程：高等数学、线性代数、高级语言程序设计（如：Matlab语言）适用专业：计算机科学与技术、信息管理与信息系统开课学院（部）、系(教研室)：医学工程技术学院、医学信息技术专业一、课程的性质与任务计算方法是一门专业必修课。当前，由于科学技术的快速发展和计算机的广泛应用，学习和掌握计算机上常用的数值计算方法及有关的基础理论知识，并能用某种高级语言（如Matlab语言）将这些常用算法编程实现，这对于计算机专业的学生来说是非常重要的。本课程着重介绍进行科学建设所必须掌握的一些最基本、最常用的算法，向高等院校有关专业的学生普及计算方法的知识。二、课程的教学内容、基本要求及学时分配（一）教学内容1．引论数值分析的研究对象、误差及有关概念、数值计算中应注意的一些原则。2．线性代数方程组的数值解法Gauss消去法、Gauss消去法的矩阵形式、主元消去法、三角分解法、迭代法、迭代法的收敛条件及误差估计。3．插值方法Lagrange插值、Newton插值、分段插值、Hermite插值、三次样条插值、数据拟合的最小二乘法。4．数值积分与微分机械求积、Newton-Cotes求积公式、复化求积、Romberg求积算法、Gauss求积公式、数值微分。5．常微分方程初值问题的数值解法Euler方法及其改进、龙格-库塔(Runge-Kutta)方法、线性多步法、收敛性与稳定性、一阶方程组与高阶方程。6．方程求根的数值方法二分法、迭代法、迭代过程的加速、Newton迭代法、Newton迭代法的几种变形。（二）基本要求1．了解数值分析的研究对象、掌握误差及有关概念。2．正确理解使用数值方法求方程的解的基本思想、数学原理、算法设计。3．了解插值是数值逼近的重要方法之一，正确理解每一种算法的基本思想、计算公式、算法设计、程序框图设计和源程序。4．掌握数值积分的数学原理和程序设计方法。5．能够使用数值方法解决一阶常微分方程的初值问题。6．理解和掌握使用数值方法对线性方程组求解的算法设计。（三）学时分配本课程的理论教学时数为54学时分配如下表：教学环节课程内容学时讲课引论4线性代数方程组的数值解法6插值方法12数值积分与微分10常微分方程初值问题的数值解法10方程求根的数值方法10总复习2合计54（四）课程内容的重点、难点重点：Lagrange插值、Newton插值、分段插值、Hermite插值、三次样条插值、机械求积、Newton-Cotes求积公式、复化求积、Romberg求积算法。难点：Gauss消去法、Gauss消去法的矩阵形式、主元消去法、三角分解法、迭代法、迭代法的收敛条件及误差估计。三、课程改革与特色本课程是一门重要的专业基础课。数值计算方法既是一门古老的学科，又是一门新兴的学科。电子计算机的产生和发展极大地促进了数值计算方法的发展。只有把数值计算方法和程序设计紧密结合起来，把算法变为计算机能直接执行的程序，才能真正使计算机帮助人们解决各种复杂的计算任务。本课程试图将数值计算方法和程序设计方法学融为一体，这也是一种尝试。四、推荐教材及参考书推荐教材：《计算机数值方法》（第三版），主编：施吉林、刘淑珍、陈桂芝，出版社：高等教育出版社，出版时间：2005年3月参考书：《数值计算方法和算法》，主编：张韵华、奚梅成、陈效群，出版社：科学出版社，出版时间：2002年3月《NumericalAnalysis》，主编：RichardL.Burden，出版社：高等教育出版社影印，出版或修订时间：2003《数值分析》，主编：金聪、熊盛武，出版社：武汉理工大学出版社，出版时间：2003年8月第一章绪论一、教学目标及基本要求通过对本章的学习，使学生对了解涉及工程和科学实验中常见的数学问题，其中包括线性方程组、函数插值、离散数据的拟合、微积分、微分方程等，这些问题是其他数学问题的基础。二、教学内容及学时分配本章主要介绍数值分析的研究对象及误差的概念。具体内容如下：第1-2学时讲授内容：计算方法的研究内容、对象与特点；误差的基本概念。三、教学重点难点1．教学重点：误差、误差种类；误差分析：误差与有效数字的关系。2.教学难点：误差分析、误差与有效数字的关系。四、教学中应注意的问题多媒体课堂教学为主。适当提问，加深学生对概念的理解。第1讲绪论基本求解步骤实际问题实际问题建立数学模型构造数值算法编程上机计算结果数学模型是通过科学实验或者观察分析一系列数据后，用数学作为工具近似地描述客观事物的一种数学表达式。在数学模型中，往往包含了若干参量，这些物理参数通常由实验仪器测得，根据仪器的精密程度，物理参数的确定也会产生一定的误差。在建立了数学模型之后，并不能立刻用计算机直接求解，还必须寻找用计算机计算这些数学模型的数值方法，即将数学模型中的连续变量离散化，转化成一系列相应的算法步骤，编制出正确的计算程序，再上机计算得出满意的数值结果。算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。例1需乘法5次，加法3次。需乘法3次，加法3次。一般地，计算n次多项式的值如若按有次乘法运算,计算共需次乘法和次加法运算。采用：秦九韶算法(1247)有递推公式:从内往外一层一层计算，社需乘法n次，加法n次，存储单元n+3个。YYN开始输入k=n输出v结束对算法所要考虑的问题,包括如下:计算速度例如,求解一个20阶线性方程组,用消元法需3000次乘法运算；而用克莱姆法则要进行次运算,如用每秒1亿次乘法运算的计算机要30万年。存储量大型问题必要考虑计算机的数据存贮。数值稳定性在大量计算中,舍入误差是积累还是能控制,这与算法有关。实际算法往往表现为某种无穷递推过程算法的精度控制方程根的二分法求解若，则为所求根否则若,则根在区间，取若,则根在区间，取每一区间为前一区间的一半，有根区间长度§1.2预备知识和误差(1)误差的来源实际问题è建立数学模型è研究计算方法è编程上机计算解结果。模型误差:在建立数学模型过程中,不可能将所有因素均考虑,必然要进行必要的简化,这就带来了与实际问题的误差。测量误差:测量已知参数时,数据带来的误差。截断误差:模型的准确解与某种数值方法的准确解之间的误差称为截断误差或方法误差。舍入误差:计算机的字长是有限的,每一步运算均需四舍五入,由此产出的误差称舍入误差。如：π、1／3，……取小数点8位、16位。[截断误差的实例]解：利用展开式的前三项，取n=2，截断误差为：0.17[舍入误差的实例]，设在一台虚构的4位数字的计算机上计算，舍入误差为0.000472。数值计算方法主要讨论截断误差和舍入误差的影响,不讨论模型误差和测量误差。三、误差的基本概念(1)误差与误差限误差不可避免，设以代表数的近似值，称是近似值的绝对误差。简称误差。误差是有量纲的,可正可负。误差通常是无法计算的,但可以估计出它的一个上界。即称是近似值的误差限，或称精度，即。(2)相对误差与相对误差限绝对误差并不能完全反应精度，称为近似值的相对误差,记作。相对误差是个相对数,是无量纲的,也可正可负。相对误差的估计,称为相对误差限,即。(3)有效数字定义:如果近似值的误差限是(某一数位的半个单位),则称准确到小数点后n位,并从第一个非零的数字到这一位的所有数字均为有效数字。如：π＝3.1415926535,3.14有三位有效数字,误差限ε=0.005;3.1416有五位有效数字,误差限为0.00005。(4)有效数字与误差限的关系：有n位有效数字，标准形式为其中ai(i=1,2,…)是0~9之间的整数,且,如果误差，称为的具有l位有效数值的近似值.(5)有效数字与相对误差的关系：标准形式为，则：a)证：b)，则证：例，已知，试问其近似值各有几位有效数字？并给出它们的误差限和相对误差限。，十分位以前都是有效数字，有两位有效数字有三位有效数字，有四位有效数字，有五位有效数字例：为使π*的相对误差小于0.001%,至少应取几位有效数字？解：，则π*=3.14159§1.3数值计算的若干原则避免两相近数相减当x较大时，计算，可先转化为,精确值令h=0.1得令h=0.0001得计算，分子出现相近数相减，可转换为，再计算2.避免绝对值太小的数做除数分母接近零的数会产生溢出错误,因而产生大的误差,此时可以用数学公式化简后再做.3.要防止大数“吃掉”小数计算机在进行算术计算时,首先要把参加运算的数对阶，即把两数都写成绝对值小于1,而阶码相同的数。如：必须改写成:如果计算机只能表示8位小数，则算出,大数吃掉了小数。这种情形是要尽量避免的。4.简化计算步骤，提高计算效率简化计算步骤是提高程序执行速度的关键，它不仅可以节省时间，还能减少舍入误差。例4：设A、B、C、D分别是10´20、20´50、50´1、1´100的矩阵，试按不同的算法求矩阵乘积E=ABCD.解：由矩阵乘法的结合律，可有如下算法1.E=((AB)C)D.计算量N=11500flop2.E=A(B(CD)).计算量N=125000flop3.E=(A(BC))D.计算量N=2200flop5.要使用数值稳定的算法我们已经知道，所谓算法的稳定性，是指误差的传播可以得到控制，在用计算机解决实际问题时，运算次数成千上万。如果误差的传播得不到控制，那么误差的累积会使问题的解答成为荒谬的，尤其是某些病态问题（如病态方程组），舍入误差对其计算结果往往有非常严重的影响。因此，在选择计算方案时，要特别谨慎。考察方程组解为四舍五入系数后，解为尽管系数变动不大，但求出得解却变动很大，这类问题称为病态的。例：蝴蝶效应（气象学家洛伦兹，1963）——南美洲亚马孙河流域热带雨林中的一只蝴蝶翅膀一拍，偶尔扇动几下翅膀，可能在两周后引起美国德克萨斯引起一场龙卷风？！第二章插值法一、教学目标及基本要求通过对本章的学习，使学生掌握插值法计算常见的数学问题。二、教学内容及学时分配本章主要介绍数值分析的插值法。具体内容如下：第3-4学时讲授内容：问题的提法、拉格朗日插值公式。第5-6学时讲授内容：插值余项、牛顿插值公式。第7-8学时讲授内容：曲线拟合。三、教学重点难点1．教学重点：插值方法的由来、拉格朗日插值公式、牛顿插值公式、曲线拟合。2.教学难点：拉格朗日插值公式、牛顿插值公式。四、教学中应注意的问题多媒体课堂教学为主。适当提问，加深学生对概念的理解。第2讲拉格朗日插值公式众所周知，反映自然规律的数量关系的函数有三种表示方法：解析表达式.(开普勒(Kepler)方程).。悬链线方程:。图象法表格法1、插值法对于一组离散点，选定一个便于计算的简单函数，如多项式函数，要求满足，由此确定函数作为的近似函数，然后通过处理获得关于的结果。这就是插值方法。2、曲线拟合选定近似函数时，不要求近似函数必须满足，而只要求在某种意义下（最小二乘法原理），使近似函数在这些点上的总偏差量最小，这类方法成为曲线拟合。§1.1多项式插值问题的一般提法插值法的概念:假设函数y=f(x)是[a,b]上的实值函数，x0,x1,…,xn是[a,b]上n+1个互异的点，f(x)在这些点上的取值分别为y0,y1,…,yn,求一个确定的函数P(x),使之满足:P(xi)=yi(i=0,1,2,…,n)(1)称x0,x1,…,xn为插值节点，关系式(1)称为插值原则，函数P(x)称为函数y=f(x)的插值函数，区间[a,b]称为插值区间。泰勒插值：人们熟悉的泰勒展开方法其实就是一种插值方法，泰勒多项式：（1）与在点邻近会很好的逼近。泰勒余项定理:定理1假设在含有点的区间[a,b]内有直到n+1阶导数，则当时，对于式（1）给出的，成立其中介于与x之间，因而。所谓泰勒插值指下述问题：问题1求作n次多项式，使满足，为一组已给数据。易看出，上述插值问题的解就是泰勒多项式（1）。例1例题分析:求作在的一次和二次泰勒多项式，利用它们计算的近似值并估算误差。解：，，，，，，在的一次泰勒多项式是时根据定理1可估计误差误差小于十分位的一半，故十分位及前面的数字为有效数字，所以结果有三位有效数字。修正可进一步得到二次泰勒公式误差小于百分位的一半，故百分位及前面的数字为有效数字，所以结果有四位有效数字。泰勒插值是一种有效的插值方法，对函数要求严格（要足够光滑，存在高阶导数），要计算函数的高阶导数，而高阶导数的计算对计算机来说就很困难；另外，计算过程不能形成机械重复的过程，不利于计算机程序实现。§1.2拉格朗日(Lagrange)插值多项式插值的存在惟一性:多项式导数易于计算，函数表达式简单，计算机易于计算，故考虑用多项式函数作为插值函数来模拟实际函数。从如下数据表着手,并假定，xx:x0x1x2…xny:y0y1y2… yn求n次多项式,使得：P(xi)=yi(i=0,1,2,…,n)。根据插值条件，有：(1)显然，这是一个关于的n+1元线性方程组，其系数矩阵的行列式为注意到插值节点两两相异，而故方程组(1)有惟一解,于是满足插值条件的多项式存在且惟一。定理由n+1个不同插值节点可以惟一确定一个n次多项式满足插值条件。从理论上说，由方程组(1)可以求出的惟一解,从而确定。但从数值计算上看，当n较大时求解线性方程组的工作量较大且不便应用。解方程组（1）需计算n+1个n阶行列式，每个n阶行列式为n!项之和，每项又是n个元素的乘积，需n-1次乘法，所以求解需要次乘法，当n较大时，计算量非常大。为解决此问题，现已提出了不少构造的巧妙办法。Lagrange插值的基函数构造法首先讨论n=1时的情形。已知，求使得显然是过和两点的一条直线。由点斜式容易求得其中，具有如下特点：称其为线性插值基函数。可以通过函数组合得出，且组合系数恰为所给数据y0,y1。再讨论n=2时的情形。显然是过、、三点的一条抛物线。仿照线性插值基函数的构造方法，令其中，具有如下特点：称其为抛物线插值基函数(如下图所示)。于是，最后讨论一般情形。求Ln(x)使得L(xi)=yi(i=0,1,2,…,n)。令n次多项式插值基函数为:,具有如下特点：。于是，满足插值条件的n次多项式可以直接写为:我们称Ln(x)为Lagrange多项式，其Lagrange插值基函数。YYN开始输入k=n输出y结束思考给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？插值余项如图所示，其截断误差Rn(x)=f(x)-Ln(x)，称为Lagrange插值多项式的余项。定理假设f(x)在[a,b]上有连续的直到n+1阶导数，且在不同插值节点取值为,是经过插值样点的Lagrange插值多项式，若引进记号：则当时，有如下的误差估计：证明：因为于是可假定具有如下形式：将x看作(a,b)上的一个固定点，作辅助函数容易看出，有共n+2个相异零点,且在[a,b]上存在n+1阶导数。根据罗尔,在的两个零点之间至少有一个零点，故在[a,b]上至少有n+1个零点。如此类推,在(a,b)上至少有1个零点,使得注意到是n次多项式，；的首项为，故。由上述方程解得。于是例题例1已知函数y=f(x)的观察数据为xk－2045yk51－31试构造f(x)的拉格朗日多项式Ln(x)，并计算f(－1)。 解先构造基函数所求三次多项式为 L3(x)=＝＋-＋ ＝ L3(－1)＝第3讲牛顿公式§1.4差商与差分及其性质1差商的概念:称为函数f(x)的一阶差商；称为函数f(x)的二阶差商；一般地，称为函数f(x)的n阶差商；特别地，定义为函数f(x)关于xo的零阶差商。由此可知，高阶差商总是由比它低一阶的的两个差商组合而成。2差商性质（a）性质1:n阶差商可以表示成n+1个函数值的线性组合,即该性质说明：k阶差商计算是由函数值f(x0),f(x1),…f(xk)线性组合而。如:；(b)性质2(对称性):差商与节点的顺序无关。即，这一点可以从性质1看出。3利用差商表计算差商利用差商的递推定义,可以用递推来计算差商。差商表：一阶差商二阶差商三阶差商如要计算四阶差商,应再增加一个节点,表中还要增加一行。4差分的概念定义设函数y=f(x)在等距节点上的函数值f(xi)=fi,其中，h为常数称作步长。称△fi=fi+1-fi▽fi=fi-fi-1δfi=f(xi+h/2)-f(xi-h/2)=分别为f(x)在处以h为步长的一阶向前差分，一阶向后差分和一阶中心差分。称符号△、▽、δ分别为向前差分算子，向后差分算子和中心差分算子。在节点等距情况下，差商可用差分表示，设步长，有一般形式(数学归纳法可证)§1.5牛顿插值公式1.牛顿插值公式的构造Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。本节介绍另外一种方法-牛顿插值法，并用它解决上面所述问题。由线性插值，令二次插值能否写成由条件得推广得,其中，为待定系数。如何求?解:因为,所以(0)又,有(1)又(2)一般地,(n)将式(n)代入式(n-1),...,式(2)代入式(1),式(1)代入式(0),如此可得:尤为注意的是：最后一项中,差商部分含有,乃是余项部分,记作;而前面n+1项中,差商部分都不含有,因而前面n+1项是关于的n次多项式,记作,这就是牛顿插值公式。2算例例1:当n=1时，,其中, 。这就是牛顿一次插值多项式，也就是点斜式直线方程。当n=2时, 这就是牛顿二次插值多项式。显然,, 。即满足二次插值条件。例2:已知1247011512求满足以上插值条件的牛顿型插值多项式。解:由于:,,,;则牛顿三次插值多项式为。拉格朗日插值与牛顿插值的比较(1)和均是n次多项式,且均满足插值条件:。由多项式的唯一性,,因而,两个公式的余项是相等的,即(2)当插值多项式从n-1次增加到n次时,拉格朗日型插值必须重新计算所有的基本插值多项式;而对于牛顿型插值,只需用表格再计算一个n阶差商,然后加上一项即可。4等距牛顿插值公式插值节点为等距节点：，,如下图：hhh...h...牛顿插值公式设等距节点，记.当，令，.例如（下图）x在x2，x3的中点时，。将牛顿插值公式中的差商用差分代替,而从而,牛顿插值公式在等距插值节点下的形式为:余项为这是等距牛顿向前插值公式。例4:设插值节点为,相应的函数值如下表,求f(2.2)。xiyiΔyiΔ2yiΔ3yiΔ4yi12.718281.763411.143960.742100.481461.54.481692.907371.886061.2235627.289064.793433.109622.512.182497.90305320.08554解：精确值f(2.2)=e2.2=9.025011。此时[xk,xk+1],x=2.2=1+2.4h故t=2.4,于是求时，在后加一项：，所以求时，在后再加一项：，所以第4讲曲线拟合§1.9曲线拟合的最小二乘法1拟合问题的数学提法通过观测、测量或试验得到某一函数在的函数值。我们可以用插值的方法对这一函数进行近似,而插值方法要求所得到的插值多项式经过已知的这n个插值结点;在n比较大的情况下,插值多项式往往是高次多项式,这也就容易出现振荡现象:虽然在插值结点上没有误差,但在插值结点之外插值误差变得很大,从“整体”上看,插值逼近效果将变得“很差”。于是,我们采用曲线拟合的方法。所谓曲线拟合是求一个简单的函数,例如是一个低次多项式,这儿不要求通过已知的这n个点,而是要求在整体上“尽量好”的逼近原函数。这时,在每个已知点上就会有误差,,数据拟合就是从整体上使误差,尽量的小一些。x1x1x2x3……xn-1xn如果要求达到最小，因误差可正可负,本来很大的误差可能会正负抵消,为防止正负抵消,可以要求达到最小,但是由于绝对值函数不可以求导，分析起来不方便,求解也很难。为了既能防止正负抵消,又能便于我们分析、求解，提出如下问题：求一个低次多项式,使得达到最小,此问题便是一个曲线拟合的最小二乘问题。1直线拟合（一次函数）a)问题的提法通过观测、测量或试验得到某一函数在的函数值，即得到n组数据,如果这些数据在直角坐标系中近似地分布在一条直线上，我们可以用直线拟合的方法。问题:已知数据,求一个一次多项式（实际上，就是求a,b）,使得达到最小注意到中,均是已知的，而a,b是未知量,是未知量a,b的二元函数,利用高等数学中求二元函数极小值(最小值)的方法，因此，上述问题转化为求解下列方程组b)正则方程组由得：得到如下的正则方程组这是个关于a,b的二元一次方程组，称其为最小二乘问题的正则方程组.解得a,b,便得到最小二乘问题的拟合函数。c)算例已知10对数据如下表,利用最小二乘法求拟合曲线。解：先列表来计算四个：形成正则方程组解得，于是，最小二乘拟合一次函数为。第三章数值积分一、教学目标及基本要求通过对本章的学习，使学生掌握积分的数值解法。二、教学内容及学时分配本章主要介绍积分的数值解法。具体内容如下：第9-10学时讲授内容：机械求积、插值型求积公式。第11-12学时讲授内容：牛顿柯特斯公式、复化求积公式。第13-14学时讲授内容：高斯公式、数值微分。三、教学重点难点1．教学重点：机械求积、牛顿柯特斯公式；复化求积公式；高斯公式。2.教学难点：复化求积公式；高斯公式。四、教学中应注意的问题多媒体课堂教学为主。适当提问，加深学生对概念的理解。第5讲机械求积、插值型求积公式2.0引言1.定积分的计算可用著名的牛顿-莱布尼兹公式来计算:其中F(x)是f(x)的原函数之一，可用不定积分求得。然而在实际问题中，往往碰到以下问题：1）被积函数f(x)是用函数表格提供的；2）被积函数表达式极为复杂，求不出原函数，或求出原函数后，由于形式复杂不利于计算；3）大量函数的原函数不容易或根本无法求出，例如概率积分，正弦型积分，等根本无法用初等函数来表示其原函数，因而也就无法精确计算其定积分，只能运用数值积分。2.所谓数值积分就是求积分近似值的方法。§2.1机械求积公式1数值积分的基本思想基本思想：定积分的几何意义：曲线，直线与x轴所围成得曲边梯形得面积，无论被积函数是什么形式，只要近似计算曲边梯形面积，就可求定积分的值，这就是数值求积的基本思想。积分中值定理，点具体值未知，只要对平均高度提供一种数值算法，相应就求得一种数值求积方法。（1）用f(x)的零次多项式来近似代替,于是，（为左矩公式）（为右矩公式）（为中矩公式）（2）用f(x)的一次多项式来近似代替,于是，（为梯形公式）（3）用f(x)的二次插值多项式,其中来近似代替,于是，特别地：当时，有（为Simpson公式）一般在区间[a,b]上的定积分，就是在区间[a,b]内取n+1个点，利用被积函数f(x)在这n+1个点的函数值的某一种线性组合来近似作为待求定积分的值，即右端公式称为左边定积分的某个数值积分公式。其中,xk称为积分节点，Ak称为求积系数。因此，一个数值积分公式关键在于积分节点xk的选取和积分系数Ak的决定，其中Ak与被积函数f(x)无关，称为机械求积公式。2代数精确度定义：若积分的数值积分公式对于任意一个次数不高于m次的多项式都精确成立，且存在一个m+1次多项式使之不精确成立，则称该数值积分公式的代数精确度为m。对于代数精确度为m的求积公式，若f(x)是不超过m次的代数多项式，求积公式是精确成立的。一般地，要使具有n次代数精度，只要令它对于都准确成立,也就是对给定n+1个互异节点，相应的求积系数满足：方程组的系数行列式是范德蒙行列式，当互异时，其值非零，利用克莱姆法则可以惟一的求出进而可以构造出求积公式，于是，有如下结论：对于任意给定n+1个互异节点总存在相应系数使至少具有n次代数精度。例：在如下求积公式中，求积分节点和相应的求积系数使其代数精确度尽可能高。解：(1)f(x)=1,,而数值积分为；得到方程；(2)f(x)=x，，而数值积分为；得到方程；(3)，，而数值积分为；得到方程；(4)，，而数值积分为；得到方程；综合上述方程：解得:。于是我们得到积分公式。再取，有，而数值积分为，两式不相等，求积公式不精确成立了。所以，该积分公式的代数精确度为3。2.1.3插值型的求积公式用求线性方程组的方法构造求积公式计算量太大，现在，用插值多项式来构造数值求积公式。设在互异节点处的函数值为，则可构造拉格朗日插值多项式：由于代数多项式的原函数容易求出，可取:(1)(2)我们称求积系数由(2)式确定的求积公式称为插值求积公式。其余项为：当被积函数取次数不超过n次多项式时，由于，所以余项，这说明求积公式对一切次数不超过n次的多项式精确成立，所以对有n+1个互异节点的插值型求积公式至少具有n次代数精度。反之，如果求积公式至少有n次代数精度，则它对于n次插值基函数也是准确成立的，即有:，因而（2）成立，这说明至少有n次代数精度的求积公式必为插值型的。综上所述，有如下结论：定理求积公式是插值型求积公式的充分必要条件是它至少具有n次代数精度。这样，给定求积节点，求积系数可通过求解线性方程组或通过插值函数计算。例1，已知，推导以这三个点为求积节点，在[0,1]上的插值型求积公式；求其代数精度例2P80题2第6讲牛顿柯特斯公式、复化求积公式§2.2Newton-Cotes公式1公式的推导Newton-Cotes公式是由拉格朗日插值公式推导出来的数值积分公式。将区间[a,b]等分n等份,记,分点为,k=0,1,...,n,这n+1个节点上的函数值为,从而区间[a,b]上的拉格朗日插值多项式为由于插值结点是等距节点，故插值多项式可以进一步化简:因为，故，因，作积分变量代换，，当x=a时，t=0；当x=b时，t=n；故记，我们称为柯特斯（Cotes）系数，它不仅与函数f(x)无关，而且与积分区间[a,b]无关。例如：当n=1时(梯形积分公式中的系数),;当n=2时(抛物线积分公式中的系数),,;当n=4时柯特斯公式于是，由柯特斯（Cotes）系数公式出发，我们得到n阶Newton—Cotes公式：。柯特斯公式市节点等距条件下的插值型求积公式，至少具有n次代数精度，当n为偶数时，能达到n+1次代数精度。（可以证明）从表中看出n=8时，出现负数，稳定性没保证，所以一般采用n=4的牛顿-柯特斯求积公式。2低阶公式及其余项常用的Newton—Cotes公式a)梯形公式n=1时，积分节点为，，则数值积分公式为：其几何意义是曲边梯形的面积近似地用梯形面积来代替。其余项b)抛物线公式（辛浦生Simpson公式）n=2时，积分节点为x0=a，，x2=b；柯特斯系数为；则数值积分公式为:其几何意义是曲边梯形的面积近似地用由抛物线形成的曲边梯形面积来代替。其余项c)柯特斯公式n=4时，积分节点为，，；柯特斯系数为,；则数值积分公式为：其余项综上所述，Newton-Cotes数值积分公式具有如下特点：(1)建立在等距积分节点上，(2)是封闭型的，即两个端点a,b也是积分节点，(3)是由拉格朗日插值公式推导而得到的。3Cotes系数的性质引理:Newton—Cotes公式的代数精确度至少是n。证明:如果是一个次数不超过n次的多项式，则其拉格朗日插值公式的插值余项为：故，这是对一切x均相等，精确成立。所以，即，数值积分公式的值精确地等于定积分的值，故n阶Newton—Cotes公式的代数精确度至少是n。性质1:归一公式：证明：由于数值积分公式的代数精确度至少为n，故对于，数值积分公式是精确成立的：，而由上述两式相等，得到：性质2:对称性：。定理Newton—Cotes公式中，n为奇数时，代数精度为n，n为偶数时，代数精度为n+1。(用求积公式余项来证明)4复化求积法随着n的增加可以减少积分误差，但高阶N-C公式又会造成数值不稳定。另外，通过求积公式的余项可以看出，截断误差与积分区间长度关系很大。通常将积分区间划分成若干小区间，每个小区间采用次数不高的求积公式，再将它们加起来，这类方法称为复化求积法。复化梯形公式 将区间等分n等份,,分点是(k=0,1,...,n),其中。在每个子区间上用梯形公式则此公式就是复化梯形公式。余项：梯形公式余项为复化梯形公式由定积分定义故复化新甫生公式在每个小区间上用辛普生公式，记的中点为，得此公式就是复合辛浦生公式。余项：复化柯特斯公式每个小区间四等分，记为，得此公式就是复化柯特斯公式。余项：算例分别利用梯形公式和Simpson公式计算积分：。解：设,步长h=1/8由复合梯形公式有：由复合Simpson公式有(步长h=1/4)：积分的相对精确值为。第7讲高斯公式、数值微分2.4Gauss公式1引言牛顿—柯特斯型求积公式是封闭型的（区间[a,b]的两端点a,b均是求积节点）而且要求求积节点是等距的,受此限制，牛顿—柯特斯型求积公式的代数精确度只能是n(n为奇数)或n+1(n为偶数)。而如果对求积节点也适当的选取,即在求积公式中不仅而且也加以选取,这就可以增加自由度，从而可提高求积公式的代数精确度。2．高斯求积公式和高斯点例:其中,固定在,可以适当选取,得到的是梯形公式,其代数精确度只有1。如果对求积节点也进行适当选取,得到如下公式:这个积分公式的代数精确度为3,这就是高斯型求积公式,上面的求积节点称为高斯点。定义1：高斯型求积公式和高斯点对于含有2n+2个参数的求积公式:,适当选取这2n+2个参数,可以使得数值积分公式的代数精确度达到2n+1,我们称这一类求积公式为高斯型求积公式，称这类求积公式的积分节点为高斯点。定义2:如果n+1个求积节点的求积公式的代数精确度为2n+1,则这n+1个求积节点称为高斯点。高斯公式求积区间为[-1，1]，对于任意求积区间[a,b]，可通过变换：，可以转到区间[-1,1]上，这时：求积公式写为由于式是插值型求积公式，只要节点确定了，求积系数也随之确定，因此，解决问题的关键在于节点的选取，即构造高斯求积公式的关键是求高斯点。3.高斯点的特征定理:插值型求积公式中，节点为高斯点的充分必要条件是：在区间[-1,1]上，以这些点为零点的n+1次多项式与任意的次数都不超过n的多项式正交，即：证明:(必要性)设为高斯点,则对于任意次数不超过次多项式,是次数不超过次的多项式,高斯公式对是准确成立的，且注意到,故。可见以高斯点为零点的n+1次多项式与一切次数不超过n的多项式正交。(充分性)设对于一切次数不超过次的多项式,成立，又设是次数不超过次的多项式,用去除,商,余,即,可知,和均是不超过n次的多项式,从而由正交条件有又因求积公式是插值多项式的构造导出的,由的选取,其代数精确度可以达到n,而是次数不超过n次的多项式,因此成立又注意到由于是次数不超过次的多项式,因此该积分公式的代数精确度至少为,因而节点是高斯点。可以根据正交条件直接求得高斯点，但涉及解线性方程组，需要寻找新方法。高斯—勒让德求积公式Legendre多项式称为勒让德(Legendre)多项式。其具有前面提到的正交性质,即对于任意次数不超过的多项式,成立。因此,多项式的零点就是相应的高斯—勒让德求积公式的高斯点。勒让德多项式的前几项如下:,,当取一个节点时，因，其零点为，以为节点，其公式为，令其对精确成立，得，所以，高斯－勒让德求积公式为：(一点高斯公式)当取两个节点时，因其零点为，。以为节点构造其公式为：令其对都精确成立，得从而得两点高斯－勒让德公式：(两点高斯公式)当取三个节点时，因其零点为，，。以为节点构造其公式为：令其对都精确成立，得例用三个节点的高斯－勒让德求积公式，求解：积分区间是[0,1]，先做变换：,把区间[0,1]化为[-1,1]上的积分，有：用复合梯形求积公式计算，对积分区间二分11次，用2049个函数值，才取得7位有效数字，用龙贝格积分公式，对积分区间二分三次，用了9个函数值，取得了同样的结果。本例仅用了三个函数值，取得同样结果，这说明高斯求积公式的精度是非常高的。2.5数值微分1中点公式按照定义，导数是差商当时的极限，若要求精度不高，则可将差商作为导数的值，如此可得：向前差商公式：向后差商公式：中心差商公式：由图P76可以看出，三种导数的近似值分别表示弦线AB,AC和BC的斜率，而导数值表示切线AT的斜率,其中以BC的斜率更接近切线AT的斜率，因此，通常取中点公式来求导。为了对中点公式进行误差分析，将在处泰勒展开，有：从截断误差的角度来看，步长越小，计算结果越准确，但从舍入误差的角度来看，当h很小时，由于很接近，直接相减会造成有效数字的严重损失。实际计算时，通常在变步长的过程中实现步长的自动选择。例P77用变步长的中点方法求在的导数值，步长从h=0.8算起。2中点方法的加速为了提高中点方法的速度，可以利用外推算法的思想进行加速。将步长折半，令同理，令，可得例用加速公式求在的导数值，步长从h=0.8算起。hG(h)G1(h)G2(h)G3(h)0.83.017650.42.791352.7159170.22.736442.7181372.7182850.12.722812.7192672.7182762.718283插值型求导公式设已知在节点上的函数值，可作n次插值多项式，并取的值作为的近似计算，即：上式称为插值型求积公式。但是，即使与处处相差不大，但与可能在某些点差别很大，需要特别注意误差分析。由于是x的未知函数，对任意给定处的点x，上式第二项无法求出。但是，如果只求其某个节点上的函数值，则上式第二项因，有余项公式：设已给出三个节点上的函数值，可作2次拉格朗日插值多项式：分别取，得带余项的三点求导式第二式，由于少用了一个函数值且精度比其他两个高，而引人关注。但必须指出，当插值多项式收敛于时，不能保证一定收敛于，而且当节点间的距离缩小时，虽然截断误差缩小了，但舍入误差却可能增大，因此，缩小步长不一定能提高计算结果的精确度。例已知函数的下列数值。x00.900.991.001.011.1021.0002.4602.6912.7182.7463.0047.389计算的近似值，并比较步长。h分别取1，0.1，0.01解：（1）（2）（3）真值为2.7182818上式的计算结果表明，当步长由1减少到0.1时，计算精度明显提高，但是当步长由0.1减少到0.01时，精度反而有所下降，问题的根源在于实际计算时，不但有截断误差，而且还有舍入误差，而数值微分恰好对舍入非常敏感，它随h的缩小而增大，这就是计算的不稳定性，所以，在计算数值微分时，一定要进行误差分析。第四章常微分方程的差分方法一、教学目标及基本要求通过对本章的学习，使学生掌握常微分方程、常微分方程方程组的数值解法。二、教学内容及学时分配本章主要介绍常微分方程的数值解法。具体内容如下：第15-16学时讲授内容：欧拉公式、改进的欧拉公式。第17-18学时讲授内容：龙格库塔方法、亚当姆斯方法。第19-20学时讲授内容：收敛性与稳定性、方程组与高阶方程。三、教学重点难点1．教学重点：改进的欧拉公式、龙格库塔方法、收敛性与稳定性。2.教学难点：收敛性与稳定性。四、教学中应注意的问题多媒体课堂教学为主。适当提问，加深学生对概念的理解。第8讲欧拉公式、改进的欧拉公式§3.0引言1．主要考虑如下的一阶常微分方程初值问题的求解:微分方程的解就是求一个函数y=y(x)，该函数满足微分方程并且符合初值条件。例如微分方程:xy'-2y=4x；初始条件:y(1)=-3。于是可得一阶常微分方程的初始问题。显然函数y(x)=x2-4x满足以上条件,因而是该初始问题的微分方程的解。3.但是,只有一些特殊类型的微分方程问题能够得到用解析表达式表示的函数解，而大量的微分方程问题很难得到其解析解，有的甚至无法用解析表达式来表示。因此，只能依赖于数值方法去获得微分方程的数值解。4．微分方程的数值解：设微分方程问题的解y(x)的存在区间是[a,b]，初始点x0=a，将[a,b]进行划分得一系列节点x0,x1,...,xn，其中a=x0<x1<…<xn=b。y(x)的解析表达式不容易得到或根本无法得到，我们用数值方法求得y(x)在每个节点xk的近似值y(xk)，即y≈y(xk)，这样y0,y1,...,yn称为微分方程的数值解。如果计算yn时，只利用yn-1，称这种方法为单步法；如果在计算yn时不仅利用yn-1，而且还要利用yn-2,yn-3,…,yn-r,则称这种方法为r步方法，也称多步法。§3.1欧拉方法§3.方程中，称为解一阶常微分方程初值问题的欧拉公式，也称显示欧拉公式。欧拉公式的几何意义非常明显，因为微分方程的解在xoy平面上表示一族积分曲线。用欧拉公式求数值解的几何意义如图：容易验证，该折线各个顶点的纵坐标就是欧拉公式算得的近似值解，所以，欧拉方法又称为折线法。算例：P98可以看出误差随着计算在积累。Euler法的特点和误差特点：(1)单步方法；(2) 显式格式；(3)局部截断误差为。局部截断误差：当时，由按照欧拉方法计算来的的误差称为局部截断误差。即，是局部截断误差。按泰勒展开欧拉法得：因此，局部截断误差是。如果局部截断误差是，称这种数值方法是p阶的。欧拉方法显然是一阶的。一阶的含义：常微分方程的解为时，若第n步精确，即前提下，欧拉公式能准确求解。§3.在对微分方程初值问题进行离散化时，如果用向后差商代替方程中的,并用近似值表示,表示,得：称为隐式欧拉公式，或后退的欧拉公式，它是关于的一个函数方程，其计算远比显式公式难但稳定性好。欧拉公式是关于的直接计算公式，称为显式的。隐式欧拉公式的右端含未知数，是关于的方程。无论向前或向后差商，它们具有相同精度，都是一阶方法。§3.以中心差商替代方程中导数项，得显式或隐式欧拉公式都是单步法，计算只用到前一步信息，上式除用到，还用到，用到前面两步信息，故称两步欧拉公式。按泰勒公式展开两步欧拉法截断误差为，是二阶方法。§3.2改进的欧拉方法§3.对方程两端从到求积分，得(1)用矩形公式计算即得欧拉公式，欧拉公式精度低，改用梯形方法计算积分得：代入（1）式得将用、用代替得离散化公式称为梯形公式。实际上就是显示、隐式欧拉公式得算术平均。梯形公式代数精度：§3.显示欧拉公式计算量小，但精度低，梯形方法提高了精度，但它是一种隐式算法，当是线性函数时，通过简单变换就能进行显式计算。但是非线性函数时，需要利用迭代法计算，计算量很大。通常，采用预测—校正技术，即先用显式方法计算，预测一个值，为隐式公式提供一个好的迭代初值，然后用梯形公式迭代一次，可得。称为改进的欧拉公式，是一种一步显式公式。可用如下嵌套形式为了编程方便，常将改进的欧拉公式改写为，，算例：P101初值问题的解为，试证明改进的Euler公式能准确求解上述问题。初值问题有如下计算公式，式中，试说明此公式是几阶方法。第9讲龙格库塔方法、亚当姆斯方法§3.3龙格－库塔方法§3.3.1令称为区间上的平均斜率，只要对提供一种算法，即可推导出一种计算公式。欧拉公式只是取点的斜率作为区间的平均斜率，精度自然很低。考察改进的欧拉公式它利用，两点的斜率取算术平均，处斜率通过已知信息用欧拉公式预报得到。可以考虑设法在多取几个点的斜率值，将它们加权平均作为区间的平均斜率。这就是龙格－库塔方法的基本思想。§3.3.2考察内一点，希望通过两个点的斜率加权平均得到，即令取，如何预报处斜率？仿照改进的欧拉公式，先用欧拉公式预测的值：然后用计算，从而得适当选取，使上述公式具有较高得精度。假定，分别将泰勒展开：代入得按泰勒展开比较得，只要，公式截断误差为特别，当，就是改进的欧拉公式，改取，，，称为变形的欧拉公式，亦称中点公式。§3.3.3为提高精度，设除外再考察一点，用三个点的斜率加权平均得出为预测的斜率值，将加权平均得出上的平均斜率，从而得然后用计算设计的计算公式具有如下形式运用泰勒展开选择参数下列库塔公式是其中一种§3.3.4继续上述过程，得出四阶方法，下列是经典格式流程图P105例P105§3.3.5步长越小，截断误差越小，但步长太小，计算量大，舍入误差也大，需要数值解法选择步长。步长选择考虑的问题：1）如何衡量和检验计算结果的精度；2）如何依据判定的精度来处理步长。以经典龙格－库塔方法为例，先以步长h求得一个近似值记为，经典龙格－库塔方法的截断误差为，故有步长折半区分两种情况处理步长：1），继续将步长折半，直至为止，取步长折半后的新值作为结果；2），步长加倍直至，取步长加倍前的老值作结果。§3.4亚当姆斯方法单步法的特点是计算时，只用到的值，此时，的值均已算出，如果在计算时，除用的值外，同时还用到的值，则称此方法为多步法。k步亚当姆斯公式：当式中的时，称为亚当姆斯显式公式。当时，称为亚当姆斯隐式公式。第10讲收敛性与稳定性、方程组与高阶方程§3.5收敛性与稳定性§3.微分方程数值解法的基本思想是：通过某种离散化手段，将微分方程转化为差分方程（代数方程）来求解。这种转化是否合理，还要看差分问题的解，当时是否会收敛到微分方程的准确解需要注意的是，如果只考虑，那么节点对固定的n将趋向于，这时讨论收敛性是没有意义的，因此，当时，同时时才合理。定义：若一种数值方法对于任意固定的，当（同时）时，有则称该方法是收敛的。考察欧拉公式（1）设为在条件下按欧拉公式计算的结果，（2）即为局部截断误差。，存在常数C使（3）考虑整体截断误差（无条件），由于（4）（1）-（2）得：由常微分方程李普希兹条件得：（5）由（3），（4），（5）式得递推得又，设（T为定数），则故若初值准确，则时，欧拉公式是收敛的。进一步考察一般的单步法：所谓单步法，就是在计算时只用到它前一步的信息。显式单步法的共同特征是，它们都是将加上某种形式的增量得出，其计算公式的形式为：，称为增量函数，不同的单步法，对应不同的增量函数。定理：单步法满足条件（李普希兹条件），且设初值是准确的，即，则该单步法是收敛的。§3.对于一个数值方法，即使是收敛的，由于初始值一般都带有误差，同时，在计算过程中还常常产生舍入误差，这些误差又必然会传播下去，对后续的计算结果都将产生影响，数值稳定性问题是讨论这种误差的积累和传播能否得到控制的问题。定义若用某一数值方法计算时，所得到的实际计算结果为，且由扰动引起以后各节点的扰动为，如果总有则称该方法是稳定的。一种数值方法是否稳定，不仅与该数值方法本身有关，而且还与微分方程的右端函数，以及步长h有关，因此稳定性问题比较复杂。为了简化讨论只考虑模型方程，欧拉公式稳定性：处有扰动，它的传播使节点产生扰动，假设欧拉公式计算中不再引入新误差，则如果原差分方程的解不增长，即有，就能保证欧拉方法的稳定性。的解不增长，h需要充分小，使。故欧拉方法是条件稳定的。隐式欧拉公式稳定性：由于，恒成立，从而，隐式欧拉公式是恒稳定的。§3.6方程组与高阶方程§3.直接推广各种算法到方程组如令，表示节点上的近似解。改进的欧拉公式为：预报校正四阶龙格－库塔方法为：§3.对，引入新变量即可化为一阶方程组：例将高阶方程y″-3y′+2y=0,y(0)=1,y′(0)=1化为一阶方程组第五章方程求根的迭代法一、教学目标及基本要求通过对本章的学习，使学生掌握方程求根的数值解法。二、教学内容及学时分配本章主要介绍方程求根的迭代法。具体内容如下：第21-22学时讲授内容：迭代收敛性与迭代加速。第23-24学时讲授内容：牛顿法、弦截法。三、教学重点难点1．教学重点：迭代收敛性与迭代加速、牛顿法。2.教学难点：迭代的收敛性。四、教学中应注意的问题多媒体课堂教学为主。适当提问，加深学生对概念的理解。第11讲迭代收敛性与迭代加速§4.1引言绪论中讲到方程求根得二分法，但二分法收敛速度慢，有必要掌握新的方法。§4.迭代法是一种逐次逼近法，使用某个固定公式（迭代公式）反复校正，逐步精确，直到满足精度。迭代法求根分两步：猜测初值2）迭代如求解初值问题用梯形公式（1）看作关于的函数方程，按欧拉公式提供猜测值，代入（1）得若仍不满足要求，则将它代入（1）式，继续得到校正值，写成迭代公式（2）一般地，为了求一元非线性方程的根，可以先将其转换为如下的等价形式（3）式（3）中连续函数称为迭代函数，其右端含未知数，不能直接求解。先用根的某个猜测值代入（3），构造迭代公式：。如果迭代值有极限，则称迭代收敛，极限值就是方程（3）的根。几何意义P127图4-1为使迭代法有效，必须保证它的收敛行，满足什么条件，才能保证收敛？以最简单的线性迭代，可以看出收敛的充分必要条件。几何意义P127图4-2,3,4,5。§4.设是方程的根，则由微分中值定理，如果存在，使得有，则迭代误差，由于，故，即迭代收敛。需注意，上述过程中需保证一切迭代值全落在，为此要求对任意，总有。综上，压缩映像原理：定理1设在上具有连续的一阶导数，满足条件：（1）对任意，总有。映内性（2）存在，使得对于任意成立。压缩性则迭代过程对于任意初值均收敛于方程的根，且有下列误差估计式：证明：由有从而有，（7）式得证，结合（7）式得由（7）式知只要的偏差足够小，就能保证迭代值足够准确，可用来控制迭代过程是否结束。流程图见P128图4－6。例1P130P142题3，5，6，7注意迭代函数的选择，同一方程，可以采用不同的迭代函数，但迭代函数可能不收敛，或收敛缓慢，迭代函数的选择非常重要。§4.在方程求根的迭代法中，迭代函数的确定，至关重要，它直接影响着迭代法的收敛性。但在实际应用中，同一个方程可以等价导出不同的迭代函数，而且要严格地利用定理1的条件判断迭代公式在整个区间内收敛（全局收敛）也非常困难，因此常常判断迭代公式的局部收敛性。通常在根的邻近考察。如果存在邻域，使得迭代过程对于任意初值均收敛，这种收敛性称为局部收敛性。定理2设在的根邻近有一阶导数，且成立，则迭代过程在邻近具有局部收敛性。证：存在充分小邻域，使，L为某个定数，根据微分中值定理：，注意到，又当时，故有，即由定理1知对于任意均收敛。例2P131§4.迭代误差，当时，称迭代过程为P阶收敛的，P＝1称线性收敛，P＝2称为平方收敛。对于在根邻近收敛的迭代公式，由于，式中介于和之间，故有，若，则为线性收敛。若，将在处进行泰勒展开有：，又，，由上式知，表明当，时平方收敛。故有下述论断：定理3设在在根的邻近有连续的二阶导数，且，则时线性收敛；当，时平方收敛。例P146题3§4.2迭代过程的加速§4.迭代过程收敛缓慢，计算量将很大，需要进行加速。设是根的某个近似值，用迭代公式校正一次得，假设在所考察得范围内变化不大，其估计值为L，则有：有迭代公式，是比更好的近似根。这样加工后的计算过程为：迭代改进合并的例3P133§4.上述加速方法含有导数，不便于计算。设将迭代值再迭代一次，又得，由于又，消去L得计算过程如下：迭代迭代改进第12讲牛顿法、弦截法§4.3牛顿法1公式的导出对于方程，设已知它的近似根，函数在处可用一阶泰勒展开来近似，取的根作为的新的近似根，记作，则：，这就是牛顿公式，相应的迭代函数是牛顿法是一种逐步线性化方法，将非线性方程的求根问题归结为计算一系列的根。牛顿法几何意义是：(牛顿法亦称切线法，直线经过、)，流程图P136图4－9例5：P137牛顿法收敛很快。其迭代公式假定是的单根，即，，则由上式知。故牛顿法至少平方收敛定理4牛顿法在的单根附近为平方收敛。(局部收敛)证：1）由知，故其局部收敛。2）代入得由上式得，故单根时平方收敛。但当是的重根时，牛顿法线性收敛。因，其中有二阶导数，且故，当m>1时，且有，故线性收敛。2开方公式给定正数c，用牛顿法解二次方程的计算公式，设是近似根，则也是近似根，它们的算术平均将是更好的近似值。定理5开方公式对于任意给定初值均为平方收敛。证明：（15）两式相除得令，则由上式得对任意，总有，故有，收敛性得证。由（15），迭代误差，有，迭代过程为平方收敛。3牛顿下山法例7P138为防止迭代发散，通常对迭代过程附加一项要求，即保证函数单调下降：，称为下山法。将牛顿法与下山法结合，在下山法保证函数值稳定下降得前提下，用牛顿法加快收敛速度。由牛顿法有，与前一步的近似值适当加权平均作为新值：其中，称为下山因子，选取适当的下山因子使单调条件成立。下山因子的选择，可从开始反复折半，一旦单调性条件成立，称下山成功。如果单调性条件始终不成立，则下山失败，需要重新选择初值进行计算。牛顿法的收敛性强烈依赖于初值的选择，实际计算中，可先采用二分法，求得足够精确的近似值，再用牛顿法。§4.4弦截法牛顿法的收敛速度快，但需要提供导数值，如果比较复杂，导数的计算困难，为避免求导数，改用差商替换牛顿法中的导数，得到：（19）该公式的几何意义如图，用差商代替弦线的斜率，称为弦截法。迭代函数，求导得当充分接近时，由定理3知弦截法线性收敛。为提高收敛速度，再改用差商替代牛顿公式中的导数，得称为快速弦截法。是一种两步法。第六章线性方程组的迭代法一、教学目标及基本要求通过对本章的学习，使学生掌握线性方程组的数值解法。二、教学内容及学时分配本章主要介绍线性方程组的数值解法。具体内容如下：第25-26学时讲授内容：迭代公式的建立。第27-28学时讲授内容：向量范数、迭代收敛性。三、教学重点难点1．教学重点：迭代公式的建立、向量范数、迭代收敛性。2.教学难点：向量范数、迭代收敛性。四、教学中应注意的问题多媒体课堂教学为主。适当提问，加深学生对概念的理解。第13讲迭代公式的建立重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用。如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题。在实际问题中产生的线性方程组的类型有很多，如按系数矩阵含零元素多少分类，有稠密和稀疏(零元素占80%以上)线性方程组之分；如按阶数的高低分类，有高阶(阶数在1000阶以上)中阶、(500~1000阶)和低阶(500阶以下)线性方程组之分；如按系数矩阵的形状和性质分类，有对称正定、三对角、对角占优线性方程组之分。因为数值解法必须考虑方法的计算时间和空间效率以及算法的数值稳定性。因此，不同类型的线性方程组，其数值解法也不相同。但是，基本的方法可以归结为两大类，即直接法和迭代法。分类：线性方程组的解法可分为直接法和迭代法两种方法。(a)直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解。最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的启发。计算代价高。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解，如何避免舍入误差的增长是设计直接法时必须考虑的问题。(b)迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列。收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题。迭代法要求方程组系数矩阵具有某种特殊形式（如对角占优阵），是解高阶稀疏矩阵方程组的重要方法。§5.1迭代公式的建立迭代法的基本思想是用逐次逼近的方法求线性方程组的解。设有方程组（1）将其转化为等价的便于迭代的形式（2）（这种转化总能实现，如令）并由此构造迭代公式（3）其中，B称为迭代矩阵f称为迭代向量。对任意的初始向量，由（3）式可求得向量序列若，则就是方程组的解。此时称迭代公式（3）是收敛的，否则称为发散的。构造的迭代法是否收敛，取决于迭代矩阵B的性质。§5.1.1例1求解方程组设取迭代初值，随着迭代次数增加，越来越接近精确解设有方程组（1）矩阵形式为，设系数矩阵A为非奇异且，从（1）式的第i个方程中解出，得其等价形式（2）取初始向量，对（2）式应用迭代法，可建立相应的迭代公式（3）记为矩阵形式（4）若将系数矩阵A分解为，其中则方程组变为（3），（4）分别称为雅克比迭代法的分量形式和矩阵形式，分量形式用于编程，矩阵形式用于讨论迭代法的收敛性。流程图P158§5。1。2高斯—赛德尔（Gauss-Seidel）迭代法雅克比(Jacobi)迭代法的优点是公式简单，迭代矩阵容易计算。在每一步迭代时，用的全部分量代入求出的全部分量，因此称为同步迭代法，计算时需保留两个近似解向量和。但在雅克比迭代过程中，对已经计算出的信息未能充分利用，即在计算第i个分量时，已经计算出的最新分量没有被利用。从直观上看在收敛的前提下，这些新的分量应比旧分量更好，更精确一些。因此，如果每计算出一个新的分量便立即用它取代对应的旧分量进行迭代，可能收敛更快，并且只需要存储一个近似解向量即可。考察例1，设已得到近似值，则新值常比老值精确，后面得计算用代替再用代替由此得据此思想可构造高斯—赛德尔（Gauss-Seidel）迭代法，其迭代公式为矩阵形式为仍将系数矩阵A分解为则方程组变为将最新分量代替旧分量，得在多数情况下用高斯—赛德尔迭代法比雅克比迭代法收敛快。但也有相反的情况，即高斯—赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯—赛德尔迭代法发散的情形。§5.1.3高斯—赛德尔（Gauss-Seidel）迭代法超松弛迭代法是高斯—赛德尔迭代法的一种改进，是解大型稀疏矩阵方程组的有效方法之一。将前一步得结果与高斯—赛德尔迭代值加权平均，得到更好得近似值。迭代加速合并后系数称为松驰因子。当某些方程组用高斯—赛德尔迭代法不收敛时，可以用低松弛方法获得收敛。。可以用来加速收敛速度。第14讲向量范数、迭代收敛性§5.2向量和矩阵的范数向量的范数对向量，其长度记作，借助长度可刻画向量的收敛性。向量序列，，则的充要条件是除长度外，还有哪些反映收敛性的度量？，其范数记为，是一个实数，满足：1）对任意向量，，当且仅当时；2）对任意实数及任意向量，；3）任意向量，（三角不等式）。按上述定义，存在多种范数，常用范数有：1）2范数：2）1范数：3）范数：上述都是P范数特例：定理1对任意向量：。证：P163不同方式规定的范数，其值一般不同，但在各种范数下考虑向量系列的收敛性时，所有范数都是一致的，向量范数具有等价性。范数等价性：，称等价。范数等价性保证应用具体范数分析收敛性的合法性。对向量序列收敛到的充分必要条件是：对于给定的P，有：矩阵的范数对n阶方阵A，将的上确界称作矩阵A的范数，记为，即：由定义知矩阵范数具有如下性质：1），当且仅当时2）对任意实数和任意方阵A，有：3）,由于，而，故矩阵范数亦可等价定义为：矩阵范数和向量范数密切相关，相应于向量的范数，记。定理2对n阶方阵，有：，，分别称为矩阵的行范数和列范数。§5.3迭代过程得收敛性迭代收敛的充分条件定理3对给定方阵G，若，则矩阵I-G为非奇异。（反证法）定理4方程组，迭代公式，若，则迭代公式对于任意初值均收敛。证：P1662、对角占优方程组对角占优：矩阵A的主对角元素的绝对值大于同行其他元素绝对值之和，即，定理5若A为对角占优阵，则它是非奇异的。证：P166定理6若线性方程组Ax=b的系数矩阵A为对角占优矩阵，则雅克比和高斯--赛德尔迭代法收敛。证：P167第七章线性方程组的直接法一、教学目标及基本要求通过对本章的学习，使学生掌握线性方程组的直接法求解。二、教学内容及学时分配本章主要介绍线性方程组的直接法。具体内容如下：第29-30学时讲授内容：消去法。第31-32学时讲授内容：追赶法、误差分析。三、教学重点难点1．教学重