Разделени разлики. Интерполационна формула на Нютон.

Разделена разлика

Имаме си функция $f$ и $n+1$ различни точки $x_0, x_1, \cdots, x_n$
Разделена разлика се дефинира по следния начин:
$f[x_i] = f(x_i), i \in [0, n]$
От едно число - това си е самата функция.
$f[x_i, x_{i+1}, x_{i+2}, \cdots, x_{i+k}] = \cfrac{f[x_{i+1}, x_{i+2}, \cdots, x_{i+k}] - f[x_i, x_{i+1}, \cdots, x_{i+k-1}]}{x_{i+k} - x_{i}}$
За повече числа - дефинира се рекурентно.

Теорема 1

Разделената разлика на числата $x_0, x_1, x_2, \cdots, x_n$ е точно равна на коефицента пред nтата степен на полинома на Лагранж за $f$ и $x_0, x_1, x_2, \cdots, x_n$.

Нещо важно! коефицентът пред nтата степен на Лагранж вероятно не е това, което си мислиш. Начинът, по който го записваме на лекции, не е с разкрити скоби - записвали сме го само като сума от разни други полиноми, но за това след малко.
В случая, полиномът е от nта степен - т.е. става въпрос за старшия му коефицент.

Д-во:
Както повечето неща, които не разбираме защо точно са верни - доказателството е по индукция.
База на индукцията: За $n = 1$ - нещата стават директно (подсказка: разпиши си полинома):

(1)
\begin{eqnarray} f[x_0, x_1] &=& \frac{f[x_1] - f[x_0]}{x_1 - x_0} \\ &=& \frac{f(x_1)}{x_1 - x_0} - \frac{f(x_0)}{x_1 - x_0} \\ &=& \frac{1}{x_0 - x_1}f(x_0) + \frac{1}{x_1-x_0}f(x_1) \\ L_1(f; x) &=& \frac{x - x_1}{x_0 - x_1}f(x_0) + \frac{x - x_0}{x_1 - x_0}f(x_1) \\ \end{eqnarray}

Както виждате - изпълнено е.
Индукционно предположение: Нека твърдението е изпълнено за $n$.
Индукционна стъпка: Ще докажем твърдението за $n + 1$.
Вземаме два интерполационни полинома на Лагранж от ред $n$:
$p(x) = L(f, [x_1, x_2, \cdots, x_n])$ - интерполиращ $f(x)$ в точките $x_1 \dots x_{n}$
$q(x) = L(f, [x_0, x_1, \cdots, x_{n-1}])$ - интерполиращ $f(x)$ в точките $x_0 \dots x_{n-1}$
Чрез тях ще изразим полинома на Лагранж от ред $n+1$.
Така лесно ще се види колко му е старшият коефицент.

$r(x) = \cfrac{(x-x_0)p(x) - (x-x_n)q(x)}{x_n - x_0}$

За $i \in \{1, 2, \cdots,n-1\}$ това си е точно равно на $f(x_i)$:
$r(x_i) = \cfrac{f(x_i)*(x_i - x_0)}{x_n - x_0} - \cfrac{x_i*f(x_i) - x_n*f(x_i)}{x_n - x_0} = \cfrac{f(x_i)*(x_n - x_0)}{x_n - x_0} = f(x_i)$

Нещо повече - за $x_0$ и $x_n$ това също е вярно!
$r(x_0) = \cfrac{(x_n - x_0)*f(x_0)}{x_n - x_0} - \cfrac{(x_0 - x_0) *q(x_0)}{x_n - x_0} = f(x_0)$
$r(x_n) = \cfrac{(x_n - x_n)*p(x_n)}{x_n - x_0} - \cfrac{(x_n - x_0) *f(x_n)}{x_n - x_0} = f(x_n)$

