《-线性代数方程组的解法-LU分解》由会员分享,可在线阅读,更多相关《-线性代数方程组的解法-LU分解(77页珍藏版)》请在金锄头文库上搜索。
1、第第6 6章章 线性方程组的求解方法 线性方程组的求解方法 6.1 引言与预备知识引言与预备知识 6.2 高斯消去法高斯消去法 6.3 矩阵三角分解法矩阵三角分解法 6.4 向量和矩阵的范数向量和矩阵的范数 6.5 误差分析误差分析 6.6 6.6 共轭梯度法 共轭梯度法 1 2 6.1 引言与预备知识引言与预备知识 在工程技术在工程技术、自然科学和社会科学中自然科学和社会科学中,经常遇到的经常遇到的许多问题最终都可归结为解线性方程组许多问题最终都可归结为解线性方程组,如电学中如电学中网络问题网络问题、用用最小二乘法求实验数据的曲线拟合问最小二乘法求实验数据的曲线拟合问题题,工程中的三次样条函
2、数的工程中的三次样条函数的插值问题插值问题,经济运行经济运行中的中的投入产出问题投入产出问题以及大地测量以及大地测量、机械与建筑结构机械与建筑结构的设计计算的设计计算问题等等问题等等,都归结为求解线性方程组或都归结为求解线性方程组或非线性方程组的数学问题非线性方程组的数学问题。因此线性方程组的求解因此线性方程组的求解对于实际问题是极其重要的对于实际问题是极其重要的。 6.1.1 引言 引言 3 a11x1+ a12x2+.+ a1nxn= b1 a21x1+ a22x2+.+ a2nxn= b2 . an1x1+ an2x2+.+ annxn= bn A =a11a12.a1n a21a22.
3、a2n . an1an2.ann,X =x1 x2 . xn,B =b1 b2 . bn简记为简记为 Ax=b,其中其中 ( 6.1 ) 常见的线性方程组是方程个数和未知量个常见的线性方程组是方程个数和未知量个 数相同的数相同的n n阶线性方程组阶线性方程组,一般形式为一般形式为 4 5 线性方程组的数值解法一般有两类线性方程组的数值解法一般有两类: 1. 直接法直接法 经过有限步算术运算经过有限步算术运算,可求得方程组精确解的方法可求得方程组精确解的方法( (若计算过程中没有舍入误差若计算过程中没有舍入误差) ). 但实际计算中由于舍入误差的存在和影响但实际计算中由于舍入误差的存在和影响,这
4、种方这种方法也只能求得线性方程组的法也只能求得线性方程组的近似解近似解. . 回顾已经学过的一种求解线性方程组的直接方法 回顾已经学过的一种求解线性方程组的直接方法 6 克莱姆法则克莱姆法则: 的系数行列式不等于零的系数行列式不等于零, ,即即 a11x1+ a12x2+ a1nxn= b1 a21x1+ a22x2+ a2nxn= b2 an1x1+ an2x2+ annxn= bn 如果线性方程组 如果线性方程组 D =a11a12a1na21a22a2n an1an2ann 0则方程组有唯一的解,且唯一的解为 其中 Dj (j=1,2,n) 是系数行列式 D 中第 j 列的元素用方程组右
5、端的常数项代替后所得到的 n 阶行列式,即 x1=D1 D,x2=D2 D,xn=Dn D,Dj=a11a1,j1b1a1,j+1a1n an1an,j1bnan,j+1ann7 例: 解线性方程组 2x1+ x25x3+ x4= 8,x13x26x4= 9,2x2 x3+2x4= 5,x1+4x27x3+6x4= 0, 解: 系数行列式为 2151130602121476D=21242rrrr=0751313060212077122 175131 ( 1)2127712+= 221232CCCC+=3530107723372=27=0故方程有唯一解. 8 2151130602121476D=
6、D1=8151 9306 5212 0476=81D2=2851 1906 0512 1076= 108D3=2181 1396 0252 1406= 27D4=2158 1309 0215 1470= 27x1=D1 D,x2=D2 D,x3=D3 D,x4=D4 D,由 得唯一解为 x1= 3,x2= 4,x3= 1,x4=19 通过上述例子通过上述例子, , 我们看到用克莱姆法则求解线性方程我们看到用克莱姆法则求解线性方程 组时组时, ,要计算要计算 n n+1 +1 个个 n n 阶行列式阶行列式, ,这个计算量是相当这个计算量是相当 大的大的, , 所以所以, , 在具体求解线性方程
7、组时在具体求解线性方程组时, , 很少用克莱很少用克莱 姆法则姆法则. . 但这并不影响克莱姆法则在线性方程组理论中的重要但这并不影响克莱姆法则在线性方程组理论中的重要 地位地位。克莱姆法则不仅给出了方程组有唯一解的条件克莱姆法则不仅给出了方程组有唯一解的条件, , 并且给出了方程组的解与方程组的系数和常数项的关系并且给出了方程组的解与方程组的系数和常数项的关系. . 10 11 2.2.迭代法迭代法 是用某种是用某种极限过程极限过程去逐步逼近线性方程组精确解的去逐步逼近线性方程组精确解的方法方法.也就是从解的某个也就是从解的某个近似值近似值出发出发,通过构造一个通过构造一个无穷序列无穷序列去
8、逼近精确解的方法去逼近精确解的方法。( (一般有限步内得不一般有限步内得不到精确解到精确解) ) 直接方法中直接方法中,最具有代表性的就是最具有代表性的就是高斯高斯- -约当消去法约当消去法。该方法适用于求解该方法适用于求解低阶稠密矩阵方程组及大型稀疏低阶稠密矩阵方程组及大型稀疏矩阵方程组矩阵方程组。 12 迭代法实现的基本步骤迭代法实现的基本步骤: (1 1)选定根的初始近似值选定根的初始近似值 (2 2)按照某种原则生成收敛于根的近似点列 按照某种原则生成收敛于根的近似点列 13 迭代法的优点迭代法的优点: (1 1)计算机存储量小计算机存储量小; (2 2)程序设计简单程序设计简单; (
9、3 3)初始方程组系数矩阵在计算过程中保持不变初始方程组系数矩阵在计算过程中保持不变。 迭代法必须考虑的关键问题迭代法必须考虑的关键问题: (1 1)算法的算法的收敛性收敛性问题问题 (2 2)算法的算法的收敛速度收敛速度问题问题 收敛性与收敛速度是如何定义的收敛性与收敛速度是如何定义的? 14 6.1.2 6.1.2 再谈向量和矩阵再谈向量和矩阵 用用 表示全部表示全部 实矩阵的向量空间实矩阵的向量空间, 表表 示全部示全部 复矩阵的向量空间复矩阵的向量空间. . RmnnmnmC mnA Rmn A = (aij) =a11a12a1n a21a22a2n am1am2amn这种实数排成的
10、矩形表这种实数排成的矩形表,称为称为 行行 列矩阵列矩阵. . mnx Rn x =x1 x2 xn称为称为 维列向量维列向量. . n15 A =a1a2an()其中 为 的第 列. iaAiA =b1Tb2T bmT其中 为 的第 行. T ibAi也可写成也可写成行向量行向量的形式的形式 写成写成列向量列向量的形式 的形式 16 (5) (5) 单位矩阵 单位矩阵 矩阵的基本运算矩阵的基本运算: (1) (1) 矩阵加法矩阵加法 C = A+ B(2) (2) 矩阵与标量的乘法矩阵与标量的乘法 C =A,cij=aij.(3) (3) 矩阵与矩阵乘法矩阵与矩阵乘法 cij=aikbkjk
11、=1n(A Rmn,B Rnp,C Rmp).,ABC=cij= aij+bij(A,B,C Rmn)(4) (4) 转置矩阵 转置矩阵 A Rmn,C = AT,cij= aji.I =e1e2en()Rnn其中其中 ek= 0,0,1 k,0,0()T,k =1,2,n.17 (6) (6) 非奇异矩阵非奇异矩阵 设设 如果如果 则称则称 是是 的逆矩阵的逆矩阵,记为记为 且 且 .R,RnnnnBA如果如果 存在存在, 1A则称 为非奇异矩阵. A如果 均为非奇异矩阵, nnBAR,AB = BA = I,BA,1A.)()(11=TTAA.)(111=ABAB则 (7) 矩阵的行列式矩
12、阵的行列式 设 ,RnnA则 的行列式可按任一行(或列)展开, Adet (A) =aijAijj=1n(i =1,2,n),即 18 其中其中 为为 的代数余子式的代数余子式, ijAija,)1(ijji ijMA+=行列式性质行列式性质: (a) det (AB) = det (A)det (B),A,B Rnn.(b) det (AT) = det (A),A Rnn.(c) det (cA) = cndet (A),c R,A Rnn.(d) det (A) 0 Aija的余子式的余子式. . 为元素 为元素 ijM是非奇异矩阵是非奇异矩阵。 19 6.1.3 矩阵的特征值与谱半径
13、矩阵的特征值与谱半径 若 为 的特征值, 的全体特征值称为 的谱,记为 ,即 记 称为矩阵 的谱半径. AAA)(A(A)= 1,2,n.(A)= max 1iniA矩阵的特征值及其各种计算方法前面张老师已经矩阵的特征值及其各种计算方法前面张老师已经详细讲述详细讲述,这里不再赘述这里不再赘述。 20 .242422221=A解解 矩阵 的特征方程为 A, 0)7()2(28243242422221 )det(223=+=+=+ = AI故 特征值为 的谱半径为 AA,7,2321=例例 求 的谱半径 A.7)(=A21 6.1.4 特殊矩阵 特殊矩阵 设 .R)(nn ijaA=(1) 对角矩
14、阵: 如果当 时, (2) 三对角矩阵:如果当 时, (3) 上三角矩阵:如果当 时, (4) 上海森伯格(Hessenberg)阵 . 01时如果当=+ijaji,(5) 对称矩阵: .如果AAT=i jaij= 0.i j 1aij= 0.i jaij= 0.22 (6) 埃尔米特矩阵:设 ACnn,(7) 对称正定矩阵: , (a) 如果AAT=. 0),(,R (b) 对任意非零向量=AxxxAxxTn(8) 正交矩阵: .1如果TAA =(9) 酉矩阵: .,CH1如果设AAAnn=(10) 初等置换阵 由单位矩阵 交换第 行与第 行(或交换第 列与第 列),得到的矩阵记为 ,且 IijijijIAH= AT