《数值方法第三章2 线性方程组》由会员分享，可在线阅读，更多相关《数值方法第三章2 线性方程组（53页珍藏版）》请在金锄头文库上搜索。
1、第3章 解线性方程组的直接方法 本章要点 高斯消元法、高斯列主元素消去法。 矩阵三角分解法、追赶法。 向量和矩阵的范数。3.3 矩阵三角分解法 矩阵三角分解法是高斯消去法解线性方程组的一 种变形解法 3.3.1 矩阵三角分解原理 应用高斯消去法解n阶线性方程组Ax=b, 经过n步消元之后, 得出一个等价的上三角型方程组 A(n) x=b(n), 对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。将非奇异阵A分解成一个下三角阵L和一个上三 角阵U的乘积 A=LU称为对矩阵A的三角分解，又称LU分解其中方程组Ax=b的系数矩阵A经过顺序消元逐步化 为上三角型A(n),相当于用
2、一系列初等变换左乘 A的结果。事实上，第1列消元将A(1)=A化为 A(2)，若令：则根据距阵左乘有L1A(1)=A(2)第2列消元将A(2)化为A(3)，若令：经计算可知 L2A(2)=A(3),依此类推,一般有LkA(k)=A(k+1)mi1= a(1) i1/ a(1) 11 i=2,3,n于是矩阵 经过消元化为上三角阵 的过程可表示为 上述矩阵 是一类初等矩阵, 它们都是单位下三角阵，且其逆矩阵也是单位 下三角阵,只需将 改为 , 就得到 。即 于是有 其中 L为由乘数构成的单位下三角阵，U为上三角阵，由此可见，在 的条件下，高斯消去法实质上是将方程组的系数矩阵A分解为两个三角矩阵的乘
3、积A=LU。这种把非奇异矩阵A分解成一个下三角矩阵L和一个上三角矩阵U的乘积称为矩阵的三角分解，又称LU分解。显然，如果 ,由行列式的性质知，方程组系数矩阵A的前n-1个顺序主子矩阵 非奇异，即顺序主子式不等于零，即其中 （A的主子阵） 反之,可用归纳法证明,如果A的顺序主子式 则 于是得到下述定理： 定理3.5 设 。如果A顺序各阶主子式,则A可惟一地分解成 一个单位下三角阵L和一个非奇异的上三角阵U的乘积。证：由于A各阶主子式不为零,则消元过程能 进行到底, 前面已证明将方程组的系数矩阵A 用初等变换的方法分解成两个三角矩阵的乘 积A=LU的过程。现仅证明分解的惟一性。设A有两种LU分解
4、其中 为单位下三角阵， 为上三角阵 A的行列式 均为非奇异矩阵,有上式两边左边同乘 ，右边同乘 得上式左边为单位下三角阵,右边为上三角阵,故应为单 位阵,即惟一性得证。 把A分解成一个单位下三角阵L和一个上三角阵U的乘积称为杜利特尔（Doolittle）分解。其中 若把A分解成一个下三角阵L和一个单位上三角阵U的乘积称为（克洛特分解Crout） 其中 3.3.2 用三角分解法解方程组求解线性方程组Ax=b时,先对非奇异矩阵 A进行LU分解使A=LU，那么方程组就化为LU x=b 从而使问题转化为求解两个简单的的三角方 程组L y=b 求解 yU x=y 求解 x 这就是求解线性方程组的三角分解
5、法的基本 思想。下面只介绍杜利特尔（Doolittle）分 解法。设A=LU为由矩阵乘法规则由此可得U的第1行元素和L的第1列元素再确定U的第k行元素与L的第k列元素,对 于k=2,3, ,n计算： 计算U的第k行元素 （j=k,k+1,n） 计算L的第k列元素 （i=k,k+1,n） （j=k,k+1,n） 计算U的第k行元素 固定 k ，对 j = i, i+1, , n 有（j=k,k+1,n） 计算L的第k列元素 同理，固定 k ，对 i = k, k+1, , n 有（i=k,k+1,n） 利用上述计算公式便可逐步求出U与L的各元素求解 Ly=b , 即计算: 求解 Ux=y , 即
6、计算： 显然, 当 时, 解 Ax=b直接三角分解法计算才能完成。设A 为非奇异矩阵, 当 时计算将中断或者当 绝对值很小时，按分解公式计算可 能引起舍入误差的积累，因此可采用与列 主元消去法类似的方法，对矩阵进行行交 换，则再实现矩阵的三角分解。用直接三角分解法解Ax=b大约需要 次乘除法。 三角分解法的存放元素的方法：的元素存放在A的，即 uuuuuu U lllL = =332322131211323121 111相应位置。优点：不用存储中间量，适合于计算机计算。说明：以上计算方法实际上是消去法的变形 紧凑格式。例3.8 用三角分解法解方程组 求解 Ly=b 得 y= 2，2，1T 求解
7、 Ux=y 得 x= -1，0，1 T所以方程组的解为 设 ，试将A进行三角分解。解：由高斯消去法得到用直接三角分解法解方程组 。解： 3.4 平方根法工程实际计算中,线性方程组的系数矩阵常常具有 对称正定性，其各阶顺序主子式及全部特征值均大于0 。矩阵的这一特性使它的三角分解也有更简单的形式 ，从而导出一些特殊的解法，如平方根法与改进的平 方根法。定理3.6 设A是c，则存在惟一的对角元素均为正 数的下三角阵L，使A=LLT 证：因A是正定矩阵, A的顺序主子式 i0, i=1,2,n 因此存在惟一的分解 A=LU n A对称：AT=A; n A正定：A的各阶顺序主子式均大于零。对称和正定L
8、是单位下三角阵, U是上三角阵, 将U再分解 其中D为对角阵, U0为单位上三角阵，于是A = L U = L D U0 又 A = AT = U0TD LT 由分解惟一性, 即得 U0T=L A=L D LT 记 又因为det(Ak)0,(k=1,2,n), 故 于是对角阵D还可分解 其中 为下三角阵,令L=L1，定理得证。 将A=LLT展开，写成 按矩阵乘法展开，可逐行求出分解矩阵L的元素，计 算公式是对于i=1,2,n j=i+1, i+2,n 这一方法称为平方根法,又称乔累斯基(Cholesky)分 解,它所需要的乘除次数约 为数量级,比LU分解 节省近一般的工作量。 例3.9 平方根
9、法求解方程组 解: 因方程组系数矩阵对称正定,设A= ,即： 由Ly=b解得 由 解得 由此例可以看出，平方根法解正定方程组的缺 点是需要进行开方运算。为避免开方运算，我们改 用单位三角阵作为分解阵，即把对称正定矩阵A分 解成 的形式，其中 为对角阵，而 是单位下三角阵,这里分 解公式为 据此可逐行计算 运用这种矩阵分解方法,方程组Ax=b即可归结为求解两个上三角方程组 和其计算公式分别为 和 求解方程组的上述算法称为改进的平方根法。这种 方法总的计算量约为 ，即仅为高斯消去法计 算量的一半。 3.5 追赶法 在数值计算中,有一种系数矩阵是三对角方程组 简记为Ax=f,A满足条件 （1）（2）
10、（3）用归纳法可以证明，满足上述条件的三对角线 性方程组的系数矩阵A非奇异，所以可以利用矩阵 的直接三角分解法来推导解三对角线性方程组的计 算公式，用克洛特分解法，将A分解成两个三角阵 的乘积，设A=LU 按乘法展开 则可计算 可依次计算 当， 由上式可惟 一确定L和U。 例3.9 用追赶法求解三对角方程组 解 由Ly=f 解出y又由Ux=y解出x 记笔记3.6 3.6 向量和矩阵的范数向量和矩阵的范数为了研究线性方程组近似解的误差估计和迭代法的收敛性, 有必要对向量及矩阵的“大小”引进某种度量-范数的概念。向量范数是用来度量向量长度的,它可以看成是二、三维解析几何中向量长度概念的推广。用Rn
11、表示n维实向量空间。记笔记3.6 3.6 向量和矩阵的范数向量和矩阵的范数定义3.2 对任一向量XRn, 按照一定规则确定一个实数与它对应, 该实数记为|X|, 若|X|满足下面三个性质:(1) |X|0；|X|=0当且仅当X=0；(2) 对任意实数， | X|=| | |X|；(3) 对任意向量YRn，|X+Y| |X|+|Y|则称该实数|X|为向量X的范数在在R Rn n中，常用的几种范数有：中，常用的几种范数有：记笔记其中其中x x1 1,x,x2 2, , ,x,xn n分别是分别是X X的的n n个分量。以上定义的个分量。以上定义的范数分别称为范数分别称为1-1-范数，范数，2-2-
12、范数和范数和 - -范数范数可以验证它们都是满足范数性质的，其中可以验证它们都是满足范数性质的，其中 是由内积导出的向量范数。是由内积导出的向量范数。3.6 3.6 向量和矩阵的范数向量和矩阵的范数 当不需要指明使用哪一种向量范数时，就用记号|.|泛指任何一种向量范数。 有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。 设x*为Ax=b的精确解，x为其近似解，则其绝对误差可表示成|x- x* |，其相对误差可表示成记笔记3.6 3.6 向量和矩阵的范数向量和矩阵的范数或例3.10 证明对任意同维向量x , y 有 证 ： 即 例3.11 设x=(1, 0, -1, 2)T, 计算 解
13、: =1+0+|-1|+2=4定理3.7 对于任意向量x ,有证: 即 当 p， 定义3.4 ( 向量序列的极限 ) 设 为 中的一向量序列， , 记。如果 (i =1,2, n)，则称 收敛于向量 ，记为定理3.8 （向量范数的等价性）设 为 上任意两种向量范数, 则存在常数C1, C20,使得对任意 恒有（证:略） 定理3.9 其中 为向量中的任一种范数。 证 由于 而对于 上的任一种 范数, 由定理3.7 知存在常数C1，C2，使 于是可得 从而定理得证。 定义3.5（矩阵的范数）如果矩阵 的某个非负的实值函数 ，满足则称 是 上的一个矩阵范数(或模) 定义3.6（矩阵的算子范数） 设n维向量X和 n 阶方阵A，当给定一种向量范数| X | 时，则定义 为矩阵的范数，并称为矩阵的算子范数。矩阵范数定义的另一种方法从定义可以看出，矩阵范数和向量范数密切相关。矩阵范数的性质可由向量范数定义直接验证。(1) 设A0, x0, 使Ax0, 根据向量范数的性质Ax 0, 所以0x0, 使Ax =0, 则=0当A=0时, 矩阵范数的性质可由向量范数定义直接验证(2)根据向量范数的性质矩阵范数的性质可由向量范数定义直接验证(3)定义3.7（矩阵的谱半径）设 的特征 值为
