Упражнение 4

Тука сложи заглавие


страницата се нуждае от дописване/преглеждане


(?) Интерполационната формула на Нютън:
L_n(f;x) = f(x_0) + \Sigma_{k=1}^n f[x_0, …, x_k](x - x_0)…(x - x_{k-1}) , x_0 <= … <= x_n

Нека функцията ни е
f(x) = (x^2 + 1) arctg x

и да вземем следните интерполационни възли:
x_0 = x_1 = -1, x_2 = 0, x_3 = x_4 = x_5 = 1

Означаваме разделените разлики с
a_{kj} = f[x_j, x_{j+1}, …, x_{j+ik}]

и ги смятаме по следния начин:
a_{kj} = (a_{k-1,j+1} - a_{k-1,j}) / (x_{j+k} - x_j), ако x_j \ne x_{j+k} ; или
f^(k)(x_j) / k! , ако x_j = x_{j+k}

Сега в Mathematica:

n = 5; x[0] = -1; x[1] = -1; x[2] = 0; Do [x[k] = 1, {k, 3, n}];
f[t_] := (t^2 + 1) ArcTan[t];
Do[a[0, j] = f[x[j]], {j, 0, n}];
Do[Do[If[x[j] != x[j + k],
a[k, j] = (a[k - 1, j + 1] - a[k - 1, j])/(x[j + k] - x[j]),
a[k, j] = Simplify[D[f[t], {t, k}] /. {t -> x[j]}] /
Gamma[k + 1]], {j, 0, n + k}], {k, 1, n}];

(* D е функцията за диференциране. Simplify - де да го знам :\ *)
L[t_] := a[0, 0] +
Sum[a[k, 0] Product[t - x[j], {j, 0, k - 1}], {k, 1, n}];
Plot[{f[t], L[t]}, {t, -1.2, 1.2}]
Plot[{f[t] - L[t]}, {t, -1.2, 1.2}]

Сега ще се занимаваме със системи на Чебишев.

Имаме крайна съвкупност от непрекъснати и ЛНЗ функции в даден интервал I : {\phi_k(x)}_{k=0}^n
По тези функции си образуваме обобщени полиноми, които представляват линейни комбинации на тези функции:
\phi(x) = a_0\phi_0(x) + … + a_n\phi_n(x), a_i са реални числа.
Ако поне едно a_k \ne 0, то полиномът "е нетривиален".

Казваме, че функциите образуват "Чебишева система", или T-система в I, ако всеки нетривиален обобщен полином
има най-много n различни нули в I.
Оказва се, че това условие (за Чебишева система) е еквивалентно на една детерминанта не знам си какво. От друга
страна, ако имаме Чебишева система, можем да интерполираме по тези функции в интервала I.

Условието функциите да образуват Чебишева система е необходимо и достатъчно, за да можем да интерполираме с
такива функции.

Най-прост пример: {1, x, x^2, …, x^n, …}. Това е Чебишева система върху реалната права: I = {-\inf, +\inf}.

Друг пример: {1, x^2, …, x^{2n}} - T система в (0, \inf). Общият брой на нулите тук е най-много 2n, то в (0,\inf)
имаме най-много n нули - условието е изпълнено. Изпълнено е и в (-\inf, 0).

Друг пример: {x, x^3, …, x^{2n+1}). Следва от горния пример - функциите тук се получават чрез умножение с x,
което в отворения интервал (0, \inf) е различно от нула.

Това са два частни случая на по-обща задача. В сила е по-общото твърдение:
Ако вземем реални неотрицателни числа 0 <= \alpha_0 < \alpha_1 < … < \alpha_n , тогава степенните функции
{ x^{\alpha_1}, x^{\alpha_2}, … , x^{\alpha_n} } образуват T система в интервала (0, \inf).

За доказателството ще ползваме една друга задача:

Нека \alpha_0 < \alpha_1 < … < \alpha_n . Да се докаже, че
{e^{\alpha_0.x}, …, e^{\alpha_n.x}} образуват T система в (-\inf, +\inf).

Доказателство: Индукция по n.
n = 0. Единствената функция e^{\alpha_0.x}. Всички нетривиални полиноми са от вида c.e^{\alpha_0.x}, c \ne 0.
Ясно е, че не може да се анулира, следователно твърдението е вярно.
Нека е вярно за n-1, n \in N. Ще го докажем за n.

Да допуснем, че \phi(x) = a_0.e^{\alpha_0.x} + a_1.e^{\alpha_1.x} + … + a_n.e^{\alpha_n.x} има n+1 различни
реални нули. Ако поне един от коефициентите е равен на 0, то тогава това ще е обобщен полином по <n функции,
и съгласно индукционното предположение не може да има повече от n-1 нули.
Нека \each a_i \ne 0.
Пишем \phi(x) във вида e^{\alpha_0.x} (a_0 + a_1.e^{(\alpha_1 - \alpha_0)x}) + a_2.e^{(\alpha_2 - \alpha_0)x} + … + a_n. e^{(\alpha_n - \alpha_0).x}. е-то пред скобите не е равно на 0 за \each x.
Означаваме частта в скобите с \psi(x).
Тогава \psi(x) има n+1 различни нули.
По теоремата на Рол, \psi'(x) ще има поне n различни нули (разделяме на интервали от 0 до 0, сеш'се).

