《线性方程组AX=B的数值解法(j)【优制课件】》由会员分享，可在线阅读，更多相关《线性方程组AX=B的数值解法(j)【优制课件】（53页珍藏版）》请在金锄头文库上搜索。
1、第3章 线性方程组AX=B的数值解法1相关知识引言n在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。n线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。2相关知识线性方程组求解问题n考虑线性方程组 Ax = bn其中A是一个是一个(n n)的非奇异矩阵, x是要求解的n维未知向量, b是n维常
2、向量3相关知识线性方程组的解的存在性和唯一性n定理3.4 设A是NN方阵，下列命题等价：给定任意N1矩阵B，线性方程组AX=B有唯一解矩阵A是非奇异的（即A-1存在）方程组AX=0有唯一解X=0det(A) 04相关知识线性方程组的解n最常见的求线性方程组Ax=b的解的方法是在方程组两侧同乘以矩阵A的逆nGram法则： Ax = b5相关知识线性方程组的解（续1）n求逆运算和行列式计算由于运算量大，实际求解过程中基本不使用，仅作为理论上的定性讨论n克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法n还有三角分解法和迭代求解法6相关知识解法
3、分类n关于线性方程组的数值解法一般有两类直接法：若在计算过程中没有舍入误差，经过有限步算术运算，可求得方程组的精确解的方法迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题7相关知识3.3 上三角线性方程组n定义3.2 NN矩阵A=aij中的元素满足对所有ij，有aij=0，则称矩阵A为上三角矩阵；如果A中的元素满足对所有ij，有aij=0，则称矩阵A为下三角矩阵。n定理3.5（回代）设AX=B是上三角线性方程组，如果akk0，其中k=1,2,N，则该方程组存在唯一解。8相关知识3.3 上
4、三角线性方程组（续1）n定理3.6 如果NN矩阵A=aij是上三角矩阵或下三角矩阵，则n 条件akk0很重要，因为回代算法中包含对akk的除法。如果条件不满足，则可能无解或有无穷解n 联系定理3.4，可知要条件akk0成立才能保证方程组存在唯一解9相关知识3.3 上三角线性方程组（续2）n求解上三角线性方程组的回代算法最后最后10相关知识上三角线性方程组的求解n基本算法： 11相关知识上三角线性方程组的求解（续1）12相关知识3.4 高斯消去法和选主元n求解有N个方程和N个未知数的一般方程组AX=B的一般做法：构造一个等价的上三角方程组UX=Y，并利用回代法求解n如果两个NN线性方程组的解相同
5、，则称二者等价n对一个给定方程组进行初等变换，不会改变它的解13相关知识3.4 高斯消去法和选主元（续1）n考虑一个简单的例子：n求解第二个方程，得n第二个方程减去第一个方程除以3再乘以4得到的新方程，得到新的方程组：n 回代到第一个方程，得14相关知识3.4 高斯消去法和选主元（续2）n考虑包含n个未知数的方程组orn作如下行变换之后方程组的解向量 x 不变对调方程组的两行用非零常数乘以方程组的某一行将方程组的某一行乘以一个非零常数，再加到另一行上n 通过对增广矩阵A|B进行如上的行变换求解15相关知识3.4 高斯消去法和选主元（续3）16相关知识3.4 高斯消去法和选主元（续4）17相关知
6、识3.4 高斯消去法和选主元（续5）18相关知识3.4 高斯消去法和选主元（续6）利用3.3节的回代法求解上述上三角方程组19相关知识3.4 高斯消去法和选主元（续7）消去过程20相关知识3.4 高斯消去法和选主元（续8）回代过程21相关知识3.4 高斯消去法和选主元（续9）n上述消去过程中，如果akk=0，则不能使用第k行消除第k列的元素，而需要将第k行与对角线下的某行进行交换，以得到一个非零主元。如果不能找到非零主元，则线性方程组的系数矩阵是奇异的，因此线性方程组不存在唯一解n选主元以避免 ，如果此主元非零，则不换行；如果此主元为零，则寻找第p行下满足 的第1行，将此行与第p行互换，使新主
7、元非零。平凡选主元策略平凡选主元策略22相关知识3.4 高斯消去法和选主元（续10）n选主元以减少误差：把元素中的最大绝对值移到主对角线上例3.17和3.18n 偏序选主元策略|akp|=max|app|,|app+1|,|aN-1p|,|aNp|n 按比例偏序选主元（平衡）策略sr=max|arp|,|arp+1|,|arN| 其中r=p,p+1,N23相关知识3.4 高斯消去法和选主元（续11）n病态问题：矩阵A中元素的微小变化引起解的很大变化cond(A)=207.01224相关知识图形解释25相关知识3.4 高斯消去法和选主元（续12）n一个线性方程组称为是病态的，如果其系数矩阵接近奇
8、异且它的行列式接近0n 矩阵条件数 cond(A)=|A|A-1|26相关知识3.5 三角分解法nA=LU:下三角矩阵L的主对角线为1，上三角矩阵U的对角线元素非零定义3.4 如果非奇异矩阵A可表示为下三角矩阵L和上三角矩阵U的乘积：A=LU，则A存在一个三角分解A非奇异蕴含着对所有的k有ukk0，k=1,2,3,4.27相关知识矩阵的LU分解n是否所有的非奇异矩阵A都能作LU分解呢？n一个例子：nN阶方阵A有唯一LU分解的充要条件是A的各阶顺序主子式均不为零28相关知识3.5 三角分解法（续1）n 利用前代/回代算法求解形如Lx=b或Ux=b的线性方程组是容易的n 如果对一个给定的矩阵A，能
9、够找到一个下三角矩阵L和一个上三角矩阵U，使A=LUn 则求解线性方程组Ax=b的问题可以分解成两个简单的问题：p Ly=bp Ux=yn 易见：Ax=(LU)x=L(Ux)=Ly=b29相关知识3.5 三角分解法（续2）n 假设已有矩阵A: n 对A作LU分解:n 检验分解结果: 30相关知识3.5 三角分解法（续3）n 构造一系列乘数矩阵M1, M2, M3, M4, MN-1使得: (MN-1M4M3M2M1)A是上三角矩阵，把它重新记成U.n对44矩阵A，M1可取:31相关知识3.5 三角分解法（续4）nM2可取:nM3可取：32相关知识3.5 三角分解法（续5）n 则U=(M3M2M
10、1)A是上三角形矩阵n 每个M矩阵都是下三角形矩阵n 如M2的逆为: n 注意到每个M矩阵的逆只是它自身下三角部分元素取相反数n A = (M3M2M1)-1 U = (M1)-1 (M2)-1 (M3)-1 U n 定义L = (M1)-1 (M2)-1 (M3)-1，则L就是一个对角元素全为1的下三角矩阵，因为所有的M矩阵的逆都是对角元素全为1的下三角矩阵33相关知识3.5 三角分解法（续6）n计算复杂性：高斯消去法与三角分解法的三角化过程是一样的，都需要次乘法和除法次减法求解LUX=B又需要N2次乘法和除法，以及(N2-N)次减法34相关知识3.5 三角分解法（续7）n 每一个M矩阵中都
11、需要计算1/A(i,i)n 当第i个对角元素为0或者很接近0时就没法计算M，这时A的直接LU分解就没法继续进行n 可以将第i行与它下面的某一行互换，该行的第i列元素非零n 带选主元过程的LU分解35相关知识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)A36相关知识3.6 求解线性方程组的迭代法n考虑线性方程组37相关知识3.6 求解线性方程组的迭代法（续1）n 高斯消去法高斯消去法 受限于舍入误差和病态性
12、n 迭代法迭代法 另一种求解线性方程组的方法n 给出初始估计值，通过迭代得到更好的解的近似值n 迭代法对求解大型线性方程组非常有效n Jacobi（雅可比）（雅可比）和Gauss-Seidel（高斯（高斯-赛赛德尔）德尔）方法方法38相关知识3.6 求解线性方程组的迭代法（续2）n将方程组改写成每个方程的左边只有一个未知数的形式：n给出初始估计值 和迭代规则39相关知识Jacobi迭代法n初始估计值n迭代一步后的结果： 40相关知识Jacobi迭代法（续1）nk步迭代后的结果：41相关知识Jacobi迭代法（续2）n例：nJacobi迭代公式：42相关知识Jacobi迭代法（续3）n初始迭代值
13、n20步迭代后43相关知识Jacobi迭代法（续4）n迭代会不会收敛到方程组的解？n迭代到何时会终止？终止的判断条件是什么？两个必须考虑的问题：44相关知识3.6 求解线性方程组的迭代法（续3）n定义3.6 设有NN维矩阵A，如果其中k1,2,N则称A具有严格对角优势具有严格对角优势（严格对角占优严格对角占优）。n 定理3.15（雅可比迭代）设矩阵A具有严格对角优势，则AX=B有唯一解X=P。利用雅可比迭代可产生一个向量序列Pk，而且对于任意初始向量P0，向量序列都将收敛到P。45相关知识3.6 求解线性方程组的迭代法（续4）n向量之间的距离可以用来判断Pk是否收敛到P。因为两个向量P=(x1
14、,x2,xN)和Q=(y1,y2,yN)之间的欧几里德距离计算复杂；而1范数具有度量的数学结构，也适合作为一个一般化的“距离公式”。而且根据线性代数的理论可知，如果两个向量的|1范数接近，则它们的欧几里德范数|2也接近。所以定义两个N维向量的距离为|1范数，用来确定N维空间中的收敛性46相关知识3.6 求解线性方程组的迭代法（续5）n1-范数： 满足一般向量范数的性质定理3.16 设X和Y是N维向量，c是一个标量。则函数|X|有如下性质：p正定性：|X|0，|X|=0当且仅当X=0p齐次性：|cX|=|c|X|p三角不等式：|X+Y|X|+|Y|47相关知识Gauss-Seidel迭代法n初始
15、估计值n迭代一步后的结果： 48相关知识n 每一次迭代新产生的 被认为是比 更好的xj的近似值，所以在计算xj+1时用 来替换 是合理的Gauss-Seidel迭代法（续1）nk步迭代后的结果：n 矩阵A具有严格对角优势时，高斯赛德尔迭代收敛49相关知识Gauss-Seidel迭代法（续2）1步G-S迭代之后： 迭代初始值：例50相关知识Gauss-Seidel迭代法（续3）n2步迭代之后 9步迭代之后 1步迭代之后 51相关知识3.6 求解线性方程组的迭代法（续6）雅可比迭代：高斯赛德尔迭代：52相关知识J-迭代和G-S迭代的比较n一般来说，用J-迭代、G-S迭代都收敛的问题，用G-S迭代收敛更快nJ-迭代保留上一步所有点的值，花费存储空间，适合并行运算，节省计算时间nG-迭代每计算出一个新点都用于下一步的计算中，不须保留上一步所有点的值，节省存储空间，但只能串行计算53相关知识
