第二章插值方法 / Interpolation
第二章 插值方法 第二章 插值方法 /* Interpolation */
引言 Chapter 2 插值方法 表示两个变量Xy内在关系一般由函数式y=f(x)表达。 但在实际问题中,有两种情况: 1由实验观测而得的一组离散数据(函数表),显然这种函 数关系式y=f(x)存在且连续,但未知 2函数解析表达式已知,但计算复杂,不便使用。通常也 函数表。如,y=sin(x),y=lg(X)。 有时要求不在表上的函数值,怎么办? 应HUST
引言 表示两个变量x,y内在关系一般由函数式y=f(x)表达 但在实际问题中 有两种情况 1 由实验观测而得的一组离散数据(函数表) 显然这种函 数关系式y=f(x)存在且连续 但未知 2 函数解析表达式已知 但计算复杂 不便使用 通常也 函数表 如 y=sin(x),y=lg(x) 有时要求不在表上的函数值 怎么办
引言 Chapter 2 插值方法 办法是:根据所给的y=f×)的函数表, 构造一个简单的连续函数g(X)近似代替f(×)。 Def:g(Ⅹ)为逼近函数,f(X)为被逼近函数 近似代替即逼近的方法有很多种,通常是:插值方法。 已知:f()的函数表「xxx1x yo y yn 求g(×)使g(X)=y1,i=01,2,3…n. Def:g(×)为f(x)的插值函数,f(X)为被插值函数 WS HUST
引言 y0 y1 … yn x0 x1 … xn y 已知 x f(x)的的函数表 办法是 根据所给的y=f(x)的函数表 构造一个简单的连续函数g(x)近似代替f(x) Def g(x)为逼近函数 f(x)为被逼近函数 近似代替即逼近的方法有很多种 通常是 插值方法 求g(x)使 g(xi) =yi i=0,1,2,3 …n. Def g(x)为f(x)的插值函数 f(x)为被插值函数
引言 Chapter 2 插值方法 构造g(×)的方法还有 一致逼近、最佳均方逼近和数据拟合 简单函数q(×)指可用四则运算计算的函数: 如:有理函数(分式函数)、多项式或分段多项式 当g(×)为多项式时,该插值方法称为代数多项式插值,称插值 数g()为插值多项式 本章主要介绍多项式插值的理论与方法。 它在实践中应用很广。 应HUST
引言 构造g(x)的方法还有 一致逼近 最佳均方逼近和数据拟合 简单函数g(x)指可用四则运算计算的函数 如 有理函数(分式函数) 多项式或分段多项式 当g(x)为多项式时 该插值方法称为代数多项式插值 称插值 数g(x)为插值多项式 本章主要介绍多项式插值的理论与方法 它在实践中应用很广
Chapter 2 插值方法 插值区间 Problem I:已知y=f(x)的函数表 XX0×1 Ⅺ且X(=01两两互异, y yo y x∈[ab] 求次数不超过n的多项式 P)=a2+ax+ax+.+aX(21) 使得R(X)=%i=01,n2) 插值条件 Def:n+1个互异点X1X2x…X称为插值节点, 其所在区间[日,b]为插值区间,(2,2)式为插值条件, 应HUST
Def n+1个互异点x1,x2,…,xn称为插值节点 其所在区间[a,b]为插值区间 (2.2)式为插值条件 Problem I 已知y=f(x)的函数表 n 2 … n P (x)=a +a x+a x + +a x ( 01 2 n 2.1) P (x )=y i=0,1, ni i …,n (2.2) y0 y1 … yn x0 x1 … xn y x 插值区间 插值条件 且xi(i=0,1,…,n)两两互异 xi [a,b] 求次数不超过n的多项式 使得
Chapter 2 多项式插值问题的几何意义 插值方法 多项式P(x),其几何曲线过给定的y=f(x)的 n+1个点(xy),i=0,1,2,…,n fx)≈Pn(x) 应HUST
x0 x1 x2 x3 x4 x f(x) ≈ Pn(x) 多项式插值问题的几何意义 多项式Pn(x) 其几何曲线过给定的y=f(x)的 n+1个点(xi,yi) i=0,1,2,…,n
Chapter 2 插值多项式的唯一性 插值方法 对于 Problem中的Pn)是否存在?存在是否唯一?如何求? 显然,关键是求RX)的系数aoa1…an 定理2.1在冂+1个互异的插值结点x1x2Xn上满足插值条件 (22)的次数不超过n的代数多项式Pn(x)存在且唯一 分析:为求P)=a+ax+a2x2+.+ax(21) 主要考虑插值条件 P(X)=yi=01 2 应HUST
插值多项式的唯一性 对于Problem I中的Pn(x)是否存在 存在是否唯一 如何求 显然 关键是求Pn(x) 的系数a0,a1,…,an. 定理2.1 在n+1个互异的插值结点x1,x2,…,xn 上满足插值条件 (2.2)的次数不超过n的代数多项式Pn(x)存在且唯一 P (x )=y i=0,1, ni i …,n (2.2) n 2 … n 分析 为求 P (x)=a +a x+a x + +a x ( 01 2 n 2.1) 主要考虑插值条件
定理21的证明 Chapter 2 插值方法 证明:由插值条件,有, n(x0)=④+aX0+a2X02+.+a1X=y P(x1)=a+aX1+aX12+.+ax1=y1 (23) P(n=ao+ax, +a,x+.a,x,=y 其系数矩阵的行列式为 2 0 0 xx2…则三(x)=x)≠0 关于未知量a0,a1…,an的0 x.×2充木线性方程组(≠x 方程组(2.3)的解aa1灬,a1存在且唯一 插值多项式存在且唯一。 应HUST
定理2.1的证明 证明 由插值条件 有 … … " … 2 n n 0 0 10 20 n0 0 2 n n 1 0 11 21 n1 1 2 n n n 0 1n 2n nn n P (x )=a +a x +a x + +a x =y P (x )=a +a x +a x + +a x =y P (x )=a +a x +a x + +a x =y 关于未知量 的 关于未知量 的 非齐次线性方程组 a ,a , ,a 01 n … (2.3) 其系数矩阵的行列式为 … … … … 2 n 00 0 2 n 11 1 2 n nn n 1x x x 1x x x 1x x x (, ) i j ∵i jx x ≠ ≠ ∴ ∴ 方程组(2.3)的解 存在且唯一 的解 a ,a , ,a 01 n … 存在且唯一 插值多项式 存在且唯一 插值多项式 存在且唯一 =V(x ,x , ,x ) n01 n … ∏∏ n i-1 i j i=1 j=0 = (x - x ) ≠ 0
Chapter 2 插值方法 例1给定)的函数表,求f(×)的次数x|-1125 不超过3的插值多项式。 y|-77435 解:设P 3aa1x+a√2、3 则 1-11-1a 0 1248a 1525125人a3(35 解方程组得a=10,a1=5a2=-10,a3=2, 即P3(×)=10+5X-10×2+2×3 n=20,在10次/秒的计算机上计算需几十万年! 应HUST
例1 给定f(x)的函数表 求f(x)的次数 不超过 3的插值多项式 -7 7 4 35 -1 1 2 5 y x = 1 2 3 0 1 -1 1 -1 -7 a 11 1 1 7 a 1 2 4 8 -4 a 1 5 25 125 35 a 解 设 P 3(x)=a 0+a1x+a 2 x 2+a 3 x 3 则 解方程组得 a 0=10,a 1=5,a 2=-10,a 3=2 即 P 3(x)=10+5x-10x 2+2x 3 n=20 , 在 10 8 次 /秒的计算机上计算需几十万年
Chapter 2 2.2 Lagrange插值——线形插值 插值方法 Problem2.1已知函数y=fx)的函数表 0×1 求次数不超过1的多项式P1(X)=a+ax, y yo y1 满足插值条件P(X)=yoP(x)=y1 分析:过两点x0y)(X1y1)作直线y=P1(x)—线形插值 解:由点斜式方程, X-x X yI-yo (x) X-X x1-x0 称为线形插值基函数, y=(x=1+x-3+-而P1(是它们的线性组 合。1(x)+1(x)=1 x +xxx=(4几7)=p0 x I Kronecker Delta */ 应HUST
2.2 Lagrange 插值——线形插值 分析 过两点(x 0,y 0),(x 1,y 1 )作直线y=P 1(x)——线形插值 1 0 0 0 1 0 - (- ) - y y y y xx x x − = y0 y 1 x0 x 1 y x Problem 2.1 已知函数y=f(x)的函数表 求次数不超过 1的多项式 P 1(x)=a 0+a 1 x 满足插值条件 P 1(x 0)=y 0, P 1(x 1)=y 1 l0 (x) l 1 (x) Σ= = 1 0 ( ) i i x yi l 1 0 0 1 01 10 - - () , () - - x x x x lx lx xx xx = = 称为线形插值基函数 而 P1(x)是它们的线性组 是它们的线性组 合 0 1 lx lx () () 1 + = 0 0 01 1 0 11 ( ) 1, ( ) 0 ( ) 0, ( ) 1 lx lx lx lx = = = = 1 ( ) , 0,1 0 i j ij i j lx ij i j δ = = = = ≠ δij /* Kronecker Delta */ 解 由点斜式方程 0 0 10 1 0 10 10 - - () - - - xx xx y Px y y y xx xx = =+ 1 0 1 01 01 10 - - ( ) - - x x x x Px y y xx xx = +