Имаме полином на Лагранж за степен $n+1$. ($r(x)$ интерполира $f$ в нужните точки, а има само един такъв полином).
$r(x) = \cfrac{(x-x_0)p(x) - (x-x_n)q(x)}{x_n - x_0}$
$r(x) = C*((x-x_0)p(x) - (x-x_n)q(x)), \quad C = \frac{1}{x_n - x_0}$
$r(x) = C*(xp(x) - xq(x)) + ...$ - нещата в многоточието са от твърде малка степен, за да ни интересуват.
$E(r) = \cfrac{E(p(x)) - E(q(x))}{x_n - x_0}$
$E$ е отбелязан старши коефицент).
Съответните старши коефиценти за $p$ и $q$ са каквито ни трябва разделени разлики.
Следователно, старшият коефицент на интерполационния полином за $n+1$ е същият, като разделената разлика за $x_0, x_1, x_2, \cdots, x_{n}$.
$f[x_0, x_1, x_2, \cdots, x_n] = \cfrac{f[x_1, x_2, \cdots, x_n] - f[x_0, x_1, \cdots, x_{n-1}]}{x_n - x_0} = E(L_n(f;x))$

Следствия от теоремата

Следствие 1

Разделената разлика на полином от степен n е старшият коефицент на полинома.
Следва директно от Теорема 1 и факта, че всеки полином от степен n е собствения си интерполационен полином на Лагранж от степен n.

Следствие 2

Разделената разлика на полином от степен по-малка от n е 0.
Следва от факта, че всеки полином от степен k е своят собствен интерполационен полином на Лагранж (когато говорим за поне $k+1$ точки - важно!), а коефицентът пред nтата степен на полином от степен по-малка от n е 0.

Следствие 3 (формула за разделена разлика)

Ще изведем пряка формула за разделена разлика, базирана на формулата за интерполационния полинома на Лагранж - просто ще му вземем коефициента пред най-високата степен.

(2)
\begin{eqnarray} L_n(f; x) &=& \sum_{k=0}^{n} l_k(x) f(x_k) \\ &=& \sum_{k=0}^{n} \frac{\omega(x)}{(x-x_k)\omega'(x_k)} f(x_k) \quad \omega(x) = (x-x_0)(x-x_1)\dots(x - x_n) \\ \Rightarrow f[x_0, \cdots, x_n] &=& \sum_{k=0}^{n} \frac{1}{\omega'(x_k)}f(x_k) \end{eqnarray}

Запомнете тази формула - използва се в доста задачи!

Следствие 4 (реда на променливите е без значение)

Ако $\{ i_0, \dots, i_n \}$ е пермутация на $\{ 0, \dots, n \}$, то $f[x_{i_0}, x_{i_1}, \dots, x_{i_n}] = f[x_0, \dots, x_n]$.
Доказва се тривиално с помощта на следствие 3 - реда на събираемите е без значение.

Следствие 5 (разделената разлика е линеен функционал)

За всеки две функции $f, g$ и константа $c$:

(3)
\begin{align} (f + c.g)[x_0, \dots, x_n] &=& f[x_0, \dots, x_n] + c.g[x_0, \dots, x_n] \end{align}

Доказва се лесно с помощта на следствие 3 - сумата се разпада на две суми и константата излиза пред втората сума.

Интерполационна формула на Нютон

Ще докажем следната формула:

(4)
\begin{eqnarray} L_n(f; x) &=& f(x_0) + \sum_{k=1}^n f[x_0, \dots, x_k] (x - x_0)\dots(x-x_{k-1}) \\ &=& \sum_{k=0}^{n} f[x_0,\dots, x_k](x - x_0)\dots(x-x_{k-1}) \\ \end{eqnarray}

Разбира се долният запис е ако приемем, че произведението $(x - x_0)\dots(x-x_{k-1})$ при $k = 0$ е 1.

Доказателство: Ще направим индукция по $n$:
База на индукцията: При $n = 0$ имаме, че $L_0(f; x) = f(x_0)$, т.е формулата е вярна.
Индукционно предположение: Нека формулата е вярна за $n - 1$, именно, ако $L_{n-1}(f;x)$ интерполира $f(x)$ в точките $x_0, \dots, x_{n-1}$, то:

(5)
\begin{align} L_{n-1}(f;x) = \sum_{k=0}^{n-1} f[x_0, \dots, x_k] (x - x_0) \dots (x - x_{k-1}) \end{align}

