簡(jiǎn)介

wikipedia: Neville's method

在數(shù)學(xué)上，Neville 算法是一種計(jì)算插值多項(xiàng)式方法，由數(shù)學(xué)家Eric Harold Neville提出。由給定的n+1個(gè)節(jié)點(diǎn)，存在一個(gè)唯一的冪次≤n的多項(xiàng)式存在，并且通過(guò)給定點(diǎn)。

算法

給定n+1個(gè)節(jié)點(diǎn)及其對(duì)應(yīng)函數(shù)值 \((x_i, y_i)\)，假設(shè) \(P_{i,j}\) 表示 \(j-i\) 階多項(xiàng)式，并且滿足通過(guò)節(jié)點(diǎn) \((x_k, y_k) \quad k =i, i+1, \cdots, j\)。\(P_{i,j}\) 滿足以下迭代關(guān)系

\[\begin{eqnarray} \begin{aligned} & p_{i,i}(x) = y_i \cr & P_{i,j}(x) = \frac{(x_j - x)p_{i,j-1}(x) + (x - x_i)p_{i+1,j}(x)}{x_j - x_i}, \quad 0\le i\le j \le n \end{aligned} \end{eqnarray}\]

以n=4的節(jié)點(diǎn)舉例，其迭代過(guò)程為

\[\begin{eqnarray} \begin{aligned} & p_{1,1}(x) = y_1, \cr & p_{2,2}(x) = y_2, p_{1,2}(x), \cr & p_{3,3}(x) = y_3, p_{2,3}(x), p_{1,3}(x),\cr & p_{4,4}(x) = y_4, p_{3,4}(x), p_{2,4}(x), p_{1,4}(x)\cr \end{aligned} \end{eqnarray}\]

代碼

偽代碼

• 由于計(jì)算插值點(diǎn)為一向量，為避免過(guò)多層循環(huán)嵌套，將每個(gè) \(P_{i,j}\) 都改寫為向量形式，各元素分別儲(chǔ)存多項(xiàng)式在插值點(diǎn) \(x_0\) 處函數(shù)值。
• 只有每次當(dāng)一列 \(P_{i,j}\) 計(jì)算完后，才能利用迭代公式計(jì)算下一列 \(P_{i,j}\) 多項(xiàng)式，因此外層循環(huán)為計(jì)算每列 \(P_{i,j}\) 多項(xiàng)式。
• 每列 \(P_{i,j}\) 個(gè)數(shù)是逐漸減少的，最開始有n個(gè)多項(xiàng)式，最終循環(huán)只有一個(gè)。

可將矩陣P[nRow,nCol]用于存儲(chǔ)多項(xiàng)式 \(P_{i,j}(x)\)。其中每行為 \(P_{i,j}(x_k)\) 在 nCol 個(gè)插值點(diǎn)\(x_k\)處函數(shù)值。每次外層循環(huán) \(P_{i,j}(x)\) 個(gè)數(shù)減少，此時(shí)從最后一行開始舍棄，每次只循環(huán)

for irow = 1: (nRow - icol) %

\(x_i\)與\(x_j\)分別用變量x1與x2代替。迭代公式可表示為

for icol = 1:nRow - 1for irow = 1: (nRow - icol) % x1 = nodes(irow); x2 = nodes(irow + icol);P(irow, :) = ( (x2 - x0).*P(irow, :) + (x0 - x1 ).*P(irow+1, :) )./( x2 - x1 );end% for end% for

最終完整代碼為

function evalPol = f1300000_Neville(x0, nodes, fnodes) % Implement Neville's algorithm to evaluate interpolation polynomial at x0 % Input: % x0 - the point where we want to evaluate the polynomial % nodes - vector containing the interpolation nodes % fnodes - vector containing the values of the function % Output: % evalPol - vector containing the value at x0 of the different % the interpolating polynomialsif iscolumn(x0)x0 = x0'; % transfer to row vector endif isrow(fnodes)fnodes = fnodes'; endnCol = length(x0); nRow = length(nodes);% P = zeros(nRow, nCol); P = repmat(fnodes, 1, nCol);for icol = 1:nRow - 1for irow = 1: (nRow - icol) % x1 = nodes(irow); x2 = nodes(irow + icol);P(irow, :) = ( (x2 - x0).*P(irow, :) + (x0 - x1 ).*P(irow+1, :) )./( x2 - x1 );end% for end% forevalPol = P(1,:); end

轉(zhuǎn)載于:https://www.cnblogs.com/li12242/p/5047042.html

總結(jié)

以上是生活随笔為你收集整理的Neville 插值方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。