《数值计算方法 教学课件 ppt 作者 刘玲 第3章 线性方程组的数值解法》由会员分享，可在线阅读，更多相关《数值计算方法 教学课件 ppt 作者 刘玲 第3章 线性方程组的数值解法（175页珍藏版）》请在金锄头文库上搜索。
1、,第3章 线性方程组的数值解法,引言,在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。 线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。,引言,关于线性方程组的数值解法一般有两类。 直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差） 迭代法：用某种极限过程去
2、逐步逼近线性方程组精确解的方法 迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题,3.1 高斯消元法,设线性方程组 简记 AX=b,高斯消元法,其中,高斯消元法,克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法。,例题,例1.用消元法解方程组,例题,第一步：-2 x（1）+(3)得,例题,第二步：1 x（2）+（4） 回代得：x=1,2,3T,3.1.1 高斯顺序消元法,下三角形方程求解 设 （1）,高斯顺序消元法,由（1）得,高斯顺序消元法,算法：,高斯顺序消元法,上三角方程组的解
3、法 设,由（2）式回代得,上三角方程组的解法,高斯顺序消去法,设 Ax=b. 记A(1)=A b(1)=b 1、第一次消元。设,高斯顺序消去法,高斯顺序消去法,设第k-1次消元得A(k)x=b(k) 其中,高斯顺序消去法,则第k次消元:,高斯顺序消去法,最后,高斯顺序消去法,也就是对于方程组AX=b系数矩阵做：,高斯顺序消去法,高斯顺序消去法,高斯顺序消去法,高斯顺序消去法,高斯顺序消去法算法框图,高斯消去法的计算量,高斯顺序消去法条件,3.1.2 高斯主元素消去法,Gauss列主元消元法 从第一列中选出绝对值最大的元素,交换,高斯列主元消去法,高斯列主元消去法,第k步 从 的第k列 ， ，
4、中选取绝对值最大项，记录所在行，即 若 交换第k行与l行的所有对应元素，再进行顺序消元。,框图,高斯列主元消去法,高斯列主元消去法,高斯列主元消去法,2. 全主元消去法,例如.求解方程组,全主元消去法,全主元消去法,全主元消去法,全主元消去法,全主元消去法,全主元消去法,Gauss全主元消元算法,Gauss全主元消元算法,Gauss全主元消元算法,3.高斯-约当消去法,与一般消去法相比，高斯约当消去法是一种无回代过程的算法 设方程组AX=b经过（k-1）次消元得,高斯-约当消去法,算法,选列主元的Gauss-Jordan消去法,Guass-Jordan消去法形式上比Guass消去法简单,求解无
5、回代过程,但从工作量角度看前者大约需要O( ),而后者需要量 O( ),比有回代的Guass消去法多O( )工作量.,小节,比较而言,Gauss顺序消去法条件苛刻,且数值不稳定; Gauss全主元消去法工作量偏大，需要比较 个元素及行列交换工作，算法复杂；对于Gauss-Jordan消去法形式上比其他消元法简单，且无回代求解，但计算量大,比Gauss顺序消去法多 计算量。因此从算法优化的角度考虑， Gauss列主元消去法比较好。,3.2 矩阵的三角分解法,我们知道对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观点来考察Gauss消元法用矩阵乘法来表示，即可得到求
6、解线性方程组的另一种直接法：矩阵的三角分解。,3.2.1 Gauss消元法的矩阵形式,3.2.2 Doolittle分解,Doolittle分解,若矩阵A有分解：A=LU，其中L为单位下三角阵，U为上三角阵，则称该分解为Doolittle分解，可以证明，当A的各阶顺序主子式均不为零时，Doolittle分解可以实现并且唯一。,A的各阶顺序主子式均不为零，即,Doolittle分解,Doolittle分解,Doolittle分解,Doolittle分解,Doolittle分解,Doolittle分解,例题,例题,例题,例题,例题,Doolittle分解,3.2.3 Cholesky分解,在应用数
7、学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元，有良好的数值稳定性。,Cholesky分解,A对称：AT=A A正定：A的各阶顺序主子式均大于零。即,Cholesky分解,由Doolittle分解，A有唯一分解,Cholesky分解,定理3.2.4 设A为对称正定矩阵，则存在唯一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,dn)且di0(i=1,n),Cholesky分解,证明：,Cholesky分解,Cholesky分解,Cholesky分解,推论：设A为对称正定矩阵，则存在唯一
8、分解 其中L为具有主对角元素为正数的下三角矩阵。,Cholesky分解,证明：,Cholesky分解的求法,Cholesky分解的求法,Cholesky分解的求法,Cholesky分解法,Cholesky分解法缺点及优点 优点：可以减少存储单元。 缺点：存在开方运算，可能会出现根号下负数。,改进Cholesky分解法,改进的cholesky分解A=LDLT,改进的cholesky分解,改进的cholesky分解,改进的cholesky分解算法,改进的cholesky分解算法,例题,例题,例题,例题,A=LDLT分解，既适合于解对称正定方程组，也适合求解A为对称，而各阶顺序主子式不为零的方程组
9、而对A=LLT只适合于对称正定方程组,3.2.4 三对角方程组求解的追赶法,三对角方程组求解的追赶法,三对角方程组求解的追赶法,三对角方程组求解的追赶法,三对角方程组求解的追赶法,其计算工作量为5n-4次乘除法。工作量小，其实现的条件为qi不为零。有以下定理可得证三对角矩阵求解的充分性条件。,解三对角矩阵线性方程组的追赶法程序框图,3.3 矩阵求逆,矩阵求逆,矩阵求逆,为使求逆过程不断提高求解精度，因此增加选主元工作，最常用的是选列主元求逆。因此增加一个数组Z(n)，记录选主元的交换号，最后在消元工作完成后，根据Z(n)对A中的元素进行相应的列交换，得到A-1,GaussJordan原地求逆法
10、,算法（原地求逆法）,例题,例题,例题,例题,例题,例题,3.4 向量和矩阵的范数,为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。,向量和矩阵的范数,在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用| x1-x2 |表示。,向量和矩阵的范数,而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间，则称为向量范数。,3.4.1向量范数,常见的向量范数,向量范数性质
11、,向量范数性质,等价性质：,向量的收敛性,3.4.2 矩阵范数,相容范数,算子范数,算子范数,算子范数,常见的矩阵范数,常见的矩阵范数,对称矩阵范数,例题,3.4.3 矩阵的谱半径和矩阵序列收敛性,例题,谱半径和矩阵序列的收敛性,矩阵序列的收敛性,3.5 病态方程组与矩阵的条件数,3.5.1 病态方程组与扰动方程组的误差分析,病态方程组与扰动方程组的误差分析,病态方程组与扰动方程组的误差分析,病态方程组与扰动方程组的误差分析,病态方程组与扰动方程组的误差分析,病态方程组,扰动方程 由于计算机字长限制，在解AX=b时，舍入误差是不可避免的。因此我们只能得出方程的近似解 。 是方程组（A+A）x=
12、b+ b (1),在没有舍入误差的解。称方程（1）为方程Ax=b的扰动方程。其中A， b为由舍入误差所产生的扰动矩阵和扰动向量。当A， b的微小扰动，解得（1）的解与Ax=b的解x的相对误差不大称为良态方程，否则为病态方程。,扰动方程组的误差界,3.5.2 矩阵的条件数,矩阵的条件数的性质,相对误差的事后估计,定理3.6.3,例题,3.6 线性方程组的迭代法,3.6.1 线性方程组迭代法概述,线性方程组迭代法概述,线性方程组迭代法概述,线性方程组迭代法概述,3.6.2 Jacobi迭代法和Gauss-Seidel迭代法,Jacobi迭代法,Jacobi迭代法,例题,例题,Jacobi迭代法的矩阵形式,Jacobi迭代法的算法,Gauss-Seidel迭代法,Gauss-Seidel迭代法,例题,Gauss-Seidel迭代法的算法,
