《计算方法word教案》word版.doc

计算方法第一章 绪 论1.0 引 言1.1 数值算法概论(1) 计算方法的研究内容、对象与特点(2) 基本求解步骤1.2 预备知识、误差(1) 误差的来源(2) 误差分析、数值稳定性的分析和说明(3) 误差的基本概念绝对误差 相对误差 有效数字(4) 数值算法251.0 引 言 现代科学的三个重要组成部分: 科学理论, 科学实验, 科学计算。它们相辅相成，互相独立，可以互相补充又都不可缺少，作为三种科学研究手段之一的科学计算是一门工具性、方法性、边缘性的新学科，发展迅速，它的物质基础是计算机(包括其软硬件系统)，其理论基础主要是计算数学。 科学计算的核心内容是以现代化计算机以及数学软件为工具，以数学模型为基础进行模拟研究。 出现了形如:计算数学,计算物理学,计算力学,计算化学, 计算生物学,计算地质学,计算经济学等许多新学科及其发展。并已形成一系列专门研究数学问题的数值解法的算法软件，如目前流行的数学软件主要有以下几种：符号运算软件： Mathematica, Maple矩阵处理软件： Matlab Matlab简介统计处理软件： SAS, Spss, Origin数学CAD软件： MathCAD等功能强大的著名数学软件。1.1 数值算法概论1.1.1 计算方法的研究内容、对象与特点内容：(1) 数值代数: 求解线性方程组的解法（分直接方法和间接方法），求矩阵的特征值与特征向量。(2) 数值逼近：插值和数值逼近，数值微分和数值积分。(3) 方程求解：非线性方程、常微分方程、偏微分方程数值解法。对象：(1) 计算方法是一门与计算机应用密切结合的实用性很强的学科； 思维方法是归纳法，核心问题是“误差”或误差分析。 (2) 计算方法这门课程讨论连续变量问题又要讨论离散变量问题，关心的是数值结果。(3) 计算方法这门课程已成为近代数学的一个重要分支。 特点：(1) 面向计算机将计算机上不能执行的运算化为在计算机上可执行的运算;(2) 有可靠的理论分析（收敛性、稳定性、误差分析）。因为可能采用了近似等价运算,故要进行误差分析,即数值的性态及数值方法的稳定性。(3) 要有好的算法，并考虑计算复杂性（时间、空间）针对所求解的数值问题研究在计算机上可执行的且有效的计算公式。(4) 要有数值试验1.1.2 基本求解步骤实际问题建立数学模型构造数值 算法编程上机计算结果说明： (1)数学模型是通过科学实验或者观察分析一系列数据后，用数学作为工具近似地描述客观事物的一种数学表达式。在数学模型中，往往包含了若干参量如物体比重、阻力系数、热交换系数等，这些物理参数通常由实验仪器测得，根据仪器的精密程度，物理参数的确定也会产生一定的误差。(2)在建立了数学模型之后，并不能立刻用计算机直接求解，还必须寻找用计算机计算这些数学模型的数值方法，即将数学模型中的连续变量离散化，转化成一系列相应的算法步骤，编制出正确的计算程序，再上机计算得出满意的数值结果。(3) 算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。评价算法的两个主要标准：计算速度和计算精度，此外，还有计算存贮量等。 一个面向计算机,计算复杂性好,又有可靠理论分析的算法就是一个好算法.计算复杂性是算法好坏的标志，它包括时间复杂性(指计算时间多少)和空间复杂性(指占用存储单元多少)。对很多数值问题使用不同算法，其计算复杂性将会大不一样，例如对20阶的线性方程组若用代数中的Cramer法则作为算法求解，其乘除法运算次数需要，若用每秒运算1亿次的计算机计算也要30万年，这是无法实现的，而用计算方法中介绍的Gauss消元法求解，其乘除法运算次数只需3 060次，这说明选择算法的重要性。当然有很多数值方法事先不可能知道其计算量，故对数值方法除理论分析外，还必须通过数值试验检验其计算复杂性。作为基本要求希望读者能适当做一些计算机上的数值试验，对加深算法的理解是极有好处的。例1.1：计算多项式的值。 算法1 由计算出后再计算。说明：需乘法6次，加法3次，存储单元7个。 算法2 计算。说明：需乘法3次，加法3次，存储单元7个。例1.2：计算n次多项式的值。 算法 采用：秦九韶算法(1247) (又称为Horner算法(1819) 计算。说明：需乘法n次，加法n次，存储单元n+3个。上述秦九韶算法的结构是递归的，它通过一次式的反复计算，逐步降低多项式的次数，直到归结为零次式为止。若以多项式的次数（或项数）定义为求值问题的规模，则秦九韶算法的特点是，在递归计算的过程中问题的规模逐次减1。例1.3：计算在某点的值。数学上有如下算法: 算法(1) 算法(2) 显然：算法（1）的计算量N=63次乘法；由于算法（2）中，故计算量N=11次乘法。算法（2）比算法（1）好。1.2 预备知识和误差1.2.1 误差的来源实际问题建立数学模型研究计算方法编程上机计算解结果a) 模型误差: 在建立数学模型过程中,不可能将所有因素均考虑,必然要进行必要的简化,这就带来了与实际问题的误差。b) 测量误差: 测量已知参数时,数据带来的误差。c) 截断误差: 在设计算法时,必然要近似处理,寻求一些简化。d) 舍入误差: 计算机的字长是有限的,每一步运算均需四舍五入，由此产出的误差称舍入误差。如：、13，取小数点8位、16位。截断误差的实例例1.4： 当很小时，可用作为的近似值，其截断误差小于。 例1.5： 已知：求的近似值，并估计误差。分析：对函数用Taylor展开，用多项式近似代替，则数值方法的截断误差为。 解：利用展开式的前三项，取n=2， 截断误差为：数值计算方法主要讨论截断误差和舍入误差的影响,不讨论模型误差和测量误差。1.2.2 误差分析的重要性以及数值稳定性一个数值方法进行计算时，由于原始数据有误差，在计算中这些误差会传播，有时误差增长很快使计算结果误差很大，影响了结果不可靠.定义一个算法如果原始数据有扰动(即误差)，而计算过程舍入误差不增长，则称此算法是数值稳定的.否则，若误差增长则称算法不稳定.例如：计算并分析误差 解：由积分估值 由积分性质知 设计如下两种算法：算法1：取，按公式 （n=0，1，2）依次计算的近似值。设。假设计算过程中不产生新的舍入误差，则有（n=0，1，2） 误差扩散。算法2：从计算，应有 。在运算过程中，舍入误差不增大,数值稳定。 n00.1820.1820.18210.0880.0900.08820.0580.0500.05830.04310.0830.043140.0343-0.1650.034350.02841.0250.028460.024-4.9580.02470.02124.9330.02180.019-124.5400.019关于数值稳定性的算法v 误差的传播与积累例：蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！v 以上是一个病态问题例5: , 解：用分部积分公式得递推式:。 用四位有效数字计算: , , , , , , , ,.分析1： 可以估计出 故 ,。 于是与精确值已经面目全非,一位有效数字也没有。这是由于如果有误差,不计中间再产生的舍入误差,该误差随着计算过程分别乘以,到时已经变成了,误差扩大了4万倍。因而该算法不是稳定的。分析2：如果递推式改为,由, ,逐步计算直到。计算结果有四位有效数字,如果有误差,其传播到所引起的误差仅为。故该算法是稳定的。三、误差的基本概念(1) 误差与误差限是精确值, 是它的一个近似值，称是近似值的绝对误差。简称误差。误差是有量纲的,可正可负。误差是无法计算的,但可以估计出它的一个上界。即,称是近似值 的误差限,即 。(2) 相对误差与相对误差限称为近似值的相对误差,记作。相对误差是个相对数,是无量纲的,也可正可负。相对误差的估计,称为相对误差限,即。实际中, 是未知的,可用来代替。当较小时,因两者的差为: 是的高阶无穷小，可忽略不计。 (3) 有效数字定义: 如果近似值的误差限是 (某一数位的半个单位),则称准确到小数点后位,并从第一个非零的数字到这一位的所有数字均为有效数字。 如： 3.14有三位有效数字,误差限=0.005;3.1416有五位有效数字,误差限为0.00005。如： 近似值准确到小数点后五位，有三位有效数字。(4) 有效数字与误差限的关系：有n位有效数字，标准形式为，则有。有效位数越多，（绝对）误差限越小。e) 有效数字与相对误差限的关系：定理1：，若有位有效数字，则其相对误差限为 反之，若的相对误差限为则至少具有n位有效数字。证：因 ，故当有n位有效数字时， 。 反之，由因此，至少具有n位有效数字。 证毕定理说明，有效位数越多相对误差限越小。实例例1 设= p=3.1415926近似值x=3.140.314101,即m=1，它的绝对误差是 0.001 592 6，有即l=3，故x=3.14有3位有效数字。x=3.14准确到小数点后第2位。又近似值x=3.1416，它的绝对误差是0.0000074，有 即m=1,l5，x=3.1416有5位有效数字。而近似值x=3.1415，它的绝对误差是0.0000926，有 即m=1,l4，x=3.1415有4位有效数字。这就是说某数有s位数，若末位数字是四舍五入得到的，那么该数有s位有效数字；例2 指出下列各数具有几位有效数字，及其绝对误差限和相对误差限： 2.000 4 0.002 009 0009 000.00解 因为x1=2.000 40.200 04101, 它的绝对误差限0.000 05=0.510 15，即m=1,l=5,故x=2.000 4有5位有效数字. a1=2，相对误差限x2=0.002 00，绝对误差限0.000 005，因为m=2，l=3，x2=0.002 00有3位有效数字. a1=2，相对误差限er=0.002 5x3=9 000，绝对误差限为0.5100，因为m=4, l=4, x3=9 000有4位有效数字，a=9，相对误差限er0.000 056x4=9 000.00，绝对误差限0.005，因为m=4，l=6，x4=9 000.00有6位有效数字，相对误差限为er=er0.000 000 56由x3与x4可以看到小数点之后的0，不是可有可无的，它是有实际意义的。例3 ln2=0.69314718，精确到103的近似值是多少？解 精确到1030.001，即绝对误差限是e0.0005, 故至少要保留小数点后三位才可以。ln2=0.6931.2.4 数值算法例:求解微分方程: 将其变成数值问题，即将其“离散化” “离散化”是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的任务之一。计算方法的主要任务1. 将计算机上不能执行的运算化为在计算机上可执行的运算；2. 针对所求解的数值问题，研究在计算机上可执行的且有效的计算公式；3. 因为可能采用了近似等价运算,故要进行误差分析,即数值问题的性态及数值 方法的稳定性。Matlab简介：MATLAB的含义是矩阵实验室,是Matrix Laboratory的缩写。它的前身是LINPACK（解线性方程）和EISPACK（解特征值问题）的FORTRAN子程序库。由于它把矩阵当成一个对象，因此编写程序更加直观、方便。1984年正式推出,最新版本为V7.0 Release14.MATLAB具有非常强大和直观的计算功能，并且由于其有非常好的扩展性能，现在已成为世界上应用最广泛的工程计算软件之一。(1)强大的数值运算功能在MATLAB环境中，有超过500种数学、统计、科学及工程方面的函数可使用，函数的命名表示自然，使得问题和解答像数学公式一般简单明了，让用户可全力发挥在解题方面，而非浪费在电脑操作上。 (2)数据分析和可视化功能、文字处理功能MATLAB可以绘制二、三维图形，与Mathematic和Maple相比，它还能处理光照模型，制作出高品质的图形。功能十分强大。MATLAB Notebook为用户提供了强大的文字处理功能，并允许WORD访问MATLAB的数值计算和可视化结果，制作科学性或工程性图文并茂的文章.(3)高级、简单、高效的程序环境 做为一种解释型的程序语言，MATLAB允许使用者在短时间内写完程序,所花的时间约为用 FORTRAN或 C 的几分之一，而且不需要编译 (compile) 及连接(link) 即能执行，同时包含了更多及更容易使用的内建功能。 (4)开放及可延伸的架构 MATLAB允许使用者接触它的大多数的数学源代码，检查运算法，更改现有函数，甚至加入自己的函数使 MATLAB成为使用者所需要的环境。 (5)丰富的工具箱MATLAB的工具箱融合了套装前软体的优点，与一个灵活的开放但容易操作之环境，这些工具箱提供了使用者在特别应用领域所需的许多函数。现有工具箱有：符号运算（利用Maple V的计算核心执行）、图像处理、统计分析、信号处理、通信、线性矩阵不等式、偏微分方程、高阶谱分析、财政金融、神经网络、模拟分析、控制系统、实时控制、小波分析、最优化、模糊逻辑、分析及合成等30多种。 _END_第二章 方程求根2.0 引 言2.1 二分法2.2 简单迭代法2.3 牛顿（Newton）法2.4 其它求根方法（迭代过程的加速方法）2.5 作业讲评2.0引 言 非线性科学是当今科学发展的一个重要研究方向，非线性方程的求根也成为其中一个重要内容。一般而言，非线性方程的求根非常复杂。 在实际应用中有许多非线性方程的例子，例如（1）在光的衍射理论（the theory of diffraction of light)中,需要求x-tanx=0的根（2）在行星轨道（ planetary orbits）的计算中,对任意的a和b，需要求x-asinx=b的根（3）在数学中，需要求n次多项式的根。非线性方程的一般形式 这里是单变量 的函数，它可以是代数多项式 ()也可以是超越函数，即不能表示为上述形式的函数。满足方程 的x值通常叫做方程的根或解，也叫函数的零点。2.1二分法(Bisection Method)1 概念:二分法也称对分区间法、对分法等，是最简单的求根方法，属于区间法求根类型。在用近似方法时，需要知道方程的根所在区间。若区间a,b含有方程f(x)=0的根，则称a,b为f(x)=0的有根区间；若区间a,b仅含方程f(x)= 0的一个根，则称a,b为f(x)= 0的一个单根区间。2基本思想 根的存在定理(零点定理)： f(x)为a,b上的连续函数，若 f(a)f(b)0，则a,b中至少有一个实根。如果f(x)在a,b上还是单调递增或递减的，则f(x)=0仅有一个实根。3构造原理直接取区间a,b的中点x=(a +b)/2作为问题的近似解，那么我们可以估计出绝对误差限仅为区间长的一半，即e=(b-a)/2。如果这个结果能满足精度要求，我们就停止进一步的计算；如果不能，就求出f(x),结果只能是下面三种情况之一：（1） f(a)f(x)0，此时我们有x*a,x； （2） f(x)f(b)0，此时我们有x*x,b；（3） f(x)=0，此时x即为问题的精确解。在前两种情况下，我们可以用x分别替换原问题中的b或a,从而把求解的区间减小了一半。这样我们又可以取新区间a,b的中点。经过N次迭代后，剩下的区间长为(b- a)/ 。这也是结果的绝对误差限。如此继续下去就达到是有根区间逐步缩小的目的，在这一些相互包含的子区间中构造收敛的数列来逼近根 。例求方程的有根区间.解根据有根区间定义，对方程的根进行搜索计算，结果如下表：方程的三个有根区间为1,2,3,4,5,6.非线性方程f(x)=0求根，包括求超越方程和代数方程的根x*,方程的根也是f(x)的零点，即f(x*)=0,x*可以是实根也可以是复根，本章以求实根为主。求实根首先要确定根x*所在区间，称为有根区间。根据连续函数性质，若f(x)在上连续，当f()f(b)0时，为有根区间,为找到方程f(x)=0的有根区间,可用逐次搜索法,也就是在x的不同点上计算f(x),观察f(x)的符号,如例2.1表中所示,只要在相邻两点f反号,则得到有根区间,本例得到三个有根区间,分别为1,23,45,6.4基本步骤假设f(x)=0，在区间a,b中只有一个根，且满足f(a)f(b)eps) x=(a+b)/2 计算f(x) 若(|f(x)|eps) 则 x为解 若f(x)*f(b)0 修正区间为x,b 若f(a)*f(x)0 修正区间为a,xEnd while 按上述步骤求根的方法称为二分法，若记做了k次二分区间处理得到的有根区间为，则有二分法对应的求根数列算式为 , k=0,1,2,。5误差估计与分析 第1步产生的有误差 第 k 步产生的有误差对于给定的精度 e ,可估计二分法所需的步数 k ： 注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，不必要求 f (a)f (b) 0，f(1)=sin10(x0.1),故f(x)0在区间0，1内有唯一实根.给定误差限e0.510-4，有只要取n14. 例2： 已知 在有一个零点， ，用二分法计算结果如下： n有根区间11.0,2.01.52.37521.0,1.51.25-1.7968731.25,1.51.3750.1621141.25,1.3751.3125-0.8483951.3125,1.3751.34375-0.3509861.34375,1.3751.359375-0.0964171.359375,1.3751.36718750.0323681.359375,1.36718751.36328125-0.03215二分法的优点：就是不管含根区间a , b多大总能求出满足要求的根，且对函数的要求不高，计算简单；缺点：不能求重根，其收敛速度在数列xn越靠近根时越慢。二分法一般常用于为方程提供初始近似值当计算出的近似根比较准确时，再用其他方法对近似根做快速进一步精化。2.2简单迭代法1 不动点迭代法的思想 将方程 改写成等价的形式 ，则的根 也满足方程 ，反之亦然。称为的不动点。而求 的根的问题就成为求的不动点问题。 2 不动点迭代法的基本过程 选取初值，以公式 进行迭代，称为迭代函数，若收敛到，则 就是 的不动点，这种方法就称为不动点迭代法。 将 转化为的方法可以是多种多样的，例： 在 上有以下方法：(1) (2) (3) (4) 取 ，有的收敛，有的发散，有的快，有的慢。例1： 用迭代法求解方程(1) 将原方程化为等价方程显然迭代法发散(2) 如果将原方程化为等价方程仍取初值依此类推,得 已经收敛,故原方程的解为.可以发现,同样的方程不同的迭代格式有不同的结果. 这与迭代函数的构造有关。迭代法是非线性方程求根中各类迭代法的基础，其涉及的处理方法，概念和理论都易于推广。 3 迭代法的几何意义记 它们交点的横坐标p即为方程的根。例2 用迭代法求方程x54x20的最小正根.计算过程保留4位小数.分析 容易判断1，2是方程的有根区间.若建立迭代格式,即 ,此时迭代发散.建立迭代格式 此时迭代收敛.解 建立迭代格式 取初值x0=1得: 取 4 迭代过程的收敛性 从前面的分析可知，收敛的迭代数列xk的极限是方程f(x)的根，但计算机是不能做无穷次计算，因此迭代法一般只能求出具有任意固定精度的根的近似值，这样在给定精度后，了解迭代进行的次数即何时终止迭代才能得到满足要求的近似根就显得非常重要。定理假设迭代函数 (x), (x)Ca, b满足下面条件:( I ) 当 xa, b 时，(x)a, b；( II ) $ 0 L 1 使得 |(x) | L 1 对 xa, b 成立。则任取x0a, b，由xk+1 =(xk) 得到的序列收敛于(x) 在a, b上的唯一不动点。并且有误差估计式：. 2. 证：由迭代格式和条件，有 xk+1-xk|(xk)- xk| |(xk)- (x*) +(x*)- xk| | x*-xk-(xk)+(x*)| | x*-xk|-|(xk)- (x*)| | x*-xk|-L|xk- x*| (1-L)| x*-xk|因为 0L1，所以有 另一方面， xk+1-xk|(xk)-(xk-1)|L|xk-xk-1| 证得结论1。反复应用上式结果，有xk+1-xkL|xk-xk-1| Lk |x1-x0|可以得到结论。证毕定理给出了收敛迭代数列xk的误差估计式，利用它，在给定精度后，要使| x*-xk|，只要计算到或 第一式可以得到迭代次数的值应取多大，但这样得到的值往往偏大，第二式是用刚算出的数列来估计误差的，它可用较小的迭代运算但到满足精度的近似解。特别当 L时，有不等式 | x* -xk|xk-xk-1 |此时可用更简单的不等式 |xk-xk-1 | 成立与否终止迭代，由于这个判别具有简单易处理特点。实用中，一般不管是否有 L成立，都用|xk-xk-1 |是否小于某个充分小的数来作为终止条件，它通常也能求出满足精度的根。 注：定理条件很难保证，可将a, b缩小，定义局部收敛性：若在 x* 的某d 领域 Bd = x | | x - x* | d 有C1a, b 且 |(x*) | 1，则由x0Bd 开始的迭代收敛。即调整初值可得到收敛的结果。简单迭代法的优点是理论丰富算法简单，易于推广；缺点是不易找到收敛最快迭代函数和局部收敛。简单迭代法主要用于迭代的理论分析上。852.3 牛顿(Newton)法1 基本思想:将非线性方程逐步线性化而形成迭代公式 Taylor 展开.取的近似根，将f (x)在点做一阶Taylor展开: 将看成高阶小量，则 于是可得著名的牛顿迭代公式： 相应的迭代函数为 2 牛顿法几何意义是：(牛顿法亦称切线法) 只要 f C1，每一步迭代都有f ( xk ) 0，而且 ，则 x*就是 f 的根。牛顿迭代公式算法1: 初始化. x0, M,置i:=02: 如果|f(xi)|，则停止. 3: 计算xi+1:=xi-f(xi)/f(xi)4: 如果|xi+1-xi| OR |f(xi)|，则停止.5: i:=i+1, 转至3.例1： 求解f(x)=ex-1.5-tan-1x 的零点。（初始点x0=-7.0）解： f(x)=-0.70210-1，f (x)=ex-(1+x2)-1 计算结果如下表：(取|f(x)|f(xk+1)|成立，必须选取适当的下山因子. 取中依次挑取下山因子.Newton法是一种局部收敛方法，通常要求初始近似在解附近才保证迭代序列收敛.为扩大收敛范围，使对任意迭代序列收敛，通常可引入参数，并将Newton迭代改为 其中，称为下山因子，式(2.4.4)称为Newton下山法.通常可选择使，计算时可取,直到满足要求为止.由此得到的序列由于满足下山条件，故它是收敛的，但它只是线性收敛.例 用Newton下山法求的解，取=0.6，计算精确到解 由于,由式(2.4.4)得Newton下山法为,若=1.5用Newton法(=1)迭代3步则求得解的近似=1.324 72.现用=0.6，用=1,则得=17.9,且f(0.6)=-1.384,而不满足下山条件.通过试算，当时，满足以下计算时参数,且当Newton法不收敛时，使用Newton下山法.具体做法是取，每次缩减成一半，并检验是否成立，若成立则做下一步.2.4 其它求根方法1.正割法：Newtons Method是二阶收敛方法，每步都要计算 f 和 f ，相当于2个函数值，比较费时,同时在很多情况下计算函数的导数值比较困难。现考虑牛顿法的一种修改，用 f 的值近似f ，可少算一个函数值。但需要2个初值 x0 和 x1。割线的斜率为: 2.艾特肯(Aitken)加速方法有的迭代过程虽然收敛，但速度很慢，因此迭代过程的加速是一个重要课题。设是根的某个近似值，用迭代公式校正一次得 ，根据微分中值定理，有其中 介于 与 之间。 假设 改变不大，近似地取某个近似，则有若将校正值 再校正一次，又得 ，由于 在两式中消去 ，得到 由此推得：在计算了及之后，可用上式右端作为的新近似，记作，一般情形是由计算， ，记该方法称为艾特肯加速方法。 可以证明：它表明序列 的收敛速度比 的收敛速度快。 作业讲评1、已知方程在附近有根，将方程写成以下三种不同的等价形式： ； ； 试判断以上三种格式迭代函数的收敛性，并选出一种较好的格式。解： 令，则，故迭代收敛； 令，则，故迭代收敛； 令，则，故迭代发散。以上三中以第二种迭代格式较好。2.4 设在方程的根的附近有连续的一阶导数，且，证明迭代公式具有局部收敛性.证：因，又由在的附近连续，则存在的某邻域：，使得都有成立.于是， 由此可知，当时，. 2.6 试证用牛顿法求方程在1，3内的根具有线性收敛性.证：令，因此，根据Newton方法有: 由于,故.于是 从而得证. 线性方程组的解法3.0 引言 3.1 雅可比(Jacobi)迭代法 3.2 高斯-塞德尔(Gauss-Seidel)迭代法3.3 超松驰迭代法 3.7 三角分解法3.4 迭代法的收敛性 3.8 追赶法 3.5 高斯消去法 3.9 其它应用 3.6 高斯主元素消去法 3.10 误差分析 3 作业讲评3 3.11 总结 3.0 引 言 重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作用.如弹性力学、电路分析、热传导和振动、以及社会科学及定量分析商业经济中的各种问题. 分类：线性方程组的解法可分为直接法和迭代法两种方法.(a) 直接法：对于给定的方程组，在没有舍入误差的假设下，能在预定的运算次数内求得精确解.最基本的直接法是Gauss消去法，重要的直接法全都受到Gauss消去法的启发.计算代价高.(b) 迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列.收敛性是其为迭代法的前提，此外，存在收敛速度与误差估计问题.简单实用,诱人. 3.1 雅可比Jacobi迭代法 (AX=b)1 基本思想:与解f(x)=0 的不动点迭代相类似,将AX=b改写为X=BX+f 的形式,建立雅可比方法的迭代格式：Xk+1=BX(k)+f ,其中，B称为迭代矩阵.其计算精度可控,特别适用于求解系数为大型稀疏矩阵(sparse matrices)的方程组.2 问题:(a) 如何建立迭代格式？ (b) 向量序列Xk是否收敛以及收敛条件?3 例题分析:考虑解方程组 (1)其准确解为X*=1, 1.2, 1.3.建立与式(1)相等价的形式： (2)据此建立迭代公式： (3) 取迭代初值,迭代结果如下表. JocabiMethodP31.cpp 迭代次数 x1 x2 x30 0 0 01 0.72 0.83 0.842 0.971 1.07 1.153 1.057 1.1571 1.24824 1.08535 1.18534 1.282825 1.095098 1.195099 1.2941386 1.098338 1.198337 1.2980397 1.099442 1.199442 1.2993358 1.099811 1.199811 1.2997779 1.099936 1.199936 1.29992410 1.099979 1.199979 1.29997511 1.099993 1.199993 1.29999112 1.099998 1.199998 1.29999713 1.099999 1.199999 1.29999914 1.1 1.2 1.315 1.1 1.2 1.3 4 Jocobi迭代公式:设方程组AX=b, 通过分离变量的过程建立Jocobi迭代公式，即 由此我们可以得到Jacobi迭代公式：Jacobi迭代公式的算法1: 初始化. n, (aij), (bj), (x1) , M.2: 执行k=1直到M为止. 执行i=1直到n为止. ; 执行i=1直到n为止. ; 输出k, (xi).另外，我们也可以建立Jacobi迭代公式的矩阵形式.设方程组AX=b,其中，A=(aij)n为非奇异阵，X=(x1,x2,xn)T, b=(b1,b2,bn)T将系数阵A分解为: A=U+D+L,U为上三角矩阵，D为对角矩阵，L为下三角矩阵.于是AX=b可改写为(U+D+L)X=b X=D-1b-D-1(U+L)X由此可得矩阵形式的Jocobi迭代公式： Xk+1=BX(k)+f 3.2 高斯-塞德尔Gauss-Seidel迭代法注意到利用Jocobi迭代公式计算时，已经计算好的值，而Jocobi迭代公式并不利用这些最新的近似值计算，仍用.这启发我们可以对其加以改进,即在每个分量的计算中尽量利用最新的迭代值，得到上式称为Gauss-Seidel迭代法.其矩阵形式是X=-(D+L)-1UX+(D+L)-1b, Xk+1=BX(k)+f .迭代次数 x1 x2 x3 0 0 0 0 1 0.72 0.902 1.1644 2 1.04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999 8 1.1 1.2 1.33.3 超松驰迭代法SOR方法1 基本思想:逐次超松弛迭代法(Successive Over Relaxation Method,简写为SOR)可以看作带参数的高斯-塞德尔迭代法，是G-S方法的一种修正或加速.是求解大型稀疏矩阵方程组的有效方法之一.2 SOR算法的构造:设方程组AX=b, 其中，A=(aij)n为非奇异阵，X=(x1,x2,xn)T, b=(b1,b2,bn)T.假设已算出x(k)， (1)相当于用高斯-塞德尔方法计算一个分量的公式.若对某个参数，作与加权的平均,即 (2)其中，称为松弛因子.用(1)式代入(2)式，就得到解方程组AX=b的逐次超松弛迭代公式： (3)显然，当取=1时，式(3)就是高斯-塞德尔迭代公式.3 例题分析:利用SOR方法解方程组 (1)其准确解为X*=1, 1, 2.建立与式(1)相等价的形式： (2)据此建立迭代公式： (3)利用SOR算法，取迭代初值,=1.5,迭代结果如下表. 逐次超松弛迭代法次数 x1 x2 x3 1 0.625000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 6 0.746250 0.908419 1.838737 7 0.997715 0.860264 1.913894 8 0.864050 0.936742 1.908605 9 0.986259 0.922225 1.945523 10 0.928110 0.958649 1.947493 11 0.985242 0.955944 1.966198 12 0.961661 0.973818 1.969521 13 0.988103 0.974699 1.979289 14 0.979206 0.983746 1.982172 15 0.991521 0.985318 1.987416 16 0.988509 0.990038 1.989513 17 0.994341 0.991414 1.992397 18 0.993538 0.993946 1.993806 19 0.996367 0.994950 1.995424 20 0.996313 0.996342 1.996331 21 0.997724 0.997018 1.997254 22 0.997871 0.997798 1.997822 23 0.998596 0.998234 1.998355GS迭代法须迭代85次得到准确值X*=1,