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

1、14.07.2020,第3章 线性方程组ax=b的数值解法,华南师范大学数学科学学院 谢骊玲,14.07.2020,引言,在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。 线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。,华南师范大学数学科学学院 谢骊玲,14.07.2020,线性方程组求解

2、问题,考虑线性方程组 ax = b 其中a是一个(n n)的非奇异矩阵, x是要求解的n维未知向量, b是n维常向量,华南师范大学数学科学学院 谢骊玲,14.07.2020,线性方程组的解的存在性和唯一性,定理3.4 设a是nn方阵，下列命题等价： 给定任意n1矩阵b，线性方程组ax=b有唯一解 矩阵a是非奇异的（即a-1存在） 方程组ax=0有唯一解x=0 det(a) 0,华南师范大学数学科学学院 谢骊玲,14.07.2020,线性方程组的解,最常见的求线性方程组ax=b的解的方法是在方程组两侧同乘以矩阵a的逆 gram法则：,ax = b,华南师范大学数学科学学院 谢骊玲,14.07.2

3、020,线性方程组的解（续1）,求逆运算和行列式计算由于运算量大，实际求解过程中基本不使用，仅作为理论上的定性讨论 克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法 还有三角分解法和迭代求解法,华南师范大学数学科学学院 谢骊玲,14.07.2020,解法分类,关于线性方程组的数值解法一般有两类 直接法：若在计算过程中没有舍入误差，经过有限步算术运算，可求得方程组的精确解的方法 迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法 迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题,华

4、南师范大学数学科学学院 谢骊玲,14.07.2020,3.3 上三角线性方程组,定义3.2 nn矩阵a=aij中的元素满足对所有ij，有aij=0，则称矩阵a为上三角矩阵；如果a中的元素满足对所有ij，有aij=0，则称矩阵a为下三角矩阵。 定理3.5（回代）设ax=b是上三角线性方程组，如果akk0，其中k=1,2,n，则该方程组存在唯一解。,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.3 上三角线性方程组（续1）,定理3.6 如果nn矩阵a=aij是上三角矩阵或下三角矩阵，则,条件akk0很重要，因为回代算法中包含对akk的除法。如果条件不满足，则可能无解或有无穷解,联系定

5、理3.4，可知要条件akk0成立才能保证方程组存在唯一解,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.3 上三角线性方程组（续2）,求解上三角线性方程组的回代算法,最后,华南师范大学数学科学学院 谢骊玲,14.07.2020,上三角线性方程组的求解,基本算法：,华南师范大学数学科学学院 谢骊玲,14.07.2020,上三角线性方程组的求解（续1）,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元,求解有n个方程和n个未知数的一般方程组ax=b的一般做法：构造一个等价的上三角方程组ux=y，并利用回代法求解 如果两个nn线性方程组的解相同，则称二

6、者等价 对一个给定方程组进行初等变换，不会改变它的解,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续1）,考虑一个简单的例子：,求解第二个方程，得,第二个方程减去第一个方程除以3再乘以4得到的新方程，得到新的方程组：,回代到第一个方程，得,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续2）,考虑包含n个未知数的方程组,or,作如下行变换之后方程组的解向量 x 不变 对调方程组的两行 用非零常数乘以方程组的某一行 将方程组的某一行乘以一个非零常数，再加到另一行上,通过对增广矩阵a|b进行如上的行变换求解,华南师范大学

7、数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续3）,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续4）,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续5）,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续6）,利用3.3节的回代法求解上述上三角方程组,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续7）,消去过程,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续8）,回代过程

8、,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续9）,上述消去过程中，如果akk=0，则不能使用第k行消除第k列的元素，而需要将第k行与对角线下的某行进行交换，以得到一个非零主元。如果不能找到非零主元，则线性方程组的系数矩阵是奇异的，因此线性方程组不存在唯一解 选主元以避免 ，如果此主元非零，则不换行；如果此主元为零，则寻找第p行下满足 的第1行，将此行与第p行互换，使新主元非零。,平凡选主元策略,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续10）,选主元以减少误差：把元素中的最大绝对值移到主对角线上,例3.17

9、和3.18,偏序选主元策略,|akp|=max|app|,|app+1|,|an-1p|,|anp|,按比例偏序选主元（平衡）策略,sr=max|arp|,|arp+1|,|arn| 其中r=p,p+1,n,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续11）,病态问题：矩阵a中元素的微小变化引起解的很大变化,cond(a)=207.012,华南师范大学数学科学学院 谢骊玲,14.07.2020,图形解释,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.4 高斯消去法和选主元（续12）,一个线性方程组称为是病态的，如果其系数矩阵接近奇异且它的

10、行列式接近0,矩阵条件数 cond(a)=|a|a-1|,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.5 三角分解法,a=lu:下三角矩阵l的主对角线为1，上三角矩阵u的对角线元素非零,定义3.4 如果非奇异矩阵a可表示为下三角矩阵l和上三角矩阵u的乘积：a=lu，则a存在一个三角分解,a非奇异蕴含着对所有的k有ukk0，k=1,2,3,4.,华南师范大学数学科学学院 谢骊玲,14.07.2020,矩阵的lu分解,是否所有的非奇异矩阵a都能作lu分解呢？ 一个例子： n阶方阵a有唯一lu分解的充要条件是a的各阶顺序主子式均不为零,华南师范大学数学科学学院 谢骊玲,14.07.2

