计算方法全书课件完整版ppt整本书电子教案最全教学教程ppt课件

1、计算方法计算方法课程组计算方法课程组12第1章 绪论1.1 计算方法概述科学计算与计算方法数学模型与计算方法计算方法的特点及学习方法1.2 误差计算机的浮点表示及算术运算误差来源误差的基本概念误差分析3应用举例1问：今有问：今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？问上、中、下禾实一秉各几何？ 九章算术九章算术3239xyz2334xyz2326xyz例：

2、一个古老的数学问题例：一个古老的数学问题4应用举例应用举例1 14线性方程组数值求解线性方程组数值求解1112111212222211nnnnnnnnaaaxbaaaxbaaaxb Axb 例：人口预测例：人口预测表格中是我国表格中是我国1950年到年到2005年的人口数（见年的人口数（见中国统计年鉴），试预测未来的人口数中国统计年鉴），试预测未来的人口数插值与曲线拟合插值与曲线拟合 年份年份人口人口(万万)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120

3、001267432005130756应用举例应用举例2 26例：例：铝制波纹瓦的长度问题铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是由机器将一块平整的铝板压建筑上用的一种铝制波纹瓦是由机器将一块平整的铝板压制而成。假若要求波纹瓦长制而成。假若要求波纹瓦长 4 英尺，每个波纹的高度英尺，每个波纹的高度(从中从中心线心线)为为 1 英寸，且每个波纹以近似英寸，且每个波纹以近似 2 英寸为一个周期。英寸为一个周期。求制做一块波纹瓦所需铝板的长度求制做一块波纹瓦所需铝板的长度 L。应用举例应用举例3 37这个问题就是要求由函数这个问题就是要求由函数 f(x)=sin x给定的曲线从给定的曲线从 x=

4、0 到到 x=48 英寸间的弧长英寸间的弧长 L，即，即:数值积分与数值微分数值积分与数值微分484822001( ) d1(cos ) dLfxxxx上述积分为第二类椭圆积分，无法用普通方法来计算上述积分为第二类椭圆积分，无法用普通方法来计算应用举例应用举例3 38Google 搜索引擎搜索引擎PageRank: 对搜索结果按重要性排序基本原理“从优质的网页链接过来的网页必定还是优质网页”超链接AB A 对B 投一票若A的质量高，则该投票分数高1998年，美国斯坦福大学的Larry Page和Sergey Brin创立了Google公司应用举例应用举例4 49应用举例应用举例4 4由于所有网

5、页的Pr值可由所有链向它的页面的重要性加和得到MPr = Pr(M-I)Pr = 0 100103/1002/13/12/1003/12/102/10M矩阵特征值计算矩阵特征值计算 线性方程组求解问题线性方程组求解问题 蝴蝶效应 洛伦兹吸引子(Lorenz attractor)是由MIT大学的气象学家Edward Lorenz在1963年给出的，他给出第一个混沌现象蝴蝶效应。 图1 蝴蝶效应示意图应用举例应用举例5 511 dxxydtdyrxyxzdtdzbzxydt 洛伦兹方程是大气流体动力学模型的一个简化的常微分方程组：应用举例应用举例5 512数值计算方法定义线性方程组的解法矩阵特征值

6、与特征向量的计算函数插值数值微分与积分非线性方程(组)的解法与最优化问题的计算方法常微与偏微分方程的数值解法有关计算方法可靠性的理论研究,如方法的收敛性和稳定性分析与误差估计等.131.1.1 科学计算与计算方法科学计算与计算方法14计算工具15计算工具16计算工具17计算工具18计算古老年轻与时俱进 计算物理、计算化学、计算力学、 数量经济、计算生物学.19理论研究科学实验科学计算计算数学科学研究20科学计算风洞21科学计算计算机计算能力的提高，衍生了计算方法这门课程22 数值计算方法的应用极为广泛，上至国防尖端科技，下至日常生活生产，如火箭和卫星的设计与控制、飞机与汽车的优化设计、尖端数控

7、机床、地质勘探与油气开发、天气预报、图像处理、网络搜索等方面都有数值计算方法的应用。 它作为一种科学方法已经渗透到许多不同的科学领域，并形成了一些诸如计算力学、计算物理、计算化学、计量经济学、生物信息学等交叉学科。23计算方法与科学计算科学计算是人类从事科学活动和解决科学技术问题不可缺少的手段。计算机科学技术的发展，为科学计算及数据处理提供了高速和高精度的计算工具。计算机运算: 只能进行加，减，乘，除等算术运算和一些逻辑运算。24计算方法与科学计算实际实际问题问题数学数学模型模型 数值数值方法方法程序程序设计设计计算机计算机计算计算解答解答科学计算的过程科学计算的过程25三维地图构建26三维地

