数值计算复习小结

第一章 科学计算 适定问题的三个特征是 存在性 唯一性 病态性 科学计算中误差的来源 建模 经验测量 前面的计算 截断或离散化 舍入 第二章 线性方程组 解的存在性和唯一性 唯一解 A 非奇异 b 任意 无数解 A 奇异 b 与 A 相容 没有解 A 奇异 b 与 A 不相容 问题的敏感性和病态性 1 矩阵的条件数可以作为界定右端向量的相对变动引起解 的最大相对变动的放大因子 即可以作为敏感性的测量 2 矩阵的条件数受矩阵重新排列和元素大小调整的影响 3 当且仅当 A 是良态矩阵是 较小的相对残差所对应解的 相对误差才能很小 4 不管条件数如何 稳定的算法产生的相对残差总是非常 小 求解线性方程组 三角线性方程组 前代和回代复杂性为 o n n 高斯消去 lu 分解 优点 A 的对角线以下的元素存储 L 以上存 储 U 节省空间 计算量不是太大 n 3 3 缺点 会出现非常小的量 消去过程中计算 某一列时需要除以这一列的主元 如果 某一步矩阵未被约化部分的主元为 0 的 话 消去过程将失败 求逆方法 缺点 1 计算量大约是高斯消去的 3 倍 计算 A 的 逆相当于求解 n 个线性方程组 总的操 作次数大约为 n 3 次乘法和同样数量的 加法 2 降低解的精度 选主元 优点 1 解决了高斯消去出现的由于主元为 0 导致的消去 失败的问题 2 减少了数据误差的传播 避免在用初等消去法乘 矩阵的其余部分以及右端向量时将前面的误 差放大 3 通常可以产生精度最高的解 高斯若当消去法 优点 消去一旦完成 矩阵将变成对角形 方 程组的解可以分别由变幻后的右端向量 的每个分量除以对角阵的相应元素得到 工作量比求解三角方程组要少得多 缺点 1 消去过程的成本并不低 2 计算量比标准的高斯消去法的计算量 要多 50 大约要 n 3 2 次乘法和同样 数量的加法 特殊类型的线性方程组 对称正定方程组 出列斯基分解 优点 1 所需计算的 n 个平方根都是正数 这使得 算法是良态的 2 不需要选主元就能保证数值稳定 3 仅仅用到 A 的下 3 角部分 因而上三角部 分不必存储 4 仅仅需要做 n 3 6 次乘法和同样数量的加 法 5 存储量和工作量仅为高斯法的一半 缺点 为了利用存储上的优势 通常需要将对称矩 阵的三角部分按一维数组存储 这样不如将 矩阵按二维数组存储方便 带状方程组 三对角方程组 1 通常系数矩阵是对角占优或正定的 因而 不用选主元就可以达到数值稳定 2 存储量为 o n 分解工作量为 o n 2 这两 项与一般的方程组相比都可以有较多的节 省 第三章 线性最小二乘 解的存在性和唯一性 最小二乘总是有解 最小二乘的解唯一的冲要条件是 A 列满秩 问题的敏感性和病态性 a 最小二乘问题的解 x 关于 b 的扰动问题的条件数不仅与 cond A 有 关 还与 b 和 Ax 的夹角有关 残差向量较小时 条件数近似为 cond A 残差向量较大时 条件数可以任意大于 cond A b 最小二乘问题的解 x 关于 Ax 的扰动问题的条件数不仅与 cond A 有 还与 b 和 Ax 的夹角有关 残差较小 以至 tan 0 时 条件数近似等于 cond A 残差大小适当时 条件数为 cond A 的平方 残差较大时 条件数可以任意大 求解最小二乘问题 正规方程组 1 形成 A 的叉积矩阵和右端向量时会产生信息 丢失 2 叉积矩阵的条件数是原矩阵的平方 3 即使在拟合良好 并且残差也较小的情况下 正规方程组也会出现条件数平方效应 这使 得计算解的敏感性比原来的最小二乘问题更 强 因此正规方程组解法时不稳定的 增广方程组 缺点 增广方程组对称但不正定 而且比原来 的方程组要大 求解时需要存储 A 的两个拷贝 而且如果我么烟对角线选主元 会再次产生正规 方程组 而正规方程组的数值稳定性很差 可以用其他的选主元的策略 以保证数值稳定 正交变换 正交变换 household 优点 1 不仅可以求解最小二乘问题 而且还可以求解系 数矩阵相同 右端向量不同的问题 2 同时在一个列中引入多个 0 效率高 缺点 1 如果要给出 Q 就要将单位阵依次乘以每个 household 变换 这些计算要用到额外的存储 2 如果有所选择地引入 0 的话 这个方法就不有效了 Givens 优点 1 可以有所选择地每次引入一个 0 元素 2 复杂程度上 比 household 更简单些 缺点 1 工作量比 household 多 50 2 需要的存储量较多 Gram Schmidt 缺点 1 舍入误差可能会导致数据丢失 2 古典的方法需要单独存储 A 和 Q 以及 R 3 改进的算法里 Q 和 R 仍需要分别存储 不如 household 4 提供了 Q 的直接表示 需要的话 需要额外的 存储 优点 1 改进的算法数值稳定性十分优越 2 提供了 Q 的直接表示 需要的时候 不用再额 外计算 第五章 非线性方程 问题的敏感性和病态性 一维空间 x 为重根时 条件数为无穷大 微小的扰动可 能使一个重根变成多个根 或者根本不是根 N 维空间 当雅克比矩阵奇异时 条件数为无穷大 求解一维非线性方程 二分法 优点 迭代过程一定收敛 安全 缺点 线性收敛 速度太慢 不能处理求根函数有垂直或水平渐近线的情况 不动点迭代 格式有不同的收敛形式 可能发散 可能收敛 很慢 也可能收敛很快 牛顿法 单根情形 收敛速度是 2 次的 重根情形 收敛速度是 1 次的 线性 优点 收敛速度快 缺点 1 这种收敛只是局部的 只有在初始值接 近真解时 牛顿法才会收敛 2 每次迭代时都要计算函数及其导数的值 导数的计算往往不方便或者计算量很大 3 不能处理求根函数有垂直或水平渐近线 的情况 割线法 缺点 1 尽管收敛是超线性的 但还是很慢 2 需要两个迭代初值 3 收敛只是局部的 为保证收敛 迭代的初 值必须落在根附近 4 不能处理求根函数有垂直或水平渐近线的 情况 优点 每次迭代工作量小 抵消了迭代次数多的缺 陷 求根的总成本还是小于牛顿法 反插法 缺点 1 需要 3 个迭代初值 2 收敛时局部的 为了保证收敛 迭代的初 值应充分接近真解 优点 收敛速度比割线法加快 线性有理插值 优点 1 可以处理有水平或者垂直渐近线的 情况 2 超线性 收敛速度比较快 比较有 效 缺点 局部收敛 为了保证收敛 迭代的初 始值应充分接近真解 第七章 插值 插值的存在性 唯一性和病态性 对给定数据点集的插值的存在和唯一性依赖于基 矩阵的非奇异性 而且参数对数据的扰动的敏感 性依赖于 A 的条件数 多项式插值 单项式基底 优点 求值简单 缺点 1 确定系数的工作量达到 o n 3 2 得到的范德蒙矩阵往往是病态的 特别是高次多项式 时更是如此 范德蒙矩阵的条件数随着 n 的增长 速度至少是指数的 n 增加时 它可以变得极为 病态 甚至变为奇异的 3 即使使用最佳位移和伸缩变换 单项式基底通常也是 病态的 拉格朗日插值 优点 1 很容易确定插值多项式 2 得到的参数是完全良态的 缺点 多项式的求值更加复杂 积分操作也更困难 牛顿插值 优点 1 既可节省形成插值多项式的计算量 又可以节约 计算给定点的值的成本 2 与数据点的排列次序无关 分段多项式插值 三次艾尔米特插值 缺点 光滑性不好 优点 1 外观上比较优美 2 能保持计算简单 效率高的性能 3 能保持原始数据的单调性 4 光滑性虽然不足 但是从外观看却 很好的反应了数据点的形态 三次样条插值 优点 光滑性好 缺点 对光滑度的要求使得插值的结果可能不单 调 B 样条 优点 1 使用 B 样条基底 求解样条函数系统的线性方 程组将非奇异且呈带状 2 具有局部性 如果给定数据节点上数据发生变 化 受到影响的只有几个基函数的系数 第八章 积分 积分解的存在性 唯一性 和问题的病态性 被积函数有界 有有限个断点 与被积函数扰动有关的积分问题通常是良态的 因为积分本身 是平均和修匀的过程 它并不受被积函数的某些微小变化的影 响 数值求积 待定系数法 如果某些权是负数 则绝对条件数会非常大 求积公式将 不稳定 牛顿 科特斯求积 优点 1 求积公式的推导和使用相对容易 2 有递推性 缺点 1 连续函数在等距离节点上的高次插值会出现 振荡 随着节点的增加并不一定能保证插值 多项式收敛到固有的函数 2 随着节点个数的增加 病态性增强 因而不 稳定 3 计算积分时若有负的权值 极易发生抵消现 象 4 对节点的个数来说 精度不是最高的 高斯求积 优点 精度是最高的 缺点 1 求得比牛顿 科特斯公式困难得多 2 求解过程中得到非线性的方程组 3 节点通常是无理数 手工计算相对麻烦 4 权和节点都是在特殊的区间上给出的 任意其他 积分区间都必须变换到标准区间上 复合求积 1 适定问题具有哪三个特征 2 矩阵的条件数的几何意义是什么 与矩阵的奇异程度有什么关系 3 解释在线性最小二乘问题中 最小二乘解x对应的残差向量r b Ax的几何意 义 并推导出正规方程组 4 比较用单项式基底做插值的优缺点 5 比较牛顿 柯特斯求积公式与高斯求积公式 6 用牛顿法解方程x e x 0在x 0 5附近的近似根 要求 0 001 计算 nn xx 1 过程保留5位小数 7 用高斯 塞德尔迭代法解方程组 123 123 123 521 2522 251 xxx xxx xxx 1 证明高斯 塞德尔迭代法收敛 2 写出高斯 塞德尔法迭代公式 3 取初始值 求出 0 0 0 0 TX 1 X 8 已知函数表 x012345 xf 7 452665128 求证由此构造的牛顿插值多项式的最高次幂的系数为 1 4 求解线性方程组的 1 Gauss Jordan 消去法 2 列主元 Gauss 消去法 3 克 莱姆法则 4 直接求逆用矩阵 向量的乘法 按工作量排序是 5 用 Household 变换消去向量 a 2 1 2 T的除第一个分量以外的分量 最后结 果是 6 使向