《数值分析课件ch5章节》由会员分享，可在线阅读，更多相关《数值分析课件ch5章节（115页珍藏版）》请在金锄头文库上搜索。
1、湘潭大学数学与计算科学学院,1,第五章 线性代数方程组的解法,湘潭大学数学与计算科学学院,2,注：如果没有特别说明，下面总假定 系数行列式的值,其中,湘潭大学数学与计算科学学院,3,利用 法则求解时存在困难：当方程 组的阶数 很大时，计算量为,常用计算方法:, 直接解法：它是一类精确方法，即若不考虑 计算过程中的舍入误差，那么通过有限步运 算可以获得方程解的精确结果.,湘潭大学数学与计算科学学院,4,迭代解法：所谓迭代方法，就是构造某种极限 过程去逐步逼近方程组的解.,经典迭代法有：,湘潭大学数学与计算科学学院,5,1 预备知识,湘潭大学数学与计算科学学院,6, 向量范数,常用向量范数：,注：
2、,湘潭大学数学与计算科学学院,7,根据定义:,湘潭大学数学与计算科学学院,8,湘潭大学数学与计算科学学院,9,湘潭大学数学与计算科学学院,10,对于常用的范数 , ,可以算出,湘潭大学数学与计算科学学院,11,可以理解为,可以理解为对任何向量范数都成立。, 向量序列的收敛性,湘潭大学数学与计算科学学院,12, 矩阵范数,(4)* | AB | | A | | B | （相容性),(5)* | Ax | | A | | x | （相容性),湘潭大学数学与计算科学学院,13,常用矩阵范数：,Frobenius 范数, 向量| |2的直接推广,对方阵 以及 有,利用Cauchy 不等式 可证。,从属
3、范数,由向量范数 | |p 导出关于矩阵 A Rnn 的 p 范数:,则,矩阵 ATA 的最大 特征根,湘潭大学数学与计算科学学院,14, 我们只关心有相容性的范数，从属范数总是相容的。,若不然，则必存在某个向量范数 | |v 使得 对任意A 成立。,反例?,湘潭大学数学与计算科学学院,15,对任何,从而,（列和范数）,湘潭大学数学与计算科学学院,16,现设,令,且,湘潭大学数学与计算科学学院,17,解：,按定义,湘潭大学数学与计算科学学院,18,矩阵范数的等价定理：,几种常用范数的等价关系：,湘潭大学数学与计算科学学院,19,定义5.3,称矩阵序列 是收敛的，,如果存在 ，使得,此时称 为矩
4、阵序列 的极限,记为, 矩阵序列的收敛性,湘潭大学数学与计算科学学院,20, 谱半径, (A),湘潭大学数学与计算科学学院,21,证明：,由从属范数的相容性，得到,将任意一个特征根 所对应的特征向量 代入,证明：,A对称,若 是 A 的一个特征根，则2 必是 A2 的特征根。,又：对称矩阵的特征根为实数，即 2(A) 为非负实数， 故得证。,对某个 A 的特征根 成立,所以2-范数亦称为谱范数。,湘潭大学数学与计算科学学院,22,证明：, 若不然，则 有非零解，即存在非零向量 使得,湘潭大学数学与计算科学学院,23,证明：,“” 若 是 B 的特征值, 则k 是 Bk 的特征值 。,则 (B)
5、k = max | | k = | mk |, ( Bk ) | Bk | 0, (B) 1,“” 首先需要一个引理,对任意 0, 存在从属范数 | | 使得 | A | (A) + 。,由 (B) 1 可知存在从属范数| | 使得 | B | 1。,| Bk | | B |k 0 as k ,Bk 0, ( B ) 1,湘潭大学数学与计算科学学院,24,定理（Neumann引理） 矩阵幂级数 收敛的充分必要条件为 ，且当 时有,证明：,若 收敛，则,从而,反之，若,（ 为 的特征值）, 矩阵级数的收敛性,湘潭大学数学与计算科学学院,25,因此 非奇异,于是由恒等式,得到,由于,因而有,即得,
6、证毕,湘潭大学数学与计算科学学院,26,推论 当 时， 非奇异，且,证明:,因为,非奇异，并且,从而,证毕,湘潭大学数学与计算科学学院,27, 矩阵的条件数,称为A的条件数，记为cond (A),常用条件数有：,cond (A)1,cond (A),cond (A)2,特别地，若 A 对称，则,条件数的性质： A可逆，则 cond (A)p 1； A可逆， R 则 cond ( A) = cond (A) ； A正交，则 cond (A)2=1； A可逆，R正交，则 cond (RA)2 = cond (AR)2 = cond (A)2 。,湘潭大学数学与计算科学学院,28, 几种特殊矩阵,类
7、似地，可以给出矩阵 为按列（严格）对角 占优矩阵的定义.,湘潭大学数学与计算科学学院,29,定义6,设 为 阶方阵（ ），若存在 阶,置换矩阵P，使得,其中 为 阶方阵, 为 阶方阵,则称 为可约矩阵；如果不存在这样的置换矩阵，,则称为不可约矩阵.,定义2 的一个等价说法是:设 为阶方阵,如果存在 的两个非空子集 和 满足,湘潭大学数学与计算科学学院,30,使得,则称 为可约矩阵；否则，称 为不可约矩阵.,例如，三对角矩阵,是不可约对角占优的,湘潭大学数学与计算科学学院,31,定理 若 为严格对角占优或为对角占优且 不可约时，则 非奇异.,湘潭大学数学与计算科学学院,32,2 高斯消元法, 高
8、斯消元法：,湘潭大学数学与计算科学学院,33,消元,记,其中,Step k：设 ，计算因子 且计算,共进行 ？ 步,n 1,湘潭大学数学与计算科学学院,34,回代,定理,若A的所有顺序主子式 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。,注：事实上，只要 A 非奇异，即 A1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。,湘潭大学数学与计算科学学院,35, 选主元消去法,例：单精度解方程组,用Gaussian 消去法计算：,8个,小主元可能导致 计算失败。,湘潭大学数学与计算科学学院,36, 全主元消去法,每一步选绝对值最大的元素为主元素，保证 。,Step
9、 k: 选取, If ik k then 交换第 k 行与第 ik 行; If jk k then 交换第 k 列与第 jk 列;, 消元,注：列交换改变了 xi 的顺序，须记录交换次序，解完后再换回来。, 列主元消去法,省去换列的步骤，每次仅选一列中最大的元。,湘潭大学数学与计算科学学院,37,例：,注：列主元法没有全主元法稳定。,例：,湘潭大学数学与计算科学学院,38, 运算量,由于计算机中乘除运算的时间远远超过加减 运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。, Gaussian 消去法:,(n k) 次,(n k)2 次,(
10、n k) 次,消元乘除次数：,1 次,(n i +1) 次,回代乘除次数：,Gaussian 消去法的总乘除次数为 ，运算量为 级。,湘潭大学数学与计算科学学院,39, 完全选主元法,比 Gaussian Elimination多出 ，保证稳定，但费时。, 列主元法,比 Gaussian Elimination只多出 ，略省时，但不保证稳定。,湘潭大学数学与计算科学学院,40,* 矩阵的三角分解, 高斯消元法的矩阵形式,Step 1:,湘潭大学数学与计算科学学院,41,单位下三角阵,A 的 LU 分解,湘潭大学数学与计算科学学院,42,证明：由1中定理可知，LU 分解存在。下面证明唯一性。,若
11、不唯一，则可设 A = L1U1 = L2U2 ，推出,上三角阵,对角元为1 的下三角阵,注： L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。 实际上只要考虑 A* 的 LU 分解，即 ，则 即是 A 的 Crout 分解。,湘潭大学数学与计算科学学院,43, Doolittle分解： LU 分解的紧凑格式,湘潭大学数学与计算科学学院,44,固定 i : 对 j = i, i+1, , n 有,lii = 1,a,将 i ，j 对换，对 j = i, i+1, , n 有,b,一般采用列主元 法增强稳定性。但注意 也必须做相应的 行交换。,25,湘潭大学数学与计算科学学院
12、,45,作业: p.171-172 1题 , 3题 , 10题 , 11题 ,13题 , 14题,湘潭大学数学与计算科学学院,46,作业: p.172 5题 , 6题 ,湘潭大学数学与计算科学学院,47, 平方根法 /* Choleskiy分解 */： 对称正定矩阵的分解法,回顾：对称正定阵的几个重要性质, A1 亦对称正定，且 aii 0,若不然，则,对任意 , 存在 , 使得 , 即 。, A 的顺序主子阵 Ak 亦对称正定,对称性显然。对任意 有 , 其中 。, A 的特征值 i 0,设对应特征值 的非零特征向量 为 ，则 。, A 的全部顺序主子式 det ( Ak ) 0,因为,湘潭
13、大学数学与计算科学学院,48,将对称 正定阵 A 做 LU 分解,即,为什么 uii 0?,因为det(Ak) 0,则 仍是下三角阵,注： 对于对称正定阵 A ，从 可知对任意k i 有 。即 L 的元素不会增大，误差可控，不需选主元。,湘潭大学数学与计算科学学院,49,算法: Choleskiy分解 将对称正定 nn矩阵 A分解成 LLT, 这里 L是下三角阵 Input: 矩阵A的维数n; 矩阵A的元素 aij 1 i, j n . Output: 矩阵L 的元素 lij ： 1 j i and 1 i n . Step 1 Set ; Step 2 For j = 2, , n, set
14、 ; 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.,因为A 对称，所以只需存半个 A，即 其中,运算量为 O(n3/6)， 比普通LU 分解少一半，但有 n 次开方。用A = LDLT 分解，可省开方时间。,湘潭大学数学与计算科学学院,50, 解三对角方程组的追赶法,Step 1: 对 A 作Crout 分解,直接比较等式两边的元素，可得到计算公式。,Step 2: 追即解 ：,Step 3: 赶即解 ：,与Gauss消去法类似，一旦 i = 0 则算法中断，故并非任何 三对角阵都可以用此方法分解。,湘潭大学数学与计算科学学院,51,注： 如果 A