8、图构建（1）实际问题：空中航测（空中连续拍照）方法，构建某地三维地形图。（2）数学模型：建立一个大型超定线性方程组。（3）数值方法：采用最小二乘方法求解该方程组的最小二乘解。（4）程序设计：任何语言。（5）计算机计算（6）问题的解，对解进行解释。27数值计算方法定义数学的一个分支，它以数字计算机求解数学问题的方法与理论为研究对象，其内容包括:28数值计算方法定义线性方程组的解法矩阵特征值与特征向量的计算函数插值数值微分与积分非线性方程(组)的解法与最优化问题的计算方法常微与偏微分方程的数值解法有关计算方法可靠性的理论研究,如方法的收敛性和稳定性分析与误差估计等.29为什么要学习计算方法为什么要

9、学习计算方法30举例说明一311.求解线性方程组Ax=b，其中A为3阶可逆方阵X=(x1, x2, x3)T;2.求代数方程x2+x-6=0在0,4上的根x*3.已知y=p(x)为x0, x1上的直线，满足p(x0)= y0 ， p(x1)= y1求p(x2)4.计算定积分5.解常微分方程初值问题(0)0yxy 1(1)baIdxabx举例说明二1.求解线性方程组Ax=B，其中A为20阶可逆方阵X=(x1, x2, , x20)T;2.求代数方程xex=1在0,1上的根x*3.已知y=f(x)为x0, x1上的函数，满足f(x0)= y0 ， f(x1)= y1求f(x2)4.计算定积分5.解

10、常微分方程初值问题321(1)lnbaIdxabx2(0)0yxyy线性方程组求解考虑线性代数方程组Ax=b的求解计算问题。其中系数矩阵A为一n阶方阵，D=det(A)0Cramer法则 xi=Di / D i=1,2,n 33积分求解对于积分由微积分知识可知：只要找到被积函数f(x)的原函数F(x)，便有下列牛顿莱布尼兹公式badxxfI)()()()(aFbFdxxfba34积分求解原因一：原函数不能用初等函数表示成有限形式原因二：原函数过于复杂babadxxxdxxsin,sin232)(22xxxf) 322ln(216916323432)(2223xxxxxxxF35积分求解原因三：

11、f (x)以离散数据点形式给出xix0 x1xnyi = f(xi)y0y1yn36积分求解有了数学模型，并不一定能够直接用计算机求解，因此我们需要学习计算方法!学习计算方法这门课程，能够让我们学会如何构造或选择那些“好”的数值计算方法。37秦九韶算法考虑对任意给定的x, 计算代数多项式 (1.1.3) 的值的问题。nkknknnnnnxaaxaxaxaxP01110)(38秦九韶算法考虑对任意给定的x, 计算代数多项式 的值的问题。显然，上式等价于nnnaxaxaxaxaxP1210)(nkknknnnnnxaaxaxaxaxP01110)(1.1.3)(1.1.5)391.1.3 计算方法

12、的特点及学习方法计算方法的特点及学习方法40课程特点计算方法是一门与计算机应用紧密结合、实用性很强的数学课程，它所涉及的数学问题面很广、内容非常丰富，亦有其自身的体系它既有数学的高度概括，又非常讲究实用性并具有高度的技巧性41课程特点第一，面向计算机，研究计算机上用的计算方法 （算法最终只可包含四则运算和逻辑运算）第二，要有可靠的理论分析 （算法收敛性、稳定性及误差分析）第三，要注重算法的效率 （计算时间、存储空间）第四，要重视数值实验42本课程的学习方法掌握构造方法的原理、思想，理解算法，会分析算法精度注重算法的效率和适用范围，针对不同情况学会选择和设计优秀算法要重视实践，通过算例和动手计算

13、，学会怎样使用数值方法在计算机上解决各类数学计算问题431.2 1.2 误差误差44误差计算机的浮点表示及算术运算误差来源误差的基本概念误差估计451.2.11.2.1计算机的浮点表示及算术运算计算机的浮点表示及算术运算46数的浮点表示实数x在计算机中被表示为 x = 0.d1d2dk2p d1=1,di为0或1，i=2,3,k, -mpM.零的浮点数通常表示为 0 = 0.0002-m 47数的浮点表示实数x在计算机中被表示为 x = 0.d1d2dk2p d1=1,di为0或1，i=2,3,k, -mpM.零的浮点数通常表示为 0 = 0.0002-m 尾数阶码48数的浮点表示 x = 0

14、.d1d2dk2p (1.2.1)给定的二进制浮点计算机，只能表示所有形如上式的有限数集S=S(k,m,M)，这是实数轴上的不等距有限点集。49数的浮点表示 S=S(3,1,2) k=3， m=1， M=2， -1p2 那么计算机能表示的浮点数集合是如下的33个点。 0 = 0.0002-1 x= 0.1d2d3 2-1 x= 0.1d2d3 20 x= 0.1d2d3 21 x= 0.1d2d3 2250数的浮点表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.11

15、0 2-1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/851数的浮点表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.110 2-1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/80152数的浮点表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.110 2-

16、1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/80153数的浮点表示例如单精度实数用32位的二进制表示，其中符号位占1位，尾数占23位，阶数占8位，可以写成如下形式 x = 0.d1d2d232p |p| 27-1 (1.2.2)注意上面的8位阶数中须有1位表示阶数的符号，所以阶数值占7位。54数的浮点表示例如单精度实数用32位的二进制表示，其中符号位占1位，尾数占23位，阶数占8位，可以写成如下形式 x = 0.d1d2d232p |p| 27-1 (1.2.2)注意上面的8位阶数中须有1位表示阶数的符号，所以阶数值占7位。55浮点数的四则运算设是

