兼职做彩平网站,网站建设ydwzjs,滨州做微商城网站,小程序制作一个需要多少钱一、引言
在数值分析中#xff0c;拉格朗日插值法是以法国十八世纪数学家约瑟夫.拉格朗日命名的一种多项式插值方法。许多实际问题中都用函数来表示某种内在联系和规律#xff0c;而不少函数都只能通过实验或观测来了解。如对实验中的某个物理量进行观测#xff0c;在若干个…一、引言
在数值分析中拉格朗日插值法是以法国十八世纪数学家约瑟夫.拉格朗日命名的一种多项式插值方法。许多实际问题中都用函数来表示某种内在联系和规律而不少函数都只能通过实验或观测来了解。如对实验中的某个物理量进行观测在若干个不同的地方得到相应的观测值拉格朗日插值法可以找到一个多项式其恰好在各个观测点取到观测到的值。这样的多项式称为拉格朗日多项式。
数学上来讲拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数。
对于给定的 n 1 n1 n1个点 ( x 0 , y 0 ) , ( x 1 , y 1 ) , ⋯ , ( x n , y n ) (x_0,y_0)\;,\;(x_1,y_1)\;,\;\cdots\;,\;(x_n,y_n) (x0,y0),(x1,y1),⋯,(xn,yn)对应于它们的次数都不超过 n n n的拉格朗日多项式 L L L只有一个。如果计入次数更高的多项式则有无穷个因为所有与 L L L相差 λ ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x n ) \lambda(x-x_0)(x-x_1)\cdots(x-x_n) λ(x−x0)(x−x1)⋯(x−xn)的多项式都满足条件。例如 已知平面上四个点-95、-42、-1-2、79拉格朗日多项式 L ( x ) L(x) L(x)黑色穿过所有点。而每个基本多项式 y 0 l 0 ( x ) , y 1 l 1 ( x ) , y 2 l 2 ( x ) , y 3 l 3 ( x ) y_0l_0(x)\;,\;y_1l_1(x)\;,\;y_2l_2(x)\;,\;y_3l_3(x) y0l0(x),y1l1(x),y2l2(x),y3l3(x)各穿过对应的一点并在其他的三个点的 x x x值上取0。
二、定义
对某个多项式函数已知有给定的 k 1 k1 k1个取值点 ( x 0 , y 0 ) , ( x 1 , y 1 ) , ⋯ , ( x k , y k ) (x_0,y_0)\;,\;(x_1,y_1)\;,\;\cdots\;,\;(x_k,y_k) (x0,y0),(x1,y1),⋯,(xk,yk) 其中 x j x_j xj对应着自变量的位置而 y j y_j yj对应着函数在这个位置的取值。
假设任意两个不同的 x j x_j xj都互不相同那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为 L ( x ) ∑ j 0 k y j l j ( x ) L(x)\sum_{j0}^ky_jl_j(x) L(x)j0∑kyjlj(x) 其中每个 l j ( x ) l_j(x) lj(x)为拉格朗日基本多项式或称插值基函数其表达式为 l j ( x ) : ∏ i 0 , i ≠ j k x − x i x j − x i x − x 0 x j − x 0 ⋯ x − x j − 1 x j − x j − 1 x − x j 1 x j − x j 1 ⋯ x − x k x j − x k l_j(x):\prod_{i0,i\neq j}^k\frac{x-x_i}{x_j-x_i}\frac{x-x_0}{x_j-x_0}\cdots \frac{x-x_{j-1}}{x_j-x_{j-1}}\frac{x-x_{j1}}{x_j-x_{j1}}\cdots\frac{x-x_k}{x_j-x_k} lj(x):i0,ij∏kxj−xix−xixj−x0x−x0⋯xj−xj−1x−xj−1xj−xj1x−xj1⋯xj−xkx−xk 拉格朗日基本多项式 l j ( x ) l_j(x) lj(x)的特点是在 x j x_j xj上的取值为1在其他的点 x i , i ≠ j x_i\;,\;i\neq j xi,ij上取值为0。
三、范例
假设有某个二次多项式函数 f f f已知它在三个点上的取值为 f ( 4 ) 10 , f ( 5 ) 5.25 , f ( 6 ) 1 f(4)10\;,\;f(5)5.25\;,\;f(6)1 f(4)10,f(5)5.25,f(6)1 需要求 f ( 18 ) f(18) f(18)的值。
首先写出每个拉格朗日基本多项式 l 0 ( x ) ( x − 5 ) ( x − 6 ) ( 4 − 5 ) ( 4 − 6 ) l_0(x)\frac{(x-5)(x-6)}{(4-5)(4-6)} l0(x)(4−5)(4−6)(x−5)(x−6) l 1 ( x ) ( x − 4 ) ( x − 6 ) ( 5 − 4 ) ( 5 − 6 ) l_1(x)\frac{(x-4)(x-6)}{(5-4)(5-6)} l1(x)(5−4)(5−6)(x−4)(x−6) l 2 ( x ) ( x − 4 ) ( x − 5 ) ( 6 − 4 ) ( 6 − 5 ) l_2(x)\frac{(x-4)(x-5)}{(6-4)(6-5)} l2(x)(6−4)(6−5)(x−4)(x−5) 然后应用拉格朗日插值法就可以得到 P P P的表达式 P P P为函数 f f f的插值函数: P ( x ) f ( 4 ) l 0 ( x ) f ( 5 ) l 1 ( x ) f ( 6 ) l 2 ( x ) P(x)f(4)l_0(x)f(5)l_1(x)f(6)l_2(x) P(x)f(4)l0(x)f(5)l1(x)f(6)l2(x) 代入我们上面的公式 P ( x ) 1 4 ( x 2 − 28 x 136 ) P(x)\frac{1}{4}(x^2-28x136) P(x)41(x2−28x136) 此时代入数值18就可以得到所求之值 f ( 18 ) P ( 18 ) − 11 f(18)P(18)-11 f(18)P(18)−11
四、证明
1. 存在性
对于给定的 k 1 k1 k1个点 ( x 0 , y 0 ) , ( x 1 , y 1 ) , ⋯ , ( x k , y k ) (x_0,y_0)\;,\;(x_1,y_1)\;,\;\cdots\;,\;(x_k,y_k) (x0,y0),(x1,y1),⋯,(xk,yk)拉格朗日插值法的思路是找到一个在一点 x j x_j xj取值为1而在其他点取值为0的多项式 l j ( x ) l_j(x) lj(x)。这样多项式 y j l j ( x ) y_jl_j(x) yjlj(x)在点 x j x_j xj取值为 y j y_j yj而在其他点取值都为0。
而多项式 L ( x ) ∑ j 0 k y j l j ( x ) L(x)\sum_{j0}^ky_jl_j(x) L(x)∑j0kyjlj(x)就可以满足 L ( x j ) ∑ j 0 k y i l i ( x j ) 0 0 ⋯ y j ⋯ 0 y j L(x_j)\sum_{j0}^ky_il_i(x_j)00\cdotsy_j\cdots0y_j L(xj)j0∑kyili(xj)00⋯yj⋯0yj 在其他点取值为0的多项式容易找到例如 ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x j − 1 ) ( x − x j 1 ) ⋯ ( x − x k ) (x-x_0)(x-x_1)\cdots(x-x_{j-1})(x-x_{j1})\cdots(x-x_k) (x−x0)(x−x1)⋯(x−xj−1)(x−xj1)⋯(x−xk) 它在点 x j x_j xj取值为 ( x j − x 0 ) ( x j − x 1 ) ⋯ ( x j − x j − 1 ) ( x j − x j 1 ) ⋯ ( x j − x k ) (x_j-x_0)(x_j-x_1)\cdots(x_j-x_{j-1})(x_j-x_{j1})\cdots(x_j-x_k) (xj−x0)(xj−x1)⋯(xj−xj−1)(xj−xj1)⋯(xj−xk) 由于已经假定 x i x_i xi互不相同因此上面的取值不等于0将多项式除以这个取值就能得到一个满足“在 x j x_j xj取值为1在其他店取值为0”的多项式。 l j ( x ) : ∏ i 0 , i ≠ j k x − x i x j − x i x − x 0 x j − x 0 ⋯ x − x j − 1 x j − x j − 1 x − x j 1 x j − x j 1 ⋯ x − x k x j − x k l_j(x):\prod_{i0,i\neq j}^k\frac{x-x_i}{x_j-x_i}\frac{x-x_0}{x_j-x_0}\cdots \frac{x-x_{j-1}}{x_j-x_{j-1}}\frac{x-x_{j1}}{x_j-x_{j1}}\cdots\frac{x-x_k}{x_j-x_k} lj(x):i0,ij∏kxj−xix−xixj−x0x−x0⋯xj−xj−1x−xj−1xj−xj1x−xj1⋯xj−xkx−xk 这就是拉格朗日基本多项式。
2. 唯一性
次数不超过 k k k的拉格朗日多项式至多只有一个因为对任意两个次数不超过 k k k的拉格朗日多项式 p 1 , p 2 p_1\;,\;p_2 p1,p2。它们的差 p 1 − p 2 p_1-p_2 p1−p2在所有 k 1 k1 k1个点上取值都为0因此必然是多项式 ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x j − 1 ) ( x − x j 1 ) ⋯ ( x − x k ) (x-x_0)(x-x_1)\cdots(x-x_{j-1})(x-x_{j1})\cdots(x-x_k) (x−x0)(x−x1)⋯(x−xj−1)(x−xj1)⋯(x−xk)的倍数。
因此如果这个差 p 1 − p 2 p_1-p_2 p1−p2不等于0次数就一定不小于 k 1 k1 k1。但是 p 1 − p 2 p_1-p_2 p1−p2是两个次数不超过 k k k的多项式之差它的次数也不超过 k k k。
所以 p 1 − p 2 0 p_1-p_20 p1−p20也就是说 p 1 p 2 p_1p_2 p1p2这就证明了唯一性。
五、优点与缺点
拉格朗日插值法的公式结构整齐紧凑在理论分析中十分方便然而在计算中当插值点增加或减少一个时所对应的基本多项式就需要全部重新计算于是整个公式都会变化非常繁琐。这时可以用重心拉格朗日插值法或牛顿插值法来代替。
此外当插值点比较多的时候拉格朗日插值多项式的次数可能会很高因此具有数值不稳定的特点也就是说尽管在已知的几个点取到给定的数值但在附近却会和“实际上”的值之间有很大的偏差。
这类现象也被称为龙格现象解决的办法是分段用较低次数的插值多项式。
六、重心拉格朗日插值法
重心拉格朗日插值法是拉格朗日插值法的一种改进。
在拉格朗日插值法中运用多项式 l ( x ) ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x k ) l(x)(x-x_0)(x-x_1)\cdots(x-x_k) l(x)(x−x0)(x−x1)⋯(x−xk) 拉格朗日插值法的数值稳定性如图用于模拟一个十分平稳的函数时插值多项式的取值可能会突然出现一个大的偏差图中的14至15中间
可以将拉格朗日基本多项式重新写为 l j ( x ) l ( x ) x − x j 1 ∏ i 0 , i ≠ j k ( x j − x i ) l_j(x)\frac{l(x)}{x-x_j}\frac{1}{\prod_{i0,i\neq j}^k(x_j-x_i)} lj(x)x−xjl(x)∏i0,ijk(xj−xi)1 定义重心权: ω j 1 ∏ i 0 , i ≠ j k ( x j − x i ) \omega_j\frac{1}{\prod_{i0,i\neq j}^k(x_j-x_i)} ωj∏i0,ijk(xj−xi)1 上面的表达式可以简化为 l j ( x ) l ( x ) ω j x − x j l_j(x)l(x)\frac{\omega_j}{x-x_j} lj(x)l(x)x−xjωj 于是拉格朗日插值多项式变为 L ( x ) l ( x ) ∑ j 0 k ω j x − x j y j L(x)l(x)\sum_{j0}^k\frac{\omega_j}{x-x_j}y_j L(x)l(x)j0∑kx−xjωjyj 即所谓的重心拉格朗日插值公式第一型或改进拉格朗日插值公式。
它的优点是当插值点的个数增加一个时将每个 ω j \omega_j ωj都除以 ( x j − x k 1 ) (x_j − x_{k 1}) (xj−xk1)就可以得到新的重心权 w k 1 w_{k 1} wk1计算复杂度为 O ( n ) \mathcal O(n) O(n)比重新计算每个基本多项式所需要的复杂度 O ( n 2 ) \mathcal O(n^2) O(n2)降了一个量级。
将以上的拉格朗日插值多项式用来对函数 g ( x ) ≡ 1 g(x)\equiv 1 g(x)≡1插值可以得到 ∀ x , g ( x ) l ( x ) ∑ j 0 k ω j x − x j \forall x,\,g(x)l(x)\sum_{j0}^k\frac{\omega_j}{x-x_j} ∀x,g(x)l(x)j0∑kx−xjωj 因为 g ( x ) ≡ 1 g(x)\equiv 1 g(x)≡1是一个多项式。
因此将 L ( x ) L(x) L(x)除以 g ( x ) g(x) g(x)后可得到 L ( x ) ∑ j 0 k ω j x − x j y j ∑ j 0 k ω j x − x j L(x)\frac{\sum_{j0}^k\frac{\omega_j}{x-x_j}y_j}{\sum_{j0}^k\frac{\omega_j}{x-x_j}} L(x)∑j0kx−xjωj∑j0kx−xjωjyj 这个公式被称为重心拉格朗日插值公式第二型或真正的重心拉格朗日插值公式。它继承了1式容易计算的特点并且在代入 x x x值计算 L ( x ) L(x) L(x)的时候不必计算多项式 l ( x ) l(x) l(x)。
它的另一个优点是结合切比雪夫节点进行插值的话可以很好地模拟给定的函数使得插值点个数趋于无穷时最大偏差趋于零。同时重心拉格朗日插值结合切比雪夫节点进行插值可以达到极佳的数值稳定性。第一型拉格朗日插值是向后稳定的而第二型拉格朗日插值是向前稳定的并且勒贝格常数很小。
