从零开始的数值分析--插值法
# 导入math模块，用于数学计算
import math
# 导入numpy模块，用于科学计算，特别是多维数组操作
import numpy as np
# 导入matplotlib.pyplot模块，用于数据可视化
import matplotlib.pyplot as plt
插值法概念与性质
概念
插值法（Interpolation） 是一种在数学和计算机科学中广泛应用的数值分析方法。其基本思想是通过已知的一组离散的数据点（通常称为节点或样本点），构建一个函数（称为插值函数），使得这个函数能够恰好通过所有这些数据点。换句话说，插值法旨在找到一个函数f(x)f(x)f(x)，它在给定的节点xix_ixi处的值与已知的数据值yiy_iyi相匹配，即满足条件f(xi)=yi,i=1,2,...,nf(x_i) = y_i, i = 1, 2, ..., nf(xi)=yi,i=1,2,...,n。这种方法常用于估计或恢复在两个或多个已知数据点之间的数据值。
常见插值方法
线性插值：最简单的一种插值方法，适用于两个数据点之间。通过直线连接这两个点来估计区间内的任意值。
多项式插值：包括拉格朗日插值、牛顿插值等，其中最常用的是拉格朗日插值法，通过构造一个n次多项式来精确通过n+1个数据点。
样条插值：如自然 cubic spline（三次样条插值）、Hermite 插值等，这类方法在保证通过所有数据点的同时，还考虑了平滑度等特性，通常用于要求导数连续的场景。
其他高级插值方法：如径向基函数插值、样条插值的变种等，它们在特定领域有更优的表现。
性质
精确性：理想的插值函数应精确通过所有给定的数据点，这是插值的基本要求。
连续性：插值函数在其定义域内应当是连续的。对于多项式插值和样条插值，通常还能保证一定阶数的导数连续。
光滑性：良好的插值方法应使得插值函数在数据点间变化平滑，避免出现不必要的波动或尖点。
稳定性：对于数据的小变动，插值结果应具有稳定性，即输入数据的微小变化不应导致输出结果发生剧烈变化。
计算复杂度：不同的插值方法在计算上有着不同的复杂度，选择时需考虑实际应用场景对计算效率的需求。
过拟合风险：特别是在使用高阶多项式插值时，虽然能完美匹配数据点，但可能在节点间产生大幅震荡，这被称为过拟合现象，影响预测的准确性。
在大致了解了基础概念后我们将插值分为了下面大致几类来介绍:
标准多项式插值
拉格朗日插值法
牛顿插值法
埃尔米特插值法
分段线性插值
样条插值
标准多项式插值:
我们现在有n+1个样本点对,我们需要去寻找一个多项式f(x)∈Pnf(x) \in \mathcal{P}_nf(x)∈Pn，使得f(xi)=yif(x_i) = y_if(xi)=yi,其中(xi,yi)(x_i,y_i)(xi,yi)为样本点。 f(x)=a0+a1x+a2x2+⋯+anxn,∀x∈{
xi} f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n,\forall x \in \{x_i\} f(x)=a0+a1x+a2x2+⋯+anxn,∀x∈{
xi}
因此,我们将上式展开并写为矩阵形式,可以得到如下结果: A=(1x0x02⋯x0n1x1x12⋯x1n⋮1xnxn2⋯xnn),x=(a0a1⋮an),b=(y0y1⋮yn)Ax=b A = \begin{pmatrix} 1 \quad x_0 \quad x_0^2 \quad \cdots \quad x_0^n \\ 1 \quad x_1 \quad x_1^2 \quad \cdots \quad x_1^n \\ \vdots \\ 1 \quad x_n \quad x_n^2 \quad \cdots \quad x_n^n \\ \end{pmatrix} , x = \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \\ \end{pmatrix} , b = \begin{pmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \\ \end{pmatrix} \\ Ax = b A=⎝⎜⎜⎜⎛1x0x02⋯x0n1x1x12⋯x1n⋮1xnxn2⋯xnn⎠⎟⎟⎟⎞,x=⎝⎜⎜⎜⎛a0a1⋮an⎠⎟⎟⎟⎞,b=⎝⎜⎜⎜⎛y0y1⋮yn⎠⎟⎟⎟⎞Ax=b
∵∥A∥=∣1x0x02⋯x0n1x1x12⋯x1n⋮1xnxn2⋯xnn∣ \because \|A\| = \begin{vmatrix} 1 \quad x_0 \quad x_0^2 \quad \cdots \quad x_0^n \\ 1 \quad x_1 \quad x_1^2 \quad \cdots \quad x_1^n \\ \vdots \\ 1 \quad x_n \quad x_n^2 \quad \cdots \quad x_n^n \\ \end{vmatrix} ∵∥A∥=∣∣∣∣∣∣∣∣∣1x0x02⋯x0n1x1x12⋯x1n⋮1xnxn2⋯xnn∣∣∣∣∣∣∣∣∣ 为Vandermonde行列式，其值∏i