查看“︁拉格朗日插值法”︁的源代码

{{NoteTA |G1=Math}}
[[File:Lagrange polynomial.svg|300px|thumb|已知平面上4个点：<font color=#6495ed>(−9, 5)</font>, <font color=#ddaa00>(−4, 2)</font>, <font color=#9acd32>(−1, −2)</font>, <font color=#ee7700>(7, 9)</font>，拉格朗日多项式：<font color=#000000>''L''（''x''）</font>（黑色）穿过所有点。而每个基本多项式：<font color=#6495ed>y<sub>0</sub>''ℓ''<sub>0</sub>(''x'')</font>, <font color=#ddaa00>y<sub>1</sub>''ℓ''<sub>1</sub>(''x'')</font>, <font color=#9acd32>y<sub>2</sub>''ℓ''<sub>2</sub>(''x'')</font>以及<font color=#ee7700>y<sub>3</sub>''ℓ''<sub>3</sub>(''x'')</font>各穿过对应的一点，并在其它的三个点的''x''值上取零。]]

在[[数值分析]]中，'''拉格朗日插值法'''是以[[法国]]18世纪[[数学家]][[约瑟夫·拉格朗日]]命名的一种[[多项式插值]]方法。许多实际问题中都用[[函数]]来表示各結果之間某种内在联系或规律，而不少函数都只能通过繁複实验和多次观测来了解。而，如果对实践中的某个[[物理]]量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个[[多项式]]，其恰好在各个观测的点取到观测到的值。上面这样的多项式就称为'''拉格朗日（插值）多项式'''（Lagrange polynomial）。[[数学]]上来说，拉格朗日插值法可以给出一个恰好穿过二维[[平面 (数学)|平面]]上若干个已知点的多项式函数。拉格朗日插值法最早被[[英国]]数学家[[爱德华·华林]]于1779年发现<ref>{{cite journal
 |author = E. Waring
 |year = 1779
 |title = Problems Concerning Interpolations
 |journal = Philosophical Transactions of the Royal Society of London
 |volume = 69
 |pages = 59-67
}}</ref>，不久后（1783年）由[[莱昂哈德·欧拉]]再次发现。1795年，拉格朗日在其著作《师范学校数学基础教程》中发表这个插值方法，从此他的名字就和这个方法联系在一起<ref>{{en}}{{cite journal |title = ''A chronology of interpolation: From ancient astronomy to modern signal and image processing,'' |author=E. Meijering |journal=Proceedings of the IEEE |volume = 90 |page = 323 }} </ref>。

对于给定的若'''n+1'''个点<math>(x_0, y_0),(x_1, y_1),\ldots,(x_n, y_n)</math>，对应于它们的次数不超过'''n'''的拉格朗日多项式<math>\scriptstyle L</math>只有一个。如果计入次数更高的多项式，则有无穷个，因为所有与<math>\scriptstyle L</math>相差<math>\lambda (x-x_0)(x-x_1)\ldots(x-x_n)</math>的多项式都满足条件。

==定义==
对某个多项式[[函数]]，已知有给定的''k'' + 1个取值点：

:<math>(x_0, y_0),\ldots,(x_k, y_k)</math>

其中<math>x_j</math>对应着[[自变量]]的位置，而<math>y_j</math>对应着函数在这个位置的取值。

假设任意两个不同的''x''<sub>''j''</sub>都互不相同，那么应用拉格朗日插值公式所得到的'''拉格朗日插值多项式'''为：

:<math>L(x) := \sum_{j=0}^{k} y_j \ell_j(x)</math>

其中每个<math>\ell_j(x)</math>为'''拉格朗日基本多项式'''（或称'''插值基函数'''），其表达式为：

:<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>{{en}}{{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), ''Stanford University''|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>

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

==範例==
假设有某个二次多项式函数<math>f</math>，已知它在三个点上的取值为：
*<math>f(4) = 10 </math>
*<math>f(5) = 5.25 </math>
*<math>f(6) = 1 </math>
要求<math> f(18) </math>的值。

首先写出每个拉格朗日基本多项式：

:<math>\ell_0(x) = \frac{(x-5)}{(4-5)}\cdot\frac{(x-6)}{(4-6)}</math>
:<math>\ell_1(x) = \frac{(x-4)}{(5-4)}\cdot\frac{(x-6)}{(5-6)}</math>
:<math>\ell_2(x) = \frac{(x-4)}{(6-4)}\cdot\frac{(x-5)}{(6-5)}</math>

然后应用拉格朗日插值法，就可以得到<math>p</math>的表达式（<math>p</math>为函数<math>f</math>的插值函数）：

:<math> p(x) = f(4)\ell_0(x) + f(5)\ell_1(x) + f(6)\ell_2(x)</math>
:<math>.\, \, \, \, \, \, \, \, \, \, = 10 \cdot \frac{(x-5)(x-6)}{(4-5)(4-6)} + 5.25 \cdot \frac{(x-4)(x-6)}{(5-4)(5-6)} + 1 \cdot \frac{(x-4)(x-5)}{(6-4)(6-5)} </math><br><math>.\, \, \, \, \, \, \, \, \, \, = \frac{1}{4}(x^2 - 28x + 136)</math><br>
此時代入数值<math>\ 18</math>就可以求出所需之值：<math>\ f(18)= p(18)= -11 </math>。

==证明==

===存在性===
对于给定的''k''+1个点：<math>(x_0, y_0),\ldots,(x_k, y_k)</math>，拉格朗日插值法的思路是找到一个在一点<math>x_j</math>取值为'''1'''，而在其他点取值都是'''0'''的多项式<math>\ell_j(x)</math>。这样，多项式<math>y_j \ell_j(x)</math>在点<math>x_j</math>取值为<math>y_j</math>，而在其他点取值都是'''0'''。而多项式<math>L(x) := \sum_{j=0}^{k} y_j \ell_j(x)</math>就可以满足

:<math>L(x_j) = \sum_{i=0}^{k} y_i \ell_i(x_j) = 0 + 0 + \cdots + y_j + \cdots + 0 = y_j</math>

在其它点取值为'''0'''的多项式容易找到，例如：
:<math>(x-x_0) \cdots (x-x_{j-1})(x-x_{j+1}) \cdots (x-x_{k})</math>
它在点<math>x_j</math>取值为：<math>(x_j-x_0) \cdots (x_j-x_{j-1})(x_j-x_{j+1}) \cdots (x_j-x_{k})</math>。由于已经假定<math>x_i</math>两两互不相同，因此上面的取值不等于'''0'''。于是，将多项式除以这个取值，就得到一个满足“在<math>x_j</math>取值为'''1'''，而在其他点取值都是'''0'''的多项式”：
:<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>
这就是拉格朗日基本多项式。

===唯一性===
次数不超过''k''的拉格朗日多项式至多只有一个，因为对任意两个次数不超过''k''的拉格朗日多项式：<math>P_1</math>和<math> P_2</math>，它们的差<math> P_1 - P_2</math>在所有''k''+1个点上取值都是'''0'''，因此必然是多项式<math>(x-x_0)(x-x_{1}) \cdots (x-x_{k})</math>的倍数。因此，如果这个差<math> P_1 - P_2</math>不等于'''0'''，次数就一定不小于''k''+1。但是<math> P_1 - P_2</math>是两个次数不超过''k''的多项式之差，它的次数也不超过''k''。所以<math> P_1 - P_2 = 0</math>，也就是说<math> P_1 = P_2</math>。这样就证明了唯一性<ref>冯有前，《数值分析》，第63页</ref>。

==几何性质==
拉格朗日插值法中用到的拉格朗日基本多项式<math>\ell_0, \ell_1, \cdots , \ell_n</math>（由某一组<math>x_0 < x_1 < \cdots < x_n</math>确定）可以看做是由次数不超过'''n'''的多项式所组成的[[线性空间]]：<math>\mathbb{K}_n[X]</math>的一组[[基底]]。首先，如果存在一组[[系数]]：<math>\lambda_0, \lambda_1, \cdots , \lambda_n</math>使得，
:<math>P = \lambda_0 \ell_0 + \lambda_1 \ell_1 + \cdots +  \lambda_n \ell_n = 0</math>，

那么，一方面多项式'''P'''是满足<math>P(x_0) = \lambda_0, P(x_1) = \lambda_1, \cdots, P(x_n) = \lambda_n</math>的拉格朗日插值多项式，另一方面'''P'''是零多项式，所以取值永远是'''0'''。所以
:<math>\lambda_0 = \lambda_1 = \cdots = \lambda_n = 0</math>。
这证明了<math>\ell_0, \ell_1, \cdots , \ell_n</math>是[[线性无关]]的。同时它一共包含'''n+1'''个多项式，恰好等于<math>\mathbb{K}_n[X]</math>的维数。所以<math>\ell_0, \ell_1, \cdots , \ell_n</math>构成了<math>\mathbb{K}_n[X]</math>的一组基底。

拉格朗日基本多项式作为基底的好处是所有的多项式都是齐次的（都是'''n'''次多项式）。

==优点与缺点==
拉格朗日插值法的公式结构整齐紧凑，在理论分析中十分方便，然而在计算中，当插值点增加或减少一个时，所对应的基本多项式就需要全部重新计算，于是整个公式都会变化，非常繁琐<ref>李庆扬，《数值分析》第4版，第31页</ref>。这时可以用重心拉格朗日插值法或[[牛顿插值法]]来代替。此外，当插值点比较多的时候，拉格朗日插值多项式的次数可能会很高，因此具有[[数值稳定性|数值不稳定]]的特点，也就是说尽管在已知的几个点取到给定的数值，但在附近却会和“实际上”的值之间有很大的偏差（如右下图）<ref>冯有前，《数值分析》，第64页</ref>。这类现象也被称为[[龙格现象]]，解决的办法是分段用较低次数的插值多项式。

==重心拉格朗日插值法==

重心拉格朗日插值法是拉格朗日插值法的一种改进。在拉格朗日插值法中，运用多项式
:<math>\ell(x) = (x - x_0)(x - x_1) \cdots (x - x_k)</math>

[[File:Lagrange polynomial Divergence.jpg|thumb|460px|拉格朗日插值法的数值稳定性：如图，用于模拟一个十分平稳的函数时，插值多项式的取值可能会突然出现一个大的偏差（图中的14至15中间）]]
可以将拉格朗日基本多项式重新写为：

:<math>\ell_j(x) = \frac{\ell(x)}{x-x_j} \frac{1}{\prod_{i=0,i \neq j}^k(x_j-x_i)}</math>
定义'''重心权'''<ref name="bary">{{cite journal
 |url     = http://www.comlab.ox.ac.uk/nick.trefethen/barycentric.pdf
 |author  = Jean-Paul Berrut, Lloyd N. Trefethen
 |year    = 2004
 |title   = Barycentric Lagrange Interpolation
 |journal = [[Society for Industrial and Applied Mathematics|SIAM]] Review
 |volume  = 46
 |issue   = 3
 |pages   = 501–517
 |doi     = 10.1137/S0036144502417715
}}{{dead link|date=2017年12月 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref>{{cite journal
 |author = 王兆清，李淑萍，唐炳涛
 |year = 2007
 |title = 一维重心型插值：公式、算法和应用
 |journal = 山东建筑大学学报
 |volume = 22
 |issue = 5
 |pages = 447–453
}}</ref>
:<math>w_j = \frac{1}{\prod_{i=0,i \neq j}^k(x_j-x_i)}</math>

上面的表达式可以简化为：
:<math>\ell_j(x) = \ell(x)\frac{w_j}{x-x_j}</math>
于是拉格朗日插值多项式变为：
:<math>L(x) = \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}y_j \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)</math>

即所谓的重心拉格朗日插值公式（第一型）或改进拉格朗日插值公式。它的优点是当插值点的个数增加一个时，将每个<math>w_j</math>都除以<math>(x_j - x_{k+1})</math>，就可以得到新的重心权<math>w_{k+1}</math>，计算复杂度为<math>\mathcal O(n)</math>，比重新计算每个基本多项式所需要的复杂度<math>\mathcal O(n^2)</math>降了一个量级。

将以上的拉格朗日插值多项式用来对函数<math>g(x)\equiv 1</math>插值，可以得到：

:<math>\forall x, \, g(x) = \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}</math>
因为<math>g(x)\equiv 1</math>是一个多项式。

因此，将<math>L(x)</math>除以<math>g(x)</math>后可得到：

:<math>L(x) = \frac{\sum_{j=0}^k \frac{w_j}{x-x_j}y_j}{\sum_{j=0}^k \frac{w_j}{x-x_j}} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)</math><ref name="bary"/>

这个公式被称为重心拉格朗日插值公式（第二型）或真正的重心拉格朗日插值公式。它继承了（1）式容易计算的特点，并且在代入''x''值计算<math>L(x)</math>的时候不必计算多项式<math>\ell(x)</math><ref name="bary"/>。它的另一个优点是，结合[[切比雪夫多项式|切比雪夫节点]]进行插值的话，可以很好地模拟给定的函数，使得插值点个数趋于无穷时，最大偏差趋于零<ref name="bary"/>。同时，重心拉格朗日插值结合[[切比雪夫多项式|切比雪夫节点]]进行插值可以达到极佳的数值稳定性。第一型拉格朗日插值是[[数值稳定性|向后稳定]]的，而第二型拉格朗日插值是向前稳定的，并且[[勒贝格常数]]很小<ref>{{cite journal
 |url = http://imajna.oxfordjournals.org/cgi/reprint/24/4/547.pdf
 |author = NICHOLAS J. HIGHAM
 |year = 2004
 |title = The numerical stability of barycentric Lagrange Interpolation
 |journal = IMA Journal of Numerical Analysis
 |volume = 24
 |issue = 4
 |pages = 547–556
}}</ref>。

== 参考文献 ==
=== 引用 ===
{{Reflist|2}}

=== 来源 ===
;书籍
* {{cite book |title =《数值分析》|edition = 第4版 |author = 李庆扬、王能超、易大义 |publisher=清华大学出版社 |year=2001 |ISBN = 7-302-04561-5 |language = zh-hans}}
* {{cite book |title=《数值分析》|author = 冯有前 |publisher = 清华大学出版社 |year=2001 |ISBN = 7-810-82495-3 |language = zh-hans}}
* {{cite web|url=http://www.tyut.edu.cn/kecheng/jisff/dzja/ch5/ch5-2.htm|title=拉格朗日插值多项式|author=|publisher=太原理工大学|language=zh-hans|deadurl=yes|archiveurl=https://web.archive.org/web/20080609165823/http://www.tyut.edu.cn/kecheng/jisff/dzja/ch5/ch5-2.htm|archivedate=2008-06-09}}

== 参见 ==
{{Portal box|数学}}
* [[约瑟夫·拉格朗日]]
* [[多项式插值]]
* [[样条插值]]
* [[伯恩斯坦多项式]]
* [[牛顿多项式]]
* [[龙格现象]]

{{約瑟夫·拉格朗日}}
[[Category:多项式]]
[[Category:插值论]]
[[Category:数学近似]]

[[he:אינטרפולציה#צורת לגראנז']]