11、020,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,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.5 三角分解法（续2）,假设已有矩阵a: 对a作lu分解: 检验分解结果:,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.5 三角分解法（续3）,构造一系列乘数矩阵m1, m2, m3, m4, mn-1使得: (mn-

12、1m4m3m2m1)a是上三角矩阵，把它重新记成u. 对44矩阵a，m1可取:,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.5 三角分解法（续4）,m2可取:,m3可取：,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.5 三角分解法（续5）,则u=(m3m2m1)a是上三角形矩阵 每个m矩阵都是下三角形矩阵 如m2的逆为: 注意到每个m矩阵的逆只是它自身下三角部分元素取相反数 a = (m3m2m1)-1 u = (m1)-1 (m2)-1 (m3)-1 u 定义l = (m1)-1 (m2)-1 (m3)-1，则l就是一个对角元素全为1的下三角矩阵，因为所有的m

13、矩阵的逆都是对角元素全为1的下三角矩阵,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.5 三角分解法（续6）,计算复杂性：高斯消去法与三角分解法的三角化过程是一样的，都需要,次乘法和除法,次减法,求解lux=b又需要n2次乘法和除法，以及(n2-n)次减法,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.5 三角分解法（续7）,每一个m矩阵中都需要计算1/a(i,i) 当第i个对角元素为0或者很接近0时就没法计算m，这时a的直接lu分解就没法继续进行 可以将第i行与它下面的某一行互换，该行的第i列元素非零 带选主元过程的lu分解,华南师范大学数学科学学院 谢骊玲,14

14、.07.2020,3.5 三角分解法（续8）,之前我们构造了一系列的m矩阵使得 是上三角矩阵 现在我们构造一系列的m矩阵和p矩阵使得 是上三角矩阵,(mn-1. m4 m3 m2 m1)a,(mn-1 pn-1 . m4 p4 m3 p3 m2 p2 m1 p1)a,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.6 求解线性方程组的迭代法,考虑线性方程组,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.6 求解线性方程组的迭代法（续1）,高斯消去法 受限于舍入误差和病态性 迭代法 另一种求解线性方程组的方法 给出初始估计值，通过迭代得到更好的解的近似值 迭代法对求解大

15、型线性方程组非常有效 jacobi（雅可比）和gauss-seidel（高斯-赛德尔）方法,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.6 求解线性方程组的迭代法（续2）,将方程组改写成每个方程的左边只有一个未知数的形式：,给出初始估计值 和迭代规则,华南师范大学数学科学学院 谢骊玲,14.07.2020,jacobi迭代法,初始估计值,迭代一步后的结果：,华南师范大学数学科学学院 谢骊玲,14.07.2020,jacobi迭代法（续1）,k步迭代后的结果：,华南师范大学数学科学学院 谢骊玲,14.07.2020,jacobi迭代法（续2）,例：,jacobi迭代公式：,华南师

16、范大学数学科学学院 谢骊玲,14.07.2020,jacobi迭代法（续3）,初始迭代值,20步迭代后,华南师范大学数学科学学院 谢骊玲,14.07.2020,jacobi迭代法（续4）,迭代会不会收敛到方程组的解？ 迭代到何时会终止？终止的判断条件是什么？,两个必须考虑的问题：,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.6 求解线性方程组的迭代法（续3）,定义3.6 设有nn维矩阵a，如果,其中k1,2,n,则称a具有严格对角优势（严格对角占优）。,定理3.15（雅可比迭代）设矩阵a具有严格对角优势，则ax=b有唯一解x=p。利用雅可比迭代可产生一个向量序列pk，而且对于任

17、意初始向量p0，向量序列都将收敛到p。,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.6 求解线性方程组的迭代法（续4）,向量之间的距离可以用来判断pk是否收敛到p。因为两个向量p=(x1,x2,xn)和q=(y1,y2,yn)之间的欧几里德距离,计算复杂；而1范数具有度量的数学结构，也适合作为一个一般化的“距离公式”。而且根据线性代数的理论可知，如果两个向量的|1范数接近，则它们的欧几里德范数|2也接近。所以定义两个n维向量的距离为|1范数，用来确定n维空间中的收敛性,华南师范大学数学科学学院 谢骊玲,14.07.2020,3.6 求解线性方程组的迭代法（续5）,1-范数： 满

18、足一般向量范数的性质,定理3.16 设x和y是n维向量，c是一个标量。则函数|x|有如下性质： 正定性：|x|0，|x|=0当且仅当x=0 齐次性：|cx|=|c|x| 三角不等式：|x+y|x|+|y|,华南师范大学数学科学学院 谢骊玲,14.07.2020,gauss-seidel迭代法,初始估计值,迭代一步后的结果：,华南师范大学数学科学学院 谢骊玲,14.07.2020,每一次迭代新产生的 被认为是比 更好的xj的近似值，所以在计算xj+1时用 来替换 是合理的,gauss-seidel迭代法（续1）,k步迭代后的结果：,矩阵a具有严格对角优势时，高斯赛德尔迭代收敛,华南师范大学数学科学学院 谢骊玲,14.07.2020,gauss-seidel迭代法（续2）,1步g-s迭代之后：,迭代初始值：,例,华南师范大学数学科