第五章 线性代数方程组的解法.ppt

1、湘潭大学数学与计算科学学院,1,第五章 线性代数方程组的解法,湘潭大学数学与计算科学学院,2,本章讨论求解线性方程组：,的数值方法.,湘潭大学数学与计算科学学院,3,其中,湘潭大学数学与计算科学学院,4,但当方程组的阶数 很大时，计算量为,假设系数矩阵行列式,由Cramer法则,方程组有唯一解，且解可表示为：,湘潭大学数学与计算科学学院,5,常用的计算方法: 直接法和迭代法, 直接法：若不考虑计算过程中的舍入误差， 则通过有限步运算可以获得方程组的精确解.,湘潭大学数学与计算科学学院,6,迭代法：采用逐次逼近的方法, 即从一个初始 近似解出发, 按某种迭代格式, 逐步逼近方程组 的解, 直至满

2、足精度要求为止.,经典迭代法有：,湘潭大学数学与计算科学学院,7,1 预备知识,湘潭大学数学与计算科学学院,8,5.1.1 向量空间及相关概念和记号,1. 向量的范数,湘潭大学数学与计算科学学院,9,根据定义:,湘潭大学数学与计算科学学院,10,湘潭大学数学与计算科学学院,11,对于常用的范数 , ,可以算出,湘潭大学数学与计算科学学院,12,可以理解为,可以理解为对任何向量范数都成立。,2. 向量序列的收敛性,湘潭大学数学与计算科学学院,13,对于 上的任何向量范数,我们可以定义矩阵范数.,1. 矩阵的范数,5.1.2 矩阵的一些相关概念及记号,湘潭大学数学与计算科学学院,14,定理5.3

3、矩阵的从属范数具有下列基本性质：,1） ，当且仅当 时，,2),定理5.3中的性质 1), 2) 和 3)是一般范数所满足的基本性质，性质 4)、5) 被称为相容性条件，一般矩阵范数并不一定满足该条件.,湘潭大学数学与计算科学学院,15,非从属范数的矩阵范数,例如，矩阵 的Frobenius范数（F-范数）,可以证明Frobenius范数满足相容性条件,对方阵 以及 有,湘潭大学数学与计算科学学院,16,三种重要的从属范数是：,（1）矩阵的1-范数(列和范数):,（2）矩阵的 -范数(行和范数):,（3）矩阵的2-范数:,其中 : 的最大特征值,湘潭大学数学与计算科学学院,17,对任何,从而,

4、（列和范数）,湘潭大学数学与计算科学学院,18,现设,令,且,湘潭大学数学与计算科学学院,19,解：,按定义,湘潭大学数学与计算科学学院,20,矩阵范数的等价定理：,几种常用范数的等价关系：,湘潭大学数学与计算科学学院,21,2. 谱半径,此时,若 为对称阵，,（ 因为 ）,湘潭大学数学与计算科学学院,22,证明,首先证明（1）.,关于矩阵的谱半径与矩阵的范数之间有如下关系.,湘潭大学数学与计算科学学院,23,今设 为 的特征值,从而,即,由 的任意性得,证毕,给定 的某一种范数 ，,湘潭大学数学与计算科学学院,24,湘潭大学数学与计算科学学院,25,定义5.3,称矩阵序列 是收敛的，,如果存

5、在 ，使得,此时称 为矩阵序列 的极限,记为,3. 矩阵级数的收敛性,湘潭大学数学与计算科学学院,26,证明：,则由定理5.4可以选择一种范数，,因此当 时，,于是得,充分性,湘潭大学数学与计算科学学院,27,必要性,设,令 为某一使 的特征值,假如 为对应的特征向量,则,这就是说对所有的,证毕,湘潭大学数学与计算科学学院,28,定理5.6(Neumann引理) 矩阵幂级数 收敛的充分必要条件为 ，且当 时有,证明：,若 收敛，则,从而,反之，若,（ 为 的特征值）,湘潭大学数学与计算科学学院,29,因此 非奇异,于是由恒等式,得到,由于,因而有,即得,证毕,湘潭大学数学与计算科学学院,30,

