C++ 使用 boost 库实现插值算法

本文介绍 Linux 环境下，如何使用 C++ 非标准库 boost，实现一维插值算法.

boost 安装 (Linux + Clion + boost_1_74_0)

下载 boost 安装包、解压缩、进入文件目录

wget https://dl.bintray.com/boostorg/release/1.74.0/source/boost_1_74_0.tar.gz
tar zxvf boost_1_74_0.tar.gz     
cd boost_1_74_0/ 

ps: 根据boost官网发布的版本信息(link)，1.73.0 boost添加了Cubic Hermite Interpolation, Modified Akima Interpolation, PCHIP Interpolation, Quintic Hermite Interpolation等插值函数。如果需要用到这几个函数，需要下载1.73.0及以上版本。

附：查看boost版本号的两种方法：

dpkg -S /usr/include/boost/version.hpp
ls /usr/local/lib | grep boost // 后缀是版本号

其中/usr/include/或/usr/local/lib是boost文件路径。一般会安装在/usr/include/或/usr/local/目录下。

附：卸载旧版本boost的方法：

sudo apt-get --purge remove libboost1.54-dev
sudo apt-get autoremove libboost1.54-dev

使用purge remove删除已安装的软件包，不保留配置文件。注意谨慎使用autoremove- 卸载所有自动安装且不再使用的软件包。

编译，指定安装路径前缀

./bootstrap.sh --prefix=/usr/local

安装

sudo ./b2 install

可能需要安装的依赖库

sudo apt-get update   
sudo apt-get install build-essential g++ python-dev autotools-dev libicu-dev build-essential libbz2-dev libboost-all-dev

参考

https://www.cnblogs.com/dylancao/p/9054821.html
https://blog.csdn.net/guotianqing/article/details/104455929

boost::math::interpolators

官方文档

Documentation

添加头函数

按照官方文档给出的示例教程，在main函数中添加相应的插值函数的头文件，如：

#include <boost/math/interpolators/pchip.hpp>

修改项目 CMakeLists.txt

set(BOOST_ROOT /usr/local/boost)
find_package(Boost REQUIRED)
include_directories(${Boost_INCLUDE_DIRS})
target_link_libraries(project_name ${Boost_LIBRARIES})

其中/usr/local/boost需要修改为boost的安装目录，project_name修改为项目名称。 修改完CMakeLists.txt后，Reload CMakeLists。

几种插值函数简介

1. Cardinal Cubic B-spline interpolation
   cardinal cubic B-spline类类型为在等间距点采样的函数提供精准快速的插值方法，可被应用于常微分方程（ODE）的数值求解。时间复杂度 O(1)。
   头文件

    #include <boost/math/interpolators/cardinal_cubic_b_spline.hpp>
   

   输入参数
   前两个输入参数：表示数据头尾的一组迭代器 或 指向数据的指针和数组长度；
   随后的两个参数：待求解方程自变量取值的起点，求解步长。
   可选参数：起止点的一阶导数值。若未提供，则由单边有限差分公式（one-sided finite-difference formulas）估计。
   调用构造函数

    std::vector<double> f{0.01, -0.02, 0.3, 0.8, 1.9, -8.78, -22.6};
    double t0 = 0;
    double h = 0.01;
    boost::math::interpolators::cardinal_cubic_b_spline<double> spline(f.begin(), f.end(), t0, h);
    boost::math::interpolators::cardinal_cubic_b_spline<double> spline(f.begin(), f.end(), t0, h, a_prime, b_prime);  //带一阶导数值
   

   求某点的插值结果

    double y = spline(x);
    double yp = spline.prime(x);          //一阶导数
    double ypp = spline.double_prime(x);  //二阶导数
   

   附：Cardinal Quadratic B-spline interpolation，Cardinal Quintic B-spline interpolation与Cardinal Cubic B-spline interpolation的功能一致，实现插值的方法略微有所差别。

2. Barycentric Rational Interpolation
   Barycentric Rational Interpolation为采样点非均匀分布的数据提供插值方法，在构建和估测两步都具有线性时间复杂度 - O(N)。
   头文件

    #include <boost/math/interpolators/barycentric_rational.hpp>
   

   输入参数
   Barycentric Rational Interpolation的构造函数很多，都需要输入自变量和因变量数据，但变量类型不同，这里我们只介绍两种。
   a. 输入为移动右值 std::move(x)

    boost::math::barycentric_rational<double> interpolant(std::move(x), std::move(y));
    boost::math::barycentric_rational<double> interpolant(std::move(x), std::move(y), 5);   //5阶，默认3阶
   

   附：介绍右值&&的两个不错的链接link1, link2。
   b. 输入为指向vector类型的指针 x.data()

    boost::math::barycentric_rational<double> b(x.data(), y.data(), r.size());
    boost::math::barycentric_rational<double> b(x.data(), y.data(), r.size(), n);  //n为拟合阶数，注意 n < r.size()
   

   求某点的插值结果

    double x = 2.3;
    double y = interpolant(x);
    double y = interpolant.prime(x);
    std::vector<double> xs = interpolant.return_x();  //返回自变量
    std::vector<double> ys = interpolant.return_y();  //返回因变量
    //注意：执行返回操作后，interpolant 不再可用（dead）。
   

3. Modified Akima interpolation
   Modified Akima interpolation采用cubic Hermite polynomials方法对非等间隔采样的数据进行插值，多项式斜率由 Akima 提出的修正后的几何重构法确定。时间复杂度为O(log(N))，但插值曲线的平滑度不如Barycentric Rational Interpolation。
   头文件

     #include <boost/math/interpolators/makima.hpp>
   

   输入参数
   自变量和因变量的右值（&&），std::move(x), std::move(y)。
   官方文档的一些问题
   使用如下的示例程序：

     std::vector<double> x{1, 5, 9 , 12};
     std::vector<double> y{8,17, 4, -3};
     using boost::math::interpolators::pchip;
     auto spline = pchip(std::move(x), std::move(y));
     // evaluate at a point:
     double z = spline(3.4);
     // evaluate derivative at a point:
     double zprime = spline.prime(3.4);
   

   使用Clion开发工具，会在makima处会给出错误提示：Use of class template ‘makima’requires template arguments.。 原因在于makima是模板类型而不是类类型，需要给出的是模板的输入参数。修改为以下语句即可通过：

     boost::math::interpolators::makima<vector<double>> spline(move(x), move(y));
   

   注意
   makima函数要求已知采样点的个数 >= 4。

4. PCHIP interpolation
   与Modified Akima interpolation类似，PCHIP interpolation也采用cubic Hermite polynomials方法对非等间隔采样的数据进行插值，但斜率由另一种方法确定。时间复杂度为O(log(N))。 头文件

     #include <boost/math/interpolators/pchip.hpp>
   

   ps
   输入参数、官方文档存在的问题及解决方案同Modified Akima interpolation方法。