查看“︁高中数学/不等式与数列/插值法”︁的源代码

== 阅读指南 ==
[[File:Crystal Clear app gnome.png | Crystal Clear app gnome | 50px]]

先前我们提到过某些根据少数已知项，猜想数列通项公式的问题。在中国大陆[[w:国家公务员考试|国家公务员考试]]行政职业能力测验、IQ测试和鱼龙混杂的小学数学智力问题中，数列找规律的问题也占了一定的比重。首先，我们在此指出，虽然培养猜想能力很重要，但是解决人为构造的过难的找规律问题是并无必要的。其次，如果对数列项的变化规律没有限制得很死，比如允许解题人非常自由地去猜想规律，是完全有可能存在多个不同答案的。事实上，给定一个数列的有限个项，在不加任何额外限制的情况下，可以写出无数个可能的递推公式。这类问题的更一般情形就是函数插值问题，它旨在设法将平面或空间中的一系列有限个函数点用一个已知解析式的曲线串起来。我们先通过对于特殊情形下函数插值的方法讨论，给出一些快速求解此类问题的思路，随后进一步介绍经典的拉格朗日插值公式。拉格朗日插值公式看上去形式较为繁琐，但是避免了求解方程中未知系数的麻烦，其正确性也不难检验。

=== 预备知识 ===
了解多项式基本运算（例如因式分解）、[[高中数学/函数与三角/函数的概念|函数的概念]]和[[高中数学/不等式与数列/数列与通项公式的概念|数列的概念]]即可。

=== 考试要求 ===
本节内容不是考试范围，对拓展知识毫无兴趣的读者可以直接跳过本节。

== 基础知识 ==
=== 插值问题与简单的插值方法 ===
<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">'''插值'''（'''interpolation'''）也叫做'''内插'''，是寻找图象通过有限多个已知点的未知函数的解析式的过程，也即将散点用函数穿插起来。如果只是寻找图象尽量接近有限多个已知点的未知函数的解析式，那么这样的过程就叫做函数的'''拟合'''（'''fitting'''）。插值是要求函数曲线或图象必须通过已知各点的特殊拟合。
</font>
</blockquote>

本节只论述平面上点集合的插值问题，并且假定所有给定点在平面直角坐标系中的x坐标各不相同。我们的大体思路是通过选取合适的独立函数作为基底，然后带入已知数据解方程组的方法确定所需的插值函数。

现在我们希望求解依次通过平面上3个指定点<math>P_1 (x_1, y_1), P_2 (x_2, y_2), P_3 (x_3, y_3)</math>的插值公式。

不妨设插值函数具有多项式的形式，插值多项式如果存在，那么显然也是形式最常见、最容易理解的解（虽然答案并非只能是多项式）。由于已知的是坐标确定的3个点，而由3个已知条件一般可以确定的是包含3个待定参数的未知多项式，我们知道包含3个待定系数的最简单的多项式为二次函数，所以可以尝试设所求的插值多项式为二次函数<math>y = a x^2 + b x + c \quad (a \neq 0)</math>。

