拉格朗日插值法

1. 基函数的构造

在证明了插值多项式的唯一性之后，接下来的问题就是：如何显式构造这个多项式？

拉格朗日从“插值条件 $P(x_i)=y_i$ 在每个节点上彼此独立”这一性质出发，给出了一种非常优雅的思路：如果我们能为每个节点 $x_i$ 构造一个多项式 $\ell_i(x)$ ，使它满足：

$\ell_i(x_i)=1$ ，即只在自己的节点上“激活”；
$\ell_i(x_j)=0 \ (j \ne i)$ ，即在其他节点上“静默”。

那么我们只需作线性组合

P(x)=\sum_{i=0}^{n} y_i \ell_i(x)

就能自动满足全部插值条件。

这就是拉格朗日插值法的核心思想：先构造一组具有“选择作用”的基函数，再用它们的线性组合得到插值多项式。

一旦得到这组基函数，对于任意给定的数据 $(y_0,\dots,y_n)$ ，插值多项式都可以表示为这些基函数的线性组合，其系数正是各节点的函数值 $y_i$ 。

为什么是线性组合？

从线性代数的视角看，所有次数不超过 $n$ 的多项式构成了一个 $n+1$ 维的向量空间 $\mathbb{P}_n$ 。我们要寻找的插值多项式，就是这个空间里的一个向量。

我们构造的 $n+1$ 个基函数 $\{\ell_i(x)\}$ 满足 $\ell_i(x_j)=\delta_{ij}$ （克罗内克 $\delta$ ），这直接保证了它们在多项式空间中是线性无关的。

因此，它们构成了一组完美的基底。我们将它们进行线性组合，本质上是将观测值 $y_i$ 作为坐标，在 $n+1$ 维空间中唯一确定了目标向量，也就是我们的插值多项式。

为了使 $\ell_i(x)$ 在其他节点处为 $0$ ，分子必须包含除 $x-x_i$ 以外的所有因子；为了使它在 $x_i$ 处取值为 $1$ ，还需要通过分母进行归一化。因此定义

\ell_i(x)=\prod_{\substack{j=0 \\ j\ne i}}^{n}\frac{x-x_j}{x_i-x_j}

这个函数形式非常优雅。不难看出：当 $x=x_i$ 时， $\ell_i(x)=1$ ；当 $x=x_j \ (j\ne i)$ 时， $\ell_i(x)=0$ ，因此它恰好满足基函数应有的性质。

2. 拉格朗日插值多项式

将各个基函数按对应函数值加权求和，就得到拉格朗日插值多项式：

L_n(x)=\sum_{i=0}^{n} y_i \ell_i(x) =\sum_{i=0}^{n} y_i \left( \prod_{\substack{j=0 \\ j\ne i}}^{n}\frac{x-x_j}{x_i-x_j} \right)

这个公式虽然看起来较复杂，但实际计算时，大多数量都是已知的，只需要将节点坐标与函数值代入即可。

为了让同学们直观理解拉格朗日基函数 $\ell_i(x)$ 的表达式，我们以二次插值（ $n=2$ ，即三个点）为例。设已知三个点 $(x_0, y_0)$ 、 $(x_1, y_1)$ 、 $(x_2, y_2)$ 。

三个基函数分别为：

\ell_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)},\quad \ell_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)},\quad \ell_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}

下面以 $\ell_1(x)$ 为例，从分子和分母两个部分说明其作用。

2.1 分子决定其他节点处的零点

分子为 $(x-x_0)(x-x_2)$ 。
当 $x=x_0$ 或 $x=x_2$ 时，分子为零，因此 $\ell_1(x_0)=\ell_1(x_2)=0$ 。
这保证了该基函数在除 $x_1$ 以外的所有节点上取值为零。

2.2 分母作为归一化因子

分母为 $(x_1-x_0)(x_1-x_2)$ ，这是一个由节点坐标确定的常数。
当 $x=x_1$ 时，分子变为 $(x_1-x_0)(x_1-x_2)$ ，与分母完全相同，于是 $\ell_1(x_1)=1$ 。
因此，分母的作用是将基函数在自己节点处的值归一化为 $1$ 。

综上，每个基函数 $\ell_i(x)$ 满足

\ell_i(x_j)=\delta_{ij}= \begin{cases} 1, & i=j, \\ 0, & i\neq j. \end{cases}

最终的二次插值多项式为：

L_2(x)=y_0\ell_0(x)+y_1\ell_1(x)+y_2\ell_2(x)

代入验证：在 $x=x_1$ 处， $\ell_0(x_1)=0$ ， $\ell_2(x_1)=0$ ，而 $\ell_1(x_1)=1$ ，故 $L_2(x_1)=y_1$ 。同理可验证其他节点。这正是“插值”的含义：多项式在已知节点处的值必须与观测值一致。

