版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: 模板 - Newton 插值 categories:

基于 C++17 标准, 实现了环上的 Newton 插值算法

{% note warning %}

{% note warning %} https://cplib.tifa-233.com/src/code/math/interp_newton_n2.hpp 存放了笔者对该算法/数据结构的最新实现, 建议前往此处查看相关代码 {% endnote %}

<!-- more -->

Newton 插值

对给定的点 $(x_0,y_0),(x_1,y1),\dots,(x{n-1},y_{n-1})$, Newton 插值得到的结果为

$$ f(x)=f[x0]+\sum{i=1}^{n-1}f[x_0,x_1,\dots,xi]\prod{k=0}^{i-1}(x-x_i) $$

其中 $f[x_0,x_1,\dots,x_i]$ 为有限差分, 定义如下:

显然, 相比 Lagrange 插值和 Neville 插值, Newton 插值可以做到 $O(n)$ 的单点插入, 且形式更加简单易懂

使用说明

环 T 须有接受 1 个整数的构造函数, T{0} 需为零元, T{1} 需为幺元

时间复杂度

成员函数列表

{% icodeweb blog lang:cpp newton-interp/NewtonInterp.h %}

代码

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp newton-interp/NewtonInterp.hpp %} </details>

示例