数值分析例题.ppt

数值分析 第一章绪论与误差分析 1绪论 数值分析的研究内容 2误差的来源和分类 3误差的表示 4误差的传播 5算法设计的若干原则 例1 3设x 2 18是由精确值x经过四舍五入得到的近似值 问x的绝对误差限 和相对误差限 各是多少 解 因为x x 0 005 关于近似数误差的大小除了用绝对误差 相对误差度量以外 还可以用有效数字度量 下面给出有效数字的概念 所以绝对误差限为 0 005 相对误差限为 三 有效数字 一个数的近似数往往是通过四舍五入的原则求得 例如 取以下近似数 可以发现每一个近似数的绝对误差限都不超过近似数末尾数位的半个单位 如果一个近似数满足这个条件 就把这个近似数从末尾到第一位非零数字之间的所有数字叫做有效数字 则分别得到这些近似数的绝对误差 结论 通过四舍五入原则求得的近似数 其有效数字就是从末尾到第一位非零数字之间的所有数字 则称近似数x 具有n位有效数字 定义1 3设数x的近似值可以表示为 其中m是整数 i i 1 2 n 是0到9中的一个数字 而 1 0 如果其绝对误差限为 例如近似数x 2 0004 其绝对误差限为 由科学计数法x 0 20004 101得到 故 该近似数有五位有效数字 是末尾数位的半个单位 即由四舍五入得来 小结 由科学计数法表示的数字 若其绝对误差限满足不等式 则有n位有效数字 例1 4下列近似数是通过四舍五入的方法得到的 试判定它们各有几位有效数字 解 我们可以直接根据近似数来判断有效数字的位数 也可以通过绝对误差限来判断 有5位有效数字 同理可以写出 可以得出x2 x3 x4各具有4 3 4位有效数字 x1 87540 x2 8754 10 x3 0 00345 x4 0 3450 10 2 已知 例1 4已知e 2 718281828 试判断下面两个近似数各有几位有效数字 解 由于 而 所以 e1有7位有效数字 同理 e2只有6位有效数字 三 绝对误差 相对误差 有效数字的关系 2 绝对误差与有效数字的关系 得到 1 绝对误差与相对误差的关系 可以知道 有效数字位数越多 绝对误差限越小 由关系式 3 相对误差与有效数字的关系 由近似数 得到相对误差限 可以看出 有效数字位数越多 相对误差限越小 及 解 由于 则近似值x 可写为 例1 5为了使的近似值的相对误差小于10 3 问应取几位有效数字 根据 只要 即可 解得 n 4 故只要取n 4 就可满足要求 即应取4位有效数字 准确数为 此时x 4 472 练习1 1 判断下列近似数个有几位有效数字 用绝对误差限表示 注意 精确值的有效数字可以认为有无限多位 如 x1 24 67 x2 3850 103 x3 0 6742 10 2 x4 0 000374 x5 0 8400 习题一 1 1下列各数都是经过四舍五入得到的近似值 试分别指出它们的绝对误差限 相对误差限和有效数字的位数 a 0 0315 b 0 3015 c 31 50 d 5000 1 2下列近似值的绝对误差限都是0 005 a 1 00031 b 0 042 c 0 00032试指出它们有几位有效数字 1 3为了使的近似值的相对误差小于0 01 试问应取几位有效数字 1 4求方程x2 56x 1 0的两个根 使它们至少具有四位有效数字 1 6设 假定g是精确的 而对时间t的测量有 0 1s的误差 证明 当t增大时 S的绝对误差增大而相对误差减小 1 5若取及初始值y0 28 按递推公式 计算y100 试估计y100有多大误差 第二章代数插值 1多项式插值问题 2Lagrange插值多项式 3差商及Newton插值多项式 4分段插值多项式 5三次样条 Spline 插值多项式 一 线性插值 n 1 求解L1 x a1x a0 使得f x L1 x x x0 x1 根据点斜式得到 如果令 则称l0 x l1 x 为一次插值多项式的基函数 这时 并称其为一次Lagrange插值多项式 f x L1 x y0l0 x y1l1 x 二 抛物线插值 n 2 求解L2 x a2x2 a1x a0 使得f x L2 x x x0 x2 关于二次多项式的构造采用如下方法 令 并由插值条件 得到 L2 x A x x1 x x2 B x x0 x x2 C x x0 x x1 L2 x0 y0 L2 x1 y1 L2 x2 y2 于是得到 则有 f x L2 x y0l0 x y1l1 x y2l2 x 如果令 并称其为二次Lagrange插值多项式 紧凑格式 则称l0 x l1 x l x 为二次插值多项式的基函数 这时 这样 就得到二次拉格朗日插值多项式的三种表示形式 紧凑格式 这样就得到在区间 a b 上关于f x 的近似计算式 基函数表示 3 x 表示式 下面给出n次拉格朗日插值多项式的构造 三 n次Lagrange插值多项式 已知n 1组离散数据 按照二次Lagrange插值多项式的构造方法 令 将插值条件Ln x0 y0代入 得到 同理 由插值条件Ln x1 y1 得到 对于误差估计式 当n 1时 于是 得到如下Lagrange插值多项式及其误差估计 这里f x Ln x Rn x 当f x Ln x 时 误差为Rn x 例2已知 分别用线性插值和二次插值计算sin0 3367 解 设 1 取x0 x1作线性插值 于是 关于误差 由 得到 2 取x0 x1 x2作二次插值 得到 关于误差 由 得到 本节 2 要点 掌握Lagrange插值多项式的构造方法及具体结构掌握Lagrange插值多项式误差分析方法和结果3 编写Lagrange插值多项式计算程序进行实际计算 练习 已知函数y f x 的如下离散数据 1 试用线性插值求函数在x 1 5处的近似值 2 试用二次插值求函数在x 1 5处的近似值 这个表达式给出了n 1阶差商与n 1阶导数之间的关系式 解 由差商与导数的关系式 得到 2 Newton插值多项式具有递推式 由 例4已知f x 的五组数据 1 0 2 2 3 12 4 42 5 116 求N4 x 如果再增加一个节点 6 282 求出N5 x 并计算N4 1 5 N5 1 5 解 先由前五组数据列差商表 10223124425116 2103074 41022 24 0 5 得到 如果 再增加一点 6 282 就在上表中增加一行计算差商 6282 166 46 8 1 0 1 由Newton公式的递推式得到 得到 练习题 已知离散数据 1 0 2 2 4 12 5 20 求三次Newton插值多项式 增加一点 6 70 后 再求出四次Newton插值多项式 关于离散数据 构造了lagrange插值多项式 Newton插值多项式 根据问题需要 有时还需要构造分段插值多项式 下面加以介绍 4 2分段线性插值 为了提高近似程度 可以考虑用分段线性插值来逼近原函数 设y f x 在节点a x0 x1 xn b处的函数值为yi f xi i 0 1 2 n 这时的插值函数为分段函数 在区间上的线性函数为 误差为 则有 令 可以按如下的方式考虑 关于整体误差 于是 当h 0时 分段线性插值S x 收敛于f x 值得注意的是 分段线性插值虽然有很好的收敛性质 但却不是光滑的 也就是说 S x 的导数不一定存在 若记则对任一x a b 都有 下面我们就考虑在节点处可导的插值多项式的构造 4 3分段Hermite插值 分段线性插值多项式S x 在插值区间 a b 上只能保证连续性 而不光滑 要想得到在插值区间上光滑的分段插值多项式 可采用分段Hermite插值 如果已知函数y f x 在节点a x0 x1 xn b处的函数值和导数值 则在小区间 xi 1 xi 上有四个插值条件 故能构造一个三次多项式Hi x 并称其为三次埃尔米特 Hermite 插值多项式 yk f xk yk f xk k 0 1 n yi 1 f xi 1 yi f xi y i 1 f xi 1 yi f xi 代入下式 得到 这样 便求出了分段三次Hermite插值多项式 关于误差 若f x 在 a b 具有4阶连续导数 可推得 其中 如果记 则有 即 关于整体误差 若f x C4 a b 则可按如下方式考虑 记 则有 于是 当h 0时 R x 0 说明分段三次Hermite插值H x 收敛于f x 本节 4 问题 2 分段线性插值有何优缺点 如何估计误差 4 如何分段线性插值算法的程序设计 1 何为高次插值的Runge现象 应如何避免 3 分段三次Hermite插值有何优缺点 如何估计误差 5 如何构造满足以下条件的插值多项式并估计误差 2 三次样条函数的定义 已知函数y f x 在节点a x0 x1 xn b处的函数值为 如果函数S x 满足条件 2 S x 在子区间 xi 1 xi 上是不超过三次的多项式 则称S x 是三次样条插值函数 3 S x 在 a b 具有二阶连续导数 yk f xk k 0 1 2 n 1 S xk yk k 0 1 2 n 常用的边界条件有以下几种 边界条件1m 边界条件2M 边界条件3 假定函数y f x 是以b a为周期的周期函数 这时要求S x 也是周期函数 即 这样我们便可以具体求出样条函数来 令 于是 得到 这样 我们只需要求出m0 m1 mn即可 边界条件1 这时方程 改写为 或者 表示为矩阵方程 2 4 由于 k k 1 方程 2 4 的系数矩阵是严格对角占优矩阵 方程 2 4 有惟一解 并可用追赶法求解 便得到三次样条函数 解出m0 m1 mn以后 代入下式 也就是 边界条件2 已知 故可以得到 将 与前面得到的方程组 结合 可以给出求解m0 m1 mn的方程组 求解此方程组 也可以求出三次样条函数 2 5 或者表示为矩阵方程 由第一个等式和第二个等式得到y0 yn m0 mn 边界条件3 周期边界条件 由第三个等式说明 令 得到 结合得到 与 将 表示为矩阵方程 2 6 其系数矩阵称作周期三对角矩阵 也是严格对角占优 因而方程组有唯一解 三次样条函数三转角算法的实现流程 Step1 输入节点x0 x1 xn 函数值y0 y1 yn 边界条件及x Step3 根据边界条件 求解相应的方程组得到m0 m1 mn Step2 计算 Step4 判断x xi 1 xi Step5 计算y si x Step6 输出y 例4已知函数y f x 的如下数据 试求其在区间 0 3 上的三次样条插值函数S x 解这里边界条件是 设 求得 已知 由方程组 及 得到方程组 解得 这样便求得 代入表达式 便得到所求的三次样条函数 本节 5 1 2 要点 什么是三次样条函数 三次样条函数的边界条件是如何给出的 三次样条函数的三转角算法是如何构造的 如何设计程序实现三转角算法 画出流程图 三对角线性方程组和一般线性方程组如何求解 完成P49习题2 12 2 13 2 三弯矩算法 只要求出在区间 xi 1 xi 上的三次多项式Si x i 1 2 n 并满足前面四类条件即可 在这里我们采用另一种方法进行求解 并称为三弯矩算法 加边界条件构成的三次样条函数为分段函数 a x0 x1 xn b yk f xk k 0 1 2 n 对于离散点及其上的函数值 方程组 2 6 的矩阵形式为 边界条件2 这说明 这时方程组 其中 边界条件1 矩阵形式为 边界条件3 由 得 矩阵形式为 针对三种边界条件求解相应的方程组 得到M0 M1 Mn后代入 就可以得到三次样条函数 并把以上算法称作三弯矩算法 例2 5求三次样条插值函数S x 满足自然边界条件 S x0 S xn 0 已知离散数据如下 解 已知M0 M4 0 先求出步长h1 0 05 h2 0 09 h3 0 06 h4 0 08 再计算 代入方程组 得到 解得M0 0 M1 1 8806 M2 0 8836 M3 1 0261 M4 0 代入 得到 5 3三次样条插值函数的误差估计 1 如果f x C a b 且划分的网格比 其中 一致有界 则当 时 S x 一致收敛于f x 2 如果f x C4 a b 且S x 满足边界条件I II 则 即h 0时 练习二 2 1当x 1 1 2时 f x 分别为0 3 4 求f x 的二次插值多项式p2 x 2 2设li x 是以xk x0 kh k 0 1 2 3为插值节点的3次插值基函数 求 2 3设l0 x l1 x ln x 是以x0 x1 xn为节点的n次Lagrange插值基函数 求证 1 2 2 4设f x C2 a b 且f a f b 0 其中 证明 2 5利用在x 100 121 144点的函数值 用插值方法求的近似值 并由误差公式给出误差界 同时与实际误差作比较 2 6在 4 x 4上给出f x ex的等距节点函数表 利用与距离最近的三点作二次插值作为的e2近似 使其误差不超过10 6 问函数表的步长应多少 2 7证明n阶差商有下列性质 1 若F x f x g x 则 F x0 x1 xn f x0 x1 xn g x0 x1 xn 2 若f x Pm m次多项式 m n则f x0 x1 xn 1 x Pm n 2 8f x x5 4x4 3x 1 求差商f 20 21 25 和f 20 21 26 2 9设f x x5 x3 1 取x0 1 x1 0 8 x2 0 x3 0 5 x4 1 试作出f x 关于x0 x1 x4的差商表 给出f x 关于x0 x1 x4的Newton插值多项式 并给出插值误差 2 11给定插值条件式f 0 0 f 1 1 f 2 0 f 3 1 分别求出边界条件为 或 的三次样条函数的分段表达式 2 10设f x x4 2x3 5 在区间 3 2 上对节点x0 3 x1 1 x2 1 x3 3 求出f x 的分段三次Hermite插值多项式在每个小区间 xi xi 1 的表达式及误差公式 第三章最佳逼近 函数的最佳平方逼近数据拟合的最小二乘法 求连续函数最佳平方逼近的步骤 1 给定 a b 上的连续函数f x 及子空间 3 求出法方程组的解c0 c1 cn 得到最佳平方逼近 4 求出误差 例3 1求在上的最佳平方逼近一次多项式 并估计误差 直接套用公式 解 设 则需要求解的方程组为 于是得到法方程组 解之得 最佳平方逼近一次多项式为 关于误差 由误差估计式 得到 在区间 1 1 上两两正交 试求f x ex在这个区间上的最佳平方逼近二次多项式 并给出误差估计 例3 2已知 根据基函数的正交性 得到 解 以作为基函数 设 从而求得 误差为 例3 3求f x arctanx在 0 1 上的最佳平方逼近二次多项式 并估计误差 解 设P2 x c0 c1x c2x2 则 需要写出法方程组 这时 法方程组为 解得 且 本节 2 小结 1 何为连续函数最佳平方逼近多项式 如何计算连续函数的最佳平方逼近n次多项式 3 如何估计最佳平方逼近n次多项式的误差 4 练习 试求函数f x 1 x在区间 1 3 上的最佳平方逼近一次多项式并估计误差 数据拟合的最小二乘法 经常由观察或测试可得到一组离散数据 这时可以考虑用最小二乘法进行数据拟合 给出逼近曲线y f x 其特点是 所求的逼近曲线不一定经过这些离散点 但却尽可能的靠近这些离散点 xi yi i 0 1 m 最小二乘拟合曲线 二 最小二乘法拟合曲线的步骤 第二步 根据图示 确定曲线所属的函数类型 例如多项式函数类 三角函数类 指数函数类 对数函数类等 假设所确定的函数类的基函数为 第一步 根据如下已知点的坐标 在坐标系里描点 则所求的函数可以表示为 只要确定了系数 就可以求出拟合曲线 第三步 对于其整体误差 所求的解应该使得上式达到极小 由极值原理应有 令 最后可以将法方程组表示为 其中 这样会更快的写出法方程组来 例如所求得最小二乘拟合函数为n次多项式 则 这时 误差 三 数值例子 例3 4根据如下离散数据拟合曲线并估计误差 解 step1 描点 step2 从图形可以看出拟合曲线近似的为一条抛物线 step3 根据基函数给出法方程组 基函数为 由 得到 即 又 求得 法方程组为 解得 求得拟合二次多项式函数 误差为 先计算出拟合函数值 得到 或者 最小二乘拟合曲线 解 在坐标轴描点 例3 5根据如下离散数据拟合曲线并估计误差 从离散点的图形上看不出原函数属于哪一类型 一般多采用多项式拟合 在此我们用二次多项式拟合 根据如下离散数据给出法方程组 这时 求得 得到法方程组 所求二次拟合曲线为 拟合曲线的平方偏差为 由 解得 最小二乘拟合曲线 例3 6对如下数据作形如y aebx的拟合曲线 解 由于函数集合 aebx a b R 不成为线性空间 因此直接作拟合曲线是困难的 在函数y aebx两端分别取对数得到 这时 需要将原函数表进行转换如下 令z lny A lna B b 则z A Bx lny lna bx 对z A Bx作线性拟合曲线 取 这时 得正则方程组 解得 于是有 拟合曲线为 最小二乘拟合曲线 例3 7利用最小二乘法解下列超定方程组 解 超定方程组很难得到一组值使得每一个方程都成立 一般情况下用尽量使每一个方程都成立的一组值作为超定方程的近似解 这时最小二乘法就可以用于解这类方程 采用最小二乘法 考虑如下的误差函数 关于法方程组的获得 可以用更简便的方法 先将方程组用矩阵表示 简化为 两边同乘以系数矩阵的转置矩阵 就得到所需要的法方程组 具体计算结果如下 与前面计算的法方程组相同 解值得最小二乘解 x1 0 3141x2 0 1333x3 0 0269 本节 3 问题 1 最小二乘法拟合曲线的步骤是什么 2 如何根据离散数据写出法方程组 3 最小二乘法拟合曲线的平方误差如何计算 4 确定经验公式中的参数 使之与下列数据拟合 解 该问题的求解 可以将其化为线性函数进行 由 得到 令 则 则 再令 函数值转化为 这时 法方程组的系数矩阵按下式计算 由 计算出 法方程组 解得c0 6 0631c1 0 0474c2 10 0748 利用 得到 最后得到 第四章数值微积分 Newton Cotes型求积公式复化求积公式Gauss型求积公式数值微分 抛物线公式n 2 梯形公式n 1 Cotes求积公式n 4 例4 1用梯形公式 Simpson公式和Cotes公式求积分 解 利用梯形公式 利用Simpson公式 得 利用Cotes公式得 而原积分为 相对而言 Cotes求积公式精度最高 梯形求积公式精度最低 例4 2用梯形公式和Simpson公式计算积分 解 由梯形公式得 由Simpson公式得 本节 1 要点 1 等距节点 Newton Cotes 的积分公式是如何构造的 2 N点等距节点的积分公式及其误差式怎么表示 3 如何由上式给出梯形公式 抛物线公式及其误差 4 问题 由上面例题可以看出 n越大 计算精度越高 那么继续增大n 是否精度继续提高呢 这里使用的是Lagrange插值逼近 有Runge现象 当然不是n越大越好 当n较大时 会出现数值不稳定 考虑到分段插值逼近的优越性 在本节方法的基础之上 给出精度高且数值稳定的新算法 复化求积公式 2 复化求积公式 类似于分段插值 为了减少数值积分的误差 把积分区间分成若干个小区间 在每个小区间上采用低阶数值积分公式 然后把这些小区间上的数值积分结果加起来作为函数在整个区间上的近似 这就是复化数值积分的思想 在区间 a b 上 取等距节点 又由定积分的区间可加性 有 由此 可以得到相应的复化梯形公式和复化抛物线公式 这时 即 则得到复化梯形公式及其误差 如果记 上式说明复化梯形公式是收敛的 利用误差估计式 可以对积分计算进行精度控制 从而确定出需要将积分区间多少等分 例如 如果我们需要将积分值的误差控制在 0范围内 只需要从 则有 解出中出 即可 例4 3用四点复化梯形公式计算 解 四点复化梯形公式就是将区间 0 1 三等分 如图 于是 而梯形公式的结果为 例4 4用复化梯形公式计算积分 应将区间 0 1 多少等分 才可以使其截断误差不超过 解 复化梯形公式的误差为 而 从而 令 于是 只要将区间至少68等分 就可以达到需要的精度要求 二 复化抛物线 Simpson 公式 已知定积分的抛物线公式及其误差为 如果对于积分 在每个小区间上都采用Simpson公式 则得到复化Simpson公式 于是 我们得到复化抛物线公式及其误差为 这时 做近似计算用 四点公式 n 3等分 的节点如 做误差限估计用 最后 总结出抛物线公式和复化抛物线公式 1 抛物线公式及其误差 2 复化抛物线公式及其误差 例4 5试利用函数的数据表 表4 1 分别用复化梯形公式 复化Simpson公式计算下列积分的近似值 表4 1数据表 也就是 解 两种复化公式分别计算如下 根据已知点的数据 需要用到九点复化梯形公式 以上两种算法对区间采用不同等分 计算量大体一致 定积分精确到小数点后七位的值是0 9460831 Simpson公式精度要高一些 对于复化抛物型公式 在这里n 4 步长 例4 6利用复化梯形公式和复化Simpson公式分别求下列定积分 若要使精度达到 10 6 问各需将区间 0 1 多少等分 解由于 从而 于是有 由复化梯形公式和复化Simpson公式的误差表示式 得到 根据上面的估计分别取 则只要 可分别解出 本节 3 小结 2 复化抛物线公式及其误差 1 复化梯形公式及其误差 3Gauss型求积公式 关于数值积分公式 除了用误差来分析其精确度以外 还可以用代数精度来判断其精度的高低 为了掌握这一方法 下面先给出代数精度的概念 一 代数精度 是区间 1 1 上关于权函数 x 1的正交多项式 即 三 常用的正交多项式 1 勒让德 Legendre 多项式 而且具有递推性质 2 契比晓夫 Chebyshev 多项式 是区间 1 1 上关于权函数的正交多项式 即 其首项系数为2n 1 具有下面的性质 2 Tn x 在 1 1 上具有n个零点 1 三项递推关系 这其实很容易由Tn x cos narccosx 计算出来 令 则有 3 Laguerre 拉盖尔 多项式 为区间 0 上关于权函数 x e x的正交多项式 即 而且Ln x 的首项系数为 1 n 具有性质 4 Hermite多项式 是区间 上关于权函数的正交多项式 即 而且Hn x 的首项系数为2n 具有性质 也就是说对于积分公式 如果我们取插值节点x1 x2 xn为关于权函数 x 正交多项式gn x 的零点 则所得到的求积公式可达到2n 1阶代数精度 这时称上面的公式为Gauss型求积公式 并称x1 x2 xn为Gauss点 下面给出构造Gauss型求积公式的步骤 第三步 求出求积公式的系数 第一步 给出关于权函数 x 正交多项式gn x 第四步 给出Gauus型求积公式并计算积分近似值 第二步 求出gn x 的n个零点 x1 x2 xn 对于积分 构造Gauss型求积公式的步骤如下 五几种常用Gauss型求积公式 1 Gauss Legendre 勒让德 求积公式 构造Gauss型求积公式除需要求出正交多项式外 还需求出正交多项式的零点和求积系数 当n 3时 这些工作均很困难 下面给出几种常用的Gauss型求积公式 关于定积分 权函数 x 1 已知Legendre多项式在 1 1 上关于 x 1正交 由Gauss型求积公式的构造 选Gauss点xk为n次Legendre多项式的零点 求积系数 Gauss Legendre求积公式中的各阶Gauss点及求积系数已经算出 使用时只需要查表即可 看下表 这时 Gauss型求积公式 称为Gauss Legendre求积公式 表4 1Gauss Legendre求积公式系数表 例4 7用具有5次代数精度的Gauss型求积公式计算 实际上 x1 0 7745966692 x2 0 x3 0 7745966692 于是由计算公式得到 A1 A3 0 5555555556 A2 0 8888888889 解 具有5次代数精度的Gauss型求积公式就是3点Gauss型求积公式 由表3 1得 可见相同个数节点的求积公式 Gauss型求积公式的精度要高 对于一般的区间 a b 上的积分 若采用等距节点x0 1 x1 0 x2 1的Simpson公式 则有 需要作变量替换 得到 即 例4 8用3点Gauss公式求积分的近似值 相比较 远比3点的Simpson公式的结果精确 2 Gauss Chebyshev求积公式 关于定积分 这时得到Gauss型求积公式 不难得求积系数 权函数为 而Chebyshev多项式在 1 1 上关于权函数正交 于是Gauss点xk为n次Chebyshev多项式的零点 注 可能是广义积分 称为Gauss Chebyshev求积公式 例4 9计算下列积分 解 用两点Gauss Chebyshev求积公式 得 3 Gauss Laguerre求积公式 权函数为 x e x 而Laguerre多项式在 0 上带权 x e x正交 于是选Gauss点为n次Laguerre多项式的零点 对应的求积系数为 称为Gauss Laguerre求积公式 故有Gauss型求积公式 Gauss Laguerre求积公式的Gauss点和求积系数见表4 2 关于定积分 表4 2Gauss 拉盖尔求积公式系数表 一般对积分 可改写为如下形式 Gauss Laguerre求积公式写为 4 Gauss Hermite求积公式 关于定积分 权函数为 而Hermite多项式在 上带权正交 于是选Gauss点为n次Hermite多项式的零点 对应的求积系数为 故有Gauss型求积公式 称为Gauss Hermite求积公式 其Gauss点及求积系数见表4 3 表4 3Gauss Hermite求积公式的求积系数表 例4 9分别用两点Gauss型求积公式计算下列积分 解 1 由Gauss 拉盖尔公式系数 节点表可以求得 2 由Gauss Hermite公式系数 节点表可以求得 3 由Gauss 拉盖尔公式系数 节点表可以求得 例4 10用两点Gauss型求积公式计算 解 先作变换 用两点Gauss Legendre求积公式 得到 如果用复化梯形公式计算 需要将 0 1 区间1024等分 准确值为0 946083 例4 11求Gauss型求积公式 解 由于上面的两点公式是Gauss型的 故应具有2n 1 2 2 1 3阶代数精度系数 这说明上式对于f x 1 x x2 x3精确成立 于是 我们将f x 1 x x2 x3逐一代入上式 得到一个非线性方程组 的系数A1 A2及节点x1 x2 解此非线性方程组 得到 从而 所求的两点Gauss型求积公式为 本节 4 问题 1 Gauss型求积公式是如何构造的 为什么n点Gauss型求积公式具有2n 1阶代数精度 2 Gauss型求积公式都有哪几种类型 如何查表计算 3 用两点Gauss型求积公式计算下列积分 4 实习题 编写Gauss型求积公式计算各种积分 4数值微分 用函数y f x 的离散数据 近似的求出函数在节点处的微分值 称作数值微分 一 Taylor展开法 为求出y f x 在某点x0处的导数值f x0 可以利用函数在此点以及前后两点的函数值 通过Taylor展式进行近似计算 xi yi i 0 1 2 n 例4 12对于函数y f x 在如下点的函数值 解 三种公式计算一阶导数值分别为 用二阶中心差分公式计算 上表数据表示的是由函数f x ex给出 其准确值为 可见 用一阶中心差商公式求一阶导数更准确一些 下面再看另一种求数值微分的方法 一阶两点微商公式 一阶三点微商公式 二阶三点微商公式 例4 13对于函数y f x 在如下点的函数值 试分别用两点 三点数值微分公式计算x 2 7处函数的一 二阶导数值 解 h 0 2时 或者 或者 h 0 1时 或者 或者 以上导数值均求的是函数f x ex在x 2 7处的一 二阶导数近似值 真值为 本节 6 问题 一阶两点微商公式 一阶三点微商公式 二阶三点微商公式 练习 已知y f x 的一组离散值 1 试用两点公式求出f x 在三点0 8 1 0 1 2的一阶导数 2 试用三点公式求出f x 在三点0 8 1 0 1 2的一阶导数 3 试用三点公式求出f x 在三点0 8 1 0 1 2的二阶导数 第四章数值微积分总结 Newton Cotes型求积公式1 梯形公式2 抛物线公式3 梯形公式 抛物线公式的误差二 复化型求积公式三 Gauss型求积公式四 数值微分 第五章线性方程组的直接解法 1Gauss消去法1 1顺序Gauss消去法1 2列主元Gauss消去法 2直接三角分解方法2 1Gauss消去法的矩阵运算2 2Doolittle分解法2 3平方根法2 4追赶法 一 顺序Gauss消去法 例1 用顺序Gauss消去法解方程组 用增广矩阵进行计算 对于 由 解得 对于 由 求得 可以看出对于方程组 只要对系数矩阵作了三角分解 由这个简单的计算过程可知 系数矩阵的三角分解很关键 从前面的分析我们可以总结出L和U的求法 但比较繁琐 下面介绍几种简单方法 通过如下两组公式很容易求解 前已述及 若在顺序Gauss消去法的过程中 每步消元的主元素akk k 0 则矩阵A可分解为A LU L为单位下三角矩阵 U为上三角矩阵 此分解称为A的Doolittle 杜利特尔 分解 可以证明akk k 0的充要条件是A的各阶顺序主子式不为零 于是有如下定理 定理5 1设n阶方阵A的各阶顺序主子式不为零 则存在惟一单位下三角矩阵L和上三角矩阵U使A LU 下面介绍矩阵三角分解的Doolittle分解方法 2直接三角分解方法 于是 对于矩阵的三角分解 可按照以下公式进行 对于i 2 3 n 计算 5 2 5 3 5 4 用计算公式 5 3 5 4 对矩阵A作的分解 5 2 称作Doolittle分解 例5 3利用Doolittle三角分解法求下列方程组 解 首先对系数矩阵用如下公式分解 1 2 3 4 1 1 1 2 6 12 3 7 6 24 6 24 所以A可以写成 L U 对方程组 则由 得到 由 解得 再由 求得方程组的解 例5 6用平方根法求解对称正定方程组 解 首先进行A的Cholesky分解 A LLT 2 0 5 0 5 2 1 5 1 得y1 2 y2 3 5 y3 1 得x1 1 x2 1 x3 1 求解Ly b 再求解LTx y 关于对称正定方程组 也可以用一般的三角分解法求解 这时由 4 114 0 25 0 25 4 3 7 0 75 1 1 求得x1 1 x2 1 x3 1 例5 7用追赶法求解三对角方程组 解 首先进行系数矩阵的三角分解 求解方程组Ly y 即 得到y1 1 2 y2 1 3 y3 1 4 y4 1 再求解方程组Ux y 即 得到x1 1 x2 1 x3 1 x4 1 第5章习题 5 1利用Gauss消去法解下列方程组Ax b 其中 1 2 5 2利用列主元Gauss消去法解下列方程组Ax b 其中 5 3对下列矩阵A进行LU分解 并求解方程组Ax b 其中 5 4对下列矩阵A进行LU分解 5 5对矩阵A进行LLT分解 并求解方程组Ax b 其中 5 6证明 用列主元Gauss消去法求解方程组Ax b相当于用Gauss消去法求解方程组PAx Pb 其中P是一个行排列矩阵 它是一些初等行变换矩阵的乘积矩阵 5 7用追赶法求解方程组 第六章线性方程组的迭代解法 1向量和矩阵的范数1 1向量的范数1 2矩阵的范数 2迭代解法与收敛性2 1迭代法的构造2 2迭代法的收敛性条件 3常用的三种迭代解法2 1Jacobi迭代法2 2Gauss Seidel迭代法2 2超松弛 SOR 迭代法 向量1 范数 向量2 范数 向量 范数 容易验证 以上三种范数都满足向量范数的三个条件 例6 1设向量x 1 3 2 0 T 求向量范数 x p P 1 2 解 对于向量x 1 3 2 0 T 根据定义可以计算出 x 1 1 3 2 0 6 由此例可见 向量不同范数的值不一定相同 但这并不影响对向量大小做定性的描述 因为不同范数之间存在如下等价关系 例6 2设矩阵 求矩阵A的范数 A p P 1 2 解根据定义 由于 则它的特征方程为 此方程的根为矩阵ATA的特征值 解得 因此 在线性方程组的研究中 经常遇到矩阵与向量的乘积运算 若将矩阵范数与向量范数关联起来 将给问题的分析带来许多方便 设 是一种向量范数 由此范数派生的矩阵范数定义为 注意 此式左端 A 表示矩阵范数 而右端是向量Ax和x的范数 利用向量范数所具有的性质不难验证 由上式定义的矩阵范数满足矩阵范数的条件 三 矩阵的谱半径 矩阵范数同矩阵特征值之间有密切的联系 设 是矩阵A相应于特征向量x的特征值 即Ax x 于是利用 向量 矩阵范数的相容性 得到 x x 从而 对A的任何特征值 均成立 Ax A x A 6 1 设n阶矩阵A的n个特征值为 1 2 n 称 为矩阵A的谱半径 从 6 1 式得知 对矩阵A的任何一种相容范数都有 A A 6 2 令Cond A A A 1 并称其为矩阵A的条件数 这时有 可见 求解线性方程组时由A b的误差所产生的误差与系数矩阵A的条件数有关 当条件数越大时 解得 1 A 1 A x A 1 A x 取 A 使得 A 1 A 1 则有 引起的误差越大 如果系数矩阵的条件数Cond A A A 1 太大 则称相应的方程组为病态方程组 此时方程组的解对扰动太敏感 病态现象是方程组的固有属性 无法改变 因此在求解时为了不至于产生太大的误差 应该尽量减少原始数据A b的误差 或者用高精度的计算机计算 例如 对于方程组 系数矩阵和逆矩阵分别为 可以求得 条件数比较大 可见该方程组为病态方程组 二 Gauss Seidel迭代法 对于三元方程组 将Jacobi迭代格式 改进为 并称其为Gauss Seidel G S 迭代格式 例6 3用Jacobi迭代法和Gauss Seidel迭代法解下列方程组 已知方程组得精确解为x 1 1 1 T 解 先改写方程如下 再写出Jacobi迭代格式 取初值为 x 0 0 0 0 T 求得 x 1 1 4 0 5 1 4 T x 6 1 00025 1 00580 1 00251 T 误差为由x 1 1 1 T得到 x 6 x 0 00580 初值也取为 x 0 0 0 0 T 求得近似解 Gauss Seidel迭代格式为 误差为由x 1 1 1 T得到 x 4 x 0 00846 Jacobi迭代法迭代6次与Gauss Seidel迭代法迭代4次的精度一致 说明Gauss Seidel迭代法收敛的较快 x 1 1 4 0 78 1 026 T x 4 0 99154 0 99578 1 00210 T 再通过加权加速收敛 并称其为超松弛迭代法 称为松弛因子 当0 1时 称为低松弛 当 1时 为Gauss Seidel迭代格式 当1 2时 称为高松弛 定理6 8SOR迭代法收敛的必要条件是0 2 定理6 9如果系数矩阵A对称正定 且0 2 则SOR法收敛 收敛性条件 四 例题分析 例6 4分别用Jacobi迭代法和Gauss Seidel迭代法解下列方程组是否收敛 可见系数矩阵严格对角占优 所以Jacobi迭代法和Gauss Seidel迭代法均收敛 第二个方程组的系数矩阵不是严格对角占优的 但可以交换两个方程的次序 将原方程变为同解方程组 这时方程组的系数矩阵严格对角占优 两种迭代法都收敛 解 第一个方程组的系数矩阵为 例6 5用Jacobi迭代法解下列方程组 问是否收敛 解 方程组的系数矩阵为 非严格对角占优 无法判断迭代法是否收敛 需要通过谱半径判断 先写出Jacobi迭代法的迭代矩阵 由于无穷范数 BJ 3 1 还无法判断迭代法是否收敛 这时只能通过求迭代矩阵的谱半径来判断 由迭代矩阵 解得特征值 谱半径 BJ 1 故Jacobi迭代法收敛 例6 6分别用Jacobi迭代法和Gauss Seidel迭代法解下列方程组 问是否收敛 由于该矩阵非严格对角占优 无法判断 但由于对称 再看是否正定 解 系数矩阵为 各阶顺序主子式 A1 1 A2 3 4 A3 1 2 说明矩阵对称正定所以Gauss Seidel迭代法收敛 但无法判断Jacobi迭代法是否收敛 再利用迭代矩阵的范数或者谱半径进行判断 由系数矩阵 写出Jacobi迭代矩阵 其 范数 BJ 1和1 范数 BJ 1 1 不小于1 还无法判断是否收敛 再求其谱半径进行判断 由det I BJ 0求得特征值 1 1 2 3 0 5 谱半径 BJ 1 1 由此可知Jacobi迭代法是发散的 例6 7取初值x 0 0 0 0 T用Jacobi迭代法解下列方程组 如果要保证各分量的误差的绝对值小于10 6 问需要迭代多少次 解 由于方程组得系数矩阵严格对角占优 所以Jacobi迭代法收敛 要确定迭代次数需要用到估计式 其中BJ E D 1A FJ D 1b 范数用 范数 由方程组得到系数矩阵和常数项 知迭代矩阵为 范数 BJ 1 3 1 FJ 1 5 x0 1 5 代入下式 得到 10 6 3k 1 750000 解得 k lg7500 lg3 8 12 故至少需要迭代9次 第6章复习小结 一 向量 矩阵的范数 矩阵的谱半径和条件数二 迭代格式的构造与收敛性条件三 常用的三种迭代法1 Jacobi迭代法2 Gauss Seidel迭代法3 超松弛 SOR 迭代法四 了解基本概念 掌握迭代算法的构造方法 收敛性条件以及编程计算 第6章习题 线性方程组的迭代解法 6 1对二维向量x x1 x2 T 画出由平面上点集 x 1 1 x 2 1 x 1所确定的几何图形 6 2证明下列不等式 1 x y x z z y 2 x y x y 6 3设 为一向量范数 P为非奇异矩阵 定义 x p Px 证明 p也是一种向量范数 6 4设A为对称正定矩阵 定义 证明 A也是一种向量范数 6 5证明范数的等价性 1 x x 2 x 2 x 2 x 1 x 2 3 A 2 A F A 2 6 6设 计算矩阵A的1 范数 2 范数 范数及相应的条件数Cond A 6 7试证明 1 如果A为正交矩阵 则Cond2 A 1 2 如果A为对称正定矩阵 则Cond2 A 1 n 1和 n分别为A的最大和最小特征值 第八章非线性方程的数值解 1二分法 2迭代法2 1迭代格式2 2收敛性条件2 3迭代法的收敛阶 3牛顿迭代法3 1迭代格式3 2迭代法的收敛阶 4弦割法 例8 1求方程x3 x 1 0在区间 1 1 5 内的实根 要求误差不超过0 005 解 令f x x3 x 1 则有f 1 1 f 1 5 0 875 且由f x 3x2 1 0 x 1 0 1 5 可知f x 0在 1 1 5 内有唯一实根x 这时f 1 f 1 5 0 我们采用二分法进行计算 每一次的计算结果由下表给出 f x x3 x 1 f 1 10 1 25 0 2969 1 25 1 5 1 375 0 2246 1 25 1 375 1 3125 0 0515 1 3125 1 375 1 3438 0 0828 1 3125 1 3438 1 3281 0 0145 1 3125 1 3281 1 3203 0 0188 1 320