17、S10由所有形如 0.d1d2d3d4 10p的4位十进制浮点数的集合，其中1 d19，0 di9，i = 2, 3, 4, 整数p满足-9 p10。下面举例说明S10上的算术运算。56浮点数计算特点加减法先对阶(将阶码统一为较大者)，后计算，再舍入乘除法先运算再舍入不在计算机数系中的数做四舍五入处理57例1.1(1) 0.2015104 + 0.1911102 0.2015104 + 0.0019104 对阶 0.2034104 计算(2) 0.2015104 + 0.191110-1 0.2015104 + 0.0000104 对阶 0.2015104 计算(3) 0.2015104 -

18、0.2008104 0.0007104 计算 0.7000101 规范化58例1.1(4) (0.2015104) (0.191110-5) (0.20150.1911) 10-1 对阶 (0.3851 10-1) 10-1 计算 0.3851 10-2 规范化(5) (0.2015104) (0.191110-5) (0.20150.1911) 109 对阶 (0.1054 101) 109 计算 0.1054 1010 规范化59浮点数计算特点计算过程中应该注意绝对值相差悬殊的两个数做加减，会造成“大数吃小数”的现象；（例2）非常接近的数相减，会损失掉有效数字； （例3）相对被除数来说，绝

19、对值很小的数做除数，会产生绝对值很大的数，甚至溢出； （例5）在运算过程中注意合理安排运算顺序，以便提高运算的精度或保护重要的参数。60例1.2在前面所述的4位十进制浮点计算机（数集S10）上求解如下一元二次方程 x2 24 x +1 = 0 (1.2.3)按求根公式，此方程的两个根是在4位十进制浮点计算机上， 0.1196102，于是按照上面求根公式有 x1=0.2396102, x2=0.400010-1143121x143-122x14361下面我们换一种方法进行计算x2，即 (1.2.4)则x2=0.417410-1。事实上，x2的精确解应为0.0417393。143121143-12

20、2x62问题631.2.2 1.2.2 误差来源误差来源64误差的来源实际实际问题问题数学数学模型模型 数值数值方法方法程序程序设计设计计算机计算机计算计算解答解答模型误差模型误差方法误差方法误差观测误差观测误差舍入误差舍入误差65例1.3为了计算函数值ex，| x | 0，并满足 | e* | = |x* - x| * (1.2.7) 则称*为近似值x*的绝对误差限，或简称误差限。69相对误差定义1.3 设x为精确值，x*为近似值，则称比值 (1.2.8)为近似值x*的相对误差，记作er*（实际应用时，常用x*代替上式分母中的x）。xxxxe*70相对误差限定义1.4 设*是近似值x*的误差

21、限，则称 (1.2.9) 为近似值x*的相对误差限，此时，有 (1.2.10)*xr*rxxxx71有效数字定义1.5 如果 | e* | = |x* - x| 0.510-n (1.2.11) 则说x*近似表示x准确到10-n位（小数点后第n位），并从此位起直到最左边的非零数字之间的一切数字都称为有效数字，并把有效数字的位数称为有效位数。72例1.4取e（e = 2.718281828459 ）的近似值x* = 2.72，则 |2.72 e | 0.001718 0.510-2即x*近似表示e准确到10-2位，因此具有3位有效数字。若取e的近似值x* = 2.71828，则 |2.71828

22、 e | 0.0000018 0.510-5即x*近似表示e准确到10-5位，因此具有6位有效数字。73有效数字定义1.6 将x的近似值x*表示为十进制浮点数的标准形式 x* = 0.d1d2dk 10m (di=0,1,9, d10) (1.2.12)如果 | e* | = |x* - x| 0.510m-n (1.2.13)则说近似值x*具有n位有效数字。这里n是正整数，m是整数。74例若x*=3578.64是x的具有6位有效数字的近似值，试求x*的误差限。75有效数字与相对误差的关系定理1.1 若近似值x*具有n位有效数字，则其相对误差满足 (1.2.14)反之，如果x*的相对误差er*

23、满足 (1.2.15)则x*至少具有n位有效数字。*-(1)11102nred*-(1)11102(1)nred761.2.4 1.2.4 误差分析误差分析77误差分析将带有误差的数据进行计算时，误差在运算过程中会进行传播，必然导致计算结果出现误差。一般来说，精确值x与近似值x*之间都比较接近，其误差可以看作是一个小的增量，即可以把误差看作微分，即 e* = x* - x = dx这表明：x的微分表示x的误差，ln x的微分表示x的相对误差xxxxeerlndd*78(1.2.16)(1.2.17)误差分析根据上式，可以得到算术运算的误差，以x, y两数为例 e* (xy) = d (xy)