6、该定理将被应用于解方程组的扰动分析和Gauss消去法的舍入误差分析.,湘潭大学数学与计算科学学院,31,4 矩阵的条件数,湘潭大学数学与计算科学学院,32,湘潭大学数学与计算科学学院,33,5. 几种特殊矩阵,且至少有一个 使不等式严格成立，则称矩阵,为按行对角占优矩阵。 若对 严格不等,式均成立，则称 为按行严格对角占优矩阵.,类似地，可以给出矩阵 为按列（严格）对角 占优矩阵的定义.,湘潭大学数学与计算科学学院,34,定义5.6,设 为 阶方阵（ ），若存在 阶,置换矩阵P，使得,其中 为 阶方阵, 为 阶方阵,则称 为可约矩阵；如果不存在这样的置换矩阵，,则称为不可约矩阵.,湘潭大学数学

7、与计算科学学院,35,使得,则称 为可约矩阵；否则，称 为不可约矩阵.,例如，三对角矩阵,是不可约对角占优的,湘潭大学数学与计算科学学院,36,定理5.8 若 为严格对角占优或为对角占优且 不可约时，则 非奇异.,湘潭大学数学与计算科学学院,37,湘潭大学数学与计算科学学院,38,湘潭大学数学与计算科学学院,39,2 Gauss消去法,湘潭大学数学与计算科学学院,40,线性代数方程组的系数矩阵为以下3种情形时, 其解可以容易求出.,湘潭大学数学与计算科学学院,41,湘潭大学数学与计算科学学院,42,5.2.1 高斯消去法,思路,(1) 将A化为上三角阵， (2) 回代求解。,湘潭大学数学与计算

8、科学学院,43,消元,记,其中,第k步：设 ，计算因子 且计算,共进行 ？ 步,n 1,湘潭大学数学与计算科学学院,44,回代,定理,若A的所有顺序主子式 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。,注：事实上，只要 A 非奇异，即 A1 存在，则可通过 逐次消元及行交换，将方程组化为三角形方程组， 求出唯一解。,湘潭大学数学与计算科学学院,45, 运算量,由于计算机中乘除运算的时间远远超过加减 运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。,Gauss 消去法:,(n k) 次,(n k)2 次,(n k) 次,消元乘除

9、次数：,1 次,(n i +1) 次,回代乘除次数：,Gauss 消去法的总乘除次数为 ，运算量为 级。,湘潭大学数学与计算科学学院,46,例：单精度解方程组,用Gauss 消去法计算：,8个,小主元可能导致 计算失败。,5.2.2 Gauss主元素消去法,湘潭大学数学与计算科学学院,47,1. 全主元消去法,每一步选绝对值最大的元素为主元素，保证 .,第 k步: 选取, If ik k , 则交换第 k 行与第 ik 行; If jk k , 则交换第 k 列与第 jk 列;, 消元,注：列交换改变了 xi 的顺序，须记录交换次序，解完后再换回来。,2. 列主元消去法,省去换列的步骤，每次仅

10、选一列中最大的主元素。,湘潭大学数学与计算科学学院,48,例：,注：列主元法没有全主元法稳定。,例：,湘潭大学数学与计算科学学院,49, 高斯消去法的矩阵形式,第1步:,记 L1 =,，则,5.2.3 矩阵的三角分解,湘潭大学数学与计算科学学院,50,由上可见,于是,湘潭大学数学与计算科学学院,51,L,单位下三角阵,A 的 LU 分解,湘潭大学数学与计算科学学院,52,若A的所有顺序主子式均不为0，则 A 的 LU 分解 唯一（其中 L 为单位下三角阵）。,证明：由前面推导可知，LU 分解存在。下面证明唯一性。,若不唯一，则可设 A = L1U1 = L2U2 ，推出,上三角阵,对角元为1

11、的下三角阵,定理5.10,湘潭大学数学与计算科学学院,53,湘潭大学数学与计算科学学院,54, Doolittle 分解,通过比较法直接导出L 和 U 的计算公式。,思路,湘潭大学数学与计算科学学院,55,固定 i : 对 j = i, i+1, , n 有,lii = 1,a,将 i ，j 对换，对 j = i+1, , n 有,b,一般采用列主元法 增强稳定性。但注意 也必须做相应的 行交换。,湘潭大学数学与计算科学学院,56,L和U存储在矩阵的原来位置，且不影响计算,湘潭大学数学与计算科学学院,57, Crout 分解,比较两边对应的元素，得,湘潭大学数学与计算科学学院,58,其中,、

