Algorytm Neville’a

Algorytm Neville’a – algorytm zaproponowany przez angielskiego matematyka Erica Harolda Neville’a. Jest używany do wyznaczania wartości wielomianu interpolacyjnego (Lagrange’a i Newtona) w danym punkcie $x.$ Ideą jest wyznaczenie rozwiązania w krokach od pojedynczych węzłów do całego ich zbioru.

Biorąc pod uwagę zbiór danych punktów węzłowych $(x_{i},y_{i}),i=1,2,\dots ,n,$ wielomian $P$ jest stopnia nie wyższego niż $n,$ a jego wartości w punktach węzłowych są takie same jak wartości interpolowanej funkcji:

$P(x_{i})=f(x_{i})=y_{i},$     dla $i=1,\dots ,n+1.$

Definiujemy wielomiany interpolacyjne i ich wartości w ustalonym punkcie $x.$

• $p_{i}$ – wartość, w punkcie $x,$ wielomianu stopnia zerowego przechodzącego przez punkt $(x_{i},y_{i}){:}$

$p_{i}=y_{i}=P_{i}(x)$     dla $i=0,\dots ,n.$

• $p_{i(i+1)}$ – wartość, w punkcie $x,$ wielomianu stopnia pierwszego przechodzącego przez punkty $(x_{i},y_{i})$ oraz $(x_{i+1},y_{i+1}){:}$

$p_{i(i+1)}=P_{i(i+1)}(x)$     dla $i=0,\dots ,n-1.$

• $p_{0\ldots n}$ – wartość, w punkcie $x,$ wielomianu stopnia n-tego przechodzącego przez $(n+1)$ punktów $(x_{i},y_{i}){:}$

$p_{0\ldots n}=P_{0\ldots n}(x)$     dla $i=0,\dots ,n.$

Wielomiany powyższego typu spełniają następującą własność rekurencyjną:

$p_{i(i+1)\ldots (i+k)}={\frac {(x-x_{i+k})p_{i(i+1)\ldots (i+k-1)}+(x_{i}-x)p_{(i+1)(i+2)\ldots (i+k)}}{x_{i}-x_{i+k}}},$

gdzie: $k$ odpowiada stopniowi wielomianu, $k=1,\dots ,n$ oraz $i=0,\dots ,n.$

Algorytm Neville’a polega na tym, że za pomocą powyższych wzorów konstruujemy tablicę symetryczną, która zawiera wartości wielomianu interpolacyjnego w ustalonym punkcie $x,$ dla $n=3{:}$

$x_{0},y_{0}=p_{0}$
	$p_{01}$
$x_{1},y_{1}=p_{1}$		$p_{012}$
	$p_{12}$		$p_{0123}$
$x_{2},y_{2}=p_{2}$		$p_{123}$
	$p_{23}$
$x_{3},y_{3}=p_{3}$

Kolejne elementy są obliczane rekurencyjnie na podstawie elementów poprzednich.

W praktyce algorytm Neville’a przedstawiamy w nieco innej wersji. Stosując oznaczenia:

$t_{(i+k),k}=p_{i(i+1),\dots ,(i+k)}$

Tablica przyjmuje postać:

$x_{0},y_{0}=t_{00}$
	$t_{11}$
$x_{1},y_{1}=t_{10}$		$t_{22}$
	$t_{21}$		$t_{33}$
$x_{2},y_{2}=t_{20}$		$t_{32}$
	$t_{31}$
$x_{3},y_{3}=t_{30}$

Ułatwia to komputerowe zaprogramowanie powyższej tablicy (jako tablicy dwuwymiarowej).

Otrzymujemy również wzór rekurencyjny w prostszej postaci:

$t_{ik}={\frac {(x-x_{i-k})t_{i,k-1}-(x-x_{i})t_{i-1,k-1}}{x_{i}-x_{i-k}}}$

gdzie: $1\leqslant k\leqslant i,$     dla $i=0,1,\dots ,n.$

Pseudokod:

       for i := 0 to n do
           t[i] = f[i]
       for i := i - 1 downto 0 do
           t[j]= t[j + 1] + (t[j + 1] - t[j]) * (x - x[i]) / (x[i] - x[j])

Szukaną wartość wielomianu interpolacyjnego otrzymujemy jako t[0].

Przykład

Dane mamy:

$i=0,1,2,3$

$x_{0}=0,$  $x_{1}=1,$  $x_{2}=3,$  $x_{3}=4$

$f(x_{0})=1,$  $f(x_{1})=3,$  $f(x_{2})=2,$  $f(x_{3})=1$

Wyliczymy wartość wielomianu interpolacyjnego w punkcie x=2. Korzystamy ze wzorów i konstruujemy tablicę:

$0,t_{00}=1$
	$t_{11}=5$
$1,t_{10}=3$		$t_{22}=10/3$
	$t_{21}=5/2$		$t_{33}=3$
$3,t_{20}=2$		$t_{32}=8/3$
	$t_{31}=3$
$4,t_{30}=1$

Zatem dla x=2 wartość wielomianu wynosi 3.

Uogólnienie algorytmu Neville’a

Mając zadane węzły $(x_{i},f_{i})$ do interpolacji można również użyć funkcji wymiernych:

$Z^{u,v}={\frac {P^{u,v}}{Q^{u,v}}}={\frac {a_{0}+a_{1}x+\ldots +a_{u}x^{u}}{b_{0}+b_{1}x+\ldots +b_{v}x^{v}}},$

spełniających warunki: $Z^{u,v}(x_{i})=f_{i},$     dla $i=0,1,\dots ,u+v.$

W przypadku interpolacji funkcjami wymiernymi można wyprowadzić uogólniony wzór Neville’a. Algorytm wygląda wówczas następująco:

$T_{i0}=f_{i},\quad T_{i,k-1}=0,\quad T_{ik}=T_{i,k-1}+{\frac {(T_{i,k-1}-T_{i-1,k-1})}{\left({\frac {x-x_{i-k}}{x-x_{i}}}\left[1-{\frac {T_{i,k-1}-T_{i-1,k-1}}{(T_{i,k-1}-T_{i-1,k-2}}}\right]-1\right)}}.$

Bibliografia

• J. Stoer, R. Bulirsch, Wstęp do analizy numerycznej, PWN, 1987.
• J.N. Lyness, C.B. Moler, Van Der Monde Systems and Numerical Differentiation, „Numerishe Mathematik” 8 (1966), s. 458–464