数值计算方法总复习.ppt

数值计算方法 总复习 第一章引言 截断误差 舍入误差误差 误差限有效数字误差的传播 如 若将前若干项的部分和作为函数值的近似公式 由于以后各项都舍弃了 自然产生了误差 Taylor展开 截断误差 舍入误差 绝对误差 绝对误差限 工程上常记为 误差 误差限 例如 相对误差 相对误差限 例1 解 已知近似值为 精确值为 求绝对误差 相对误差 绝对误差 相对误差 或 有效数字 用科学计数法 记 其中 的截取按四舍五入规则 有4位有效数字 有6位有效数字 有8位有效数字 例2 数据误差的传播 绝对误差为 相对误差为 称为f的条件数 其绝对值的大小可反映函数值对数据的敏感程度 误差的传播 利用上面的误差估计公式 可以得到两个数的和 差 积 商的误差估计 误差的控制 算法的稳定性 第二章非线性方程求根 基本概念局部收敛 全局收敛收敛阶算法及其收敛性二分法简单迭代法牛顿法及其简单变形 局部收敛与全局收敛 上面定理所涉及的收敛性 即在根邻域的收敛性称为局部收敛性 具有局部收敛性质的迭代法通常对初值的要求很高 使用起来不太方便 因而 人们通常希望迭代算法对相对大的范围的初始点具有收敛性 这种收敛性称为全局收敛性 定义2 2 1设迭代过程收敛于的根 如果迭代误差满足下列关系则称该迭代序列是p阶收敛的 时要求 当p 1时 称为线性收敛 当p 1时 称为超线性收敛 当p 2时 称为平方收敛或二次收敛 显然 迭代序列的收敛阶越高 它的收敛速度就越快 收敛阶 补充 定理 算法的基本思想 将区间对分 保留有根的区间 舍去无根的区间 如此往复 以逐步逼近方程的根 基本条件 二分法 算法的步骤 ax0b a1b1 此时有误差估计 常用来估计k的值 算法的收敛性 用二分法求方程 在 1 1 5 内的实根 要求 解 即可推出所需的迭代次数满足 在区间 1 1 5 上至少存在一个根 其具体过程如下 例 由于 因而 由误差估计式 原理 简单迭代 迭代格式 定理2 2 1 收敛性 压缩映像 保证迭代不中断 Lipschitz条件 定理2 2 1的条件 2 不容易得到 由微分中值定理 推论 不难得到如下推论 从而 有如下误差估计 定理在推论的条件下 有误差估计式 注由于定理中条件 1 一般难于验证 而且在大区间上 这些条件也不一定都成立 所以实际使用迭代法总是在根的邻近进行 表明收敛性与初值的选择有关 定理2 2 2 例 解 也可化为等价方程 但此时定理条件不成立 迭代序列不能保证收敛 将非线性方程线性化 以线性方程的解逐步逼近非线性方程的解 基本思想 Newton迭代方法 迭代格式 Newton迭代法的计算步骤 缺点 对初值要求较高 计算量较大 优点 收敛速度快 精度高 格式简单 应用广泛 优点与缺点 局部收敛性 全局收敛性 定理2 2 3 保证了根的存在性 函数单调 根惟一 函数图形的凸向不变 例 解 简化Newton法 迭代格式 进一步简化 收敛性与收敛速度 推广的简化Newton法只有线性收敛速度 迭代格式 收敛性与收敛速度 迭代格式 收敛性与收敛速度 Newton下山法 迭代格式 收敛性与收敛速度 弦割法 迭代格式 收敛性与收敛速度 单点弦割法 单点弦割法的局部收敛性 由简单迭代的一般收敛性理论可以推出 单点弦割法是局部收敛的且一般只有线性收敛速度 单点弦割法的全局收敛性 定理2 3 2 第三章线性方程组的数值解法 基本概念向量范数 矩阵范数 条件数严格对角占优矩阵 对角占优矩阵 不可约矩阵算法及其收敛性高斯消元法矩阵的三角分解及其应用迭代法 1 2 3 4 显然 并且由于 例求下列向量的各种常用范数 解 根据向量的常用范数可以得到常用的矩阵算子范数 10 11 12 证明见书P70 例 求矩阵A的各种常用范数 解 由于 特征方程为 容易计算 计算较复杂 对矩阵元素的变化比较敏感 不是从属范数 较少使用 理论上 使用最广泛 性质较好 定义3 3 5 13 矩阵的谱半径 显然 由定义可知 实特征值为绝对值 复特征值为模 定义3 3 7 矩阵的条件数 矩阵A的条件数与所取范数有关 通常记 显然 当A对称时 严格对角占优矩阵 对角占优矩阵 不可约矩阵 容易验证下面矩阵 按行 或列 都不严格对角占优 但它是不可约按行 或列 对角占优的 虽然不可约 但不按行 或列 对角占优 而矩阵 Gauss消元法 基本思想 Gauss消元法的运算量 数级 不必选主元的情况 当系数矩阵A对称正定或严格对角占优或不可约对角占优时 可不必选主元 Gauss消元法是不稳定的算法 其中小主元是不稳定的根源 因而在Gauss消元法中要避免小主元的出现 这就需要采用 选主元 的技术 所谓选主元 简单地说就是选取绝对值最大的元素作主元 全选主元或列选主元 算法的稳定性 矩阵的LU分解法 按上图逐框求出矩阵A的LU分解 紧凑格式法 上一页下一页返回 称为矩阵A的乔累斯基分解 上一页下一页返回 称为对称正定矩阵A的乔累斯基分解 利用乔累斯基 Cholesky 分解式来求解Ax b的方法也称Cholesky方法或平方根法 例 利用系数矩阵的LU分解 求解方程组 解 LU分解的紧凑格式为 上一页下一页返回 迭代法的一般形式及其收敛性 迭代法 一 雅可比 Jacobi 迭代法 几种古典迭代算法 建立迭代格式 记 Jacobi迭代的矩阵形式 易知 Jacobi迭代有 二 逐次代换法 Gauss Seidel迭代 Gauss Seidel迭代的矩阵形式 三 逐次超松弛迭代 SOR迭代 SOR迭代的矩阵形式 定理3 4 1 一 收敛性判别定理 定理3 14 一般迭代算法的收敛性 定理3 4 2 Jacobi迭代收敛 Gauss Seidel迭代发散 古典迭代法的收敛性 第四章插值方法 基本概念插值节点 插值多项式 插值基函数差商及其性质算法及其收敛性Lagrange插值Newton插值分段线性插值 1 这就是插值问题 1 式为插值条件 Lagrange插值就是选用节点上的函数值作为插值条件 选用代数多项式作为插值函数 Lagrange插值 已知n 1个互异插值节点 xi f xi i 0 1 2 n 插值基函数 基函数仅与节点有关而与被插函数无关 容易验证 Ln xi f xi i 0 1 2 n n次Lagrange插值多项式 因此n次Lagrange插值多项式还可表示成 例4 1 4已知插值点 2 00 17 00 0 00 1 00 1 00 2 00 2 00 17 00 求三次插值 并计算f 0 6 解先计算4个节点上的基函数 三次Lagrange插值多项式为 f 0 6 L3 0 6 0 472 n次插值多项式的误差 定理4 1 3设Ln x 是 a b 上过插值点 xi f xi i 0 1 2 n的n次Lagrange插值多项式 节点xi两两互异 若f x Cn 1 a b 则 x a b 存在 x a b 使得 Lagrange插值的优缺点优点 形式整齐 规范 理论上保证插值的存在唯一性 缺点 计算量大 重复计算多 不具有承袭性 Newton插值 因此 每加一个节点时 只附加一项上去即可 有 再继续下去待定系数的形式将更复杂 一阶差商 f x 关于点x0 x1的一阶差商记为f x0 x1 差商及其性质 二阶差商 f x 关于点x0 x1 x2的二阶差商记为f x0 x1 x2 一般地 k阶差商f x0 x1 xk 定义为 性质1k阶差商f x0 x1 xk 可表成节点上函数值f x0 f x1 f xk 的线性组合 即 例如 k 2时 性质2各阶差商具有对称性 即改变差商中节点的次序不会改变差商的值 设i0 i1 ik为0 1 k的任一排列 则 由性质1知 任意改变节点的次序 只改变公式右端求和的次序 故其值不变 例如 由定义知 性质3若f x 为n次多项式 则一阶差商f x xi 为n 1次多项式 由定义 性质4若f x 在 a b 存在n 1阶导数 xi a b i 0 1 n 固定x a b 则n 1阶差商与导数存在如下关系 令x xi 则分子为0 说明分子中含有因子x xi 与分母约去 解 例对f x x7 x4 3x 1 求f 20 21 f x 20 21 26 和f x 20 21 27 利用差商与导数的关系 性质4 显然 f 7 x 7 f 8 x 0 由性质4得 由差商的定义一阶差商是由节点上函数值定义的 二阶差商是由一阶差商定义的 依此构造差商表 差商的计算 n次Newton插值公式 插值误差为 由插值的唯一性 Ln x Nn x 因此 Newton插值是Lagrange插值的另一种表示形式 他们的误差也相同 即当f x Cn 1 a b 时 有 故得差商的性质4 例给定四个插值点 2 17 0 1 1 2 2 19 计算N2 0 9 N3 0 9 解首先列差商表 所以 N2 0 9 17 8 0 9 2 3 0 9 2 0 9 1 63 N3 0 9 N2 0 9 1 25 0 9 0 9 2 0 9 1 1 30375 差分及其性质 一般地 m阶差分定义为 1 线性性质 例如 差分的重要性质 2 若f x 是m次多项式 则 3 差分值可由函数值算出 即 函数值可由差分值算出 即 由Rn x 的表达式得 4 各阶差分之间有如下关系 5 差商和差分有如下关系 函数的差分可以列成如下向前差分 向后差分和中心差分表 向前差分 向后差分表 中心差分表 等距节点Newton插值 1 Newton前插公式 Newton前插公式 插值余项为 2 Newton后插公式 插值余项为 插值多项式与被插函数的逼近程度同分点的数目和位置有关 一般地 分点越多 逼近程度越好 但也有例外 例4 4 1 分段线性插值 不同次数的Lagrange插值多项式的比较图 Runge现象 插值多项式在插值区间上发生剧烈的震荡 它揭示了高次插值多项式存在的缺陷 产生的原因 误差由截断误差和舍入误差两部分组成 而在插值的计算过程中 舍入误差可能会扩散或放大 n越大 端点附近抖动越大 由于高次多项式插值很可能产生Runge现象 在多项式插值中一般不宜选取高次多项式 分段线性插值 给定N 1个插值点 xi yi i 0 1 2 N 过这N 1个点 可作折线函数P x IN x 称之为函数f x 的分段线性插值 分段线性插值函数也可以写成基函数的形式 其中基函数li x 为非负的且局部非零 称为局部支撑性 的分段线性函数 可以看出 当节点加密时 分段线性插值函数与被插函数的函数值有很好的近似性 例已知函数 在区间 0 5 上取等距插值节点 如下表 求区间上分段线性插值函数 并利用它求出 近似值 解 在每个分段区间 上 于是 实际值 当n 7时 P 4 5 0 04762270321996当n 10时 P 4 5 0 04705882352941由此可见 对于光滑性要求不高的插值问题 分段线性插值的效果非常好 计算也简单 0 04705882352941 定理4 4 1设函数f x C a b 则有如下收敛性 定理4 4 2设函数f x C2 a b 则 例4 4 2已知计算f 1 2 f 3 3 解 第五章函数最佳逼近 基本概念正规方程组算法及其收敛性离散最小二乘逼近最佳平方逼近 一般最小二乘拟合多项式 对于离散数据 xk yk k 1 2 m 用n n m 次多项式来拟合曲线 设多项式 的系数是下述极小值问题的解 一阶必要条件 直接计算易得 故 或 称为正规方程组 可表示为 例5 1 4用二次多项式函数拟合如下数据 解 设p x a0 a1x a2x2 形成正规方程组 m 7 约定直接计算有 方法一 一般地 为定义在X上的广义多项式 记为 定义残差的平方和 最小二乘问题为 求解极小值问题 正规方程组便可化为 将其表示成矩阵形式 例5 1 6用给定数据 求经验公式f x a bx3 x 3 2 124y 14 38 34 78 322 7 解约定直接计算得 法方程 于是法方程组为 所求经验公式为 f x 10 675 0 137x3 函数的最佳平方逼近 上述问题等价于求多元函数 的最小值 由多元函数取极值的必要条件 得 于是有 上述方程组称为正规方程组 也可以写为 例5 2 1 解 取基函数为 建立正规方程组 根据内积公式 可得 正规方程组为 所求拟合函数为 第六章数值微积分 基本概念代数精度算法及其收敛性Newton Cotes求积公式复化梯形公式和复化辛普森公式两点微分公式和三点微分公式 定义设有近似式 则称该近似式具有m次的代数精度 代数精度也称代数精确度 代数精度 容易验证 梯形求积公式的代数精度为1 Simpson求积公式的代数精度为3 例 试确定下面积分公式中的参数使其代数精确度尽量高 解 因此 所以该积分公式具有3次代数精确度 例 求以下微分公式的代数精度 解 故代数精度为2 对于一般的n阶插值型求积公式 由误差公式 可知 其代数精度至少为n 对于Newton Cotes求积公式 我们有 定理 定理 Newton Cotes求积公式 在微积分中 定积分是Riemann和的极限 即 数值积分就是取定积分极限中的有限项的和 即 其中 xk称为积分节点 Ak称为积分系数 我们的任务就是确定积分系数Ak 使I f In f 最常用的方法就是用插值多项式近似代替被积函数f x 来确定Ak 得数值积分公式 截断误差为 1 基本求积公式 Newton Cotes求积公式是指等距节点下使用Lagrange插值多项式建立的数值求积公式 各节点为 其中 而 因此有 令 n阶Newton Cotes求积公式 Newton Cotes公式的余项 误差 即有 注意是等距节点 Newton Cotes求积公式可化为 Cotes系数与积分区间无关 仅与n和k有关 表Cotes系数 n 1 2 8 下面列出两个低阶Newton Cotes公式及其余项 Cotes系数为 求积公式为 称为梯形求积公式 或两点公式 梯形求积公式及其余项 积分中值定理 连续 可积不变号 故 梯形公式的余项为 几何意义 直边梯形代替曲边梯形 Cotes系数为 求积公式为 抛物线 Simpson 求积公式及其余项 上式称为Simpson求积公式 也称三点公式或抛物线公式 即 几何意义 Simpson公式的余项为 例 解 复化梯形求积公式 将 a b 分成n个小区间 在每个区间上用梯形求积公式 再将n个小区间上的数值积分累加起来 就得到区间 a b 上的数值积