24、= d x d y = e* (x) e* (y) e* (xy) = d (xy) = y d x + x d y = y e* (x) + x e* (y) er* (xy) = d ln(xy) = d ln(x) + d ln(y) = er*(x) + er*(y)0()()(ddd2*2*yyyxexyeyyxxyyxyxe)0()()()ln(d)ln(dlnd*yyexeyxyxyxerrr79误差分析而更一般的情况是，当自变量有误差时计算函数值时也会产生误差。其误差可以用函数的Taylor展开式进行估计。2* *)(2)()()()(xxfxxxfxfxf)()()()()(

25、*xexfxfxfxfe80例1.5已知 由于 的精确值未知，取 1.414进行计算，试问上述3个表达式哪个计算精度最高？f1(x)=(x-1)6f2(x)=99-70 xf3(x)=270991270-991-262281例1.582例1.5830.6320.3680.2640.2080.1680.1600.0400.720例1.6考虑积分 (1.2.25)的近似计算.此积分满足递推关系式 In = 1 nIn-1, (1.2.26)假定我们首先计算出I0的近似值 ，保留3位有效数字，利用递推关系式(1.2.26)依次算出101dxexIxnn0I0I1I2I5I4I6I3I7I84例1.6

26、10=1-1=1-0.632=0.368II21=1-2=1-0.736=0.264II6=0.040I76=1-7=1-0.280=0.720II85例1.6根据积分公式那么1110100，使得对于一切xRn有214,stxx12stscxxcx21xxn xxxn x（2.5.8）（2.5.9）向量的范数向量序列收敛性向量序列收敛性定义定义2. 2 设x(k)= ( x1(k), x2(k), xn(k)T 为Rn 上的一个向量序列(k=1,2,)， x*= ( x1*, x2*, xn*)TRn. 如果对于i=1,2, n 有 则称向量序列x(k 收敛于向量x*。 215*)(limik

27、ikxx向量的范数容易证明，x(k) 收敛于向量x*的充要条件是再由(2.5.8)和(2.5.9)式可知，上式成立等价于2160lim*)(xxkk0lim2*)(xxkk0lim1*)(xxkk矩阵范数 定义定义2.3设设 为为A的实值函数，若它满足下的实值函数，若它满足下列条件列条件（1）正定性）正定性 ，当且仅当，当且仅当A=0时等号成立时等号成立（2）齐次性）齐次性（3）三角不等式）三角不等式 则称则称 为为 上的一个上的一个矩阵范数矩阵范数（或矩阵模）（或矩阵模）, 的值称为矩阵的值称为矩阵A的范数的范数217n nR0 A ()kAkAkR C ,n nABABA BR ( )n

28、nARN AA()N AAAn nAR 矩阵范数相容范数相容范数218 , ,n nnn nABABA B RAxAxxR A R （ 2.5.13）（ 2.5.14）矩阵范数算子范数算子范数最常用的是利用向量范数来定义的矩阵范数矩阵范数称之为矩阵A的算子范数算子范数，其中2191,2,p 01maxmaxppppxxpAxAAxx（ 2.5.15）矩阵范数证明：容易证明，由(2.5.15)式所定义的函数满足定义2.3的三个条件，故它是矩阵范数。另外，当x=0时， (2.5.14)式显然成立。对任意的x0,两边乘以即为(2.5.14)式。220定理2.3由(2.5.15)式所定义的矩阵范数为相

29、容范数:nnpRR0maxpppyppAxAyAxypx矩阵范数再来证(2.5.13)式。注意到由(2.5.14)式有定理证完。221,n nA BRnB xR111m ax m ax m ax pppppxppxppxppABABxABxABxAB矩阵范数定理2.4对于由(2.5.15)式所定义的矩阵范数下列等式成立：其中AT表示A的转置矩阵。22211111m a xm a xnijinjnijjniAaAa2A(ATA之最大特征值之最大特征值)1/2(2.5.16)(2.5.17)(2.5.18)矩阵范数证明先证(2.5.16)式。首先，对任意满足 的xRn，因为 ，故有2231x1jx

30、x1111111max ()max max()maxniijji ni njnnijjiji ni njjAXAxa xaxa 矩阵范数另一方面，设第k行为元素绝对值和最大的行，即则可令此时，x满足且有2241x111maxnnkjiji njjaa 11111()()maxnnkkjjkjkjjjnnkjiji njjAxa xa sng aaa sgn()jijxa矩阵范数再证等式(2.5.18)，注意当 时，ATA是对称非负定矩阵，故ATA有完全正交的特征向量系 ，即其中 为ATA的特征值22512,nv vvn nAR22(,)( ,)TTTAxAx Axx A Axx A Ax0,

31、( ,)1, Tii iijijA Avvv vij10n矩阵范数对于任意的xRn，借助于特征向量系可表示为且从而有2261niiixv2221( , )niixx x112111(, )(,) =(,)nnTTjji ijinnnjjji iiijiiA Ax xA Avvvv 矩阵范数227由于故有上式说明 是 的上界，并且这个上界在x=v1时达到。定理证完。2221111nnnniiiiiii 121222(, )TnxA Ax xAxx122A xx矩阵范数22811111m a xm a xnijinjnijjniAaAa2A(ATA之最大特征值之最大特征值)1/2行和范数行和范数列

32、和范数列和范数谱范数谱范数01maxmaxppppxxpAxAAxx（2.5.15）谱半径矩阵A的特征值的按模最大值称为A的谱半径记作，即其中是A的特征值。定理1.6对任意 ，有2291( )maxii nA ( )Ain nAR( ) 1,2,pAAp谱半径由谱半径的定义,矩阵的2范数可记为当A是实对称矩阵时，由（1.4.18）式有这也就是说，此时A的2范数与该矩阵的谱半径相等。2302()TAA A22()()( )TAA AAA第2章 解线性方程组的数值法2.1 引入2.2 Gauss消元法2.3 矩阵的三角分解2.4 消元法在计算机上的实现2.5 向量和矩阵范数2.6 矩阵的条件数与病

33、态方程组矩阵的条件数与病态方程组2.7 迭代法2312.6 矩阵的条件数与病态方程组232病态方程组233例2.2 令 , 并设123123(,) ,(,)TTxxxxbb bb1/2 1/3 1/41/3 1/4 1/51/4 1/5 1/6A病态方程组234令Ly = b, 可解得于是，由Ux = y, 可解得112133123121546ybybbybbb11232123312372240180240900720180720600 xbbbxbbbxbbb病态方程组321332123211600720180 72090024018024072 bbbxbbbxbbbx235),(321b

34、bbb)1500,1860,492( xx病态方程组236定义 如果矩阵A或常数项b的微小变化,引起方程组Ax=b的巨大变化,则称此方程组为“病态病态”方程组方程组,矩阵A称为“病态”矩阵，否则称方程组为“良态”方程组，A称为“良态”矩阵。条件数237设A为非奇异矩阵,用x表示Ax=b的精确解,而 是扰动方程组的精确解.由Ax=b和(1.5.1)两式相减,可知解的误差 满足方程由此x A xbbA xbxx x 1xAb条件数238利用矩阵的范数性质,有另外,由Ax=b又有由(1.5.2)式和(1.5.3)式,便可得:1pppxAbppppAxAxb1()ppppppxbAAxb条件数239设

35、 是下面扰动方程组的精确解。由Ax=b和(1.5.1)两式相减，可知解的误差 满足方程由此x ()AA xb)(-xxAxAxx x )(-1xxAAx条件数240于是有即pppppxxAAxxAAx-1-1)(-ppppppAAAAxxx1 -条件数241定义2.5 设 为可逆矩阵,称 为矩阵A在范数 意义下的条件数条件数.矩阵A的条件数越大，方程组的扰动误差对方程组的解的影响越严重。因此称条件数过大的方程组为病病态方程组。态方程组。n nARp1( )pppCondAAA第2章 解线性方程组的数值法2.1 引入2.2 Gauss消元法2.3 矩阵的三角分解2.4 消元法在计算机上的实现2.

36、5 向量和矩阵范数2.6 矩阵的条件数与病态方程组2.7 迭代法迭代法242 迭代法是求解线性代数方程组的另一类方法。由于它具有保持迭代矩阵不变的特点，因此迭代法特别适合求解大型稀疏系数矩阵的方程组。2.7 迭代法243迭代法的一般形式考虑求解线性代数方程组为了采用迭代法，首先要将方程组（2.7.1）改写成等价的形式其中 为已知向量， 代表未知向量。244Axb(2.7.1),n nnijMRMmgRnxRxMxg(2.7.2)迭代法的一般形式给定初始近似值 ，定义向量序列称为迭代序列迭代序列，并称M为迭代矩阵迭代矩阵。245(0)nxR( )kx(1)( ) 0,1,2.kkxMxgk（2.

37、7.3）迭代法的一般形式如果当k时， 有极限，设为 ,则在等式（2.7.3）两端取极限可得此式表明迭代序列的极限恰为方程组的解。因此，如果迭代序列收敛，则当k充分大时，可将x(k)取作方程组的近似解。246( )kx*nxR(1)( ) 0,1,2.kkxMxgk（2.7.3）( )kx*xMxg（2.7.4）迭代法的收敛性利用迭代公式（2.7.3）构造序列 ，以求得方程组（2.7.2）的近似解的算法称为解（2.7.2）式的简简单迭代法单迭代法。若迭代序列 收敛，就称此迭代法是收敛的。247( )kx( )kxxMxg(1)( ) 0,1,2.kkxMxgk（2.7.3）(2.7.2)迭代法的

38、收敛性显然，只有收敛的迭代法才能使用，因此必须回答在何种条件下，由公式（2.7.3）所定义的 为收敛的向量序列248( )kx(1)( ) 0,1,2.kkxMxgk（2.7.3）迭代法收敛性为讨论迭代法的收敛性，引入误差向量 (k) = x (k) - x *则利用(2.7.2)和(2.7.4)可得 (k+1) = x (k+1) - x *= Mx (k) + g (Mx* + g) = M (x (k) x*) = M(k)于是可以迭代得出 (k+1) = M(k) = M 2(k-1) = = M k+1(0) (2.7.5)迭代法收敛，即 (k+1)0 (零向量) (k)。由于x(0

39、)是任给的，所以其充要条件是M k+10 (零矩阵) (k)。249迭代法的收敛性( )(1)kkxMxg250(1)( ) 0,1,2.kkxMxgk*xM xgxMxgAxb(2.7.1)(2.7.2)(2.7.4)(2.7.3)迭代法的收敛性根据上式可以判定，对任意x(0)即 的充分必要条件是 （零矩阵），k，由此得到下面结果.251( )*kxx( )0kM ( )*0kxx( )*(0)*(), 0,1,2,.kkxxM xxk迭代法的收敛性定理定理2.6 设M = (mij) R nn, 则M k0(k)的充要条件是(M) 1。定理定理2.7 迭代法(2.7.3)对任何初始近似值x

40、(0)均收敛的充分必要条件是迭代矩阵M的谱半径(M) 1。推论推论2.1 若|M|1（|允许为任何一种相容范数）, 则迭代法(2.7.3)收敛。252(1)( ) 0,1,2.kkxMxgk(2.7.3)迭代法的收敛速度定理 当 时，由迭代法（2.7.3）式所定义的序列满足如下估计式：证明略.2531H( )kx( )*( )(1)( )*(1)(0)11kkkkkHxxxxHHxxxxH一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是否收敛迭代求解满足终止条件,迭代结束254xMxg( 1)( )kkxM xg()(1)kkxx()1M1M雅可比迭代法例例2.3 求解方程组若将

41、方程组表示成如下形式2551552218474zyxzyxzyx4782145152xyzyxzzxy7421 481525yzxxzyxyz雅可比迭代法 给出了雅可比迭代格式 如果从初始点(x0, y0, z0) = (1, 2, 2) 开始，即将x0= 1, y0= 2, z0= 2代入（1.6.8）每个方程的右边，可得到如下新值：256( )( )(1)( )( )(1)( )( )(1)7421 481525kkkkkkkkkyzxxzyxyz(1)(1)(1)72-241.7521 4283.375152253.00 xyz雅可比迭代法考虑方程组 Ax=b 其中 是非奇异的, 为已知

42、向量。将矩阵A写成如下 A=D-L-U其中 为对角阵, -L, -U分别为A的严格下、上三角部分构成的三角阵。257n nARnbR11(,)nnDdiag aa雅可比迭代法2131321200000nnaLaaaa 258121312321,00000nnnnaaaaaUa雅可比迭代法当D非奇异,即aii0(i=1,2,n)时,可将方程组Ax=b写成于是可得迭代格式称此格式为求解方程组Ax=b的雅可比迭代法.注意到L+U=D-A,故(2.7.9)式也可写成25911()xDLU xD b(2.7.9)(1)1( )1() 0,1,2,.kkxD L U xD bk(2.7.10)11()xI

43、D A xD b雅可比迭代法Jacobi方法的迭代矩阵为Jacobi迭代法的分量形式为26011()HDL UID A 1(1)( )( )111() 1,2, ,1,2, .inkkkiijjijjijj iiixa xa xbin ka (2.7.11)雅可比迭代法例2.4 求解方程组2611552218474zyxzyxzyx雅可比迭代法例2.4 求解方程组2621552218474zyxzyxzyx雅可比迭代法263kx(k)y(k)z(k)01.02.02.01-1.53.3755.026.6872.516.375334.68758.015625-17.254-46.61718817

44、.8125-123.734385-307.929688-36.150391211.281256502.62793-124.9296881202.56836高斯赛德尔迭代法简单迭代法(2.7.3)的分量形式是可以用这些新值来计算 , 于是可得迭代格式这种方法称为赛德尔迭代法.2641(1)( )( )1 1,2, , .inkkkiijjijjijj ixh xh xgin(1)kix1(1)(1)( )1 inkkkiijjijjijj ixh xh xg(2.7.12)高斯赛德尔迭代法对雅可比迭代(2.7.11)式运用赛德尔技巧得到称(2.7.13)式为高斯赛德尔迭代法,其矩阵形式为并可整理

45、成一般迭代法的形式2651(1)(1)( )111() 1,2, .inkkkiijjijjijj iiixa xa xbina (2.7.13)(1)1(1)( )()kkkxDLxUxb(1)1( )1()()kkxDLUxDLb(2.7.14)高斯赛德尔迭代法例例2.5 试用Jacobi迭代法和Gauss-Seidel迭代法求解下面线性方程组，并分析其收敛性266123123123226+4223xxxxxxxxx 高斯赛德尔迭代法例例2.5 试用雅可比迭代法和高斯-赛德尔迭代法求解下面线性方程组，并分析其收敛性解解：雅可比迭代法和高斯-赛德尔迭代法的迭代公式分别为：2671231231

46、23226+4223xxxxxxxxx 111(1)( )( )23(1)( )( )23(1)( )( )326224322kkkkkkkkkxxxxxxxxx 111(1)( )( )23(1)(1)( )23(1)(1)(1)326224322kkkkkkkkkxxxxxxxxx 高斯赛德尔迭代法都将都将 作为初值进行计算，结果见表2.2。表表2.2 例例2.5计算结果计算结果268(0)(0)(0)123(,)(0,0,0)xxx迭代次数迭代次数Jacobi迭代法迭代法G-S迭代法迭代法kx(k)y(k)z(k)x(k)y(k)z(k)000000016-4-3621324-11-16

47、-7-49321390372514213-422-175-1197高斯赛德尔迭代法269下面分析其收敛性，设Jacobi方法和Gauss-Seidel方法的迭代矩阵分别为1022()101220JMDL U1022()021086G SMDLU高斯赛德尔迭代法270下面分析其收敛性，设雅可比方法和高斯-赛德尔方法的迭代矩阵分别为1022()101220JMDL U1022()021086GMDLU分别计算两个矩阵的特征值即1 =2 =3=0, 故(MJ) = 00,求开方值的问题就是要解方程 x2-a=0这样归结出的是个非线性方程，从初等数学的角度来看它的求解有难度。该如何化难为易呢？2793

48、.1 引入设给定某个预报值x0,希望借助于某种简单方法确定校正量x，使校正值x1=x0+x能够比较准确地满足所给方程x2-a=0，即有280axx203.1 引入设给定某个预报值x0,希望借助于某种简单方法确定校正量x，使校正值x1=x0+x能够比较准确地满足所给方程x2-a=0，即有一般来说，x是一个小量，因此忽略掉x的平方项，上述方程便是一个关于x 的一次方程，据此写出x ，从而对校正值x1=x0+x 有281axx2000121xaxx3.1 引入反复施行这种预报校正方法，即可导出开方公式从给定的某个初值x00出发，利用上式反复迭代，即可获得满足精度要求的开方值282kkkxaxx211

49、a3.1 引入283例例3.1：用开方算法求根号 =？误差到10-6解：分别取x0=9和x0=20,90kkkxaxx211ixixi09.00000020.00000019.50000012.25000029.4868429.79846939.4868339.49178949.4868339.48683459.4868339.486833第三章 非线性方程（组）的数值解3.1 引入3.2非线性方程问题非线性方程问题3.3二分法3.4不动点迭代法3.5牛顿迭代法3.6解非线性方程组的牛顿迭代法284例例3.2 考虑下面的非线性方程(1) ex+1=0， (2) x6-2x5-8x4+14x3+

50、11x2-28x+12=0,(3) cosx=0;285例例3.2 考虑下面的非线性方程(1) ex+1=0，此方程无解(2) x6-2x5-8x4+14x3+11x2-28x+12=0,(3) cosx=0;(1)式无解；(2)式有三个解，x=1，-2，3，无论x取值的区间怎样变化，只要它包含-2,3这个区间，解的性质和个数不变。但这三个解的性质又各不相同，x=3是一个单根，x= -2是两重根，x=1则是三重根。(3)式随x的取值范围不同，解的个数也不同。事实上，在整个实数轴上有无穷多个解。在讨论非线性问题时，通常总是要更强调“ “定义域定义域” ”，往往要求的是自变量在一定范围内的解，道理

51、就在于此。286在科学研究和工程设计中, 经常会遇到的一大类问题是非线性方程 f(x) =0 的求根问题，其中f(x)为非线性函数。方程f(x)=0的根, 亦称为函数f(x)的零点。 287如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程 为n次代数方程，当n1时,方程显然是非线性的288111000 ()nnnnna xaxa xaa 给定如下非线性方程组 i=1,2,n （3.2.1)引入向量、向量函数记号 (3.2.2)则方程组可改为 F(x)=0 当n=1时，方程组(3.2.1)是一个非线性方程式 f(x) = 0 (

52、3.2.3)2890),(21nixxxf12nxxxx12( )( )( )( )nf xfxF xfx000 0定义定义3.1 设有x*使f(x*)=0则称x*为方程(3.2.3)的根或根或零点零点。若存在正整数m,使f(x)=(x-x*)mg(x) (3.2.4)且0g(x*)+，则称x*为(3.2.3)式的m重根重根。当m=1时，x*为单根，这时x*满足条件f(x*)=0, f(x*) 0;290第三章 非线性方程（组）的数值解3.1 引入3.2非线性方程问题3.3二分法二分法3.4不动点迭代法3.5牛顿迭代法3.6解非线性方程组的牛顿迭代法291292 二分法的基本思想二分法的基本思

53、想: 首先确定有根区间,将区间二等分, 通过判断f(x)的符号, 逐步将有根区间缩小, 直至有根区间足够地小, 便可求出满足精度要求的近似根。293二分法294例3.3 用二分法求方程f(x)=sinx-x2/4=0的非零实根的近似值，使误差不超过10-2.解295例3.3 用二分法求方程f(x)=sinx-x2/4=0的非零实根的近似值，使误差不超过10-2.解nanbnxn+1f(xn+1)01.521.750.21836111.7521.8750.075179621.87521.9375-0.049622831.8751.93751.902650.040420841.906251.937

54、51.9218750.15601451.9218751.93751.92968750.00536340第三章 非线性方程（组）的数值解3.1 引入3.2非线性方程问题3.3二分法3.4不动点迭代法不动点迭代法3.5牛顿迭代法3.6解非线性方程组的牛顿迭代法2963.4.13.4.1不动点迭代法不动点迭代法不动点迭代法是一种逐次逼近的方法，它的基本思想是通过构造一个递推关系式 (迭代格式) ，计算出根的近似值序列,并要求该序列收敛于方程的根.将方程f(x)=0改写成等价形式 x= (x) (3.4.1)定义定义3.2 称所有满足方程x = (x)的点x，为此方程的方程的不动点不动点。297取初始

55、迭代值x0，记x1 = (x0), x2 = (x1), , 一般有 (3.4.2)记数列x0, x1 ,xk,为xk，当k充分大时，如果xk有极限x*存在，即 (3.4.3)则对(2.1.6)式两边同时取极限，得 (3.4.4)这表明x*为等价方程x = (x)的不动点，即x*为方程f(x)=0的根。298kkxx1*kkxx lim *kkkk*xxxxlimlim1 上述求解方程f(x)=0的根的近似值的过程，称为不动点迭代不动点迭代法法，其中(3.4.2)式中的(x)称为迭代函数迭代函数，x0称为迭代的初迭代的初始值始值，公式(3.4.2)称为迭代格式迭代格式或迭代过程迭代过程，xk称

56、为根x*的第k次近似值，xk称为迭代数列迭代数列。若极限式(3.4.3)成立，则称此迭代法为收敛的收敛的，否则称为发散的发散的。 应用迭代法求方程根的基本问题是：1）化等价方程，构造迭代函数；2）研究迭代数列xk的收敛性、收敛速度及误差估计。2993.4.2迭代法的几何解释迭代法的几何解释 通常将方程f(x)=0化为与它同解的方程x = (x)的方法不止一种,有的收敛,有的不收敛,这取决于(x)的性态,方程x = (x)的求根问题在几何上就是确定曲线y= (x)与直线y=x的交点P*的横坐标。(a)(b)300迭代法的几何意义迭代法的几何意义 3013023.4.3 3.4.3 迭代法的收敛迭

57、代法的收敛定理定理3.1（收敛性定理收敛性定理）假定方程x = (x)满足： 1) (x)在a,b上连续；2)当xa,b时, (x) a,b；3) (x)存在，且对任取xa,b有 (3.4.6)则方程x=(x) 在a,b上存在唯一不动点x*，且对任取x0a,b，由迭代格式 xk+1=(xk) , k=0,1,2,所定义xk收敛于唯一不动点x* ，即 同时下列误差估计式成立 1L x*kkxx limkkkxxLxx1*11(3.4.7)01*1xxLLxxkk(3.4.8)证明证明：令h(x)=x-(x)，则h(x)在a,b上连续且可微。根据定理3.1的条件(2)知h(a)0, h(b)0，由