\psi'(x) = a_1(\alpha_1 - \alpha_0)e^{(\alpha_1 - \alpha_0)x} + a_2(\alpha_2 - \alpha_0)e^{(\alpha_2 - \alpha_0)x}
+ … + a_n(\alpha_n - \alpha_0)e^{(\alpha_n - \alpha_0)x}. Всеки коефициент \alpha_i \ne 0.
Това е нетривиален обобщен полином на {e^{(\alpha_k - \alpha_0)x}}_{k=0}^n. Съгласно ИП, този полином има най-много
n-1 нули, което е противоречие с Рол. Следователно \psi(x) има най-много n нули.

Задача следваща (всъщност предишната :) ): Ако 0 \le \alpha_0 \lt \alpha_1 \lt … \lt \alpha_n , тогава функциите
{t^{\alpha_0}, …, t^{\alpha_n}} образуват T-система в (0, \inf).

Ще използваме едно твърдение от лекциите.
Свойство: Ако {\phi_k(x)_{k=0}^n образуват T система в I и x = h(t) е строго монотонна непрекъсната функция в
I_1, приемаща стойности в I, тогава {\phi(_k(h(t))}_{k=0}^n образуват T система в I_1.

Произтича непосредствено от дефиницията: Ако допуснем, че обобщен полином по тези нули (със сменената променлива) има n+1 нули, те са вече t_0, …, t_n, тогава по оригиналната система обобщеният полином със същите коефициенти има n+1 нули в x_0 = h(t_0), … x_n = h(t_n), противоречие.

Прилагаме свойството: x = ln t, t \in (0, \inf). ln е строго монотонно растяща в (0,\inf) и приема стойности в
(-\inf, +\inf). Следователно { … } = {t^{\alpha_0}, t^{\alpha_1}, …, t^{\alpha_n}} образуват T система в
интервала (0,\inf).

Друга задача: Нека f(x) \in C^n[a,b] и f^{(n)} \ne 0, \each x \inf (a,b).
Да се докаже, че {1, x, …, x^{n-1}, f(x)} образуват T система в [a,b].
Решение: Да допуснем, че \exists обобщен полином \phi_(x( = a_0 + a_1x + … + a_{n-1}x^{n-1} + a_nf(x),
който има n+1 различни нули в [a,b], x_0 < … < x_n. Задължително е a_0 \ne 0.

Прилагаме теоремата на Рол: между всеки две x_i и x_{i+1} \phi'(x) има нула. Това означава поне n различни нули в
отворения интервал [a,b]. Аналогично, \phi''(x) има поне n-1 нули. Така \phi^{(n)}(x) има поне една нула в (a,b).
Но n-тата производна \phi^{(n)} = a_nf^{(n)}(x) \ne 0 в (a,b) - противоречие.
Така получихме, че всеки ненулев полином има най-много n различни нули в [a,b].

Приложения на горната задача:
Задача: Да се докаже, че:
а) {1, x, x.cos(x)} образуват T система в [0, \Pi/2].
б) {1, x, x.sin(x)} образуват T система в [\Pi/2, \Pi].

Решение: Приложения на горната задача при n=2. Трябва да се уверим, че втората производна е различна от 0.
а) (x.cos(x))'' = -x.cos(x) - 2.sin(x) < 0 в интервала (0, \Pi/2) .
б) (x.sin(x))'' = -x.sin(x) + 2.cos(x) < 0 в интервала (\Pi/2, \Pi).
Можем да разсъждаваме и така: Щом втората производна е отрицателна, първата е строго монотонно намаляваща. Тогава
първоначалната функция само веднъж си сменя (монотонността), т. е. max 2 корена.

Защо не използваме алгебричните полиноми за интерполиране, а Чебишевите?
Алгебричните полиноми са лесни за интерполиране, но понякога търсим и … още нещо. Например:
f(x) = e^{-x}. Тогава \lim_{x \to +\inf} f(x) = 0.
Ако, вместо с полином, интерполираме с функции от вида {1/(x-a_0), 1/(x-a_1), …, 1/(x-a_n)},
a_0 < a_1 < … <a_n, тези функции образуват T система в интервал, несъдържащ [a_0,a_n] - Всеки обобщем полином
\phi(x) = c_0(1/(x-a_0)) + c_1(1/(x-a_1)) + … + c_n(1/(x-a_n)) = P_n(x)/(x-a_0)(x-a_1)…(x-a_n) ,
P_n(x) \in \Pi(x).
Тъй като отгоре имаме полином от deg n, а отдолу - полином от deg n+1 то обобщеният полином ще клони към 0 при
x, клонящо към +\inf.

Примерна програмка:

f0[t_] := 1/(t+1);
f1[t_] := 1/(t+2);
f2[t_] := 1/(t+3);
f[t_] := Exp[-t];
(* x[0] = 0, x[1] = 1, x[2] = 2; *)
Solve[{a*f0[0] + b*f1[0] + c*f2[0] == f[0],
a*f0[1] + b*f1[1] + c*f2[1] == f[1],
a*f0[2] + b*f1[2] + c*f2[2] == f[2]}, {a, b,c}]

(* Изкарва:

a -> (3 (10 - 12 E + 3 E^2))/E^2,
b -> -((12 (15 - 16 E + 3 E^2))/E^2),
c -> (30 (6 - 6 E + E^2))/E^2

*)

L[t_] = Simplify[a*f0[t] + b*f1[t] + c*f2[t] /.a -> (3 (10 - 12 E + 3 E^2))/E^2,
b -> -((12 (15 - 16 E + 3 E^2))/E^2),
c -> (30 (6 - 6 E + E^2))/E^2
];
Plot[f[t] - L[t], {t, 0, 100}]

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