知识卡片

普通读书笔记卡 · 3692.b.2

拉格朗日公式直接构造插值式

理解等级:中级

给定n个横坐标互异的样本(xₖ,yₖ),为每个样本构造基多项式:

Lₖ(x)=∏ⱼ≠ₖ(x−xⱼ)/(xₖ−xⱼ)

Lₖ(xₖ)=1,而在其他采样点上为0,所以插值式为A(x)=Σₖ yₖLₖ(x)。互异性保证分母xₖ−xⱼ≠0。

补充教学演示:两点 (0,2)、(1,5) 给出 A(x)=2(1−x)+5x=2+3x;代回两点即得原样本值。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[5000,10000))。 - 结论依据:第30.1节 `OEBPS/images/Art_P1042.jpg`(式30.5)给出拉格朗日显式插值公式;要求采样点 x₀,…,xₙ₋₁ 互异,使分母不为零。两点算例是依据该公式补充的教学演示,不是原书例题。 - 公式图核读:A(x)=Σₖ₌₀ⁿ⁻¹ yₖ·∏ⱼ≠ₖ(x−xⱼ)/∏ⱼ≠ₖ(xₖ−xⱼ),每项在 xₖ 为 yₖ,在其他采样点为0。 - 原始内容:A faster algorithm for n -point interpolation is based on Lagrange’s formula : You might want to verify that the right-hand side of equation (30.5) is a polynomial of degree-bound n that satisfies A ( x k ) = y k for all k .