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

第3章 线性方程组AX=B的数值解法 引言 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。 线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。 线性方程组求解问题 考虑线性方程组 Ax = b 其中A是一个(n ×n)的非奇异矩阵, x是要求解的n维未知向量, b是n维常向量 线性方程组的解的存在性和唯一性 定理3.4 设A是N×N方阵，下列命题等价： 给定任意N×1矩阵B，线性方程组AX=B有唯一解 矩阵A是非奇异的（即A-1存在） 方程组AX=0有唯一解X=0 det(A) ≠0 线性方程组的解 最常见的求线性方程组Ax=b的解的方法是在方程组两侧同乘以矩阵A的逆 Gram法则： 线性方程组的解（续1） 求逆运算和行列式计算由于运算量大，实际求解过程中基本不使用，仅作为理论上的定性讨论 克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法 还有三角分解法和迭代求解法 解法分类 关于线性方程组的数值解法一般有两类 直接法：若在计算过程中没有舍入误差，经过有限步算术运算，可求得方程组的精确解的方法 迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法 迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题 3.3 上三角线性方程组 定义3.2 N×N矩阵A=[aij]中的元素满足对所有ij，有aij=0，则称矩阵A为上三角矩阵；如果A中的元素满足对所有ij，有aij=0，则称矩阵A为下三角矩阵。 定理3.5（回代）设AX=B是上三角线性方程组，如果akk≠0，其中k=1,2,…,N，则该方程组存在唯一解。 3.3 上三角线性方程组（续1） 定理3.6 如果N×N矩阵A=[aij]是上三角矩阵或下三角矩阵，则 3.3 上三角线性方程组（续2） 求解上三角线性方程组的回代算法 上三角线性方程组的求解 基本算法： 上三角线性方程组的求解（续1） 3.4 高斯消去法和选主元 求解有N个方程和N个未知数的一般方程组AX=B的一般做法：构造一个等价的上三角方程组UX=Y，并利用回代法求解 如果两个N×N线性方程组的解相同，则称二者等价 对一个给定方程组进行初等变换，不会改变它的解 3.4 高斯消去法和选主元（续1） 考虑一个简单的例子： 求解第二个方程，得 3.4 高斯消去法和选主元（续2） 考虑包含n个未知数的方程组 3.4 高斯消去法和选主元（续3） 3.4 高斯消去法和选主元（续4） 3.4 高斯消去法和选主元（续5） 3.4 高斯消去法和选主元（续6） 3.4 高斯消去法和选主元（续7） 3.4 高斯消去法和选主元（续8） 3.4 高斯消去法和选主元（续9） 上述消去过程中，如果akk=0，则不能使用第k行消除第k列的元素，而需要将第k行与对角线下的某行进行交换，以得到一个非零主元。如果不能找到非零主元，则线性方程组的系数矩阵是奇异的，因此线性方程组不存在唯一解 选主元以避免 ，如果此主元非零，则不换行；如果此主元为零，则寻找第p行下满足 的第1行，将此行与第p行互换，使新主元非零。 3.4 高斯消去法和选主元（续10） 选主元以减少误差：把元素中的最大绝对值移到主对角线上 3.4 高斯消去法和选主元（续11） 病态问题：矩阵A中元素的微小变化引起解的很大变化 3.4 高斯消去法和选主元（续12） 一个线性方程组称为是病态的，如果其系数矩阵接近奇异且它的行列式接近0 3.5 三角分解法 A=LU:下三角矩阵L的主对角线为1，上三角矩阵U的对角线元素非零 矩阵的LU分解 是否所有的非奇异矩阵A都能作LU分解呢？ 一个例子： N阶方阵A有唯一LU分解的充要条件是A的各阶顺序主子式均不为零 3.5 三角分解法（续1） 3.5 三角分解法（续2） 3.5 三角分解法（续3） 3.5 三角分解法（续4） M2可取: M3可取： 3.5 三角分解法（续5） 3.5 三角分解法（续6） 计算复杂性：高斯消去法与三角分解法的三角化过程是一样的，都需要 3.5 三角分解法（续7） 3.5 三角分解法（续8） 3.6 求解线性方程组的迭代法 考虑线性方程组 3.6 求解线性方程组的迭代法（续1） 3.6 求解线性方程组的迭代法