数值计算方法与算法.ppt

数值计算方法与算法 教学目标 掌握常用的数值计算方法掌握计算方法的数学原理学会选择恰当的计算方法学会使用流行的计算软件 教学计划 教材及参考 数值计算方法与算法 张韵华 奚梅成 陈效群编 科学出版社 2006 科学计算导论 MichaelT Heath著 张威 贺华 冷爱萍译 清华大学出版社 2005 数值计算方法解题指导 张韵华编 科学出版社 2003 网络教学资源 联系方式 教师 王新茂xinmao 理化大楼16 016 3607565助教 杨荣rongyang 136 15607693 第0章绪论 数学建模数值计算 实际问题数学问题近似解 什么是数值计算方法 什么是 好的 数值计算方法 误差小 误差分析耗时少 复杂度分析抗干扰 稳定性分析 误差的类型绝对误差 真实值 近似值相对误差 绝对误差 真实值误差的来源原始误差 截断误差 舍入误差 一些例子 计算地球的体积计算计算如何减小计算误差 选择好的算法 提高计算精度范数的定义满足非负性 齐次性 三角不等式的实函数 常用的向量范数常用的矩阵范数矩阵的谱半径例 计算矩阵的范数和谱半径 例 范数在误差估计中的应用 作业一 145页习题6第1 2题 作业二 利用公式编写两个计算ex的C程序 一个用单精度 另一个用双精度 令x 1 5 10 15 20 比较它们和库函数exp x 之间的运行时间和计算误差 思考如何减小误差 第1章插值 函数逼近用未知函数f x 的值构造近似函数 x 要求误差小 形式简单 容易计算 常用的函数逼近方法插值 xi yi i 0 1 n 拟合 x f x 尽可能小通常取 x a0 0 x an n x 其中 i x 为一组基函数 多项式插值给定平面上n 1个插值点 xi yi 构造n次多项式 x 满足 xi yi i 0 1 n 单项式插值 Lagrange插值 Newton插值 k阶差商 差商的性质以x0 xn为节点的n次插值多项式 x 的首项系数等于f x0 xn 证明 分别以x0 xn 1和x1 xn为节点构造n 1次插值多项式 1 x 和 2 x 则有对n用归纳法 f x0 xn 与x0 xn的顺序无关 误差估计 证明 设 则有n 2个零点 根据中值定理 存在于是 Hermite插值给定平面上n 1个插值点 xi yi mi 构造2n 1次多项式 x 满足 xi yi xi mi i 0 1 n 单项式基函数 Lagrange基函数 误差估计 证明 设 则有2n 3个零点 根据中值定理 存在于是 Runge现象 并非插值点取得越多越好 解决办法 分段插值 三次样条插值给定平面上n 1个插值点 xi yi 构造分段三次多项式 x 满足 xi yi x 可微 x 连续 作业一 习题1第2 4 6 8 10 12 14 16题 作业二 在半圆上随机选取10个点 构造插值多项式 画出函数图像 并比较3种插值方法的计算误差 作业三 思考3种插值系数之间的关系 比较3种插值方法的优缺点和应用范围 第2章数值微分和数值积分 数值微分差商法向前差商向后差商中心差商 插值法在x附近取点 xi f xi 构造插值多项式 样条法在x附近取点 xi f xi 构造样条函数 f x x 例 用中心差商公式计算f xi 例 用向后差商公式计算f 0 2 f 0 4 例 设xi x0 i h i 1 n 计算 xk 解 误差估计前后差商中心差商插值微分 数值积分插值法 若积分公式对任意m次多项式都取等号 则称积分公式具有至少m阶的代数精度 插值型积分公式的代数精度 n 当积分节点x0 xn给定时 代数精度 n的积分公式唯一 例 设xi a i h i 0 n h b a n 计算Newton Cotes积分解 特别 当n 1 2时 积分公式分别称为梯形公式Simpson公式 误差估计特别 梯形公式和Simpson公式的误差为代数精度 1代数精度 3 复化数值积分 梯形公式Simpson公式 Richardson外推法我们要计算假设则有比和更高的精度 误差估计 Romberg积分公式等分的梯形公式 瑕积分重积分Gauss Legendre积分 定理 假设满足则插值积分公式具有2n 1阶的代数精度 证明 课本21页性质1 3 若f x 为m次多项式 则f x0 xn x 为m n 1次多项式 求多项式空间在内积下的标准正交基 解法1 对任意基作Gram Schmidt正交化 解法2 对任意度量方阵作相合对角化 解法3 求解正交关系的线性方程组 解法4 Legendre多项式 作业一 习题2第1 11题 作业二 使用各种方法计算的值 其中0 x 1 要求误差 1e 9 第3章曲线拟合的最小二乘法 曲线拟合对区间I上的连续函数f 构造特定类型的函数 使 f 对离散数据序列 xi yi i 1 2 m 构造特定类型的函数 使 xi yi 最小二乘法求 使最小 求 使最小 多项式拟合其中是标准正交基 求使最小 奇异值分解Moore Penrose广义逆矛盾方程组的解 其他类型的离散数据拟合 作业一 习题3第1 5题 作业二 对下列数据 用最小二乘法求形如的经验公式 第4章非线性方程求根 问题求f x 0在区间 a b 内的实根求f x 0在x0附近的一个实根求f x 0在x0附近的一个复根求多项式f x 0的所有复根求非线性方程组的根方法用近似函数 x 的根逼近f x 的根 二分法已知f a f b 0则根在 b c 内 当 f c 或 b a 时 输出c 迭代步数 O log2 不动点当 x L 1时 xk 1 L xk 当 xn 1 xn 时 输出xn 迭代步数 O logL Lipschitz常数 线性收敛 Newton法 一阶Taylor展开 当 f xk 或 xk 1 xk 时 输出xk 1 迭代步数 O loglog 二次收敛 Newton法 p重根情形 用Newton迭代法求f z z3 2z 2的根 当初值分别位于红 蓝 绿色区域时 迭代收敛到三个根 当初值位于黑色区域时 迭代陷入死循环0 1 0 图片引自JohnHubbard DierkSchleicher ScottSutherland Howtofindallrootsofcomplexpolynomials Inventionesmathematicae146 1 33 2001 弦截法 线性插值 当 f xk 或 xk 1 xk 时 输出xk 1 迭代步数 O loglog 弦截法的收敛速度 Newton法解非线性方程组求的所有复根等价于求x1 xn使f t t x1 t xn 其他求根方法Brent 反插值x y Halley 二阶Taylor展开 Muller 二次插值 有理插值 作业一 习题4第1 3 5 7 8题 作业二 比较各种求根方法的优缺点 第5章解线性方程组的直接法 问题 求解n元线性方程组AX B 方法 速度 精度 存储 下三角方程组上三角方程组n n 1 2次加减法 n n 1 2次乘除法 Gauss消元法解一般方程组 2n3 3n2 5n 6次加减法 n3 3n2 n 3次乘除法 追赶法解三对角方程组3n 3次加减法 5n 4次乘除法 线性方程组解的精度矩阵条件数 Gauss消元法的实质是LU分解存在性 A的顺序主子式 0 唯一性 L1U1 L2U2 L1 1L2 U1U2 1对角精确度 A 1b的相对误差 L U b 的相对误差 cond L cond U Dolittle分解Courant分解 全 列 行主元分解LDLT分解 Cholesky分解 QR分解 SVD分解Givens旋转Householder反射 作业一 习题5第1 8题 1 作业二 计算100阶Hilbert矩阵H的逆矩阵A以及AH I的元素平方和 第6章解线性方程组的迭代法 Jacobi迭代Gauss Seidel迭代 迭代法解线性方程组AX BAXk 1 B C AXk B C称为Conditioner 满足 C 1或 C 1通常取C I A 1 其中 A 于是Xk 1 Xk 1 AXk B Jacobi迭代 D定理 A行对角优 或A列对角优 Jacobi迭代收敛 Gauss Seidel迭代 D L定理 A行对角优 或A列对角优 或A正定 Gauss Seidel迭代收敛 松弛迭代 w 1D L定理 松弛迭代收敛 0 w 2定理 A正定且0 w 2 松弛迭代收敛Newton迭代求A 1 Xk 1 2Xk XkAXk 作业一 145页习题3 6 7 作业二 用迭代法计算10阶Hilbert矩阵H的逆矩阵A以及AH I的元素平方和 第7章计算矩阵的特征值和特征向量 问题1 求复方阵的模最大 最小 特征值 方法 幂法 反幂法问题2 求复方阵的所有特征值 方法 QR迭代问题3 求Hermite方阵的所有特征值 方法 Jacobi方法 幂法当A只有一个模最大的特征值 max 并且x0与 max的特征向量amax不正交时当A的模最大的特征值都相同时 以上迭代仍然收敛 当A的模最大的特征值各不相同时 可以选取数s使A sI的模最大的特征值只有一个 当A恰有m个模最大的特征值时 有R的特征值就是A的模最大的特征值 反幂法当A只有一个模最小的特征值 min 并且x0与 min的特征向量amin不正交时计算A sI的模最小的特征值等价于计算A的最接近s的特征值 QR迭代利用QR分解 酉相似A为上三角 QR迭代的本质是幂法当时 QR迭代收敛 可对A sI作QR分解 加速收敛 Jacobi方法通过Givens旋转 逐渐减小非对角元 本质是2阶Hermite方阵的酉相似 Jacobi方法具有2阶收敛速度 复矩阵的奇异值分解A U V一般方法AHA VH 2V或AAH U 2UHQR迭代Jacobi方法计算2阶方阵的SVD 作业一 167页习题1 3 2 2 3 4 作业二 计算10阶Hilbert矩阵的正交相似标准形以及过渡矩阵 第8章常微分方程数值解 问题 求解一阶常微分方程的初值问题 解法 化微分方程为积分方程 Euler折线法向前Euler公式向后Euler公式Picard迭代中心Euler公式梯形公式改进的Euler公式 Runge Kutta方法选取 xi cij 使yr有最高精度p 即 Runge Kutta方法的误差估计设满足Lipschitz条件设满足初值误差截断误差整体误差 线性多步法 其中 t 为f t y t 的q次插值多项式 当xn xn q为插值节点时 称为显式Adams公式 当xn 1 xn 1 q为插值节点时 称为隐式Adams公式 一阶常微分方程组的初值问题 解法 同一阶常微分方程的初值问题 高阶常微分方程的初值问题解法 令化方程为 单步法 收敛性稳定性将 应用于方程y y 得yn 1 E h yn 当 E h 1时 称 绝对稳定