核心思想

拉格朗日插值法通过构造一组具有“筛选”性质的基函数，将插值问题转化为已知值的线性组合。每个基函数只在对应节点处为 $1$ ，在其他节点处为 $0$ ，从而使最终多项式自动满足所有插值条件。这种方法避免了直接求解线性方程组，并清晰地揭示了插值问题的线性结构。

3. 代码样例和局限性

航天局需要实时预测探测器相对于行星中心的径向距离 $r$ 。由于深空通信延迟，我们无法获得连续的遥测数据，只能通过深空网（DSN）每隔一段时间获得一个离散的观测点。

现在，你需要根据已有的三个观测点，利用拉格朗日插值法构造一个二次多项式，从而预测在特定时刻 $t$ 时探测器的位置，为接下来的轨道修正提供依据。

已知观测数据：

观测序号	时间 t (秒)	径向距离 r (千米)
$P_0$	$0.0$	$5000.0$
$P_1$	$10.0$	$4800.0$
$P_2$	$30.0$	$4200.0$

编写一个通用的拉格朗日插值函数，能够接受任意数量的 Point 对象。
利用上述三个观测点，计算并输出探测器在 $t = 20.0$ 秒时的预测径向距离。
思考题：如果此时雷达又回传了一个 $t = 40.0$ s 的新观测点，你的代码是否能方便地在原有基础上更新结果？

同学们不妨尝试在C++中实现这段代码。

main.cpp

#include <iostream>
#include <vector>

struct DataPoint {
    double t; // 自变量 x (Time)
    double r; // 因变量 y (Radial Distance)
};

double lagrangePredict(const std::vector<DataPoint>& dataset, double targetTime) {
    double predictedR = 0.0;
    int n = dataset.size();

    // 外层循环：对应公式中的线性叠加项 (Σ)
    for (int i = 0; i < n; ++i) {
        // L_i(x) 的权重初始化为 y_i
        double basisValue = dataset[i].r;

        // 内层循环：构造基函数 l_i(x) 的连乘部分 (Π)
        for (int j = 0; j < n; ++j) {
            // 根据基函数定义：j 不能等于 i，否则分母为 0
            if (j != i) {
                // 公式：l_i(x) = Π (x - x_j) / (x_i - x_j)
                basisValue *= (targetTime - dataset[j].t) / (dataset[i].t - dataset[j].t);
            }
        }

        // 线性叠加：将各基函数的分量累加
        predictedR += basisValue;
    }

    return predictedR;
}

int main() {
    // 1. 模拟深空探测器的观测数据 (t 为秒, r 为千米)
    // 假设轨道正在向近星点俯冲
    std::vector<DataPoint> orbitLog = {
        {0.0, 5000.0},   // 观测点 1
        {10.0, 4800.0},  // 观测点 2
        {30.0, 4200.0}   // 观测点 3
    };
    double predictAt = 20.0; // 我们想知道 20s 时的位置

    // 2. 执行插值算法
    double result = lagrangePredict(orbitLog, predictAt);

    // 3. 结果输出与逻辑验证
    std::cout << "======== 航天器轨道预测分析 ========" << std::endl;
    std::cout << "采样点总数: " << orbitLog.size() << " (二阶插值)" << std::endl;
    std::cout << "预测时刻: " << predictAt << " s" << std::endl;
    std::cout << "预测结果: " << result << " km" << std::endl;

    // t=20 介于 10s 和 30s 之间，结果 4533.33 符合物理趋势
    return 0;
}

从实际的代码样例中，我们可以看出拉格朗日插值法的如下缺陷：

如果你已经计算好了 $n$ 个点的插值公式，现在新增第 $n+1$ 个点。由于每个基函数 $l_i(x)$ 的分母都包含了所有节点 $(x_i - x_j)$ ，新节点的加入会导致之前算好的所有基函数全部作废。
算法复杂度过高： $O(n^2)$ 。对于每一个预测点 $x$ ，程序都要重新跑两层循环（求和 + 连乘）。如果采样点 $n$ 很大，每一帧都调用该算法会产生不可忽视的计算开销。
数值稳定性差：当采样点距离极其接近时，分母项 $(x_i - x_j)$ 会趋于零。在计算机浮点数精度受限的情况下，这种“除以极小数”的行为会放大舍入误差。

为了解决这部分难题，我们将在下一章引入数值分析中的另一位巨人—牛顿插值法。它的核心逻辑可以用两个词概括：增量与缓存。牛顿插值法使用了差商表的思想，解决了拉格朗日插值法不能添加新采样点的缺陷。