数值分析期末复习总结.pdf

1 绝对误差 绝对误差 绝对误差绝对误差 exx x 精确值精确值 x 近似值近似值 则称则称 为为绝对误差限绝对误差限 误差限误差限 若存在一个正数若存在一个正数 使得 使得 工程上通常记为 工程上通常记为 x x e x x 1 绝对误差绝对误差可能取正 也可能取负可能取正 也可能取负 绝对误差绝对误差越小越具有参考价值越小越具有参考价值 但但绝对误差绝对误差却不能很好地表示近似值的精确程度却不能很好地表示近似值的精确程度 相对误差相对误差 相对误差 相对误差 x x er x 若存在正数若存在正数 r 使得 使得 er r 则称 则称 r 为为相对误差限相对误差限 由于真值难以求出 通常也使用下面的定义作为相对误差由于真值难以求出 通常也使用下面的定义作为相对误差 x x 2 er x 近似值的精确程度取决于近似值的精确程度取决于相对误差相对误差的大小的大小 实际计算中我们所能得到的是实际计算中我们所能得到的是误差限误差限或或相对误差限相对误差限 有效数字有效数字 有效数字 有效数字 若近似值若近似值x 的误差限是某一位的半个单的误差限是某一位的半个单 位位 即截取按四舍五入规则即截取按四舍五入规则 且该位到且该位到x 的第的第一一位非位非位位 即截取按四舍五入规则即截取按四舍五入规则 且该位到且该位到x的第位非的第位非 零数字共有零数字共有n位 则称位 则称x 有有n位有效数字位有效数字 10m 0 设设x 为为x的近似值 若的近似值 若x 可表示为可表示为 等价描述等价描述 3 x a1 a2 an 10m a1 0 且有且有 x x 0 5 10m n 1 则则x 有有 n 位有效数字位有效数字 有效数字有效数字 例 例 3 14159265 近似值 近似值 x1 3 1415 x2 3 1416 问问分别有几位有效数字分别有几位有效数字 问问 x1 x2分别有几位有效数字分别有几位有效数字 例 例 写出下列各数的具有写出下列各数的具有 5 位有效数字的近似值位有效数字的近似值 187 9325 0 03785551 2 7182828 8 000033 187 93 0 037856 2 7183 8 0000 4 注 注 注 注 0 23000 2300有有有有4 4位有效数字 而位有效数字 而位有效数字 而位有效数字 而0 230 23只有只有只有只有2 2位有效数字位有效数字位有效数字位有效数字 1230012300如果写成如果写成如果写成如果写成0 1230 123 10105 5 则表示只有 则表示只有 则表示只有 则表示只有3 3位有效数字 位有效数字 位有效数字 位有效数字 数字末尾的0不可以随意添加或省略 数字末尾的0不可以随意添加或省略 2 有效数字有效数字 定理 定理 设近似值设近似值 x 可表示为可表示为 x a1 a2 al 10m a1 0 12l 1 若若 x 具有具有 n 位有效数字 则其相对误差限满足位有效数字 则其相对误差限满足 1 r 2a1 10 n 1 5 反之 若反之 若 x 的的相对误差限相对误差限满足 则 满足 则 x 至少有至少有 n 位有效数字 位有效数字 1 r 2 a1 1 10 n 1 有效位数越多 相对误差限越小 有效位数越多 相对误差限越小 第二章 计算方法 第二章 插值法 6 插值基本概念插值基本概念 什么是插值 插值区间插值区间 已知函数已知函数y f x 在在 a b 上有定义 且已经测得在点上有定义 且已经测得在点 a x0 x1 xn b 处的函数值为处的函数值为y0 f x0 yn f xn 如果存在一个如果存在一个简单易算简单易算的函数的函数P x 使得 使得 P f i1 2 插值节点插值节点 插值节点插值节点无需递无需递 7 P xi f xi i 1 2 n 则称则称P x 为为f x 的的插值函数插值函数 求插值函数求插值函数P x 的方法就称为的方法就称为插值法插值法 插值节点插值节点无需递无需递 增排列增排列 但必须 确保 但必须 确保互不相同互不相同 插值条件插值条件 基函数插值法基函数插值法 基函数法 n 1 维线性空间维线性空间 通过基通过基函数来构造函数来构造插值多项式的方法插值多项式的方法就就称为称为基函数基函数插值插值法法 Zn x 次数不超过次数不超过n的多项式的全体的多项式的全体 记记 设设 z0 x z1 x zn x 构成构成Zn x 的一组基 则插值多项式的一组基 则插值多项式 P x a0z0 x a1z1 x anzn x 8 通过基通过基函数来构造函数来构造插值多项式的方法插值多项式的方法就就称为称为基函数基函数插值插值法法 寻找合适的基函数寻找合适的基函数 确定插值多项式在这组基下的表示系数确定插值多项式在这组基下的表示系数 基函数法基本步骤基函数法基本步骤 3 Lagrange插值插值 单项式单项式基函数 利用线性无关的单项式族利用线性无关的单项式族 2 1 n xxx Lagrange插值基函数 利用线性无关的单项式族利用线性无关的单项式族 1 xxx 构造构造 n 次多项式 次多项式 2 012 n n f xaa xa xa x 9 设设lk x 是是n次多项式 在插值节点次多项式 在插值节点x0 x1 xn上满足上满足 1 0 kj jk lx jk 则称则称lk x 为节点为节点x0 x1 xn上的上的拉格朗日插值基函数拉格朗日插值基函数 线性与抛物线插值线性与抛物线插值 两种特殊情形 n 1 01 10 01 101 0110 xxxx L xy lxy l xyy xxxx 线性插值多项式 一次插值多项式 线性插值多项式 一次插值多项式 n 2 10 n 2 020112 012 010210122021 xxxxxxxxxxxx yyy xxxxxxxxxxxx 抛物线插值多项式 二次插值多项式 抛物线插值多项式 二次插值多项式 2 Lx 插值举例插值举例 例 例 已知函数已知函数y lnx的函数值如下的函数值如下 x 0 40 50 60 70 8 解解 x lnx 0 9163 0 6931 0 5108 0 3567 0 2231 试分别用试分别用线性插值线性插值和和抛物线插值抛物线插值计算计算ln 0 54 的近似值的近似值 线性插值线性插值取取0 50 6 得得 为了减小截断误差 通常选取插值点为了减小截断误差 通常选取插值点x邻接的插值节点邻接的插值节点 11 线性插值线性插值 取取 x0 0 5 x1 0 6 得得 将将x 0 54代入可得 代入可得 01 101 0110 0 18231 6046 xxxx L xyyx xxxx ln 0 54 L1 0 54 0 6202 插值举例插值举例 抛物线插值抛物线插值 取取 x0 0 4 x1 0 5 x2 0 6 可得可得 l0 54L 0 54 0 6153 ex21 m ln 0 54 L2 0 54 0 6153 在实际计算中 不需要给出插值多项式的表达式在实际计算中 不需要给出插值多项式的表达式 ln 0 54 的精确值为 的精确值为 0 616186 见见抛物线插值的精度比线性插值要高抛物线插值的精度比线性插值要高 12 可可见见 抛物线插值的精度比线性插值要高抛物线插值的精度比线性插值要高 Lagrange插值多项式简单方便 只要取定节点就可写 出基函数 进而得到插值多项式 易于计算机实现 插值多项式简单方便 只要取定节点就可写 出基函数 进而得到插值多项式 易于计算机实现 4 Lagrange插值插值 lk x 的表达式的表达式 由构造法可得由构造法可得 011 011 1 kkn kkk k n j jj k k kn j kk xxxxx lx xxx xxxxxxxx xx xx 13 l0 x l1 x ln x 构成构成Zn x 的一组基的一组基 性质性质 注意注意 l0 x l1 x ln x 与插值节点有关 但与函数 与插值节点有关 但与函数f x 无关无关 误差估计误差估计 如何估计误差 xLxfxR nn 插值余项插值余项 定理定理 设设f x Cn a b n阶连续可微阶连续可微 且 且f n 1 x 在在 a b 内存在 则对内存在 则对 x a b 有 有 1 n f 14 1 1 1 n x nnn f Rxf xLxx n 其中其中 x a b 且与且与x有关有关 101 nn xxxxxxx 证明 证明 板书 板书 插值余项插值余项 几点说明 余项公式只有当余项公式只有当f x 的高阶导数存在时才能使用的高阶导数存在时才能使用 1 0 1 n n ni i M Rxxx n 如果 则如果 则 1 1 n n fxM x与与x有关 通常无法确定有关 通常无法确定 实际使用中通常是估计其上界实际使用中通常是估计其上界 15 计算插值点计算插值点x上的近似值时 应选取与上的近似值时 应选取与x相近插值节点相近插值节点 插值误差举例插值误差举例 例 例 已知函数已知函数y lnx的函数值如下的函数值如下 x 0 40 50 60 70 8 x lnx 0 9163 0 6931 0 5108 0 3567 0 2231 试估计试估计线性插值线性插值和和抛物线插值抛物线插值计算计算ln 0 54 的误差的误差 解解 线性插值线性插值 2 101 2 f R xxxxx 16 线性插值线性插值 2 2 4f 101 2 1 0 54 2 0 540 5 0 540 6 0 0048R x0 0 5 x1 0 6 0 5 0 6 5 Newton 插值插值 为什么 Newton 插值 Lagrange插值简单易用 但若要增加一个节点时 全部基函 数 插值简单易用 但若要增加一个节点时 全部基函 数lk x 都需重新计算 不太方便 都需重新计算 不太方便 设计个可以逐次生成插值多项式的算法设计个可以逐次生成插值多项式的算法即即次插值多项式次插值多项式 解决办法解决办法 17 设计设计一一个可以逐次生成插值多项式的算法个可以逐次生成插值多项式的算法 即即n次插值多项式次插值多项式 可以通过可以通过n 1次插值多项式生成次插值多项式生成 Newton 插值法插值法 新的基函数新的基函数 设插值节点为设插值节点为x0 xn 考虑插值基函数组 考虑插值基函数组 1x 0 10 201 011 1 nn x xxx xxxxx xxxxxxx 18 当增加一个节点当增加一个节点 xn 1 时 只需加上基函数时 只需加上基函数 1 0 n ni i xx Newton 插值插值 此时此时f x 的的 n 次插值多项式为次插值多项式为 1n 010201 0 nnk k pxaa xxaxxxxaxx 问题问题 如何从如何从 pn 1 x 得到得到 pn x 19 怎样确定参数怎样确定参数 a0 an 需要用到需要用到差商差商 均差 均差 差商差商 什么是差商 设函数设函数f x 节点 节点x0 xn ji ij ji f xf x f x x xx f x 关于点关于点xi xj的的一阶差商一阶差商 jkij ijk ki f xxf x x f x xx xx 20 f x 关于点关于点xi xj xk 的的二阶差商二阶差商 101 01 0 kk k k f xxf xx f xxx xx k 阶差商阶差商 差商的一般定义差商的一般定义 6 差商的性质差商的性质 k 阶差商与阶差商与k 阶导数之间的关系 阶导数之间的关系 若若f x 在在 a b 上 具有 上 具有k 阶导数 则至少存在一点阶导数 则至少存在一点 a b 使得使得 01 k k f f xxx k 21 差商的计算差商的计算 如何巧妙地计算差商 差商表差商表 xi xi 一阶 差商 二阶差商三阶差商一阶 差商 二阶差商三阶差商 n 阶差商阶差商 x0 x1 x0 x1 x0 x1 22 x1 x2 x3 xn x1 x2 x3 xn x0 x1 x1 x2 x2 x3 xn 1 xn x0 x1 x2 x1 x2 x3 xn 2 xn 1 xn x0 x1 x2 x3 xn 3 xn 2 xn 1 xn x0 x1 xn 差商举例差商举例 例 例 已知已知y x 的函数值表 试计算其各阶差商的函数值表 试计算其各阶差商 i0123 ex23 m i0123 xi 2 112 f xi 531721 解 解 差商表如下差商表如下 xi xi 一阶差商二阶差商三阶差商一阶差商二阶差商三阶差商 ex24 m 23 2 1 1 2 5 3 17 21 2 7 4 3 1 1 Newton 插值公式插值公式 Newton 插值公式 由差商的定义可得由差商的定义可得 000 f xf xxxf x x 1 101100 xxxfxxxxfxxf 2 0010nnnn xxxfxxxxfxxxf n 1 1 x x0 2 x x0 x xn 1 n 1 24 1 xx0 2 xx0 xxn 1 n 1 102100100 xxxxxxxfxxxxfxfxf 100 nn xxxxxxf 100nnn xxxxxxxxxf Nn x Rn x 7 Newton 插值公式插值公式 f x Nn x Rn x 1n 010201 1 ni i n aa xxaxxxxaxNxx Nn x 是是 n 次多项式次多项式 nixxfaxfa ii 2 1 000 其中其中 25 001 nnnn f x xxxRxxxxxx Nn xi f xi i 0 1 2 n重要性质重要性质 Nn x 是是f x 的的 n 次插值多项式次插值多项式 Newton Lagrange Newton 插值多项式与 Lagrange 插值多项式 f x 在在x0 x1 xn上上的的 n 次插值多项式是唯一的 次插值多项式是唯一的 Nn x Ln x 余项也相同余项也相同 26 1 0 00 1 n nn x nii ii f f x x xxxxx n 1 0 1 n x n f f x x x n 0 k f x xf k k 将将 x 看作节点看作节点 插值举例插值举例 例 例 已知函数已知函数y lnx的函数值如下的函数值如下 x0 40 50 60 70 8 插值节点无需递 增排列 但必须 确保互不相同 插值节点无需递 增排列 但必须 确保互不相同 解解 取节点取节点0 5 0 6 0 4 作差商表 试分别用 作差商表 试分别用牛顿牛顿线性插值和抛物线插值计算线性插值和抛物线插值计算ln 0 54 的近似值的近似值 x0 40 50 60 70 8 lnx 0 9163 0 6931 0 5108 0 3567 0 2231 xi xi 一阶差商 二阶差商一阶差商 二阶差商 0 5 0 6931 N1 x 0 6931 1 8230 x 0 5 27 0 6 0 4 0 5108 0 9163 1 8230 2 0275 2 0450 N1 x 0 6931 1 8230 x 0 5 N1 0 54 0 6202 N2 x 0 6931 1 8230 x 0 5 2 0450 x 0 5 x 0 6 N2 0 54 0 6153 ex25 m 第三章 计算方法 第三章 函数逼近与FFT 28 8 函数逼近函数逼近 三个问题三个问题 问题一问题一 已知一个函数的数值表已知一个函数的数值表 插值插值 数值逼近数值逼近 xx1x2 xn yy1y2 yn 能否找到一个能否找到一个简单易算简单易算的的 p x 使得 使得 p xi yi 问题二问题二 函数函数 f x 的表达式非常复杂 能否找到一个的表达式非常复杂 能否找到一个简简 29 单易算单易算的的 p x 使得 使得p x 是是 f x 的一个的一个合理的逼近合理的逼近 问题三问题三 问题一的表中的数值带有误差 能否找到一 个 问题一的表中的数值带有误差 能否找到一 个简单易算简单易算的的 p x 可以 可以近似地表示这些数据近似地表示这些数据 赋范线性空间赋范线性空间 赋范线性空间赋范线性空间 C a b 线性空间线性空间 C a b f x C a b 1 范数范数 1 d b a f xf xx 2 d b f xfxx 2 范数范数 30 2 d a f xfxx max a x b f xf x 2 范数范数 范数 范数 逼近标准逼近标准 度量度量 p x 与与 f x 的近似程度的常用两种标准的近似程度的常用两种标准 使尽可能地小使尽可能地小 maxxfxpfp bxa 使尽可能地小 使尽可能地小 2 1 2 2 b a dxxfxpfp 一致逼近一致逼近 31 平方逼近平方逼近 函数逼近函数逼近 记记Hn为所有次数不超过为所有次数不超过n的多项式的多项式 组成的集合组成的集合 给定函数给定函数f x C a b 若若P x Hn使得使得 最佳逼近最佳逼近 组成的集合组成的集合 给定函数给定函数f x C a b 若若 x n使得 使得 min n P H f xPxf xP x 则称则称P x 为为f x 在在C a b 上的上的最佳逼近多项式最佳逼近多项式 32 最佳一致逼近最佳一致逼近 min n P H f xPxf xP x 9 函数逼近函数逼近 最佳平方逼近最佳平方逼近 i ff 最小二乘拟合最小二乘拟合 给定给定 f x C a b 的数据表的数据表 xx0 x1 xn yyyy 22 min n P H f xPxf xP x 33 2 1 n ii i f xP x 寻找寻找 P x 使得下面的离散 使得下面的离散 2 范数最小范数最小 yy0y1 yn 正交多项式正交多项式 定义定义 设设 n x 是首项系数不为是首项系数不为0的的n次多项式 若次多项式 若 0 bjk 则称为则称为 a b 上带权上带权 x 正交正交 性质性质 1 设设是正交多项式族是正交多项式族H为所有次数不超过为所有次数不超过 0 0 jkjk a k j xxx dx Ajk 0 n n 称称 n x 为为n 次正交多项式次正交多项式 34 性质性质 1 设设是正交多项式族是正交多项式族 Hn为所有次数不超过为所有次数不超过 n的多项式组成的线性空间 则 构成 的多项式组成的线性空间 则 构成Hn的一组基的一组基 0 k k 012 n xxxx Legendre 多项式多项式 Legendre 多项式多项式 勒让德多式勒让德多式 2 0 1d P 1 P 1 2 d n n nnn xxx nx 在在 1 1 上带权上带权 x 1的正交多项式称为的正交多项式称为勒让德多勒让德多项项式式 x 1 1 n 1 2 记号 记号 P0 P1 P2 35 Pn x 的首项的首项xn 的系数为 的系数为 2 2 21 1 2 2 2 nn nnnn nn 则是则是首项系数为首项系数为 1的勒让德多项式的勒让德多项式 2 P 1 2 n n n n nd xx ndx P n x 令令 Legendre多项式多项式 1 0 xP xxP 1 11 1 P 21 P P nnn nxnxxnx 其中其中P0 x 1 P1 x x 2 13 2 2 xxP 2 35 3 3 xxxP 8 33035 24 4 xxxP 8 157063 35 xxxxP 36 8 157063 5 xxxxP ex31 m 10 Chebyshev 多项式多项式 Chebyshev 多项式多项式 夫多式夫多式 2 1 1 x x 在在 1 1 上带权上带权 x 的正交多项式称为的正交多项式称为切比雪切比雪夫多夫多项项式式 x 1 1 n 0 1 2 xnxTnarccoscos 切比雪夫多项式的表达式切比雪夫多项式的表达式 37 x 1 1 n 0 1 2 令令x cos 则 则 Tn x cos n 展开后即得 展开后即得 222444 2224422 coscossincossin 1 1 nnn nnn nnn nn T xCC xC xxC xx Chebyshev多项式多项式 1 0 xT xxT 1 2 2 11 xTxxTxT nnn 12 2 2 xxT xxxT34 3 3 188 24 4 xxxT xxxxT52016 35 38 xxxxT52016 5 ex32 m Chebyshev 零点插值多项式零点插值多项式 Chebyshev 插值插值 以以Chebyshev 多项式的多项式的零点零点作为作为插值节点插值节点进行插值进行插值 好处 好处 误差最小误差最小 定理定理 设设f x Cn 1 1 1 插值节点 插值节点x0 x1 xn 为为Tn 1 x 的的n 1个零点 则个零点 则 21 cos 2 1 k k x n 39 min n n p Hx f xL xf xp x 1 1 2 1 n n n f xL xfx n 且且 最佳平方逼近最佳平方逼近 设设 f x C a b 0 x 1 x n x C a b 线性 无关 令 线性 无关 令 01 span n 求求 S x 使得使得 22 22 min s f xSxf xS x S 称为称为 f 在在 中的中的最佳平方逼近函数最佳平方逼近函数 40 S x 称为称为 f x 在在 中的中的最佳平方逼近函数最佳平方逼近函数 其中其中 2 2 2 d b a f xS xfS xf fS xS xx 11 最佳平方逼近最佳平方逼近 如何求如何求 S x 对任意对任意S x 可设可设 S x a0 0 a1 1 an n x 则求则求S x 等价于求下面的多元函数的最小值点等价于求下面的多元函数的最小值点 2 01 d n b njj I a aaxf xaxx 41 01 0 njj a j f 0 k I a k 0 1 n 最佳平方逼近最佳平方逼近 0 2 d0 n b jjk a j k I xf xaxxx a 即即 1 d d n bb jjkk aa j axxxxx f xxx k 0 1 n 0 n jkjk j af 42 0001000 1011111 0 n n nnnnnnn ad ad ad kk df 法方程法方程 G 求求在在 0 1 上的次最佳平方逼近多项式上的次最佳平方逼近多项式 举例举例 例 例 教材教材68页 例页 例 6 2 1f 求求在在 0 1 上的上的一一次最佳平方逼近多项式次最佳平方逼近多项式 2 1f xx 解 解 1 2 00 0 1 1 d1 147dffxx 1 2 11 0 1 d0 609dfx fxxx 00 11 2 1 21 3 ad d 01 0 934 0 426aa 43 11 1 21 3ad S x 0 934 0 426 x 22 22 0 0 0026 n jj j xf xaf 0 066x 最佳平方逼近多项式最佳平方逼近多项式 n次最佳平方逼近多项式次最佳平方逼近多项式 f x C a b 在在 Hn中的最佳平方逼近 记为中的最佳平方逼近 记为 取取 Hn的一组基 的一组基 1 x x2 xn 则法方程为 则法方程为 11 1 2n 00 ad Hilbert 矩阵矩阵 n S 44 2 111 231 111 12 n n nnn 11 nn ad ad H H 严重病态 只适合求低 次最佳逼近 严重病态 只适合求低 次最佳逼近 12 正交函数作逼近正交函数作逼近 若若 0 1 n 正交 则法方程的解为正交 则法方程的解为 k k kk f a kk 所以所以k 0 1 n 01 01 0011 n n nn fff Sxxxx 误误差差 2 22 n k f 45 误误 22 22 0 k k kk f xf x 2 2 2 0 n k k kk f f x Bessel 不等式不等式 曲线拟合曲线拟合 已知已知f x 在某些点的函数值 在某些点的函数值 xx0 x1 xm f x y0y1 ym 能否找到一个简单易算的能否找到一个简单易算的p x 使得 使得f x p x f 但是但是 1 m 通常很大通常很大 2 yi本身是测量值 不准确 即本身是测量值 不准确 即 yi f xi 这时不要求这时不要求而只要而只要 46 这时不要求这时不要求 p xi yi 而只要而只要 p xi yi 总体上尽可能小总体上尽可能小 曲线拟合曲线拟合 p xi yi 总体上尽可能小总体上尽可能小 常见做法常见做法 使最小使最小 使最小使最小 max 1 ii mi yxp m i ii yxp 1 常见做法常见做法 太复杂太复杂 不可导 求 解困难 不可导 求 解困难 47 使最小使最小 m i ii yxp 1 2 最小二乘法 最小二乘法 目前最好的多项式曲线拟合算法目前最好的多项式曲线拟合算法 最小二乘最小二乘 曲线拟合的最小二乘问题曲线拟合的最小二乘问题 已知函数值表已知函数值表 xi yi 在函数空间 在函数空间 中求中求S x 使得 使得 2 2 00 min mm iiiiii s x ii SxyS xy 其中其中 i是点是点xi处的权处的权 48 这个问题实质上是最佳平方逼近问题的这个问题实质上是最佳平方逼近问题的离散形式离散形式 可以将求连续函数的最佳平方逼近函数的方法直接用 于求解该问题 可以将求连续函数的最佳平方逼近函数的方法直接用 于求解该问题 其中其中 i是点是点xi处的权处的权 13 最小二乘求解最小二乘求解 对任意对任意S x span 0 1 n 可设可设 S x a0 0 a1 1 an n x 0 0 1 1n n 则求则求S x 等价于求下面的多元函数的最小值点等价于求下面的多元函数的最小值点 2 01 0 m niii i I a aaS xy 2 mn ijjii axy 49 00 ijjii ij 0 k I a k 0 1 n 最小值点最小值点 最小二乘求解最小二乘求解 n j kkkj fa 0 k 0 1 n 这里的内积是这里的内积是离散带权内积离散带权内积 即 即 0 m jkijiki i xx 0 m kiiki i ff xx 法方程法方程 50 0001000 1011111 0 n n nnnnnnn ad ad ad kk df 法方程法方程 G 最小二乘求解最小二乘求解 设法方程的解为 设法方程的解为 a0 a1 an 则则 S x a0 0 a1 1 an n x 结论结论 S x 是是 f x 在在 中的中的 最小二乘解最小二乘解 51 f 举例举例 最小二乘问题中 如何选择最小二乘问题中 如何选择数学模型数学模型很重要 即如何选取 函数空间 很重要 即如何选取 函数空间 span 0 1 n 通常需要根据物理 通常需要根据物理p 0 1 n 意义 或所给数据的分布情况来选取合适的数学模型 意义 或所给数据的分布情况来选取合适的数学模型 52 14 多项式拟合多项式拟合 多项式最小二乘曲线拟合多项式最小二乘曲线拟合 Hn span 1 x xn 即即 i xi 则相应的法方程为则相应的法方程为 m i iii m i ii m i n ii m i ii m i ii m i n ii m i ii m i i fx f a a xxx xx 0 0 1 0 0 1 0 2 0 000 53 m i i n ii n m i n ii m i n ii m i n ii fx a xxx 00 2 0 1 0 此时为此时为f x 的的 n 次最小二乘次最小二乘拟合多项式拟合多项式 0 n k k k Sxa x 举例举例 例 例 求下面数据表的二次最小二乘拟合多项式求下面数据表的二次最小二乘拟合多项式 xi 00 250 500 751 00 f 1 00001 28401 64872 11702 7183 得法方程得法方程 4015 4 4514 5 7680 8 3828 15625 1875 1 5625 1875 15 2 875 15 25 2 1 0 a a a f xi 1 00001 28401 64872 11702 7183 解 解 设二次拟合多项式为 设二次拟合多项式为 2 2102 xaxaaxp 解得解得8437 0 8641 0 0052 1 210 aaa 54 解得解得8437 0 8641 0 0052 1 210 aaa 所以此组数据的二次最小二乘拟合多项式为所以此组数据的二次最小二乘拟合多项式为 2 2 8437 08641 00052 1 xxxp 1 若题目中没有给出各点的权值若题目中没有给出各点的权值 i 默认为 默认为 i 1 2 该方法不适合该方法不适合n较大时的情形 病态问题 较大时的情形 病态问题 第四章 计算方法 第四章 数值积分与数值微分 55 数值积分数值积分 d b I ff xx a ff 微积分基本公式 微积分基本公式 b a aFbFxxf d 但是在许多实际计算问题中但是在许多实际计算问题中 1 F x 表达式较复杂表达式较复杂时时计算较困难计算较困难如如 1 f x 56 3 f x 表达式未知表达式未知 只有通过测量或实验得来的数据表 只有通过测量或实验得来的数据表 2 F x 难求 难求 甚至有时不能用初等函数表示 如 甚至有时不能用初等函数表示 如 21 sin x f xxe x 1 F x 表达式较复杂表达式较复杂时时 计算较困难计算较困难 如如 6 1 f x x 15 几个简单公式几个简单公式 d b a f xxba f 基本思想 基本思想 a b 矩形公式矩形公式 d b a f xxba f a d 2 b a ab f xxba f d b a f xxba f b 57 梯形公式梯形公式 1 d 2 b a f xxbaf af b 抛物线公式抛物线公式 1 d 4 62 b a ab f xxbaf aff b 一般形式一般形式 数值积分公式的一般形式数值积分公式的一般形式 般地般地用用f 在在 b 上的些离散点上的些离散点 0 d n b ii a i f xxA f x 机械求积方法机械求积方法 一一般地般地 用用f x 在在 a b 上的上的一一些离散点些离散点 a x0 x1 xn b 上的函数值的加权平均作为上的函数值的加权平均作为f 的近似值 可得的近似值 可得 58 求积节点求积节点求积系数求积系数 将定积分计算转化成被积函数的将定积分计算转化成被积函数的函数值函数值的计算的计算 无需求原函数无需求原函数 易于计算机实现易于计算机实现 代数精度代数精度 定义定义 如果对于所有次数不超过 如果对于所有次数不超过m 的多项式的多项式f x 公式 公式 d n b ii f xxA f x 精确成立 但对某个次数为精确成立 但对某个次数为m 1的多项式不精确成立 则称 该求积公式具有 的多项式不精确成立 则称 该求积公式具有m 次代数精度次代数精度 0 ii a i ff 将将f x 1 x x2xm 依次代入依次代入 公式精确成立公式精确成立 代数精度的验证方法代数精度的验证方法 59 将将f x 1 x x x依次代入依次代入 公式精确成立公式精确成立 但对但对f x xm 1 不精确成立 即 不精确成立 即 22 11 0 d 2 mmn b mm ii a i ba A xxx m k 0 1 m 11 0 d 1 kkn b kk ii a i ba A xxx k 举例举例 例 例 试确定系数试确定系数Ai 使得下面的求积公式具有尽可能高的 代数精度 并求出此求积公式的代数精度 使得下面的求积公式具有尽可能高的 代数精度 并求出此求积公式的代数精度 1 012 1 d 1 0 1 f xxA fA fA f 解 解 将 将f x 1 x x2 代入求积公式 使其精确成立 可得代入求积公式 使其精确成立 可得 11 012 22 02 33 02 12 20 32 3 AAAba AAba AAba 60 02 解得解得A0 1 3 A1 4 3 A2 1 3 所以求积公式为 所以求积公式为 3 1 0 4 1 d 1 1 fffxxf 易验证该公式对易验证该公式对f x x3 也精确成立 但对也精确成立 但对f x x4 不精 确成立 所以此求积公式具有 不精 确成立 所以此求积公式具有3 次代数精度 次代数精度 16 插值型求积公式插值型求积公式 设求积节点为 设求积节点为 a x0 x1 0 总存在一算子范数总存在一算子范数 使得 使得 A 稳定性理论分析稳定性理论分析 理论分析 理论分析 1 由于右端项的扰动而引起的解的变化 1 由于右端项的扰动而引起的解的变化 bbxxA 设设 1 bAx bAx 1 又又 xAb 1 b b AA x x 2 由于系数矩阵的扰动而引起的解的变化 2 由于系数矩阵的扰动而引起的解的变化 92 bxxAA 设设 1 xxAAx 1 xxAAx 1 A A AA xx x Ax b的的条件数 矩阵矩阵A的的条件数 24 稳定性理论分析稳定性理论分析 定理 定理 考虑线性方程组考虑线性方程组Ax b 设 设b是精确的 是精确的 A 有有微小微小的变化的变化 A 此时的解为 此时的解为x x 则 则 A 1 1 1 A xA AA A x A A A 当当 A充分小时 不等式右端约为充分小时 不等式右端约为 1 A A A A 93 证明 证明 bxxAA 设设 11 xAAxxAAxx 1 xxAAx 结论结论 矩阵条件数矩阵条件数 条件数与范数有关条件数与范数有关常用的有常用的有无穷范数无穷范数和和2范数范数 1 Cond AAA 条件数与范数有关条件数与范数有关 常用的有常用的有无穷范数无穷范数和和2 范数范数 1 Cond AAA 1 2 2 2 Cond AAA 94 Cond A 2称为称为谱条件数谱条件数 当 当A对称时有对称时有 1 1 2 2 2 1 max Cond min i i n i i n AAA 举例举例 例 例 计算计算Cond A 和和Cond A 2 11 11 0001 A 11 0001 解 解 Cond A A 1 A 4 104 1 1000110000 1000010000 A 95 2 2 00012 00010 0004 0 2 A Cond A 2 max min 4 104 A对称 且对称 且 第六章 计算方法 第六章 线性方程组的迭代解法 96 25 矩阵分裂迭代法矩阵分裂迭代法 矩阵分裂迭代法基本思想矩阵分裂迭代法基本思想 A MN A的一个 矩阵分裂 的一个 矩阵分裂 Ax b 给定一个初始向量给定一个初始向量x 0 可得可得迭代格式迭代格式 11 xM NxM b A M N Mx Nx b M 非奇异非奇异 97 1 kk xBxf k 0 1 2 给定一个初始向量给定一个初始向量x 0 可得可得迭代格式迭代格式 其中其中B M 1N称为称为迭代矩阵迭代矩阵 收敛性分析收敛性分析 1 kk xBxf 基本收 敛定理 基本收 敛定理 定理定理 对任意初始向量对任意初始向量x 0 上述迭代格式收敛的充要条件是 上述迭代格式收敛的充要条件是 1B 证明 板书证明 板书 定理定理 若存在算子范数若存在算子范数 使得 使得 B 1 对任意的初始向量 对任意的初始向量 上述迭代格式收敛上述迭代格式收敛 98 x 0 上述迭代格式收敛上述迭代格式收敛 例例 考虑迭代法考虑迭代法x k 1 Bx k f的收敛性 其中的收敛性 其中 0 90 0 30 8 B 充分条件充分条件 Jacobi 迭代迭代 考虑线性方程组考虑线性方程组 Ax bAx b 其中其中A aij n n非奇异 且对角线元素全不为非奇异 且对角线元素全不为0 1122 diag nn Daaa 将将A分裂成分裂成A D L U 其中 其中 99 21 1 1 0 0 0 nn n a L aa 121 1 0 0 0 n nn aa U a Jacobi 迭代迭代 Jacobi 迭代迭代 1 1 1 kk xDLU xD b k 0 1 2 令令M D N L U 可得 可得 雅可比雅可比 Jacobi 迭代方法迭代方法 迭代矩阵记为 迭代矩阵记为 1 JDLU 100 分量形式 分量形式 1 1 11 in k iiijjijjii jj i xba xa xa i 1 2 n k 0 1 2 26 Gauss Seidel 迭代迭代 1 11122133111 1 22211233222 kkkk nn kkkk nn xba xa xa xa xba xa xa xa 在计算时 如果用代替 则可能会得到更好的收敛效果 在计算时 如果用代替 则可能会得到更好的收敛效果 1 k i x 1 1 11 kk i xx 11 kk i xx 1 1122 11 kkkk nnnnn nnnn xba xa xaxa 1 kkkk b 101 1 11122133111 1 1 22211233222 1 1 1 1 1122 11 kkkk nn kkkk nn kkkk nnnnn nnnn xba xa xa xa xba xa xa xa xba xa xaxa Gauss Seidel 迭代迭代 1 1 1 kkk xDbLxUx 写成矩阵形式写成矩阵形式 此迭代方法称为此迭代方法称为 高斯高斯 塞德尔塞德尔 Gauss Seidel 迭代法迭代法 k 0 1 2 11 1 kk xDLUxDLb 可得可得 102 1 GDLU 迭代矩阵记为 迭代矩阵记为 11 1 111 kk kkk xDLDLA xDLb IDLA xDLbxDLbAx SOR 迭代迭代 在在G S 迭代中迭代中 1 1 1 11 11 11 kkkkk iiii iii iii nnii xba xaxaxa xa 为了得到更好的收敛效果 可在修正项前乘以一个为了得到更好的收敛效果 可在修正项前乘以一个松弛因子松弛因子 于是可得迭代格式 于是可得迭代格式 1 1 1 in kk iijjijjii jj i k i ba xa xax 103 1 1 1 1 in kk iijjijjii j k ii j i k ba xaaxxx 1 1 1 11 1 in kk iijjijjii jj k i k ii ba xaxa xx SOR 迭代迭代 1 1 1 kkkkk xxDbLxUxDx 写成矩阵形式写成矩阵形式 xxDbLxUxDx 11 1 1 kk xDLDU xDLb 可得可得 SOR Successive Over Relaxation 迭代方法迭代方法 104 1 1 LDLDU 迭代矩阵记为 迭代矩阵记为 SOR 的优点的优点 通过选取合适的 通过选取合适的 可获得更快的收敛速度 可获得更快的收敛速度 SOR 的缺点的缺点 最优参数 最优参数 的选取比较困难的选取比较困难 27 迭代收敛迭代收敛充充条件条件 收敛性收敛性 收敛性定理收敛性定理 Jacobi 迭代收敛迭代收敛的的充充要要条件条件 J 1 G S 迭代收敛的迭代收敛的充要充要条件条件 G 1 SOR 迭代收敛的迭代收敛的充要充要条件条件 L 1 Jacobi 迭代收敛的迭代收敛的充分充分条件条件 J 1 G S迭代收敛的迭代收敛的充分充分条件条件 G 1 105 G S 迭代收敛的迭代收敛的充分充分条件条件 G 1 SOR 迭代收敛的迭代收敛的充分充分条件条件 L 1 Jacobi G S 收敛性收敛性 定理定理 若若A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优 则 则A 非奇异非奇异 定理定理 若若A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优 则 则Jacobi 迭 代和 迭 代和G S 迭代均收敛迭代均收敛 定理定理 若若A对称对称且对角线元素均大于且对角线元素均大于0则则 106 定理定理 若若A 对称对称 且对角线元素均大于且对角线元素均大于0 则则 1 Jacobi 迭代收敛的充要条件是迭代收敛的充要条件是A 与与2D A 均正定 均正定 2 G S 迭代收敛的充要条件是迭代收敛的充要条件是A 正定 正定 SOR 收敛性收敛性 SOR 收敛的必要条件收敛的必要条件 定理定理 若若SOR 迭代收敛 则迭代收敛 则0 2 定理定理 若若A对称正定 且对称正定 且0 2 则则SOR 迭代收敛 迭代收敛 SOR 收敛的充分条件收敛的充分条件 107 定理定理 若若A严格对角占优或不可弱约对角占优 且严格对角占优或不可弱约对角占优 且0 1 则则SOR 迭代收敛 迭代收敛 举例举例 例例 设 给出设 给出Jacobi 和和G S 收敛的充要条件收敛的充要条件 1 1 1 aa Aaa aa 解 解 A 对称 且对角线元素均大于对称 且对角线元素均大于0 故 故 1 Jacobi 收敛的充要条件是收敛的充要条件是A 和和2D A 均正定均正定 2 G S 收敛的充要条件是收敛的充要条件是A 正定正定 A正定正定 22 123 10 10 1 12 0DDaDaa 0 51a 108 0 51a 2D A正定正定 22 123 10 10 1 12 0DDaDaa 0 50 5a Jacobi 收敛的充要条件是 收敛的充要条件是 0 5 a 0 5 G S 收敛的充要条件是 收敛的充要条件是 0 5 a 1 28 举例举例 解法二 解法二 Jacobi 的迭代矩阵为的迭代矩阵为 0 0 0 aa Jaa aa 设设 是是J的特征值 则由的特征值 则由det I J 0 可得可得 a 2 2a 0 Jacobi 收敛的充要条件是收敛的充要条件是 J 1 1 即 即 0 5 a 0 5 109 收敛速度收敛速度 定义定义 迭代格式迭代格式x k 1 Bx k f的平均收敛速度为的平均收敛速度为 1 1 ln k k k R BB 渐进收敛速度为渐进收敛速度为 ln R BB 110 B 越小 收敛越快越小 收敛越快 第七章 计算方法 第七章 非线性方程 组 的数值解法 111 不动点迭代不动点迭代 基本思想基本思想 构造构造f x 0的的一一个等价方程个等价方程 xx 构造构造f x 0的个等价方程的个等价方程 xx x 的不动点的不动点 f x 0 x x 等价变换等价变换 f x 的零点的零点 112 29 不动点迭代不动点迭代 具体过程具体过程 任取任取一一个迭代初始值个迭代初始值x计算计算 任取个迭代初始值任取个迭代初始值x0 计算计算 得到一个迭代序列 得到一个迭代序列 x0 x1 x2 xn 1 kk xx k 0 1 2 113 几何含义 几何含义 求曲线求曲线y x 与直线与直线y x的交点的交点 连续性分析连续性分析 设设 连续连续若若收敛收敛即即则则lim xx 收敛性分析收敛性分析 设设 x 连续连续 若若收敛收敛 即即 则则 1 limlim lim kkk kkk xxx lim k k xx 0