已阅读5页,还剩14页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第2章 线性代数方程组与矩阵运算本章自学内容: 线性代数方程组的直接解法 线性代数方程组的迭代解法 矩阵分解2.1 线性代数方程组的直接解法 一、Gauss消去法 1. 将增广矩阵经过一系列的初等行变换变成右上三角矩阵。即 其中为单位上三角矩阵(除最后一列外) 对于k从0开始直到n-2作以下两步(假设对于任意的k有0): (1) 归一化 / ,jk1,n1 / (2) 消元 ,ik1,n1;jk1,n1 ,ik1,n1 2. 进行回代,依次解出,。 /, ,kn2,1,0 分析:时间复杂度 归一化 n k + 1 消去 (n k + 1)(n k) 共 回代 总共 多项式界算法 空间复杂度 in place 可靠性 当|0时,运算就会中断(因为出现分母为0的情况); 即使|0,但当|很小时,一方面会损失精度,另一方面还可能会导致商太大而使计算产生溢出。 数值计算是不稳定的。 二、选主元 1) 列选主元 采用列主元的高斯消去法是不影响求解结果的。 2) 全选主元 JS(0:n1) JS(k)记忆做到第k步时,与第k列进行交换的列号。 全选主元高斯消去法求解线性代数方程组的步骤如下: (1) 对于k从0到n2做以下运算: 全选主元 系数矩阵归一化 / ,jk1,n1 常数向量归一化 / 系数矩阵消元 ,ik1,n1;jk1,n1 常数向量消元 ,ik1,n1 (2) 进行回代 解出 / 回代逐个解出 ,。即 ,kn2,1,0 (3) 恢复解向量 三、Gauss-Jordan消去法 (1) 对于k从0到n1做以下运算: 全选主元 系数矩阵归一化 / ,jk1,n1 常数向量归一化 / 系数矩阵消元 ,i0,1,n1;ikjk1,n 常数向量消元 ,i0,1,n1;ik 归一化 n k + 1 消去 (n k + 1)(n 1) 共 四、三对角方程组 = 高斯消去法求解三对角方程组的步骤如下: 1) 对于k从0到n2做以下运算: 系数矩阵归一化 常数向量归一化 系数矩阵消元 常数向量消元 经过这一步后,方程组变为 = 2) 进行回代 解出 回代逐个解出,。即 ,kn2,1,0 “追”的过程需要做4(n1)次乘除法,而“赶”的过程需要做n次乘除法。因此,“追赶法”的计算工作量为(5n4)次乘除法。 当三对角方程组中的系数矩阵(三对角矩阵)满足条件 | | ,k1,2,n2 |时,“追赶法”的计算过程中不会出现中间结果数量级的巨大增长和舍入误差的严重积累。2.2 病态方程组 某些方程组系统对于增广矩阵元素的微小变化是很敏感的,这样的系数矩阵称为病态矩阵。例:中度病态矩阵 解为 =2.40481 1.60321但如果方程组变为 解变为 =3 1计算过程中的微小误差可能影响它的解。当用低精度计算时尤其突出。 例: 解为 =0 2。但如果方程组变为 解变为 =200.00 -198.01。通常用条件数来衡量问题的病态性。方程组系统的条件数定义为 K = 其中是系数矩阵的最大值范数,它是行元素绝对值之和的最大值,即 = 如果条件数K接近于1,矩阵是健康的;否则,如果它比1大得多,则矩阵是病态的。例: = = K = = 2.000120001 = 40004.0001采用校正法求解病态方程组: (1) 求解 ,得到一组近似解。 (2) 计算剩余(残)向量 (3) 求解 ,解出。 (4) 计算 (5) 令,转(2)重复这个过程。直到满足条件 : 当时,精确到小数点后第k位; 当时,准确到k位有效数字。Further: 提高求解精度 增加计算工具(系统)的有效数字位数。如由单精度改为双精度。 选主元(一般全主元)。 校正法。 但 双精度运算对提高精度影响较大。 对严重病态者,选主元对精度影响不太大。 校正法的修正作用最大(可以不选主元,运算中断者除外)。2.3 线性代数方程组的迭代解法一、简单迭代法 将 变为 得到简单迭代格式为 即 ,i0,1,n1 第k1次迭代值与准确解之间的误差为 ,i0,1,n1有 ,i0,1,n1若令 则有 ,i0,1,n1如果令 则有 结论:简单迭代格式收敛条件为 上述条件是一个充分条件,并不是必要条件。 例 求解方程组 变为 迭代格式为 取迭代初值为(0,0,0),通过13次的迭代计算,收敛于 1.10000,1.20000,1.30000 实际上,该方程组的准确解为 1.1,1.2,1.3 在上例中,如果用下列迭代格式 仍取迭代初值(0,0,0),则用迭代格式计算得到的迭代值序列如下: 0.0, 0.0, 0.0 8.3, 4.2, 3.6 43.1, 13.9, 43.0 如果继续计算下去,其绝对值会越来越大,不可能趋于一个常数。即该迭代格式发散。二、赛德尔(Seidel)迭代法 设方程组 ,i0,1,n1经过分离后变成 ,i0,1,n1 如果 则赛德尔迭代格式 ,i0,1,n1对于任意给定的初值均收敛于方程组的解。 在收敛的情况下,赛德尔迭代法比简单迭代法的收敛速度要快。但收敛范围并不重合,只是部分相交。三、高斯-赛德尔迭代法 如果方程组 ,i0,1,n1的系数矩阵满足 ,i0,1,n1则可以直接得到 ,i0,1,n1于是赛德尔迭代格式变为 ,i0,1,n1对于任意初值均收敛于方程组的解。称为高斯-赛德尔迭代法,简称为赛德尔迭代法。例 方程组 对角线占绝对优势 高斯-赛德尔迭代格式为 如果对角线占绝对优势,则高斯-赛德尔方法总是收敛于精确解,与所选的初值无关。编程很简单,计算很有效率的,广泛用于求解工程问题中的主对角线优势的线性方程组。2.4 矩阵求逆 = = 由高斯-约当消去法 = 两边分别用右乘得 = 即 一、原地工作的矩阵求逆经过前k步(0k-1)后 及做第k步 压缩:(1) 前k步得到的的前k列结果压缩存放在矩阵的前k列; (2) 第k步in place。 即第k步为 例 方程组 = = 二、全选主元 IS(0:n1) JS(k)记忆做到第k步时,与第k行进行交换的行号,即做到第k步时,第k行与第IS(k)行进行了交换。 JS(0:n1) JS(k)记忆做到第k步时,与第k列进行交换的列号,即做到第k步时,第k列与第JS(k)列进行了交换。 选主元过程: (1) A(k,j)A(IS(k),j),j0,1,n1 (2) A(i,k)A(i,JS(k),i0,1,n1 恢复原理: 恢复过程: 对于k从n1到0,分别做以下两步: (1) A(k,j)A(JS(k),j),j0,1,n1 (2) A(i,k)A(i,IS(k),i0,1,n1 矩阵求逆的计算工作量(乘除法次数)为。求下列矩阵的逆矩阵: , 2.5 矩阵分解 一、LU分解 = 三角分解之一。其中是主对角线元素为1的下三角矩阵,是上三角矩阵 = , = 方程组=可以化成下列两个方程组: = =利用方程组=可以解出,再利用方程组=解出。 二、 豪斯荷尔德变换 设列矩阵 满足 ,则 2 称为豪斯荷尔德矩阵。显然,为对称矩阵。并且可以证明,还是一个正交矩阵。 例 设给定一个列矩阵 显然,列矩阵满足 对应的豪斯荷尔德矩阵为 在实际应用中,使用的其前若干个元素一般为零,即 其中 0,0 在这种情况下,豪斯荷尔德矩阵为 其中 用上述豪斯荷尔德矩阵左乘一个矩阵后,将保持该矩阵的前k行的元素不变。即 用上述豪斯荷尔德矩阵右乘一个矩阵后,将保持该矩阵的前k列的元素不变。即 应用1:构造一个豪斯荷尔德矩阵,使之左乘矩阵的第k列后,使该列的前k个元素保持不变,而第k1个元素到最后一个元素均变成零。 矩阵的第k列为 设用于构造豪斯荷尔德矩阵的列矩阵为 对应的豪斯荷尔德矩阵左乘矩阵的第k列后,使该列的前k个元素不变(显然的),而使后面的nk1个元素变为零(要求)。即 考虑到,是一个常数。得到 ,ik1,n1 实际计算公式如下: ,ik1,n1 应用2:假设对称矩阵的前k行和前k列已经为三对角形式。构造一个豪斯荷尔德矩阵,分别左乘对称矩阵的第k列与右乘第k行(即作相似变换),使该列与该行变成三对角形式,而前k行和前k列的元素不变。 矩阵的第k列为 设用于构造豪斯荷尔德矩阵的列矩阵为 对应的豪斯荷尔德矩阵左乘矩阵的第k列后,使该列的前k1个元素不变(显然的),而使后面的nk2个元素变为零(成要求的三对角形式)。即 考虑到。得到 = = , i=(k+2),(k+3),(n-1)其中 = 由于是对称矩阵,用相同的豪斯荷尔德矩阵右乘矩阵的第k行,就将该行变换成三对角形式。即 三、QR分解 = 其中为mm的正交矩阵,为mn的上三角矩阵。 根据豪斯荷尔德(Householder)变换的应用1。依次用豪斯荷尔德变换将矩阵的每一列变换成上三角矩阵,最后得到的上三角矩阵即为,而所有豪斯荷尔德矩阵的乘积即为。 首先确定一个矩阵(为豪斯荷尔德矩阵,下同),用左乘,即 使中第1列的第2个元素到最后一个元素均变成零。 再确定一个矩阵,用左乘,即 使中第2列的第3个元素到最后一个元素均变成零,而中第一行及第一列保持不变。 以此类推,一般来说,确定一个矩阵,用左乘,即 使中第k列的第k1个元素到最后一个元素均变成零,而中前k1行及前k1列保持不变。 这个过程一直做到 为止。其中smin(m,n)。此时有 最后得到 使 Further: 分解法求解对称方程组 为单位下三角矩阵,为对角矩阵 令 ,即 等价于 等价于 由 解出 再由 解出 Cholesky分解(平方根)法求解对称正定方程组 对称正定矩阵:det()0,k0,1,n1 即对于对称矩阵,二次函数 0,且只有当时有 为上三角矩阵 令 ,即 等价于 等价于 由 解出 再由 解出 可以推导出直接用公式求解 共轭梯度法求解对称正定方程组 基本思想:对于任意一个初始列向量作迭代 ,i0,1,n1其中为共轭正交的向量,为数量。其迭代值序列 ,收敛于方程组的准确解。 因此,共轭梯度法的关键是如何根据系数矩
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电池部件制备工变革管理知识考核试卷含答案
- 光缆线务员操作水平能力考核试卷含答案
- 乳品浓缩工安全知识竞赛评优考核试卷含答案
- 甲壳类繁育工安全文化能力考核试卷含答案
- 纸盒制作工安全意识强化考核试卷含答案
- 轨道作业车司机安全宣传竞赛考核试卷含答案
- 煤气净化回收工复试水平考核试卷含答案
- 印花色浆配制操作工技术水平模拟考核试卷含答案
- 精细木工岗中专业基础考核试卷含答案
- 电子玻璃制品研磨抛光工操作安全强化考核试卷含答案
- 《隧道施工与管理》全套教学课件
- T/ZACM 001-2025脑卒中后吞咽障碍耳穴压豆技术
- EPC项目图纸会审与深化方案
- 2026吸入制剂技术突破与呼吸系统药物开发报告
- 压力性损伤诊疗与护理规范
- DB32-T 5434-2026 太湖流域农业面源污染负荷评估规范
- 注册消防工程师继续教育2025年部分题目与答案(126题)
- 2.14 Day 14上海新中考英语之情景对话填空专项练习每日2篇
- 初中数学九年级上册圆的基本概念知识清单
- 2026年内江市科级干部任职资格考试题库附答案
- 创伤性脑损伤的评估和治疗
评论
0/150
提交评论