Разделени разлики с кратни възли

Понятието разделена разлика на дадена функция в дадени точки, с което боравихме до този момент, има една особеност и тя е, че точките трябваше да са различни.
Cъществува и обощена дефиниция на понятието при не непременно различни точки. Ще се възползваме от нея за построяването на интерполационния полином с кратни възли (решение на интерполационната задача на Ермит)

Нека $\bar{x} = (x_0, x_1, \dots, x_N)$ е произволна редица от точки, $x_0 \leq x_1 \leq \dots x_N, \ x_i \in \mathbb{R}, \ i = 0, 1, \dots, N$
$\bar{x}$ ще записваме и по следния начин: $\bar{x} = ((t_1, \nu_1), (t_2, \nu_2), \dots, (t_n, \nu_n))$ като това означава следното:

$\nu_1$ на брой $x_i$ са равни на $t_1$
$\nu_2$ на брой $x_i$ са равни на $t_2$
$\vdots$
$\nu_n$ на брой $x_i$ са равни на $t_n$

Тук вече можем да твърдим, че $t_1 < t_2 < \dots < t_n$ и $\nu_1 + \nu_2 + \dots + \nu_n = N + 1$

Нека $f(x)$ е достатъчно гладка1 функция в интервала $[t_1, t_n]$. Ще казваме, че полиномът $P(x) \in \Pi_N$ интерполира $f(x)$ във възлите $\bar{x}$, ако $P^{(j)} (t_i) = f^{(j)} (t_i)$ за $i = 1,2, \dots, n$ и $j = 0, 1, \dots, \nu_i - 1$

Разделена разлика (дефиниция)

Нека $x_0 \leq x_1 \leq \dots x_N$ е произволна редица от реални числа и $f(x)$ е достатъчно гладка функция в интервала $[x_0, x_N]$.
Разделена разлика на $f(x)$ в точките $x_0, x_1, \dots x_N$ (записваме $f[x_0, x_1, \dots, x_N]$) ще наричаме коефициентът пред $x^N$ в полинома на Ермит, интерполиращ $f(x)$ във възлите $x_0, x_1, \dots, x_N$.

Теорема (явен вид на разделена разлика)

Нека $x_0 \leq x_1 \leq \dots \leq x_N$ е редица от реални числа и $f(x)$ е достатъчно гладка функция в интервал, който ги съдържа.
Тогава

(1)
\begin{align} f[x_0, x_1, \dots, x_N] = \begin{cases} \frac{f[x_1, x_2, \dots, x_N] - f[x_0, x_1, \dots, x_{N-1}]}{x_N - x_0} & x_0 < x_N \\ \frac{f^{(N)} (x_0)}{N!} & x_0 = x_1 = \dots = x_N \end{cases} \end{align}

Очевидно тази теорема ни дава рекурентната връзка между обощените разделени разлики.
За доказателството и ще ни е необходимо едно помощно твърдение. И така..

Лема

Нека $t_1, t_2, \dots, t_m$ и $\xi$ са произволни реални числа и $f(x)$ е достатъчно гладка функция в интервал, който съдържа тези числа.
Тогава

(2)
\begin{align} \Big( (x - \xi).f(x)\Big)[t_1, t_2, \dots, t_m, \xi] = f[t_1, t_2, \dots, t_m] \end{align}

Доказателство на теоремата:
В случая когато $x_0 = x_1 = \dots =x_N = a$, развиваме функцията в ред на Тейлър (виж и wikipedia - Ред на Тейлър)… до N-ти ред и получаваме интерполиращия я полином

(3)
\begin{align} T_n(f; x) = f(a) + \frac{f'(a)}{1!}(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \dots + \frac{f^{(N)}(a)}{N!}(x - a)^N \end{align}

От явния вид на полинома и от дефиницията за раделена разлика с кратни възли, се вижда, че $f[x_0, x_1, \dots, x_N] = \frac{f^{(N)} (x_0)}{N!}$

В другия случай, когато $x_0 < x_N$, използваме лемата

(4)
\begin{eqnarray} (x_N - x_0). f[x_0, x_1, \dots, x_N] &=& \Big((x_N - x)f(x) + (x - x_0)f(x)\Big)[x_0, x_1, \dots, x_N] = \\ &=& \Big((x_N - x)f(x)\Big)[x_0, x_1, \dots, x_N] + \Big((x - x_0)f(x)\Big)[x_0, x_1, \dots, x_N] = \\ &=& -\Big((x - x_N)f(x)\Big)[x_0, x_1, \dots, x_N] + \Big((x - x_0)f(x)\Big)[x_0, x_1, \dots, x_N] = \\ &\overset{\underset{\mathrm{Lemma}}{}}{=}& -f[x_0, x_1, \dots, x_{N-1}] + f[x_1, x_2, \dots, x_N] \end{eqnarray}
(5)
\begin{align} \Longrightarrow f[x_0, x_1, \dots, x_N] = \frac{f[x_1, x_2, \dots, x_N] - f[x_0, x_1, \dots, x_{N-1}]}{x_N - x_0} \quad \Box \end{align}

Твърдение

Формулата на Нютон за интерполационния полином на Лагранж остава в сила и за интерполационния полином на Ермит.

Или, иначе казано:
Ако $\bar{x} = (x_0, x_1, \dots, x_N)$ са произволни точки и функцията $f$ има $N$ непрекънати производни в интервала $[x_0, x_N]$, тогава полиномът

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

интерполира $f$ в точките $\bar{x}$


Пример - задачка:
Да се построи полином $p(x) \in \Pi_3$, такъв че $p(0) = -1,\ p'(0) = -2,\ p''(0) = 0,\ p(1) = 4$
Решение:
В тази задача интерполационните възли са $x_0 = x_1 = x_2 = 0,\ x_3 = 1$.
От гореспомената формула на Нютон с обощени разлики имаме следното:(7)
\begin{eqnarray} p(x) & = & p(x_0) + p[x_0, x_1](x - x_0) + p[x_0, x_1, x_2](x - x_0)(x - x_1) + p[x_0, x_1, x_2, x_3](x - x_0)(x - x_1)(x - x_2) \\ & = & p(0) + p[0,0]x + p[0,0,0]x^2 + p[0,0,0,1]x^3 \end{eqnarray}

Сега трябва да си изчислим раделените разлики с помощта на таблица.

chm_6.3.PNG

$p[x_i] = p(x_i)$, което е стойността на функцията в дадената точка (това е първата колонка). За втората колонка важи правилото от горната теорема, че когато възлите са равни се взима (в случая) стойността на първата производна в тази точка върху 1! , а иначе пак по формулата се смята. Третата колонка - аналогично, но с втора производна за равните възли и четвъртата колонка мисля, че пак е ясна :) (сори, че обяснението е малко shit, ама това е)