58、连续函数的介值定理，必有x*a,b，使h(x*)=0，即x*=(x*)。因此x*便为方程x=(x)于a,b内的不动点。假设另有 ，且 ，使 ，则由拉格朗日中值定理，得 其中 介于x*和 之间，因x*= ，故只有 ，这与定理3.1中|(x)|L1矛盾303,bax*xx )(xx)()()(*xxxxxxx0)(1)(*xxx1)(对任xa,b，由|(x)|L1得即对任xa,b， 。注意及304*111*2*120()()()()0kkkkkkkxxxxxxL xxL xxL xxk *limxxkkkkxxLxx*1*kkkkxxxxxx11*kkkxxxx11*得即(3.4.7)式成立，由于

59、再利用已证(3.4.7)式，即知(3.4.8)式成立。3051*1kkkkxxxxxxkkxxLxx*(1)kL xx111)()(kkkkkkxxLxxxx01212xxLxxLkkk306定理3.1给出了迭代法收敛的充分条件且十分适用。首先，对有根区间a,b并没有限制其范围大小，只要满足条件1）2）3）即可，故a,b可取为任意有限大小的区间。因此，可视此定理为大范围收敛定理大范围收敛定理。其次，在收敛性的证明过程中可以看出，迭代序列收敛速度的快慢取决于L的大小，L越小，收敛越快。结论中的第一个误差估计式可以作为上机控制迭代中止的一个条件；第二个误差估计式可用于估计满足指定误差精度所需的迭代

60、次数k.307事实上，由定理的证明过程可知，定理的条件(3)可放宽为：若(x) 在a, b满足Lipschitz条件，即对a, b 上的任意两点x1, x2, 有且Lipschitz常数L1，则定理依然成立。 2121Lxxxx例3.4求方程 f(x)=xex-1=0 (或x=e-x) 在1/2,ln2中的解。若要求迭代次数k至少应为多少？3086*10kxx解：取迭代函数 ，当x1/2,ln2时， (x)连续可微，又 ，故(x)为单调下降函数，且有又可见，(x)满足定理2.1的全部条件，因此x=e-x于1/2,ln2有唯一不动点，且由 所定义的迭代序列xk收敛到此不动点。取初值x0=1/2，