Индукционна стъпка: Нека $L_{n}(f;x)$ интерполира $f(x)$ в точките $x_0, \dots, x_{n}$.
Разглеждаме следната разлика:
$L_{n}(f,x) - L_{n-1}(f,x)$
Това е полином с максимална степен $n$ (защото $L_{n}(f,x)$ е с максимална степен $n$та).
Той се нулира в точките $x_0, x_1, x_2, \cdots, x_{n-1}$, защото при тях и двата полинома на Лагранж съвпадат с интерполираната функция:
$L_{n}(f,x_i) - L_{n-1}(f,x_i) = f(x_i) - f(x_i) = 0, \quad i \in [0,1,\cdots, n-1]$
Т.е имаме полином с максимална степен $n$, на който знаем всичките корени, следователно може да запишем:
$L_{n}(f,x) - L_{n-1}(f,x) = C * (x - x_0)(x - x_1)\cdots(x - x_{n-1})$
Където $C$ е старшият коефицент на полинома, който е от степен $n$ - понеже $L_{n-1}(f;x)$ е от по-ниска степен, следователно той съвпада със старшия коефициент на $L_{n}(f,x)$, който е $f[x_0, x_1, x_2, \cdots, x_{n}]$.

Преместваме разни неща от другата страна и получаваме:
$L_{n}(f,x) = L_{n-1}(f,x) + f[x_0, x_1, x_2, \cdots, x_{n}] * (x - x_0)(x - x_1)\dots(x - x_{n-1})$
Сега остава да приложим индукционното предположение за да получим:

(6)
\begin{eqnarray} L_{n}(f; x) &=& L_{n-1}(f,x) + f[x_0, x_1, x_2, \cdots, x_{n}] * (x - x_0)(x - x_1)\dots(x - x_{n-1}) \\ &=& \sum_{k=0}^{n-1} f[x_0, x_1, \dots, x_k] * (x-x_0) \dots (x - x_{k-1}) + f[x_0, x_1, x_2, \cdots, x_{n}] * (x - x_0)(x - x_1)\dots(x - x_{n-1}) \\ &=& \sum_{k=0}^{n} f[x_0, x_1, \dots, x_k] * (x-x_0) \dots (x - x_{k-1}) \\ \end{eqnarray}

С това формулата е доказана.

Забележка:
Формулата на Нютон е доста по-неточна от формулата на Лагранж, защото в нея многократно се прилага деление (при смятането на разделените разлики). Делението (при реални числа, но на повечето езици и при цели) е силно неточна операция - добре е да се прави по-малко. При хубава реализация на Полинома на Лагранж, деленията могат да бъдат сведени до едно на едночлен, докато тук стигат до n на едночлен.

Представяне на грешката с разделена разлика

Твърдение

Нека $L_n(f; x)$ интерполира $f(x)$ в точките $x_0, \dots, x_n$. Тогава за произволно $x$ е изпълнено:

(7)
\begin{align} f(x) - L_n(f; x) = f[x_0, \dots, x_n, x] \omega(x) \end{align}

Доказателство: Нека фиксираме едно произволно $x$.
Нека $L_{n+1}(f; t)$ интерполира $f(t)$ в точките $x_0, \dots, x_n, x$. Тогава (използвайки същата връзка, която изполваме в доказателството на интерполационната формула на Нютон) получаваме:
$L_{n+1}(f; t) - L_n(f; t) = f[x_0, \dots, x_n, x] (t - x_0)\dots(t-x_n)$
Така, за точката $t = x$ получаваме1:

(8)
\begin{eqnarray} f(x) - L_n(f; x) &=& f[x_0, \dots, x_n, x] (x-x_0)\dots(x-x_n) \\ &=& f[x_0, \dots, x_n, x] \omega(x) \\ \end{eqnarray}

Следствие

Използвайки представянето на грешката без разделени разлики, именно: ако $f \in C^{n+1}[a, b]$ и $a \le x_0 < \dots < x_n \le b$ то съществува $\xi \in (a, b)$, такова че:

(9)
\begin{align} f(x) - L_n(f; x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \omega(x) \end{align}

Може да заключим следното: ако $f(x) \in C^{k}[a, b]$ и $a \le x_0 < \dots x_k \le b$, то съществува $\xi \in (x_0, x_k)$ такова че:

(10)
\begin{align} f[x_0, \dots, x_k] = \frac{f^{(k)}(\xi)}{k!} \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License