Крайни разлики. Интерполационни полиноми с крайни разлики.

Крайни разлики

В предната тема разглеждахме разделени разлики, като интерполационните възли бяха произволни точки. В тази глава ще се съсредоточим върху частния случай, в който интерполационните възли са на равно разстояние помежду си. Именно:
$x_0, x_1, \cdots, x_n, \cdots$ са интерполационните възли, където $x_i = x_0 + ih$, за $i \in \mathbb{N}$ и $h > 0$, което ще наричаме стъпка.
Функцията $f(x)$ трябва да е дефинирана в точките $\{ x_i \}$, като за краткост ще отбелязваме $f_i = f(x_i)$.

Дефиниция (крайна разлика)

Крайна разлика от $k$ти ред дефинираме индуктивно по следния начин:

  1. $\Delta^0 f_i = f_i$
  2. $\Delta^k f_i = \Delta^{k-1}f_{i+1} - \Delta^{k-1}f_i$

Вместо $\Delta^1$ ще пишем просто $\Delta$.

Пример

  • $\Delta^1 f_i = \Delta^0 f_{i+1} - \Delta^0f_i = f_{i+1} - f_i$
  • $\Delta^2 f_i = \Delta f_{i+1} - \Delta f_i = (f_{i+2} - f_{i+1}) - (f_{i+1} - f_i) = f_{i+2} - 2f_{i+1} + f_i$
  • $\Delta^3 f_i = f_{i+3} - 3f_{i+2} +3f_{i+1} - f_i$

Твърдение (връзка между крайна и разделена разлика)

Сигурно сте забелязали, че разликата в дефинициите на 2те разлики е, че при крайната не се дели на нищо самата разлика. Ето и формулата, с която може да се пресмятат разделените разлики във вид на крайни и обратно:

(1)
\begin{align} f[x_0, x_1, \cdots, x_n] = \frac{\Delta^n f_0}{h^n.n!} \end{align}

Доказателство: Доказателството се прави тривиално по индукция:
База на индукцията: $f[x_0] = f(x_0) = f_0 = \Delta^0 f_0 = \frac{\Delta^0 f_0}{h^0 . 0!}$ - вярно
Индукционно предположение: Допускаме, че $f[x_0, x_1, \cdots, x_{n-1}] = \frac{\Delta^{n-1} f_0}{h^{n-1}.(n-1)!}$ е вярно
Индукционна стъпка:

(2)
\begin{eqnarray} f[x_0, x_1, \cdots, x_n] &=& \frac{f[x_1, x_2, \cdots, x_n] - f[x_0, x_1, \cdots, x_{n-1}]}{x_n - x_0} \\ &=& \frac{\frac{\Delta^{n-1} f_1}{h^{n-1}.(n-1)!} - \frac{\Delta^{n-1} f_0}{h^{n-1}.(n-1)!}}{n.h} \\ &=& \frac{\Delta^{n-1}f_1 - \Delta^{n-1}f_0}{h^n . n!} \\ &=& \frac{\Delta^n f_0}{h^n . n!} \end{eqnarray}

Теорема (директна формула за крайна разлика)

В сила е следната формула:

(3)
\begin{align} \Delta^n f_i = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} f_{i+k} \end{align}

Доказателство: Ще използваме връзката между разделена и крайна разлика:
Първо да забележим, че $f[x_i, x_{i+1}, \cdots, x_{i+n}] = \frac{\Delta^n f_i}{n! . h^n}$ е еквивалентно на $\Delta^n f_i = n! h^n f[x_i, x_{i+1}, \cdots, x_{i+n}]$
На кратко ще разпишем разделената разлика, ще вземем $n!$ и ще видим, че полученото можем да нагласим до нютонов бином.