12、分别为单位下、上三角阵,例,实际上，进一步可以做分解,湘潭大学数学与计算科学学院,59, 对称正定矩阵的Cholesky分解,湘潭大学数学与计算科学学院,60,将对称 正定阵 A 做 LU 分解,即,为什么 uii 0?,因为det(Ak) 0,则 仍是下三角阵,湘潭大学数学与计算科学学院,61,注： 对于对称正定阵 A ，从 可知对任意k i 有 。即 L 的元素不会增大，误差可控，不需选主元。,湘潭大学数学与计算科学学院,62,算法: Cholesky分解 将对称正定 nn矩阵 A分解成 LLT, 这里 L是下三角阵 Input: 矩阵A的维数n; 矩阵A的元素 aij 1 i, j n

13、. Output: 矩阵L 的元素 lij ： 1 j i and 1 i n . Step 1 Set ; Step 2 For j = 2, , n, set ; Step 3 For i = 2, , n1, do steps 4 and 5 Step 4 Set ; Step 5 For j = i+1, , n, set ; Step 6 Set ; Step 7 Output ( lij for j = 1, , i and i = 1, , n ); STOP.,运算量为 O(n3/6)， 比普通LU 分解少一半，但有 n 次开方。用A = LDLT 分解，可省开方时间。,湘潭大

14、学数学与计算科学学院,63, 解三对角方程组的追赶法,步骤1: 对 A 作Crout 分解,直接比较等式两边的元素，可得到计算公式。,步骤2: 追即解 ：,步骤3: 赶即解 ：,与Gauss消去法类似，一旦 i = 0 则算法中断，故并非任何 三对角阵都可以用此方法分解。,湘潭大学数学与计算科学学院,64,注： 如果 A 是严格对角占优阵，则不要求三对角线上的所有元素非零。 根据不等式 可知：分解过程中，矩阵元素不会过分增大，算法保证稳定。 运算量为 O(6n)。,湘潭大学数学与计算科学学院,65,3 Gauss消去法的误差分析,湘潭大学数学与计算科学学院,66,求解 时，A 和 的误差对解

