以內插多項式來做數值積分

前情提要: 數值積分初探

連續函數可以用多項式來逼近它, 因此直覺來講, 既然我們已經找到一個離給定函數"很近"的多項式了, 何不就以這個多項式的積分值來當成原函數積分值的一個逼近呢.

Goal: 任意給定一可積分函數 $f(x)$, $x\in[-1, 1]$, 我們想要算 $\int^1_{-1} f(x) dx$.

我們先講內插多項式

給定任意 $n+1$ 個不重複的點在 $[-1, 1]$ 區間, 我們把他們記為 $x_0, x_1, \cdots, x_n.$ 接著我們計算函數 $f(x)$ 在這些點上的值, 記為 $f_i = f(x_i)$, 這樣我們就有平面上的 $n+1$ 個點座標 $(x_i, f_i)$.

有這些點我們就一定能找到一個 $n$ 次多項式 $p_n(x)$ 使得說這個多項式會通過這些所有的點, 也就是 $p_n(x_i) = f_i$. 這就叫做內插多項式.

內插多項式一個很簡潔的表示法是把它寫成 Lagrange polynomial 的樣子. 我們先引進 Lagrange basis function $$ \ell_i(x) = \prod^n_{k=0, k\ne i} \frac{x-x_k}{x_i-x_k}. $$ 很明顯可以看出這是一個 $n$ 次多項式, 而且有很特殊的性質, 也就是 $\ell_i(x_j)=\delta_{ij}$.

$\delta_{ij}$ 是所謂的 Kronecker delta function, 如果 $i=j$ 則 $\delta_{ij}=1$, 反之如果 $i\ne j$ 則 $\delta_{ij}=0$. 舉例來說, $\delta_{11}=1$, 而 $\delta_{12}=0$.

因此我們可以將內插多項式 $p_n(x)$ 改寫成 $$ p_n(x) = \sum^n_{i=0} f_i \ell_i(x). $$ 這就是內插多項式的 Lagrange 表示法.

接著我們就可以來做積分了!

我們直接以內插多項式來逼近函數並做積分, $$ \int^1_{-1} f(x)dx \approx \int^1_{-1} p_n(x)dx = \int^1_{-1} \sum^n_{i=0} f_i \ell_i(x)dx = \sum^n_{i=0} f_i \left(\int^1_{-1} \ell_i(x)dx\right). $$ 理論上, 如果插值點 $x_i$ 是一開始就給定並且固定的, 那我們就可以把 Lagrange basis function $\ell_i(x)$ 算出來, 並且把他的積分也算出來. 我們把積分出來的值記為 $w_i$, 也就是 $$ w_i = \int^1_{-1} \ell_i(x)dx. $$ 如此我們就可以把積分改寫成 $$ \int^1_{-1} f(x)dx \approx \sum^n_{i=0} w_i f_i. $$ 這就是以內插多項式來做積分.

Remark: 如果 $f(x)$ 本身就是個 $n$ 次或以下的多項式, 那我們做出來的內插多項式就不是 approximation 而是等號了. 那這樣我們做出來的積分事實上應該就是等號! 也就是說 $$ \int^1_{-1} p(x)dx = \sum^n_{i=0} w_i f_i, $$ where $p(x)$ is a polynomial with degree less than or equals to $n$.

舉個簡單的例子來試試

假設我們只想要用兩個端點來估算積分, 那我們有 $x_0=-1, x_1=1$. 因此得到 Lagrange basis polynomials $$ \ell_0(x) = \frac{x+1}{2}, \quad \ell_1(x)=\frac{x-1}{-2}. $$ 接著可以算出 $$ w_0 = \int^1_{-1} \ell_0(x)dx = 1, \quad w_1=\int^1_{-1}\ell_1(x)dx=1. $$ 也就是說 $$ \int^1_{-1} f(x)dx \approx f(-1) + f(1), $$ 得到所謂的梯形法!

延伸閱讀: 高斯積分