(4)
\begin{eqnarray} \Delta^n f_i &=& n! h^n f[x_i, x_{i+1}, \cdots, x_{i+n}] \\ &=& n! h^n \sum_{k=i}^{i+n} \frac{1}{w'(x_k)} f(x_k) \\ &=& n! h^n \sum_{k=i}^{i+n} \frac{1}{ \underbrace{(x_k - x_i)}_{(k-i)h} \underbrace{(x_k - x_{i+1})}_{(k-i-1)h}\cdots \underbrace{(x_k-x_{k-1})}_{h} \underbrace{(x_k-x_{k+1})}_{-h}\cdots \underbrace{(x_k - x_{i+n})}_{-(i+n-k)h}} f_k \\ &=& n! h^n \sum_{k=i}^{i+n} \frac{1}{h^n \underbrace{(k-i)(k-i-1)(k-i-2)\cdots 1}_{(k-i)!}. (-1)^{n-k+i} \underbrace{1.2.\cdots .(i+n-k)}_{(i+n-k)!}} f_k \\ &=& \sum_{k=i}^{i+n} (-1)^{n-k+i} \frac{n!}{(k-i)! (i+n-k)!} f_k \\ &=& \star \end{eqnarray}

тук е момента да положим $l = k - i$.

(5)
\begin{eqnarray} \star &=& \sum_{l=0}^{n} (-1)^{n-l} \frac{n!}{l! (n-l)!} f_{i+l} \\ &=& \sum_{l=0}^{n} (-1)^{n-l} \binom{n}{l} f_{i+l} \\ \end{eqnarray}

с което формулата е доказана!

Свойства на крайните разлики

  • $\Delta^k(f+cg)_i = \Delta_k f_i + c\Delta^k g_i$, за произволни функции $f, g$ и константа $c$;
  • Ако $f(x)$ е полином: $f(x) = a_0 + a_1 x + \cdots + a_n x^n$, тогава $\Delta^n f_0 = n! h^n a_n$;

Формули на Нютон за интерполиране напред/назад

Дефиниция (обобщен биномен коефициент)

Нека $t \in \mathbb{R}$ и $k \in \mathbb{N}_0$. Дефинираме:

(6)
\begin{align} \binom{t}{k} = \begin{cases} 1 & k = 0 \\ \frac{t(t-1)\cdots(t-k+1)}{k!} & k \in \mathbb{N} \\ \end{cases} \end{align}

Вече можем да пресмятаме биномни коефициенти с нецели коефициенти.

Формула на Нютон за интерполиране напред в равноотдалечени възли

Или още известна като последния да затвори вратата.

(7)
\begin{align} L_n(f; x_0 + th) = \sum_{k=0}^{n} \binom{t}{k} \Delta^k f_0 \end{align}

Доказателство: Да си припомним първо формулата за интерполиране на Нютон:

(8)
\begin{align} L_n(f;x) = \sum_{k=0}^{n} f[x_0, \cdots, x_k] (x-x_0)(x-x_1)\cdots(x - x_{k-1}) \end{align}

Сега ще заместим разделената разлика с крайна разлика (по вече познатата ни формула) и също ще положим $x = x_0 + th$, където $t \in \mathbb{R}$ (отместване в брой възли от началото):

(9)
\begin{eqnarray} L_n(f;x) &=& \sum_{k=0}^{n} f[x_0, \cdots, x_k] (x-x_0)(x-x_1)\cdots(x - x_{k-1}) \\ L_n(f;x_0 + th) &=& \sum_{k=0}^{n} \frac{\Delta^{k} f_0}{k! h^k} t(t-1)\cdots(t-k+1)h^k \\ &=& \sum_{k=0}^{n} \binom{t}{k} \Delta^k f_0 \\ \end{eqnarray}

Обръщам внимание, че това е само при равноотдалечени възли - възлите трябва да са на едно и също разстояние $h$ един от друг.

Формула на Нютон за интерполиране назад в равноотдалечени възли

(10)
\begin{align} L_n(f; x_n + th) = \sum_{k=0}^{n} \binom{t+k-1}{k} \Delta^k f_{n-k} \end{align}

Доказателство: Абсолютно по същия начин като горната - просто полагаме $x$ да бъде $x_n + th$ (отместване в брой възли от края). Нямам никаквно намерение/желание да го разписвам :)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License