计算方法_8

nullnull上次课主要讲述了求方程根的迭代公式的建立2. 快速弦截法，它的迭代公式是1. Newton法，它的迭代公式是null还讲述了解线性方程组的两个迭代公式2. Gauss-Seidel 迭代法1. Jacobi 迭代法null3. 超松弛法(SOR)令超松弛法是利用加权将Gauss-Seidel法加速的一种方法。首先有Gauss-Seidel迭代公式：迭代过程的加速具有重要的意义。null称 ω 为松弛因子，通常取 。 松弛因子ω的取值对迭代公式的收敛速度影响极大。实际计算时，可以根据方程组的系数矩阵的性质，并结合实践计算的经验来选取合适的松弛因子。整理得到：null4. 迭代公式的矩阵示以及 b=(b1, b2, …, bn)T 和 x=(x1, x2, …, xn)T。线性方程组可用矩阵表示为Ax=b，其中null将A分裂成=L+D+U Jacobi迭代公式可表达为或者null迭代公式的收敛性与矩阵G有关，我们称它为迭代矩阵。下面简单介绍一些有关概念。或者 Gauss-Seidel迭代公式可表达为 都可以表达为null第二节 向量和矩阵的范数 1. 向量的范数 对于向量 X=(x1, x2, …, xn)，其长度记为||X||2:和向量对于向量序列则的充要条件是：null定义：对于向量 X=(x1, x2, …, xn)，其范数||X||为一个实数，满足：1．非负性：对于任意向量X, ||X||0,且||X||=0 X=0;2.齐次性：对于任意实数及任意向量X|| X||=| | ||X||3.三角不等式：对于任意向量X,Y||X+Y||||X||+||Y||null常用范数：2-范数：1-范数：p-范数：-范数：定理1. 对于任意向量X null证.得证。范数等价：若存在正数c1 ,c2 ,使得对任意向量X,均有则称范数 与 等价。null推论. 任何范数 均与 等价。特别， 彼此等价。注. 范数等价具有传递性。2.矩阵的范数设A为n阶方阵，称为矩阵A的范数。null注. 对于任意向量，有1．对于任意方阵A, ||A||0,且||A||=0 A=0;2.对于任意实数及任意方阵A|| A||=| | ||A||3.对于任意两个方阵A,B，有||A+B||||A||+||B||， ||AB|| ||A||||B||null仅验证3的第一个不等式。另外null对于向量的p-范数,相应矩阵的p-范数记为定理2.对阶方阵 ，有（行范数）（列范数）null 前面讲过对于解线性方程组 Ax=b 的迭代公式可表达为 x(k+1) = G x(k) + V b 定理4：若迭代矩阵G满足条件 ||G||<1，则迭代 公式收敛。第三节 迭代过程的收敛性1. 迭代收敛的充分条件null2. 对角占优方程组称为A对角占优阵。系数矩阵为对角占优阵的线性方程组称为对角占优方程组。如果n阶方阵A满足条件定理5：对角占优阵是非奇异的。 定理6：对角占优方程组的Jacobi迭代公式和 Gauss-Seidel迭代公式均收敛。null第六章 线性方程组的直接法 这是一个众所周知的古老算法，用在计算机上仍然十分有效。 要注意误差分析。舍入误差的积累有时甚至会严重影响解的精度。 null第一节 消去法(1)先将方程组(1)的第一个方程中 x1 的系数化为1，再消去后两个方程中的 x1 ，得到1. Jordan消去法例：求解方程组null(2)再将方程组(1)的第二个方程中 x2 的系数化为1，消去其它方程中的 x2 ，得到最后解得： x1 = 9，x2 = -1，x3 = -6null对一般形式的线性方程组第一步将方程组(3)的第一个方程中 x1 系数化为1，再消去其它方程中的 x1 ，得到(3)以上是Jordan消去法。nullnull第2步将新方程组的第二个方程中 x2 的系数化为1，再消去其它方程中的 x2 ，经过 k-1 步后原方程组被加工成：第 k 步将上面新方程组的第k个方程中 xk 的系数化为1，再消去其它方程中的 xk ，原方程组被加工成：null其中，施与的运算为：nullnull第n步以后方程组变成即为方程组的解。 Jordan消去法的乘除法的总计算量大约是n3/2 。null流程图的主体部分是1=>kakj/akk=>akj, j=k+1,…,n. bk/akk=>bk1=>iaij-aikakj=>aij,j=k+1,…,n. bi-aikbk=>bii=k?i=n?k=n?1+i=>i1+k=>kYNNNY输出b1, b2,…, bnnullGauss消去法是Jordan消去法的一种改进。仍用前面的例题来说明。第一步同Jordan消元法。第二步仅消去最后一个方程的 x2 ，得到解得 x3 = -6，回代到第二个方程得 x2 = -1，最后解出 x1 = 9。2. Gauss消去法Gauss消去法分消元和回代两个环节。null第一步同Jordan消元法，保留第一个方程。对剩下的方程进行消元，第 k-1 步以后方程组是消元过程第 k 步将上面新方程组的第k个方程中 xk 的系数化为1，再消去下面方程的 xk 项，原方程组被加工成：null其中，施与的运算为：null第 n 步以后方程组是null自下而上逐步回代，依次求得 xn , xn-1 ,…, x1 。回代过程Gauss消去法的乘除法的总计算量大约是 n3/3。 这两种消去法的一个共同问题是第 k 步要 用 作除法，因此要求它们不等于零。null在Gauss消去法的执行过程中第 k 步要用 作除法，因此它必须不等于零。一般线性方程组使用Gauss消去法时，即使 不为零但其绝对值很小，也会影响计算的精度。定理7：假设方程组是对角占优的，则 (k=1,2,…,n) 全不为零。(证明略)3. 选主元素null例：考察在十进制四位有效数的浮点计算机求解方程组经过第一步消元应得实际得到最后得到 x1 = 0，x2 = 1，结果严重失真。null再进行消元，得到为了避免这类错误的有效方法是调整方程次序。最后得到 x1 = x2 = 1，结果保证有四位有效数。null并且适当交换方程的次序，使得 绝对值最大，称它为第 k 步主元素。整个过程叫选主元。流程图如下：对于一般形式的方程组进行Gauss消元时，第 k 步检查方程组中的变量 xk 的系数选主元应和前面的Gauss消元法结合使用。nullakk=>d,k=>Lk+1=>i|aik|>|d|?aik=>d,i=>Li=n?i+1=>i≤≠d = a[k][k]; L = k; for (i=k+1; i<=n; i++) { if (fabs(a[i][k])>fabs(d)) { d= a[i][k]; L = i; } }aLj=>t,akj=>aLj,t=>akj j=k,k+1,…,n bL=>t,bk=>bL,t=>bkd=0?L=k?输出奇异结束if (fabs(d)==≠=≠null 这节课主要讲述了迭代法收敛条件是迭代矩阵 G 满足 ||G||<1。特别是对角占优方程组收敛。 我们还讲述了线性方程组求解两种消去法 1. Jordan消去法 2. Gauss消去法 作业：p198.2