15、有何影响？, 设 A 精确， 有误差 ，得到的解为 ，即,又,湘潭大学数学与计算科学学院,67, 设 精确，A有误差 ，得到的解为 ，即,(只要 A充分小，使得,湘潭大学数学与计算科学学院,68, cond (A) 取决于A，与解题方法无关。,湘潭大学数学与计算科学学院,69,精确解为,A1 =,解：考察 A 的特征根,39206 1,此时精确解为,2.0102 200%,湘潭大学数学与计算科学学院,70, Gauss消去法的舍入误差,舍入误差分析方法 1. 向前误差分析方法：按照所执行的运算次序而估计舍入误差积累的界限. 这种方法的好处是估计比较准确，但对复杂算法（如Gauss消去法）一般难

16、以进行。 2. 向后误差分析方法：将实际计算过程的误差转换为关于原始数据的误差。,湘潭大学数学与计算科学学院,71,对Gauss消去法,其具体提法是：,对于系数矩阵扰动：,求解 时, 所得的计算解 是 如下扰动方程,的精确解。,湘潭大学数学与计算科学学院,72,Gauss消去法由两个独立算法所组成: 一是对A做LU分解; 二是求解三角方程组. 这两个独立运算均会产生舍入误差. 如果是选主元的Gauss消去法,由于只增加了 矩阵行、列的交换，并不产生新的舍入误差，因此并不影响误差分析。,湘潭大学数学与计算科学学院,73,湘潭大学数学与计算科学学院,74,湘潭大学数学与计算科学学院,75,湘潭大学

17、数学与计算科学学院,76,由上可见，对Gauss消去法，,湘潭大学数学与计算科学学院,77,4 解线性方程组的迭代法,湘潭大学数学与计算科学学院,78, 如何建立迭代格式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？,思 路：,湘潭大学数学与计算科学学院,79,Jacobi 法和 Gauss - Seidel 法, Jacobi 迭代方法,湘潭大学数学与计算科学学院,80,写成矩阵形式：,L,U,D,Jacobi 迭代阵,湘潭大学数学与计算科学学院,81,解,湘潭大学数学与计算科学学院,82,湘潭大学数学与计算科学学院,83,算法: Jacobi迭代方法 求解 给定初始值 . Input:

18、方程和未知量的个数 n; 矩阵元素 a ; 元素 b ; 初始近似值 X0 ; 误差容限 TOL; 最大迭代次数 Nmax. Output: 近似解 X 或失败的信息. Step 1 Set k = 1; Step 2 While ( k Nmax) do steps 3-6 Step 3 For i = 1, , n Set ; /* 计算 xk */ Step 4 If then Output (X ); STOP; /* 成功 */ Step 5 For i = 1, , n Set X 0 = X ; /* 更新 X0 */ Step 6 Set k +; Step 7 Output

19、(超过最大迭代次数); STOP. /* 失败 */,如果 aii = 0，怎么办?,迭代过程中，A 的元素 不改变，故可以事先调整好 A 使得 aii 0，否则 A不可逆。,必须等X(k)完全计算 好了才能计算X(k+1)，因此 需要两组向量存储。,湘潭大学数学与计算科学学院,84, Gauss - Seidel 迭代方法, ,只存一组向量即可。,写成矩阵形式：,Gauss-Seidel 迭代阵,湘潭大学数学与计算科学学院,85,例 求方程组,的GaussSeidel迭代格式。,湘潭大学数学与计算科学学院,86,湘潭大学数学与计算科学学院,87, 松弛法,换个角度看Gauss - Seide

20、l 方法：,其中ri(k+1) =,残量,相当于在 的基础上加个余项生成 。,湘潭大学数学与计算科学学院,88,写成矩阵形式：,松弛迭代阵,湘潭大学数学与计算科学学院,89,解,湘潭大学数学与计算科学学院,90,湘潭大学数学与计算科学学院,91,的收敛条件,充分条件: |B| 1,必要条件:,0, 迭代法的收敛性,湘潭大学数学与计算科学学院,92,迭代,证明：,湘潭大学数学与计算科学学院,93,（充分条件）若存在一个矩阵范数使得 | B | = q 1, 则迭代收敛，且有下列误差估计：,证明：,湘潭大学数学与计算科学学院,94,证明：首先需要一个引理,若A 为严格对角占优阵，则det(A) 0

21、，且所有的 aii 0。,证明：若不然，即det(A) = 0，则 A 是奇异阵。,存在非零向量 使得,我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别证明：任何一个| | 1 都不可能是对应迭代阵的特征根，即 | I B | 0 。,Jacobi: BJ = D1( L + U ),aii 0,如果 | | 1 则,是严格对角占优阵,关于Gauss-Seidel迭代的证明 与此类似。,湘潭大学数学与计算科学学院,95,湘潭大学数学与计算科学学院,96,若线性方程组 的系数矩阵 是 对角元素为正的实对称阵，则Jacobi方法收敛的充 分必要条件是 和 同时正定.,定理,定理,

22、湘潭大学数学与计算科学学院,97,注：Jacobi方法和GS方法的收敛条件大多数是互不包含的. 二种方法都存在收敛性问题。 Gauss-Seidel方法收敛时，Jacobi方法可能不收敛； 而Jacobi方法收敛时， Gauss-Seidel方法也可能不收敛。,湘潭大学数学与计算科学学院,98,例：给出方程组 其中,问:Jacobi迭代法和Gauss-Seidel迭代法是否收敛？,解：,对,湘潭大学数学与计算科学学院,99,而,即,所以，对,Jacobi方法收敛，G-S方法发散,同理，对于,其中,湘潭大学数学与计算科学学院,100,即得,而,湘潭大学数学与计算科学学院,101,则,湘潭大学数学与计算科学学院,102,设 A 可逆，且 aii 0，松弛法从任意 出发对某个 收敛 ( H ) 1。,H的计算是太复杂， 谱半径难于获得!,定理,湘潭大学数学与计算科学学院,10