Тука сложи заглавие
страницата се нуждае от дописване/преглеждане
Припомняме си функции за интерполиране (тъпо обяснение, ама не успях да запиша цялата мисъл):
$0 \le x_0 < x_1 < ... < x_{2n} \le 2\pi$
$f(x), \tau_n(f;x) = \underset {k=0} {\overset {2n} {\sum}} \lambda_k(x).f(x_k)$, където
$\lambda_k(x) = \underset {j = 0, j \ne k} {\prod} \cfrac {sin \cfrac {x - x_j} 2} {sin \cfrac {x_k - x_j} 2}$
$x_0 = 0, x_1 = \frac \pi 3, x_2 = \frac \pi 2, x_3 = \pi, x_4 = \frac {3 \pi} 2 , n = 2$
В Mathematica:
n = 2; x[0] = 0; x[1] = Pi/3; x[2] = Pi/2; x[3] = Pi; x[4] = 3 Pi/2;
Do[l[k_, t_] := (s = 1; Do[If[j != k, s *= Sin[(t - x[j])/2]/Sin[(x[k] - x[j])/2]], {j, 0, 2 n}]; s), {k, 0, 2 n}];
T[f_, t_] := Sum[l[k, t] f[x[k]], {k, 0, 2 n}];
f[t_] := Cos[t]/(2 - Sin[3 t]);
Plot[{f[t], T[f, t]}, {t, 0, 2 \[Pi]}]
Plot[{f[t] - T[f, t]}, {t, 0, 2 \[Pi]}]
Сега ще реализираме и формулата за интерполиране в равноотдалечени възли - там нещата се получават
и за произволно n. Формулата в този случай е
$x_k = \frac {2k\pi} {2n + 1}, k = 0, \dots, 2n$
$\tau_n = \frac 1 {2n+1} \sum_{k = 0}^{2n} \cfrac {sin \cfrac {(2n + 1)(x - x_k)} 2} {sin \cfrac {(x - x_k)} 2} .f(x_k)$
Mathemagica: Ще дефинираме функцията "ядро на Дирихле" с име Dn:
n = 5; Do[x[k] = 2 k*Pi/(2 n + 1), {k, 0, 2 n}];
Dn[t_] := Sin[(2 n + 1) t/2]/Sin[t/2];
T[f_, t_] := Sum[Dn[t - x[k]] f[x[k]], {k, 0, 2 n}]/(2 n + 1);
f[t_] := Cos[t]/(2 - Sin[3 t]);
Plot[{f[t], T[f, t]}, {t, 0, 2 \[Pi]}]
Plot[{f[t] - T[f, t]}, {t, 0, 2 \[Pi]}]
Грешката изглежда голяма? Опитваме с n = 10, 15, 20, …, 300 …
През останалата част от упражнението ще интерполираме чрез сплайни от ниска степен - по-точно първа. Тези сплайни
представляват начупени линии - прост, но не толкова лош апарат.
ИНТЕРПОЛИРАНЕ СЪС СПЛАЙН ФУНКЦИИ ОТ ПЪРВА СТЕПЕН
Функциите от първа степен с възли от $x_1$ до $x_n$ бележим с $S_1(x_1, \dots, x_n)$ - линейно пространство с dim n+2 .
Един базис се задава така: $\{1, x, (x-x_k)_+ ; k = 1, 2, ..., n\}$.
B-сплайните образуват по-хубав базис. Те изглеждат като едни колибки, пресичат абсцисата в $x_i$ и $x_{i+2}$,
а ординатата в $x_{i+1}$
FIXME: ASCII art, подмени с картинка
/ / / / / _/|\
$x_i x_{i+1} x_{i+2}$
Ние ще използваме функциите $|x - x_k|$ :
FIXME: ASCII art, подмени с картинка
\ /
\ /
\ /
_\/__
$x_k$
Нека $a < x_1 < x_2 < ... < x_n < b$.
Задача. Да се докаже, че функциите $\{|x - x_k|\}_{k=1}^n$ са линейно независими в [a, b].
Решение: Да допуснем, че съществува линейна комбинация
$\phi(x) = \underset {k=1} {\overset n {\sum}} c_k.|x - x_k| \equiv 0 , x \in [a, b]$ .
Ще покажем, че коефициентите $c_k$ са нули. Дефинираме $x_0 := a, x_n+1 := b$.
$\phi(x)$ е полином от $\Pi_1$ във всеки интервал $[x_i, x_{i+1}]$. Нека $x \in [x_i, x_{i+1}]$ и $\phi(x) \equiv 0$ в този интервал.
$\phi(x) = \sum_{k=1}^i c_k.(x - x_k) - \sum_{k=i+1}^n c_k.(x - x_k) = (c_1 + c_2 + ... + c_i - c_{i+1} - ... - c_n)x + F \equiv 0$, F - свободен член.
Тогава можем да построим следната система:
(1) \Sigma_{k=1}_i c_K - \Sigma_{k=i+1}_n = 0 &&
(2) \Sigma_{k=1}_{i-1} c_k - \Sigma_{k=i}_n = 0.
Вадим (1) от (2) и получаваме
c_i + c_i = 0 => c_i = 0 , като това е за всяко i \in [1, n].
Следователно функциите са линейно независими.
Задача. Дадени са възлите a = x_0 < x_1 < … < x_n = b. f(x) е функция, дефинирана в [a, b].
Нека I_1(f; x) \in S_1 (x_1, …, x_n) e сплайн-функция, която интерполира f(x) в точките x_i, i = 1, …, n.
Ако I_1(f; x) се запише като \Sigma_{k=0}^n c_k.[x-x_k|, да се намерят коефициентите {c_K}_{k=0}^n.
Ще напишем условията и ще изведем формули за коефициентите c_k.
Решение: Искаме I_1(f; x_i) = f(x_i) за i = 0, …, n.
f(x_i) = \Sigma_{k=0}^{i-1} c_k.(x_i - x_k) - \Sigma_{k=i+1}^n c_k.(x_i - x_k)
f(x_{i+1}) = \Sigma_{k=0}^i c_k.(x_{i+1} - x_k) - \Sigma_{k=i+2}^n c_k.(x_{i+1} - x_k)
Изваждаме второто от първото и получаваме /* CAUTION: ERROR POSSIBILITY BELOW */
f(x_{i+1}) - f(x_i) = \Sigma_{k=0}^{i-1} c_k(x_{i+1} - x_i) + c_i(x_{i+1} - x_i)
- \Sigma_{k=i+2}^n c_k(x_{i+1} - x_i) - c_{i+1}(x_{i+2} - x_i)
Пъхаме двете събираеми в двете суми и получаваме
f(x_{i+1}) - f(x_i) = \Sigma_{k=0}^i c_k(x_{i+1} - x_i) - \Sigma_{k=i+1}^n c_k(x_{i+1} - x_i)
Нещо си правим и пишем разделени разлики:
f[x_i, x_{i+1}] = \Sigma{k=0}^i c_k - \Sigma{k=i+1}^n c_k
f[x_{i-1}, x_i] = \Sigma{k=0}^{i-1} c_k - \Sigma{k=i}^n c_k
Вадим ги и получаваме
c_i = 1/2(f[x_i, x_{i+1}] - f[x_{i-1}, x_i]) , 1 \le i \le n-1
f(x_0) = I_1(f; x_0) = \Sigma{k=0}^n c_k(x_k - x_0)
f(x_n) = I_1(f; x_n) = \Sigma{k=0}^i c_k(x_k - x_n)
От тези двете получаваме: f(x_0) + f(x_n) = \Sigma{k=0}^n c_k(x_n - x_0)
\Sigma_{k=0}^n c_k = (f(x_0) + f(x_n))/(x_n - x_0).
c_0 - \Sigma_{k=1}^n c_k = f[x_0,x_1]
Оттук:
c_0 = 1/2((f(x_0) + f(x_n))/(x_n - x_0) + f[x_0, x_1])
По някакъв начин получаваме и :
c_n = 1/2((f(x_0) + f(x_n))/(x_n - x_0) + f[x_{n-1}, x_n])
Получихме всички необходими коефициенти [ъъъ … ok?].
Тези формули ще използваме следващия път. Сега ще дефинираме едно понятие:
Модул на непрекъснатост на функция:
Ако имаме една функция f(x), дефинирана в краен затворен интервал [a,b], бележим нейния модул на непрекъснатост с
\omega(f; \delta) , 0 < \delta \le b-a
\omega(f; \delta) = sup {|f(x) - f(y)| : x, y \in [a,b], |x - y| \le \delta}
Това е някаква "мярка", колко "голяма" може да бъде разликата на две функции, при условие, че аргументите са
на разстояние не повече от делта.
Две свойства:
1. Ако f \in C[a,b] /*непрекъсната в [a,b]*/ => \omega(f; \delta) -> 0 (\delta -> 0)
2. Ако \delta_1 < \delta_2, \omega(f; delta_1) \le \omega(f; delta_2).
Второто следва от факта, че супремумът се взима от по-голямо множество и, съответно, е по-голям или равен.
Задача. Да се докаже, че за всяко x \in [a,b], |f(x) - I_1(f;x)| \le \omega(f; \Delta), където
\Delta = max(x_{i+1} - x_i), 0 \le i \le n-1 .
Полиномът от първа степен ще е начупена линия, която интерполира f(x) /* това вечее не мога да нарисувам */.
Този полином ще е интерполационният полином на Лагранж.
Решение: При x \in [x_i, x_{i+1}],
I_1(f;x) = (x_{i+1} - x)/(x_{i+1} - x_i) f(x_i) + (x - x_i)/(x_{i+1} - x_i) f(x_{i+1})
f(x) = (x_{i+1} - x)/(x_{i+1} - x_i) f(x) + (x - x_i)/(x_{i+1} - x_i) f(x)
Тогава:
|f(x) - I_1(f; x)| = |(x_{i+1}-x)/(x_{i+1}-x_i) (f(x) - f(x_i)) + (x-x_i)/(x_{i+1}-x_i) (f(x) - f(x_i))|
\le (x_{i+1}-x)/(x_{i+1}-x_i) |f(x) - f(x_i)| + (x-x_i)/(x_{i+1}-x_i) |f(x) - f(x_{i+1})|
\le (x_{i+1}-x)/(x_{i+1}-x_i) \omega(f; x-x_i) + (x-x_i)/(x_{i+1}-x_i) \omega(f; x_{i+1} -x)
/*понеже (x - x_i) и (x_{i+1} - x) са по-малки или равни на (x_{i+1} - x_i)*/
\le \omega(f; x_{i+1} - x_i) \le \omega(f; \Delta).
Следствие: Ако x_{i+1} - x_i = (b-a)/n /*равноотдалечени възли*/ за i = 0, …, n-1 => \Delta = (b-a)/n,
то следва, че |f(x) - I_1(f;x)| \le \omega(f; (b-a)/n) -> 0 (n -> \inf), ако f \in C[a,b].