Твърдение

Ако $x_0, x_1, \dots, x_n$ са произволни реални числа и $f(x)$ е достатъчно гладка функция в интервал, който ги съдържа, тогава $f[x_0, x_1, \dots, x_n]$ зависи непрекъснато от интерполационните възли $x_0, x_1, \dots, x_n$.

Това твърдение някакси въвежда понятието непрекъснатост на разделени разлики. На лекции не е доказана верността на твърдението, така че, цитирам, "приемаме го на доверие". За по-любопитните - в учебника на Б. Боянов ("Лекции по числени методи") е доста добре обяснено.

Лема (формула на Поповичу-Стефенсон)

За произволни точки $x_0, x_1, \dots, x_n$ и достатъчно гладни функции $f$ и $g$ (в интервал, който съдържа точките) е в сила следната формула:

(8)
\begin{align} (f.g) [x_0, x_1, \dots, x_n] = \sum_{k = 0}^n f[x_0, x_1, \dots, x_k] g[x_k, x_{k+1}, \dots, x_n] \end{align}

Доказателство:
Провеждаме индукция по $n$:
1. При $n = 0$ имаме следното: $(f.g)[x_0] = f(x_0)g(x_0) = f[x_0]. g[x_0]$. Базата е доказана/показана.

2. Нека формулата е вярна за $n - 1$.

3. Ще доказажем, че е вярна и за $n$.
Използваме дефиницията за разделена разлика: $\frac{f(x) - f(x_0)}{x- x_0} = f[x_0, x]$, за произволни числа $x_0, x$, следователно:
$f(x) = f(x_0) + f[x_0, x](x - x_0)$ е вярно за всяко $x$ - т.е може да го ползваме като друг запис на функцията $f(x)$.

Тогава

(9)
\begin{eqnarray} (f.g) [x_0, x_1, \dots, x_n] & = & \Big((f(x_0) + f[x_0, x](x - x_0))g(x)\Big)[x_0, x_1, \dots, x_n] =\\ & = & \Big(\underbrace{f(x_0)}_{\mathrm{const}} g(x)\Big)[x_0, x_1, \dots, x_n] + \Big((f[x_0, x](x - x_0)g(x) \Big)[x_0, x_1, \dots, x_n] =\\ & = & f(x_0).g[x_0, x_1, \dots, x_n] + \Big(f[x_0, x].g(x)\Big)[x_1, x_2, \dots, x_n] =\\ & = & f[x_0]g[x_0, x_1, \dots, x_n] + \sum_{k = 1}^n (f[x_0, x])[x_1, x_2, \dots, x_k] . g[x_k, x_{k+1}, \dots, x_n] \end{eqnarray}

За тези, които не са го разбрали - преходът от втори към трети ред стана с помощта на горе-споменатата лема2, а получихме четвърти ред като приложихме индукционното предположение.

Формулата ще бъде доказана, ако покажем, че
$(f[x_0, x]) [x_1, x_2, \dots, x_k] = f[x_0, x_1, \dots, x_k]$ при $k = 1, 2, \dots, n$

Тук отново използваме интерполационната формула на Нютон.

(10)
\begin{eqnarray} f[x_0, x_1, \dots, x_k] & = & \Big(\underbrace{f(x_0)}_{\mathrm{const}} + f[x_0, x](x - x_0)\Big) [x_0, x_1, \dots, x_k] =\\ & = & 0 + \Big((f[x_0, x](x - x_0)\Big)[x_0, x_1, \dots, x_k] =\\ & = & (f[x_0, x])[x_1, x_2, \dots, x_k] \quad \Box \end{eqnarray}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License