數值方法/插值

插值

多項式插值

插值是一種將離散資料點擴充套件到函式的方法。如果給定的資料點在$\mathbf {R} ^{2}$ 中，則多項式插值很常見。多項式插值背後的主要思想是，給定n+1個離散資料點，存在一個唯一的n階多項式來擬合這些資料點。一般來說，低階多項式是不可能的，高階多項式是不唯一的。如果多項式$p(x)$ 定義為

$p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}$

則可以用以下系統求解未知係數

${\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.$

其中$x_{0}\ldots x_{n}$ 是給定的資料點。系統中的矩陣稱為範德蒙矩陣。假設所有資料點都是不同的，則範德蒙矩陣是非奇異的，因此係統可以唯一地求解。

如果要插值的資料點的數量變大，多項式的次數也會變大，這可能會導致資料點之間出現振盪，並增加誤差。對於大量資料點，建議使用其他方法。

徑向基函式

科學和工程中的一個常見問題是多元插值一個函式f，它的值僅在有限的點集上已知。因此，令$\Omega \subset \mathbf {R} ^{d}$ 是一個開放的有限域。給定一組不同的點X和實數，任務是構造一個函式$s:\mathbf {R} ^{d}\rightarrow \mathbf {R}$，滿足插值條件

$s(x_{i})=f_{i}$

在過去的幾十年裡，徑向基函式插值方法在空間中X上的點分佈不規則的問題中越來越受歡迎。在基本形式中，徑向基函式插值選擇一個固定的函式 $\phi :\mathbf {R_{+}} \rightarrow \mathbf {R}$ 並透過 $\phi$ 定義一個插值函式，其中係數 $c_{i}$ 是實數，對於 $\|\cdot \|$ 通常選擇歐幾里德範數，而 $\phi$ 是一個徑向基函式。

我們可以看到，近似函式s 是徑向對稱函式的線性組合，每個函式都以一個確定的點 $x_{i}$ 為中心。點 $x_{i}$ 通常被稱為 RBF 插值的中心 或配置點。這種方法可以追溯到 Hardy，他早在 1971 年就使用多二次 RBF 從一組分散的測量資料中重建地理表面。還要注意，中心 $x_{i}$ 可以位於域中的任意點，不需要網格。對於某些 RBF，指數收斂已經得到證明。徑向基函式已成功應用於各種問題，例如計算機圖形學、神經網路、透過配置方法求解微分方程以及許多其他問題。

其他流行的 $\phi$ 選擇包括高斯函式和所謂的薄板樣條，由 Duchon 在 1970 年代發明。薄板樣條是透過求解變分問題得到的。薄板樣條的優點是它們的條件數在縮放下保持不變。另一類函式是 Wendland 的緊支撐 RBF，它們與眾不同，因為它們會導致稀疏插值矩陣，因此可以有效地求解生成的線性系統。然而，問題的條件數會隨著中心的數量而惡化。當使用具有全域性支援的 RBF 進行插值時，矩陣A 通常會隨著中心的增加而變得病態。高斯函式、多二次函式和反多二次函式是無限平滑的，並涉及一個尺度或形狀引數， $\epsilon$ > 0。\ref{fig:var-eps2} 顯示了具有不同 $\epsilon$ 值的高斯 RBF。減小 $\epsilon$ 往往會使基函式變平。對於給定的函式，近似的質量可能很大程度上取決於此引數。特別地，增加 $\epsilon$ 會改善條件數（縮放後點的分離距離 $q_{X}:=min\,\,\Vert x_{j}-x_{k}\Vert$ 會增加）。

求解插值問題會導致以下線性方程組

$Ac=f$

其中 $a_{ij}=\phi (\|x_{i}-x_{j}\|),c=(c_{j})_{j=1,...,N},f=(f_{j})_{j=1,...,N}.$ 。因為只有點之間的距離出現在 *A* 中，所以解決該系統的努力與空間維度無關，這在更高維度插值時尤其重要。Franke 在 1982 年提出一個問題，即矩陣 *A* 是否非奇異，因此對於任何 *f* 的選擇，都保證存在唯一的插值函式。幾年後，Micchelli 和 Madych 及 Nelson 的結果獨立證明了這一猜想對於許多有用的 RBF 都是成立的。唯一的條件是至少有兩個中心，並且所有中心都是不同的。薄板樣條是一個例外，對於非平凡的點分佈，矩陣 *A* 可能為奇異。例如，如果點 $x_{2},...,x_{n}$ 分佈在中心 $x_{1}$ 周圍的單位球面上，那麼第一行和第一列將包含零。解決這個問題的方法是將一個 *m* 度多項式 *p* ($m\geq 1$) 新增到插值函式中，這樣插值函式就變成了

$s(x)=\sum _{j=1}^{N}c_{i}\phi (\|x-x_{j}\|)+p(x)$

並要求節點是 *不溶解的* ($\Pi _{d}^{m}$)，這意味著每個多項式 $p\in \Pi _{d}^{m}$ 都由它在 *X* 上的值決定。$p\in \Pi _{d}^{m}$ 表示 *n* 個變數中所有多項式到 *m* 次的集合，而 $p_{k}$ 是此空間的標準基多項式。如果所有點都不同，則點集對於 $\Pi _{0}^{d}$ 是不溶解的，如果並非所有點都排列在一條線上，則對於 $\Pi _{1}^{d}$ 是不溶解的。

現在的插值條件是

$\sum _{j=1}^{N}c_{j}\phi (\Vert x_{i}-x_{j}\Vert )+\sum _{j=1}^{l}d_{j}p_{j}(x_{i})=f_{i},\qquad i=1,...,N$

由於插值條件導致在N + l個未知數中存在N個方程，因此該系統是欠定的。 因此，施加額外的邊條件，這些條件代表了多項式再生的性質。 這意味著，如果資料來自多項式 $p\in {\mathcal {P}}_{m}^{d}$，即$f_{i}=p(x_{i})$，那麼插值函式s必須與p一致。 這些條件相當於

$\sum _{j=1}^{l}d_{j}p_{j}(x_{i})=0,\quad 1\leq i\leq l.$

為了找到c和d，我們需要求解線性方程組

$A\,c+P\,d=f,\qquad P^{T}c=0,$

其中$P_{ij}=p_{j}(x_{i})$，A的定義如上所述。 這些方程可以總結為

如果函式 $\phi$ 屬於以下函式類別，則該系統有唯一的解。

定義 連續函式 $\Phi :\mathbf {R} ^{d}\rightarrow \mathbf {R}$ 被稱為條件正定m階，簡稱為 $\Phi \in CPDm$，如果對於 每個不同的點集 $X=\{x_{1},...,x_{N}\}\subset \Omega$ 和對於每個複數值集 $\{c_{1},...,c_{N}\}$，其中

$P\,\,c=\sum _{j=1}^{N}c_{j}p(x_{j})=0\qquad for\,all\,p\in \Pi _{m}^{d}$

二次形式

$c\,\,A\,\,c^{T}=\sum _{j=1}^{N}\sum _{k=1}^{N}c_{j}c_{k}\Phi (x_{j}-x_{k})\geq 0$

為正數。如果此外，$c\,\,A\,\,c^{T}=0$ 意味著 $c=0$，那麼 $\phi$ 被稱為嚴格的 m 階 CPD。對於 $m=0$，$\Phi$ 被稱為正定。

如果徑向基函式 $\phi (\|x-y\|)=\Phi (x-y)$ 被稱為條件正定，如果相應的多元函式 $\Phi$ 是條件正定的。

如果一個函式是正定的，那麼相應的插值矩陣也是正定的。TPS 和 MQ 是條件正定函式，Gau、IMQ 和 Wen 是正定函式。

除了證明問題是適定的，還需要證明收斂性。然而，對於大多數 RBF，收斂性只在無限方形網格上的全域性插值中得到保證。對於薄板樣條函式，區域性插值的收斂性證明也是已知的。

廣義厄米特插值問題

插值問題也可以用點評估表示，即對函式 *f* 作用狄拉克 δ 函式。如果 ${\mathcal {S}}$ 是一個向量空間，那麼對應於 *x* 的狄拉克 δ 函式 $\delta _{x}$ 定義為

$\delta _{x}(f)=f(x),\quad f\in {\mathcal {S}}$

資料透過以下方式生成

$f_{j}=\int f(x)\delta (x-x_{j})dx$

如前所述，設 $\{x_{1},...,x_{N}\}$ 為中心。更一般地說，資料可以由任何一組線性泛函 $\lambda _{1},...,\lambda _{N}$ 作用於某個函式 *f* 生成。為了避免冗餘資料，這些分佈需要相互獨立。 $\lambda _{i}$ 不限於點評估，可以是任意線性泛函，包括微分和差分運算元。這個問題包括 Hermite 函式和 ${\mathcal {E}}'$，即所有緊支撐分佈的集合。對於一個分佈 $\lambda \in {\mathcal {E}}'$，對應一個線性泛函，它透過分佈的卷積作用於 $f\in {\mathcal {E}}$。它可以寫成

$(\lambda ,f)=\int (\lambda *f)(x)dx=\int f(y)\lambda (x-y)dy$

現在，任務是在給定資料的情況下進行插值，$f_{i}=(\lambda _{i},f)$

使得 $s=\Phi *\lambda +p$ 滿足

$(\lambda _{i},s)=f_{i},\quad for\,\,i=1,...,N$

這裡，插值函式的形式為

$s(x)=\sum _{j=1}^{N}c_{j}\lambda _{j}^{y}\phi (\Vert x-y\Vert )+p(x)$

其中，$c_{j}$ 是適當的實係數，而 $\lambda _{j}^{y}$ 表示 $\lambda$ 作用於 $\phi$，將後者視為|y的函式。*

$\sum _{j=1}^{N}\lambda _{j}(p)\phi _{j}(x)=\lambda (p),\quad for\,all\,p\in {\mathcal {P}}_{m}^{d}$

插值矩陣 $A=(a)_{ij}$ 在 \ref{eq:rbf-lgs} 中的條目現在由以下公式給出：

$a_{ij}=\lambda ^{x}\lambda ^{y}\phi (\Vert x-y\Vert )$

如果線性泛函的數量等於中心的數量，並且 $\phi$ 屬於條件正定函式類，則存在唯一解。