线性方程组AX=B的数值解法jppt课件.ppt

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