线性方程组AX=B的数值解法(j)

华南师范大学数学科学学院 谢骊玲,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章 线性方程组,AX,=,B,的数值解法,9/14/2024,华南师范大学数学科学学院 谢骊玲,引言,在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。,线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。,9/14/2024,华南师范大学数学科学学院 谢骊玲,线性方程组求解问题,考虑线性方程组,Ax = b,其中,A,是一个,(,n,n,),的非奇异矩阵,x,是要求解的,n,维未知向量,b,是,n,维常向量,9/14/2024,华南师范大学数学科学学院 谢骊玲,线性方程组的解的存在性和唯一性,定理,3.4,设,A,是,N,N,方阵，下列命题等价：,给定任意,N,1,矩阵,B,，线性方程组,AX,=,B,有唯一解,矩阵,A,是非奇异的（即,A,-1,存在）,方程组,AX,=0,有唯一解,X,=0,det(,A,) 0,9/14/2024,华南师范大学数学科学学院 谢骊玲,线性方程组的解,最常见的求线性方程组,Ax,=,b,的解的方法是在方程组两侧同乘以矩阵,A,的逆,Gram,法则：,Ax,=,b,9/14/2024,华南师范大学数学科学学院 谢骊玲,线性方程组的解（续,1,）,求逆运算和行列式计算由于运算量大，实际求解过程中基本不使用，仅作为理论上的定性讨论,克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法,还有,三角分解法,和,迭代求解法,9/14/2024,华南师范大学数学科学学院 谢骊玲,解法分类,关于线性方程组的数值解法一般有两类,直接法：若在计算过程中没有舍入误差，经过有限步算术运算，可求得方程组的精确解的方法,迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法,迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.3,上三角线性方程组,定义,3.2,N,N,矩阵,A,=,a,ij,中的元素满足对所有,i,j,，有,a,ij,=0,，则称矩阵,A,为上三角矩阵；如果,A,中的元素满足对所有,i,j,，有,a,ij,=0,，则称矩阵,A,为下三角矩阵。,定理,3.5,（回代）设,AX,=,B,是上三角线性方程组，如果,a,kk,0,，其中,k,=1,2,N,，则该方程组存在唯一解。,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.3,上三角线性方程组（续,1,）,定理,3.6,如果,N,N,矩阵,A,=,a,ij,是上三角矩阵或下三角矩阵，则,条件,a,kk,0,很重要，因为回代算法中包含对,a,kk,的除法。如果条件不满足，则可能无解或有无穷解,联系定理,3.4,，可知要条件,a,kk,0,成立才能保证方程组存在唯一解,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.3,上三角线性方程组（续,2,）,求解上三角线性方程组的回代算法,最后,9/14/2024,华南师范大学数学科学学院 谢骊玲,上三角线性方程组的求解,基本算法：,9/14/2024,华南师范大学数学科学学院 谢骊玲,上三角线性方程组的求解（续,1,）,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元,求解有,N,个方程和,N,个未知数的一般方程组,AX,=,B,的一般做法：构造一个等价的上三角方程组,UX,=,Y,，并利用回代法求解,如果两个,N,N,线性方程组的解相同，则称二者等价,对一个给定方程组进行初等变换，不会改变它的解,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,1,）,考虑一个简单的例子：,求解第二个方程，得,第二个方程减去第一个方程除以,3,再乘以,4,得到的新方程，得到新的方程组：,回代到第一个方程，得,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,2,）,考虑包含,n,个未知数的方程组,or,作如下行变换之后方程组的解向量,x,不变,对调方程组的两行,用非零常数乘以方程组的某一行,将方程组的某一行乘以一个非零常数，再加到另一行上,通过对增广矩阵,A,|,B,进行如上的行变换求解,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,3,）,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,4,）,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,5,）,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,6,）,利用,3.3,节的回代法求解上述上三角方程组,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,7,）,消去过程,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,8,）,回代过程,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,9,）,上述消去过程中，如果,a,kk,=0,，则不能使用第,k,行消除第,k,列的元素，而需要将第,k,行与对角线下的某行进行交换，以得到一个非零主元。如果不能找到非零主元，则线性方程组的系数矩阵是奇异的，因此线性方程组不存在唯一解,选主元以避免 ，如果此主元非零，则不换行；如果此主元为零，则寻找第,p,行下满足 的第,1,行，将此行与第,p,行互换，使新主元非零。,平凡选主元策略,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,10,）,选主元以减少误差：把元素中的最大绝对值移到主对角线上,例,3.17,和,3.18,偏序选主元策略,|,a,kp,|=max|,a,pp,|,|,a,pp,+1,|,|,a,N,-1,p,|,|,a,Np,|,按比例偏序选主元（平衡）策略,s,r,=max|,a,rp,|,|,a,rp,+1,|,|,a,rN,|,其中,r,=,p,p,+1,N,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,11,）,病态问题：矩阵,A,中元素的微小变化引起解的很大变化,cond(A,)=207.012,9/14/2024,华南师范大学数学科学学院 谢骊玲,图形解释,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.4,高斯消去法和选主元（续,12,）,一个线性方程组称为是病态的，如果其系数矩阵接近奇异且它的行列式接近,0,矩阵条件数,cond(,A,)=|,A,|,A,-1,|,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法,A,=,LU,:,下三角矩阵,L,的主对角线为,1,，上三角矩阵,U,的对角线元素非零,定义,3.4,如果非奇异矩阵,A,可表示为下三角矩阵,L,和上三角矩阵,U,的乘积：,A,=,LU,，则,A,存在一个三角分解,A,非奇异蕴含着对所有的,k,有,u,kk,0,，,k,=1,2,3,4.,9/14/2024,华南师范大学数学科学学院 谢骊玲,矩阵的,LU,分解,是否所有的非奇异矩阵,A,都能作,LU,分解呢？,一个例子：,N,阶方阵,A,有唯一,LU,分解的充要条件是,A,的各阶顺序主子式均不为零,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,1,）,利用前代,/,回代算法求解形如,Lx,=,b,或,Ux,=,b,的线性方程组是容易的,如果对一个给定的矩阵,A,，能够找到一个下三角矩阵,L,和一个上三角矩阵,U,，使,A,=,LU,则求解线性方程组,Ax,=,b,的问题可以分解成两个简单的问题：,Ly,=,b,Ux,=,y,易见：,Ax,=(,LU,),x,=,L,(,Ux,)=,Ly,=,b,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,2,）,假设已有矩阵,A,:,对,A,作,LU,分解,:,检验分解结果,:,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,3,）,构造一系列乘数矩阵,M,1,M,2,M,3,M,4,M,N,-1,使得,:,(,M,N,-1,M,4,M,3,M,2,M,1,),A,是上三角矩阵，把它重新记成,U,.,对,44,矩阵,A,，,M,1,可取,:,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,4,）,M,2,可取,:,M,3,可取：,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,5,）,则,U,=(,M,3,M,2,M,1,),A,是上三角形矩阵,每个,M,矩阵都是下三角形矩阵,如,M,2,的逆为,:,注意到每个,M,矩阵的逆只是它自身下三角部分元素取相反数,A,= (,M,3,M,2,M,1,),-1,U,= (,M,1,),-1,(,M,2,),-1,(,M,3,),-1,U,定义,L,= (,M,1,),-1,(,M,2,),-1,(,M,3,),-1,，则,L,就是一个对角元素全为,1,的下三角矩阵，因为所有的,M,矩阵的逆都是对角元素全为,1,的下三角矩阵,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,6,）,计算复杂性：高斯消去法与三角分解法的三角化过程是一样的，都需要,次乘法和除法,次减法,求解,LUX,=,B,又需要,N,2,次乘法和除法，以及,(,N,2,-,N,),次减法,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,7,）,每一个,M,矩阵中都需要计算,1/,A,(,i,i,),当第,i,个对角元素为,0,或者很接近,0,时就没法计算,M,，这时,A,的直接,LU,分解就没法继续进行,可以将第,i,行与它下面的某一行互换，该行的第,i,列元素非零,带选主元过程的,LU,分解,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.5,三角分解法（续,8,）,之前我们构造了一系列的,M,矩阵使得,是上三角矩阵,现在我们构造一系列的,M,矩阵和,P,矩阵使得,是上三角矩阵,(,M,N,-1,.,M,4,M,3,M,2,M,1,),A,(M,N,-1,P,N,-1,. M,4,P,4,M,3,P,3,M,2,P,2,M,1,P,1,)A,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.6,求解线性方程组的迭代法,考虑线性方程组,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.6,求解线性方程组的迭代法（续,1,）,高斯消去法,受限于舍入误差和病态性,迭代法,另一种求解线性方程组的方法,给出初始估计值，通过迭代得到更好的解的近似值,迭代法对求解大型线性方程组非常有效,Jacobi,（雅可比）,和,Gauss-Seidel,（高斯,-,赛德尔）,方法,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.6,求解线性方程组的迭代法（续,2,）,将方程组改写成每个方程的左边只有一个未知数的形式：,给出初始估计值 和迭代规则,9/14/2024,华南师范大学数学科学学院 谢骊玲,Jacobi,迭代法,初始估计值,迭代一步后的结果：,9/14/2024,华南师范大学数学科学学院 谢骊玲,Jacobi,迭代法（续,1,）,k,步迭代后的结果：,9/14/2024,华南师范大学数学科学学院 谢骊玲,Jacobi,迭代法（续,2,）,例：,Jacobi,迭代公式：,9/14/2024,华南师范大学数学科学学院 谢骊玲,Jacobi,迭代法（续,3,）,初始迭代值,20,步迭代后,9/14/2024,华南师范大学数学科学学院 谢骊玲,Jacobi,迭代法（续,4,）,迭代会不会收敛到方程组的解？,迭代到何时会终止？终止的判断条件是什么？,两个必须考虑的问题：,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.6,求解线性方程组的迭代法（续,3,）,定义,3.6,设有,N,N,维矩阵,A,，如果,其中,k,1,2,N,则称,A,具有严格对角优势,（,严格对角占优,）。,定理,3.15,（雅可比迭代）设矩阵,A,具有严格对角优势，则,AX,=,B,有唯一解,X,=,P,。利用雅可比迭代可产生一个向量序列,P,k,，而且对于任意初始向量,P,0,，向量序列都将收敛到,P,。,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.6,求解线性方程组的迭代法（续,4,）,向量之间的距离可以用来判断,P,k,是否收敛到,P,。因为两个向量,P,=(,x,1,x,2,x,N,),和,Q,=(,y,1,y,2,y,N,),之间的欧几里德距离,计算复杂；而,1,范数具有度量的数学结构，也适合作为一个一般化的“距离公式”。而且根据线性代数的理论可知，如果两个向量的,|,|,1,范数接近，则它们的欧几里德范数,|,|,2,也接近。所以定义两个,N,维向量的距离为,|,|,1,范数，用来确定,N,维空间中的收敛性,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.6,求解线性方程组的迭代法（续,5,）,1-,范数： 满足一般向量范数的性质,定理,3.16,设,X,和,Y,是,N,维向量，,c,是一个标量。则函数,|,X,|,有如下性质：,正定性,：,|,X,|0,，,|,X,|=0,当且仅当,X,=0,齐次性,：,|,cX,|=|,c,|,X,|,三角不等式,：,|,X,+,Y,|,X,|+|,Y,|,9/14/2024,华南师范大学数学科学学院 谢骊玲,Gauss-Seidel,迭代法,初始估计值,迭代一步后的结果：,9/14/2024,华南师范大学数学科学学院 谢骊玲,每一次迭代新产生的 被认为是比 更好的,x,j,的近似值，所以在计算,x,j,+1,时用 来替换 是合理的,Gauss-Seidel,迭代法（续,1,）,k,步迭代后的结果：,矩阵,A,具有严格对角优势时，高斯赛德尔迭代收敛,9/14/2024,华南师范大学数学科学学院 谢骊玲,Gauss-Seidel,迭代法（续,2,）,1,步,G-S,迭代之后：,迭代初始值：,例,9/14/2024,华南师范大学数学科学学院 谢骊玲,Gauss-Seidel,迭代法（续,3,）,2,步迭代之后,9,步迭代之后,1,步迭代之后,9/14/2024,华南师范大学数学科学学院 谢骊玲,3.6,求解线性方程组的迭代法（续,6,）,雅可比迭代：,高斯赛德尔迭代：,9/14/2024,华南师范大学数学科学学院 谢骊玲,J-,迭代和,G-S,迭代的比较,一般来说，用,J-,迭代、,G-S,迭代都收敛的问题，用,G-S,迭代收敛更快,J-,迭代保留上一步所有点的值，花费存储空间，适合并行运算，节省计算时间,G-,迭代每计算出一个新点都用于下一步的计算中，不须保留上一步所有点的值，节省存储空间，但只能串行计算,9/14/2024,华南师范大学数学科学学院 谢骊玲,