将已知的3个点的坐标带入所设的二次函数可得：<br />
<math>
\left\{
\begin{array}{l}
y_1 = a x_1^2 + b x_1 + c \\
y_2 = a x_2^2 + b x_2 + c \\
y_3 = a x_3^2 + b x_3 + c
\end{array}
\right.
</math><br />
由于<math>x_1, x_2, x_3, y_1 y_2, y_3</math>都已知，这是一个以a、b、c为未知系数的三元一次方程组。由这3个方程容易求出所需的a、b、c的值（这里暂不考虑线性方程组解的存在性和唯一性等技术细节），从而确定所需二次函数的具体系数，从而得到所需的插值公式。

由于[[高中数学/不等式与数列/多阶等差数列|多阶等差数列]]的通项公式正好是高次多项式，这种使用多项式进行插值的方法也可以看成是将点序列视作多阶等差数列求解。

[[File:Crystal Clear app kdict.png | Crystal Clear app kdict | 50px]]
知识背景：
这种方法类似于利用合适的[[w:幂级数|幂级数]]来逼近特定已知函数。插值问题中所求的插值函数不一定必须取多项式的形式，甚至满足条件的多项式取法也有很多，例如可以是各阶[[w:切比雪夫多项式|切比雪夫多项式]]、各阶[[w:勒让德多项式|勒让德多项式]]以及本节下面马上会介绍的经典的[[w:拉格朗日插值法|拉格朗日插值多项式]]。由线性[[w:泛函分析|泛函分析]]和函数[[w:逼近理论|逼近理论]]中的知识可知，只要是满足函数[[w:线性无关|线性无关]]条件的函数系都可以用于完美地拟合已知的有限个或无限个离散点。例如由微积分中三角级数构成的事实可知，取系数待定的一列正交的三角函数之和进行插值并求解方程也可以达到目标。如果需要拟合的目标是定义在整个<math>\mathbb{R}</math>上的任意已知函数，则所需的函数系还必须是[[w:完备性|完备的]]。

<!-- 本小节例题 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题：
求解依次通过平面上3个已知点<math>P_1 (1, 2), P_2 (3, 4), P_3 (5, 6)</math>的1个插值多项式。

<!-- 本小节例题的解答 -->
<div class="collapsible answer" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>解答：<br />
 由于已知3个坐标确定的点，需要由3个条件确定的最简单的多项式是二次多项式，所以可以设所求的插值多项式为二次多项式：
 <math>y = a x^2 + b x + c (a \neq 0)</math>
 将已知的3个点的坐标分别作为3组条件代入其中可得：<br />
 <math>
 \begin{array}{l}
  \left\{
  \begin{array}{l}
   y_1 = a x_1^2 + b x_1 + c \\
   y_2 = a x_2^2 + b x_2 + c \\
   y_3 = a x_3^2 + b x_3 + c \\
  \end{array}
  \right. \quad \Rightarrow \quad
  \left\{
  \begin{array}{l}
   2 = a \times 1^2 + b \times 1 + c \\
   4 = a \times 3^2 + b \times 3 + c \\
   6 = a \times 5^2 + b \times 5 + c \\
  \end{array}
  \right. \\
  \Rightarrow a = 0, b = 1, c = 1
 \end{array}
 </math><br />
 由于它不满足二次函数最高次项系数不为零的前提条件，所以实际上得到的是一个一次多项式。故所求的插值多项式可以取为<math>y = a x^2 + b x + c = x + 1</math>。
 </p>
</div>
<div class="collapsible finalAnswer" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243); color: red;">
 <p>答案：<math>y = x + 1</math>或其它同样满足题意的解。</p>
</div>
<div class="collapsible remarks" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>点评：一般来说，已知n个坐标点，那么可以设所需的插值多项式具有n-1次多项式的最一般形式。但是在少数情形下，通过代入数值并解方程所得到的结果会自动退化为更简单的、低于n-1阶的多项式。</p>
</div>

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：就上述例题所示的已知3个点的情形而言，所求的插值多项式也可以设置成类似<math>y = a x^4 + b x^3 + x</math>这种更高次的缺项多项式的形式。只是这样一来，其计算量会比设置成2次多项式要更大一些，所以并无必要。我们可以借助计算机软件求出此时的解为：<br />
<math>y = - \frac{121}{615} x^4 + {736}{615} x^3 - \frac{2537}{615} x</math><br />
很明显，这样设也并不是不可以，也能得到满足题意的解，但是会使求解过程复杂化。一般来说，取满足需要的最简便的可行形式即可。

这样得到的插值多项式一般会随所给已知点数量和位置的不同而不同，而且给定的已知点的取值可以非常随意，这也表明符合要求的插值多项式原则上可以有无穷多个。

=== 拉格朗日插值法 ===
上述的待定系数法的明显不足是需要求解方程组，拉格朗日插值法避免了这个麻烦的步骤。作为代价，它采用了复杂但是巧妙的构造，而且也容易在各个已知点上验证其正确性。

==== 2个点与3个点的插值 ====
[[File:Lagrange portrait.jpg |thumb |150px |法国数学家约瑟夫·拉格朗日（Joseph Lagrange，1736年－1813年）在数学和物理学的诸多领域都有重大贡献。]]

'''拉格朗日插值法'''（'''Lagrange polynomial interpolation'''）是一种不需要求解方程就可以直接获得插值函数的方法。它曾被好几个人独立地提出过，最后以法国数学家[[w:约瑟夫·拉格朗日|约瑟夫·拉格朗日]]（1736年－1813年）冠名。

要求经过<math>A(x_1, y_1), B(x_2, y_2)</math>这2个固定点的插值函数，拉格朗日插值法给出的答案是：<br />
<math>y = y_1 \cdot \frac{x - x_2}{x_1 - x_2} + y_2 \cdot \frac{x - x_1}{x_2 - x_1}</math>

要求经过<math>A(x_1, y_1), B(x_2, y_2), C(x_3, y_3)</math>这3个固定点的插值函数，拉格朗日插值法给出的答案是：<br />
<math>y = y_1 \cdot \frac{(x - x_2)(x - x_3)}{(x_1 - x_2)(x_1 - x_3)} + y_2 \cdot \frac{(x - x_1)(x - x_3)}{(x_2 - x_1)(x_2 - x_3)} + y_3 \cdot \frac{(x - x_1)(x - x_2)}{(x_3 - x_1)(x_3 - x_2)}</math>

==== 多个点的插值 ====
<blockquote style="padding: 1em; border: 2px dotted;">
<font color="#008000">对某个多项式函数，已知有给定的k+1个取值点<math>(x_0, y_0), (x_1, y_1), \ldots, (x_k, y_k)</math>，假设任意两个不同的''x''<sub>''j''</sub>都互不相同，那么一般形式的拉格朗日插值公式被定义为：<br />
:<math>L(x) := \sum_{j=0}^{k} y_j \ell_j(x)</math><br />
其中每个<math>\ell_j(x)</math>为'''拉格朗日基本多项式'''（或称'''插值基函数'''），其表达式为：<br />
:<math>\ell_j(x) := \prod_{i=0,\, i\neq j}^{k} \frac{x-x_i}{x_j-x_i} = \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots \frac{(x-x_{k})}{(x_j-x_{k})}.</math><ref>{{cite web |url= https://ccrma.stanford.edu/~jos/Interpolation/Lagrange_Interpolation.html |title=Lagrange Interpolation |author=Julius Orion Smith III |publisher=Center for Computer Research in Music and Acoustics (CCRMA), ''[[w:Stanford University|Stanford University]]'' |language=en |accessdate=2009-12-22 |archive-date=2009-06-28 |archive-url=https://web.archive.org/web/20090628090440/http://ccrma.stanford.edu/~jos/Interpolation/Lagrange_Interpolation.html |dead-url=no}}</ref>
</font>
</blockquote>

拉格朗日基本多项式<math>\ell_j(x)</math>的特点是在<math>x_j</math>上取值为1，在其它的点<math>x_i, \quad (i \neq j)</math>上取值为0。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：拉格朗日公式给出的的确是多项式，虽然它可能初看上去长得像一连串的[[w:分式|分式]]之和。

拉格朗日插值法的公式结构整齐紧凑，可以直接套用，避免了解方程组的繁琐，多项式结果的存在性也比较明显。

==== 拟合数列的通项 ====
由于数列可以看成是取值离散的特殊函数（因此有人也称呼数列为“整标函数”），我们不多做说明，直接通过例题了解拉格朗日插值法在数列插值中的应用。

<!-- 本小节例题1 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题1：
已知数列<math>\{a_n\}</math>满足<math>a_1 = 1, a_2 = 100, a_3 = 10000</math>，求符合给定的这前3项的一个数列通项公式。

<!-- 本小节例题1的解答 -->
<div class="collapsible answer" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>解答：<br />
 由拉格朗日插值公式可得：<br />
 <math>
 \begin{array}{l}
  a_n = a_1 \cdot \frac{(n - 2)(n - 3)}{(1 - 2)(1 - 3)} + a_2 \cdot \frac{(n - 1)(n - 3)}{(2 - 1)(2 - 3)} + a_3 \cdot \frac{(n - 1)(n - 2)}{(3 - 1)(3 - 2)} \\
  = \frac{a_1}{2} \cdot (n - 2)(n - 3) - a_2 \cdot (n - 1)(n - 3) + \frac{a_3}{2} \cdot (n - 1)(n - 2) \\
  = \frac{1}{2} \cdot (n - 2)(n - 3) - 100 \cdot (n - 1)(n - 3) + \frac{10000}{2} \cdot (n - 1)(n - 2) \\
  = \frac{9801}{2} n^2 - \frac{29205}{2} n + 9703
 \end{array}
 </math>
 </p>
</div>
<div class="collapsible finalAnswer" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243); color: red;">
 <p>答案：<math>a_n = \frac{9801}{2} n^2 - \frac{29205}{2} n + 9703 \quad (n \in \mathbb{Z})</math>或其它同样满足题意的解。</p>
</div>

<!-- 本小节例题2 -->
[[File:Crystal Clear action edit.png | Crystal Clear action edit | 50px]]
相关例题2：
已知数列<math>\{a_n\}</math>满足<math>a_1 = 1, a_2 = 11, a_3 = 112, a_4 = 1122</math>，求符合给定的这前4项的一个数列通项公式。

<!-- 本小节例题2的解答 -->
<div class="collapsible answer" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243);">
 <p>解答：<br />
 <math>
 \begin{array}{l}
  a_n = a_1 \cdot \frac{(n - 2)(n - 3)(n - 4)}{(1 - 2)(1 - 3)(1 - 4)} + a_2 \cdot \frac{(n - 1)(n - 3)(n - 4)}{(2 - 1)(2 - 3)(2 - 4)} + a_3 \cdot \frac{(n - 1)(n - 2)(n - 4)}{(3 - 1)(3 - 2)(3 - 4)} + a_4 \cdot \frac{(n - 1)(n - 2)(n - 3)}{(4 - 1)(4 - 2)(4 -3)} \\
  = - \frac{a_1}{6} \cdot (n - 2)(n - 3)(n - 4) + \frac{a_2}{2} \cdot (n - 1)(n - 3)(n - 4) - \frac{a_3}{2} \cdot (n - 1)(n - 2)(n - 4) + \frac{a_4}{6} \cdot (n - 1)(n - 2)(n - 3) \\
  = - \frac 1 6 \cdot (n - 2)(n - 3)(n - 4) + \frac{11}{2} \cdot (n - 1)(n - 3)(n - 4) - \frac{112}{2} \cdot (n - 1)(n - 2)(n - 4) + \frac{1122}{6} \cdot (n - 
1)(n - 2)(n - 3) \\
  = \frac{409}{3} n^3 - \frac{1545}{2} n^2 + \frac{8239}{6} n - 736
 \end{array}
 </math>
 </p>
</div>
<div class="collapsible finalAnswer" style="clear both; border:thin solid rgb(167, 215, 249); background-color: rgb(243, 243, 243); color: red;">
 <p>答案：<math>a_n = \frac{409}{3} n^3 - \frac{1545}{2} n^2 + \frac{8239}{6} n - 736 \quad (n \in \mathbb{Z})</math>或其它同样满足题意的解。</p>
</div>

== 计算机求解 ==
=== Mathematica ===
[[w:Wolfram Mathematica|Mathematica]]软件提供了专门的内置命令“InterpolatingPolynomial”用于生成最常见的几种插值多项式，其语法格式为：<ref>{{cite web |url= https://reference.wolfram.com/language/ref/InterpolatingPolynomial.html |title=InterpolatingPolynomial - Wolfram语言参考资料 |author= |publisher=Wolfram Alpha官方网站 |language=zh-cn |date=2020年 |access-date=2020年12月27日}}</ref><br />
<syntaxhighlight lang="Mathematica">
InterpolatingPolynomial[{f1,f2,…},x]; (* 构建一个关于 x 的插值多项式，在连续的 x 的整数值 1、2、… 上再生成函数值 f_(i) *)
InterpolatingPolynomial[{{x1,f1},{x2,f2},…},x]; (* 对于函数值 f_(i)，对应于 x 的值 x_(i) 构建一个插值多项式 *)
InterpolatingPolynomial[{{{x1,y1,…},f1},{{x2,y2,…},f2},…},{x,y,…}]; (* 构建一个使用变量 x、y、… 的多维插值多项式 *)
InterpolatingPolynomial[{{{x1,…},f1,df1,…},…},{x,…}]; (* 构建一个插值多项式，同时拟合函数值及其导数 *)
</syntaxhighlight>

可以看到，Mathematica不仅支持本节主要讲述的简单的函数值插值，也支持多元函数的插值，还支持生成可以同时拟合目标函数值及其导数值的插值多项式。

[[File:Crystal Clear action info.png | Crystal Clear action info | 50px]]
提示：使用多项式同时拟合函数及其导数是一个比较强的限制条件。[[w:埃尔米特多项式|埃尔米特多项式]]就是满足这一要求的例子。

给定有限个点的函数插值示例（因为只有一行命令，分号此时可以不写）：
<syntaxhighlight lang="Mathematica">
InterpolatingPolynomial[{{-1, 4}, {0, 2}, {1, 6}}, x];
</syntaxhighlight>

给定有限个项的数列插值示例：
<syntaxhighlight lang="Mathematica">
InterpolatingPolynomial[{1, 4, 9, 16}, n];
</syntaxhighlight>

== 补充习题 ==
[[File:Crystal Clear app ksirtet.png | Crystal Clear app ksirtet | 50px]]
[[File:Crystal Clear app laptop battery.png | Crystal Clear app laptop battery | 50px]]

== 参考资料 ==
{{Reflist}}

== 外部链接 ==
{{wikipedia|插值}}
{{wikipedia|拉格朗日插值法}}
* <ref>{{cite web |url= https://demonstrations.wolfram.com/InterpolatingPolynomial/ |title=InterpolatingPolynomial - Wolfram Demonstrations Project |author= |publisher=Wolfram Alpha官方网站 |language=zh-cn |date=2011年3月7日 |access-date=2020年12月27日}}</ref>（通过交互式动画演示插值点对所得多项式图形的影响）

{{DEFAULTSORT: interpolation methods}}
[[category:函数]]
[[category:高中数学]]