计算方法第三章r.pdf

第三章第三章 插值法插值法 第一节第一节插值多项式的基本概念插值多项式的基本概念 假设已经获得若干点上的函数值假设已经获得若干点上的函数值 即提供了一张数据表即提供了一张数据表 如何如何利用这张表求某个给定点上的函数值利用这张表求某个给定点上的函数值呢呢 插值方插值方 法所要研究的就是这个课题 法所要研究的就是这个课题 0 1 ii f xy in x 0 x 1 x 2 x n x yf x 0 y 1 y 2 y n y 通常用多项式来作为近似函数 称为通常用多项式来作为近似函数 称为插值多项式插值多项式 2 012 n nn P xaa xa xa x 数据表中的函数值为已知的节点称为数据表中的函数值为已知的节点称为插值节点插值节点 插值节点上所 插值节点上所 给的函数值称为给的函数值称为样本值样本值 函数值待求的点称为 函数值待求的点称为插值点插值点 插值节 插值节 点所界定的范围称为点所界定的范围称为插值区间插值区间 如果所给插值点位于插值区间 如果所给插值点位于插值区间 之内 这种插值过程称为之内 这种插值过程称为内插内插 否则称为 否则称为外插外插 如果插值条件只是给出节点的函数值 称为如果插值条件只是给出节点的函数值 称为拉格朗日插值拉格朗日插值 如 如 果既有函数值也有节点处函数的导数值 称为果既有函数值也有节点处函数的导数值 称为埃尔米特插值埃尔米特插值 因式定理 多项式因式定理 多项式P x 具有具有r 次因式次因式 x a r 的充要条件的充要条件 是是P a P a P a r 1 0 最一般的插值条件 最一般的插值条件 是是重根 重根 1 1 ii rr iiiiii xyxyxy 定理 一旦插值条件给定 则插值多项式是唯一的 定理 一旦插值条件给定 则插值多项式是唯一的 i r i x 01 1 m rrrn 设函数设函数 y f x 在闭区间在闭区间 a b 上有上有n 1 阶导数 阶导数 满足前面的一般插值条件 且插值节点各不相同 满足前面的一般插值条件 且插值节点各不相同 则插值截断误差为则插值截断误差为 01 1 01 1 1 m n nnn rrr nm R xf xP xfx n xxxxxxx 01 01 1 m m rrrn x xxx 在之间 与 有关 证明思路 构造辅助函数 用罗尔定理 证明思路 构造辅助函数 用罗尔定理 33 4 2 012 1 4 R xf xP x fxxxxxx 300300311322 P xy P xy P xy P xy 2 3012 2 3012 g tf tP txxxxxx f tP txxxxxx 值得注意的是在较大区间上进行插值时 误差可能会值得注意的是在较大区间上进行插值时 误差可能会 很大 另外 一般情况下 外推不如内插好 很大 另外 一般情况下 外推不如内插好 第二节第二节 Lagrange插值公式插值公式 插值条件是插值条件是 0011 nn x yx yx y Lagrange插值实质上是求通过上面插值实质上是求通过上面 n 1 个点的个点的 n 次多项式 次多项式 一次插值 一次插值 问题为求一次多项式 即一次函数 过以下问题为求一次多项式 即一次函数 过以下 两点 两点 容易求出 该函数为 容易求出 该函数为 0011 x yx y 01 01 0110 xxxx yyy xxxx 二次插值 二次插值 问题为求二次多项式 即二次函数 过以下三点 问题为求二次多项式 即二次函数 过以下三点 容易求出 该函数为 容易求出 该函数为 001122 x yx yx y 12 0 0102 02 1 1012 01 2 2021 xxxx yy xxxx xxxx y xxxx xxxx y xxxx 一般插值问题 求过一般插值问题 求过n 1n 1个点个点 的不超过的不超过n n次多项式次多项式 称为称为LagrangeLagrange插值基函数 满足 插值基函数 满足 0011 nn x yx yx y n L x 0 n nii i L xy l x i l x 1 0 ijijij ij l x ij 011 011 iin i iiiiiin xxxxxxxx l x xxxxxxxx 问题问题 过过n 1n 1个点的个点的LagrangeLagrange插值多项插值多项 式是否唯一 式是否唯一 满足n 1个插值条件的n次多项式是唯一 的 满足n 1个插值条件的多项式不是唯一 的 插值公式的误差为 插值公式的误差为 1 01 1 nn n x n R xf xL x f xxxxxx n 1 1 1 01 max 1 n n xa b n nn Mfx M R xxxxxxx n 计算程序计算程序 框图框图 始 终 输入数据 x 及 0 1 ii x yin 0 0yi 计算权系数 i 存单元 中 in i yyy 1ii Lagrange 公式的计算流程 第三节第三节 逐次线性插值逐次线性插值 函数函数 y f x 在节点在节点上的插值多项上的插值多项 式记为式记为 则有 则有 ijk x xx i jk Nx i jk p qi jk p i jk qi jk p p qp NxL xNx NxNx xx xx Aitken 埃特肯 算法埃特肯 算法 Neville 列维尔 算法列维尔 算法 0 1 0 1 0 1 1 0 1 k pk kpk k pk NxL xNx NxNx xx xx 1 1 1 1 2 1 1 i iki ik iiki ik i ki NxL xNx NxNx xx xx Aitken 埃特肯 算法埃特肯 算法 0 x 0 N 1 x 1 N 0 1 Nx 2 x 2 N 0 2 Nx 0 1 2 Nx 3 x 3 N 0 3 Nx 0 1 3 Nx 0 1 2 3 Nx Neville 列维尔 算法列维尔 算法 0 x 0 N 1 x 1 N 0 1 Nx 2 x 2 N 1 2 Nx 0 1 2 Nx 3 x 3 N 2 3 Nx 1 2 3 Nx 0 1 2 3 Nx 例子 求方程例子 求方程在在 2 3 内的根内的根 思路 用反函数思路 用反函数 3 250 xx yx 163 122 058823 0 392 058232 0965892 095659 0 012 1 51E 5 2 095659 2 094553 2 0945292 0945542 094553 第四节第四节牛顿插值牛顿插值 001122 nn xfx fxfxf 010201 011 n nn Nxcc xxc xxxx xxxxxxc 差商差商 设函数设函数 f x 定义函数在两个不同点的一阶差商为定义函数在两个不同点的一阶差商为 三个不同点的二阶差商为 三个不同点的二阶差商为 在点在点处处 K 1 阶差商为 阶差商为 ij ijij ij f xf x f x xxxij xx ijjk ijk ik f x xf x x f x x x xx 011 kk x xx x 0111 011 01 kkk kk k f x xxf xxx f x xxx xx 给定给定 n 1个点的函数值 则牛顿插值公式为 个点的函数值 则牛顿插值公式为 0010 01201 01011 1 01011 0 1 2 iii n nn nn nn xff xin Nxf xf x xxx f x x xxxxx f x xxxxxxxx NxN f x xxxxxxxx 差商的计算简表 差商的计算简表 00 1101 2212012 33231230123 4434234123401234 x f x x f xf x x x f xf x xf x x x x f xf x xf x x xf x x x x x f xf x xf x x xf x x x xf x x x x x 例子 例子 用用0 30 45 60 90五个点作出五个点作出sinx 牛顿插值多项式 牛顿插值多项式 做差商表做差商表 00 300 50 016667 450 70710 013807 0 000063556 600 8660 010595 0 00010707 0 0000007 9010 0044658 0 0001362 0 00000049 牛顿插值的截断误差 牛顿插值的截断误差 1 01101 nn nn NxN f x xxxxxxxx 1111 01110111 nnnnn nnnnn f xNxNx f x xxxxxxxx 1 01101 nn nn f xNxNx f x xxxxxxxx 01101 nn nn R xf xNx f x xxxxxxxx 例子 例子 用用0 30 45 60 90五个点作出五个点作出sinx 牛顿插值多项式 牛顿插值多项式 做差商表做差商表 00 9010 01111 1800 0 01111 1 235e 4 270 1 0 0111104 572e 7 36000 011111 235e 44 572e 70 差商的计算公式 差商的计算公式 差商的对称性 差商的对称性 差商的线性差商的线性 011 0 00 k j kk j kj kk kikjji ii ij f x f x xxx x xxxxxx ijji ij ijji f xf xf xf x f x x xxxx ijkjikikj f x x xf x x xf x x x 010101 nnn f xu xv x f x xxu x xxv x xx 由于由于n次插值多项式是唯一的 所以牛顿插值公式与次插值多项式是唯一的 所以牛顿插值公式与LagrangeLagrange 插值多项式一样 这意味着余项也一样 插值多项式一样 这意味着余项也一样 LagrangeLagrange余项为 余项为 所以牛顿余项也一样 所以牛顿余项也一样 1 01 1 n x nn f R xxxxxxx n 01101 1 01 01 1 nnn n x n k x k xxxxxxxxf x x xx f xxxxxx n f f x xx k 差商与导数的关系差商与导数的关系 重节点差商重节点差商 推论 当推论 当n个节点全为同一个点 牛顿插值变成个节点全为同一个点 牛顿插值变成 泰勒多项式 泰勒多项式 01 1 n n f x xxf n 0000 1 n f x xxfx n 差商的导数差商的导数 n 次多项式的的次多项式的的 1 阶差商是阶差商是 n 1 次多项式 次多项式 1 011011 1 n nn df f x xxxf x xxx x dxn 推论 设推论 设 p x 是是 n 次多项式 次多项式 k n 时时 k 阶差商是阶差商是 n k 次次 多项式 多项式 k n 时时 k 阶差商为零 阶差商为零 000 00 0 0 0 0 g xp xp xg xg xxx q x p xp xxx q x p xp x p x xq x xx 差分差分 设函数设函数 定义 定义为该函为该函 数在数在 i 点的点的一阶差分一阶差分 记为 记为 类似地 定义类似地 定义二阶差分为二阶差分为 K 阶差分为阶差分为 此差分称为此差分称为向前差分向前差分 ii f xxf在的函数值为 1ii ff 0 1 2 i fin 2 1 0 1 2 iii fffi 11 1 0 1 2 kkk iii fffi 类似地 类似地 向后差分向后差分定义为 定义为 中心差分中心差分定义为 定义为 1 0 1 2 iii fffin 11 1 0 1 2 kkk iii fffi 1 21 0 1 2 iii fffin 1 21 2 0 1 2 iii fffin 11 1 21 0 1 2 kkk iii fffi 差商与差分的关系 差商与差分的关系 等距节点时等距节点时 0 2 01 nnn nn n nnn f xf xf x f x xx n hn hn h 0i xxih 第五节第五节带导数的插值带导数的插值 问题的提出 如果在已知节点处不仅知道函数值 问题的提出 如果在已知节点处不仅知道函数值 同时还指导导数同时还指导导数值 这样 插值多项式就要求在值 这样 插值多项式就要求在 已知节点处与已知节点处与函数值和导数值都相等函数值和导数值都相等 这就是所 这就是所 谓谓埃尔米特插值埃尔米特插值 记为 记为 H x 1 牛顿插值 牛顿插值 如果已知如果已知某个点某个点 i 的的 则 则 插值节点应视为插值节点应视为个相同节点个相同节点 并注意到 并注意到k 1 重节点的差商重节点的差商 1 i r iiii y y yy i r i x 1 k i iiii k fx f x x xx k 例子 例子 已知关于函数已知关于函数 y f x 的函数值 导数值的函数值 导数值 00 1111 221 1 0 0 4 0 6 1 2 5 xy xyyy xyy 10 0 4 4 0 404 0 403 1 1 222 10 1 253121 0 0 0 0 0 0 0 0 2 3 1 1 1 5 fy fy fy 已知函数在已知函数在n个不同的节点处的函数值和导数值 个不同的节点处的函数值和导数值 求次数不超过求次数不超过2n 1次的多项式次的多项式 设想该多项式具有形式设想该多项式具有形式 1 2 iii x y y in 2121 1 2 niinii HxyHxyin 21 11 nn njjjj jj Hxy h xy h x 0 1 2 0 1 2 jiijji jijiij h xh xj in h xhxj in 由条件可得 由条件可得 此外 由此外 由得 得 2 jj h xAxB Wx 111 111 jjn j jjjjjjn xxxxxxxx W x xxxxxxxx 1 0 jjjj h xh x 1 2 2 0 1 2 j jj jjj jjj AxB AWx AAxB Wx Bx Wx 2 1 2 jjjjj h xWxxxWx 同理 同理 由由 可得 可得 最后 得到埃尔米特插值公式 最后 得到埃尔米特插值公式 2 jjj h xC xx Wx 1 jj h x 22 11 jjjjj CWxCh xxx Wx 21 11 22 11 1 2 nn njjjj jj nn jjjjjjjj jj Hxy h xy h x WxxxWx yxx Wx y 特别 当特别 当 n 2 时 三阶埃尔米特多项式为 时 三阶埃尔米特多项式为 311322311322 H xyH xyH xyH xy 2 12 31 1212 2 21 2 2121 22 21 1122 1221 12 12 xxxx Hxy xxxx xxxx y xxxx xxxx xxyxxy xxxx 埃尔米特插值公式唯一 埃尔米特插值公式唯一 误差估计 设被插值函数在插值区间上误差估计 设被插值函数在插值区间上2n次连续可导 次连续可导 则在则在n个节点上的个节点上的2n 1次插值多项式的余项为 次插值多项式的余项为 特别 对于特别 对于2个节点个节点3次插值 余项为 次插值 余项为 2121 2 2 12 2 nn n x n Rxf xHx f xxxxxx n 4 22 3312 4 x f R xf xHxxxxx 例子 例子 3333 0 0 0 0 1 1HHHH sinx 22 3 xx Hxxx 如用距离较小的两个点插值 效果会好得多如用距离较小的两个点插值 效果会好得多 33 33 0 0 2 1 0 1 2 0 HH HH 22 3 2 2 1 2 2 2 2 xxx Hxx 第六节第六节样条函数样条函数 由于被插值函数高阶导数未知 因此 如果高阶导数随阶数由于被插值函数高阶导数未知 因此 如果高阶导数随阶数 增长出现无限增长 则由误差公式可知 高阶插值公式就不增长出现无限增长 则由误差公式可知 高阶插值公式就不 一定无限接近被插值函数 这称为一定无限接近被插值函数 这称为龙格现象龙格现象 所以 在进行多项式插值时 不宜进行高次多项式插值 所以 在进行多项式插值时 不宜进行高次多项式插值 一个解决的途径是一个解决的途径是分段低次插值分段低次插值 龙格现象 样条函数插值 给定区间一个样条函数插值 给定区间一个划分划分 如函数如函数 S x 满足下面条件 满足下面条件 1 在每个小区间 在每个小区间上为上为m 次多项式 次多项式 2 S x 及及m 1 阶导数在整个区间上连续 阶导数在整个区间上连续 则称则称 S x 是关于该划分的是关于该划分的 m 次次样条函数样条函数 划分点称 划分点称 为节点 为节点 m 3 时 就是最常用的时 就是最常用的 3 次样条函数 次样条函数 01 N a baxxxb 1 1 2 jj xxjN 3次样条函数的基本思想 次样条函数的基本思想 将样条函数在每一个子区间端点的二阶导数值当作参将样条函数在每一个子区间端点的二阶导数值当作参 数 则用这两个二阶导数值可以将样条函数表示出数 则用这两个二阶导数值可以将样条函数表示出 来 再利用衔接条件 即每一段样条函数在相邻两来 再利用衔接条件 即每一段样条函数在相邻两 个子区间端点处的二阶导数相等 建立求解二阶导个子区间端点处的二阶导数相等 建立求解二阶导 数的方程组 数的方程组 设设S x 在每个小区间在每个小区间端点的二阶导端点的二阶导 数为 数为 则 则 记记 将上式积分两次 并利用端点函数值已知 将上式积分两次 并利用端点函数值已知 有 有 1 1 2 jj xxjN 11 jjjj S xMS xM 1 1 11 jj jj jjjj xxxx SxMM xxxx 33 1 1 22 11 1 1 66 66 1 2 jj jj jj jjjjjj jj jj jj xxxx S xMM hh MhxxM hxx yy hh xxxjN 1jjj hxx 我们注意到 在相邻的两个子区间我们注意到 在相邻的两个子区间和和 的共同端点处 样条函数一阶导数相等 的共同端点处 样条函数一阶导数相等 经过化简 最后得到 经过化简 最后得到 11jjj xxx 1 jj x x 1 jj xx 11 1 1 111 1 2 1 1 2 1 6 jjjjjj j jjj jj jjjjjj j jj MMMd h jN hh yyhyyh d hh 注意到上面的方程组总共只有注意到上面的方程组总共只有 N 1个方程 而未知数却共有个方程 而未知数却共有 N 个 因此 要求解方程 还需要两个条件 即两个方个 因此 要求解方程 还需要两个条件 即两个方 程 通常有以下几种方案程 通常有以下几种方案 1 给出端点一阶导数值 给出端点一阶导数值 这相当于增加两个方程 这相当于增加两个方程 2 给定端点二阶导数值 得方程 给定端点二阶导数值 得方程 特别 令二阶导数在端点为零 得特别 令二阶导数在端点为零 得 10 010 11 1 1 6 2 6 2 NN NNN NN yy MMy hh yy MMy hh 0 N yy 00 NN MyMy 0 0 0 N MM 3 样条件函数在第一后最后一个区间上为二次多项样条件函数在第一后最后一个区间上为二次多项 式 即样条函数在第一和最后一个区间上的二阶式 即样条函数在第一和最后一个区间上的二阶 导数为常数 得两个方程 导数为常数 得两个方程 总之 可以将方程组统一写为 总之 可以将方程组统一写为 011 NN MMMM 000 1111 1 20 2 02 N NNN Md Md Md 4 周期性条件 这只有在给的初值满足 周期性条件 这只有在给的初值满足时才能用 时才能用 此时 由周期性 此时 由周期性 就得到两个 就得到两个 方程 第一个方程为方程 第一个方程为 第二个方程为 第二个方程为 最后一个方程为 最后一个方程为 最后 方程组为 最后 方程组为 0N yy 1111 NN yyMM 10112111211 22 N MMMdMMMd 0N MM 11 11 2 2 NNNNNN NNNNN MMMd MMMd 1111 2222 1 2 2 2 N NNNN Md Md Md 小结小结 插值法 其目的是利用节点上的值 构造通过这些节点的多插值法 其目的是利用节点上的值 构造通过这些节点的多 项式 从原则上说 利用项式 从原则上说 利用n 1个节点的值 可以构造个节点的值 可以构造n次多次多 项式 而且这种构造是项式 而且这种构造是唯一的唯一的 利用待定系数法 将节点 利用待定系数法 将节点 值带入后 得到一个值带入后 得到一个n 1阶线