《线性代数方程组的数值解法new》由会员分享，可在线阅读，更多相关《线性代数方程组的数值解法new（162页珍藏版）》请在金锄头文库上搜索。
1、第3章 线性方程组的数值解法,3.1 引言与预备知识 3.2 高斯消去法 3.3矩阵三角分解法 3.4向量和矩阵的范数误差分析 3.5迭代方法,这一章讨论线性方程组,3.1 引言与预备知识,的数值解法.,在自然科学和工程技术中,很多问题归结为解线性方程组.例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程边值问题等都导致求解线性方程组，而这些方程组的系数矩阵大致分为两种，一种是低阶稠密矩阵(例如，阶数不超过150). 另一种是大型稀疏矩阵(即矩阵阶数高且零元素较多).,3.1.1 引
2、言,有的问题的数学模型中虽不直接表现为含线性方程组,但它的数值解法中将问题“离散化”或“线性化”为线性方程组.因此线性方程组的求解是数值分析课程中最基本的内容之一.,关于线性方程组的解法一般有两大类：,但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解. 本章将阐述这类算法中最基本的和具有代表性的算法就是高斯消元法,以及它的某些变形和应用.这类方法是解低阶稠密矩阵方程组及某些大型稀疏矩阵方程组(例如，大型带状方程组)的有效方法.,1. 直接法,经过有限次的算术运算,可以求得方程组的精确解(假定计算过程没有舍入误差).如线性代数课程中提到的克莱姆算法就是一种直接法.但该法
3、对高阶方程组计算量太大,不是一种实用的算法.,就是用某种极限过程去逐步逼近方程组精确解的方法. 迭代法具有计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点，但存在收敛条件和收敛速度问题.迭代法是解大型稀疏矩阵方程组(尤其是由微分方程离散后得到的大型方程组)的重要方法.,为了讨论线性方程组数值解法，需复习一些基本的矩阵代数知识.,2. 迭代法,3.1.2 向量和矩阵,基本概念：,用Rmn表示全部mn实矩阵的向量空间；,用Cmn表示全部mn复矩阵的向量空间.,(由数排成的矩阵表，称为m行n列矩阵).,其中aj为A的第j列的m维列向量. 同理,(m维列向量).,其中biT为
4、A的第i行的n维行向量.,矩阵的基本运算：,(1) 矩阵加法,(2) 矩阵与标量的乘法,(3) 矩阵与矩阵的乘法,(4) 转置矩阵,(5) 单位矩阵,其中,(6) 非奇异矩阵,则称B是A的逆矩阵，记为A-1，且(A-1)T=(AT)-1. 如果A-1存在，则A称为非奇异矩阵. 如果A、B均为非奇异矩阵，则有(AB)-1=B-1A-1.,(7) 矩阵的行列式,设ARnn，则A的行列式可按任一行(列)展开,其中Aij为aij的代数余子式，Aij=(-1)i+jMij，Mij为元素aij的余子式.,行列式性质：,定理1 设ARnn，则下述命题等价：,(1) 对任何bRn，方程组Ax=b有唯一解.,(
5、2) 齐次方程组Ax=0只有唯一解零解x=0.,(3) det(A)0.,(4) A-1存在.,3.2 高斯消去法,本节介绍高斯消去法(逐次消去法)及消去法和矩阵三角分解之间的关系. 虽然高斯消去法是一种古老的求解线性方程组的方法(早在公元前250年我国就掌握了解方程组的消去法)，但由它改进、变形得到的选主元素消去法、三角分解法仍然是目前计算机上常用的有效方法.我们在中学学过消去法,高斯消去法就是它的标准化的、适合在计算机上自动计算的一种方法.,3.2.1 高斯消去法,设有线性方程组,或写成矩阵形式,简记为Ax=b.,如: 上三角矩阵所对应的线性方程组,解为,当m=n时，对三角形方程组的解非常
6、容易，如,例如:,下三角矩阵所对应的线性方程组,计算量（乘除法的主要部分）都为 n2/2.,解为,因此，我们将一般的线性方程组化成等价的三角形方程组来求解.,首先举一个简单的例子来说明消去法的基本思想.,例1 用消去法解方程组,解 第1步，将方程(2.2)乘上-2加到方程(2.4)上去，消去(2.4)中的未知数x1，得到,第2步，将方程(2.3) 加到方程(2.5)上去，消去(2.5)中的未知数x2，得到与原方程组等价的三角形方程组,显然，方程组是(2.6)是容易求解的，解为,上述过程相当于对方程的增广阵做初等行变换,其中ri用表示矩阵的第i行.,由此看出，用消去法解方程组的基本思想是用逐次消
7、去未知数的方法把原方程组Ax=b化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法求解. 换句话说，上述过程就是用初等行变换将原方程组系数矩阵化为简单形式(上三角矩阵)，从而求解原方程组(2.1)的问题转化为求解简单方程组的问题. 或者说，对系数矩阵A施行一些行变换(用一些简单矩阵左乘A)将其约化为上三角矩阵. 这就是高斯消去法.,下面讨论求解一般线性方程组的高斯消去法.由,将(2.1)记为A(1)x=b(1)，其中,(1) 第1步(k=1).,设a11(1)0，首先计算乘数 mi1= ai1(1) /a11(1) (i=2,3,m). 用-mi1乘(2.1)的第一个方程，加到第i个
8、(i=2,3, ,m)方程上，消去(2.1)的从第二个方程到第m个方程中的未知数x1，得到与(2.1)等价的方程组,(2.7),简记为 A(2)x=b(2)，,其中A(2), b(2)的元素计算公式为,(2) 第k次消元(k=1,2,s, s=min(m-1,n).,设上述第1步， ，第k-1步消元过程计算已经完成，即已计算好与(2.1)等价的方程组，简记为 A(k)x=b(k)，其中,设akk(k)0，计算乘数 mik= aik(k) /akk(k) (i=k+1, ,m). 用-mik乘(2.8)的第k个方程加到第 i个(i= k+1, , m)方程上，消去从第k+1个方程到第m个方程中的
9、未知数xk，得到与(2.1)等价的方程组A(k+1)x=b(k+1)，,其中A(k+1), b(k+1)的元素计算公式为，,显然A(k+1)中从第1行到第k行与A(k)相同.,(3) 继续上述过程，且设aii(i)0 (i=1,2, ,s)，直到完成第s步消元计算. 最后得到与原方程组等价的简单方程组A(s+1)x=b(s+1) ，其中A(s+1)为上阶梯.,特别当m=n时，与原方程组等价的简单方程组为A(n)x=b(n)，即,由(2.1)约化为(2.10)的过程称为消元过程.,如果A是非奇异矩阵，且akk(k)0 (k=1,2,n-1)，求解三角形方程组(2.10)，得到求解公式,(2.10
10、)的求解过程(2.11) 称为回代过程.,注意：设Ax=b，其中ARnn为非奇异矩阵，如果a11(1)=0，由于A为非奇异矩阵，所以A的第1列一定有元素不等于零，例如al10，于是可交换两行元素(即r1rl)，将al1 调到(1,1)位置，然后进行消元计算，这时A(2)右下角矩阵为n-1阶非奇异矩阵，继续这过程，高斯消去法照样可进行计算.,总结上述讨论即有,定理5 设Ax=b，其中ARnn.,(1) 如果akk(k)0 (k=1,2,n)，则可通过高斯消去法将Ax=b约化为等价的三角形方程组(2.10)，且计算公式为,(a) 消元计算(k=1,2, ,n-1),(b) 回代计算,(2) 如果A
11、为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换)将方程组Ax=b约化为等价的三角形方程组(2.10).,例2 解方程组,解：消元,回代得,习题:求解下列方程组,，,(1),(2),3.2.2 高斯主元素消元法,由高斯消去法知道, 在消元过程中可能有akk(k)0的情况，这时消去法将无法进行；即使主元素akk(k)0但很小时，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠.,先看一个例子,高斯消去法也称主元素消去法 (条件det A0),即当akk(k)=0 时，高斯消元法无法进行；或 | akk(k) |1时，带来舍入误差的扩散。（小主元）,解 (方
12、法1)高斯消元法(用4位有效数字),例3,(小主元产生了大误差),(方法2)列主元消元法，先交换行,这个例子告诉我们，在采用高斯消去法解方程组时，小主元可能产生麻烦，故应避免绝对值小的主元素akk(k)，对一般矩阵来说，最好每一步选取系数矩阵(或消元后的低阶矩阵)中绝对值最大的元素作为主元素，以使高斯消去法具有较好的数值稳定性，这就是全主元素消去法，在选主元时要花费较多机器时间，目前主要使用的是列主元素消去法,上例2,其中系数矩阵,3.2.3 矩阵三角分解,将上三角矩阵A(n)记为U，由(2.14)得到,其中,为单位下三角矩阵.,这就是说，高斯消去法实质上产生了一个将A分解为两个三角形矩阵相乘
13、的因式分解，于是我们得到如下重要定理，它在解方程组的直接法中起着重要作用.,定理 (矩阵的LU分解) 设A为n阶矩阵，如果A的顺序主子式Di0 (i=1,2,n-1)，则A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，即 A=LU, 且这种分解是唯一的.,对于例1，系数矩阵,由高斯消去法 m21=0，m31=2，m32=-1，故,从而得到求矩阵行列式的计算公式为,消元法的应用,1. 求行列式,高斯消元法,2. 求逆矩阵(用高斯-若当消去法),例子 分别用高斯消元法和列主元消元法求矩阵的行列式.,解： 高 斯 消 元 法,大数“吃掉”了小数！,列 主 元 消 元 法,例4 用高斯-若当方
14、法求下列矩阵的逆矩阵.,解 由分块矩阵,所以得,3.3 矩阵三角分解法,高斯消去法有很多变形，有的是高斯消去法的改进，改写，有的是用于某一类特殊矩阵的高斯消去法的简化. 下面我们将介绍矩阵的直接三角分解法，解特殊方程组用的平方根法及追赶法.,定义 如果 L为单位下三角阵，U为上三角阵，则称A=LU为杜里特尔(Doolittle)分解；如果 L为下三角阵，U为单位上三角阵，则称A=LU为克劳特(Crout)分解.,3.3.1 直接三角分解法(LU分解),在3.2.3已经通过高斯消去法得到一个将A分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，A=LU，其中,并由定理7得到这种分解是唯一的.,
15、将高斯消去法改写为紧凑形式，可以直接从矩阵A的元素得到计算L,U元素的递推公式，而不需要任何中间步骤，这就是所谓直接三角分解法. 一旦实现了矩阵A的LU分解，那么求解Ax=b的问题就等价于求两个三角形方程组., Ly=b，求y；, Ux=y，求x.,1. 不选主元的三角分解法,设A为非奇异矩阵，且有分解式A=LU，其中L为单位下三角矩阵，U为上三角矩阵，即,其中,a11 a12 a1k a1n u11 u12 u1k u1n 第1框 a21 a22 a2k a2n l21 u22 u2k u2n 第2框 ak1 ak2 akk akn lk1 lk2 ukk ukn 第k框 an1 an2 ank ann ln1 ln2 lnk unn 第n框,比较式 A=LU 两端的元素, 按下图所示顺序逐框进行，先求ukj，后求lik. 由第一框可得,得,假设前k -1框元素已求出，则由,有了矩阵 A 的LU分解计算公式 , 解线性方程组 Ax=b 就转化为依次解下三角方程组 Ly=b 与上三角方程组 Ux=y 其计算公式如下：, Ly=b, Ux=y,例5 求矩阵,解 用紧凑格式,的LU (Dooli
