Системи на Чебишов. Интерполиране на тригонометрични полиноми.

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


Обобщен полином

Нека $\varphi_0(x), \varphi_1(x), \dots, \varphi_n(x)$ са непрекъснати и линейно независими функции в интервала $I$.
Всяка линейна комбинация $\varphi(x) = a_0\varphi_0(x) + a_1\varphi_1(x) + \dots + a_n\varphi_n(x)$ ще наричаме обобщен полином по системата $\{\varphi_i\}$.

$\varphi(x)$ е нетривиален обобщен полином, ако поне един от коефициентите $a_0, a_1, \dots, a_n$ е различен от $0$.

Дефиниция (система на Чебишов (или Т-система))

Казваме, че функциите $\{\varphi_k\}_{k = 0}^n$ образуват система на Чебишов (a.k.a Т-система), ако всеки нетривиален обобщен полином по тях има неповече от $n$ нули в интервала $I$.

Означаваме:
$\Omega_n = \{ \varphi(x) = a_0\varphi_0(x) + a_1\varphi_1(x) + \dots + a_n\varphi_n(x) \ | \ a_i \in \mathbb{R}, \ i = 0, 1, \dots, n \}$

Обща интерполационна задача

По дадени $x_0 < x_1 < \dots <x_n$ от $I$ и стойности $y_0, y_1, \dots, y_n$, да се намери $\varphi(x) \in \Omega_n$, такъв че

(1)
\begin{eqnarray} (1) && \varphi(x_k) = y_k \\ && k = 0, 1, \dots, n \end{eqnarray}

Задачата (1) има единствено решение $\varphi(x) \in \Omega_n$ тогава и само тогава, когато детерминантата

(2)
\begin{align} D(x_0, x_1, \dots, x_n) = \begin{vmatrix} \varphi_0(x_0) & \varphi_1(x_0) & \dots & \varphi_n(x_0) \\ \varphi_0(x_1) & \varphi_1(x_1) & \dots & \varphi_n(x_1) \\ \vdots & \vdots & \ddots & \vdots \\ \varphi_0(x_n) & \varphi_1(x_n) & \dots & \varphi_n(x_n) \end{vmatrix} \end{align}

е различна от нула.

Теорема

Функциите $\{\varphi_k(x)\}_{k = 0}^n$ образуват система на Чебишов в $I$ тогава и само тогава, когато $D(x_0, x_1, \dots, x_n) \neq 0$ за всеки избор на точки $x_0 < x_1 <\dots < x_n$ от $I$.

Доказателство:
1. Необходимост $(\Rightarrow)$
Нека $\{ \varphi_k(x) \}_{k=0}^{n}$ образуват Чебишова система в $I$. Да предположим, че съществуват $n + 1$ точки $x_0 < x_1 < \cdots < x_n$ от $I$, такива че $D(x_0, x_1, \cdots, x_n) = 0$. Тогава хомогенната система:

(3)
\begin{array} {|ccccccccc} a_0 \varphi_0(x_0) &+& a_1 \varphi_1(x_0) &+& \cdots &+& a_n \varphi_n(x_0) &=& 0 \\ a_0 \varphi_0(x_1) &+& a_1 \varphi_1(x_1) &+& \cdots &+& a_n \varphi_n(x_1) &=& 0 \\ \vdots & & \vdots & & \ddots & & \vdots \\ a_0 \varphi_0(x_n) &+& a_1 \varphi_1(x_n) &+& \cdots &+& a_n \varphi_n(x_n) &=& 0 \\ \end{array}

Има ненулево решение $(a_0^\star, a_1^\star, \cdots, a_n^\star)$. Тогава $\varphi(x) = a_0^\star \varphi_0(x) + \cdots + a_n^\star \varphi_n(x)$ е нетривиален обобщен полином на $\{ \varphi_k \}_{k=0}^{n}$, който има $n + 1$ нули в $I$. Противоречие. Следователно $D(x_0, \cdots, x_n) \ne 0$.
2. Достатъчност $(\Leftarrow)$
Нека $D(x_0, \cdots, x_n) \ne 0$, за всеки $x_0 < x_1 < \cdots < x_n$ от $I$. Да допуснем, че $\{ \varphi_k \}_{k=0}^{n}$ не образуват Т-система в $I$. Следователно съществува полином $\varphi(x) = a_0 \varphi_0(x) + \cdots + a_n \varphi_n(x)$ който има поне $n + 1$ различни нули в интервала $I$. Тогава $D(x_0, \cdots, x_n) = 0$. Противоречие! Следователно $\{ \varphi_k \}_{k=0}^{n}$ образуват Т-система в $I$.

Свойства на Т-системите

Ако функциите $\{\varphi_k\}_{k = 0}^n$ образуват Т-система в $I$, то

  1. те образуват Т-система и във всеки интервал $I_1 \subset I$.
  2. ако $g(x) \neq 0$ за $\forall x \in I$, тогава функциите $\{g(x)\varphi_k(x)\}_{k = 0}^n$ също образуват Т-система в $I$.
  3. ако $h(t)$ е строго монотонна функция в $I_1$, която приема стойности в $I$, тогава функциите $\{\varphi_k(h(t))\}_{k = 0}^n$ образуват Т-система в $I_1$.

Примери на Т-системи

  • $\{1, x, x^2, \dots, x^n \}$ образуват Т-система в $\mathbb{R}\ (-\infty, +\infty)$
  • $\{1, x^2, \dots, x^{2n} \}$ образуват Т-система в $(0, \infty)$
  • $\{ x, x^3, \dots, x^{2n+1} \}$ образуват Т-система в $(0, \infty)$

Твърдение

Ако $0 \leq \alpha_0 < \alpha_1 < \dots < \alpha_n$, тогава $\{ x^{\alpha_0}, \ x^{\alpha_1}, \dots, x^{\alpha_n} \}$ образуват Т-система в $(0, \infty)$.

Лема

Всеки тригонометричен полином от ред $n$ притежава най-много $2n$ различни нули в интервала $[0, 2\pi)$.

(4)
\begin{align} \tau_n(x) = a_0 + \sum_{k = 1}^n (a_k\cos kx + b_k\sin kx) \end{align}

Доказателство:
Сега ще изпoлзваме малко комплексен анализ, по-конкретно:

(5)
\begin{align} \sin x = \frac{e^{ix} - e^{-ix}}{2i} \quad \cos x = \frac{e^{ix} + e^{-ix}}{2} \end{align}

Ако се чудите от къде идват тези връзки, може да си решите системата:

(6)
\begin{array} {|ccccc} e^{ix} &=& \cos x &+& i \sin x \\ e^{-ix} &=& \cos x &-& i \cos x \\ \end{array}

Бе като цяло цялата работа е много нагласена, лекторът каза че имало 'естествено' разширение на степенуването, което включва комплексни числа. Ние ще използваме само $e^{ix}$ - т.е $e$ повдигнато на някоя чисто имагинерна степен.

След като имаме горните връзки лесно получаваме, че:

(7)
\begin{eqnarray} \cos kx &=& \frac{z^k + z^{-k}}{2} \\ \sin kx &=& \frac{z^k - z^{-k}}{2i} \\ z &=& e^{ix} \\ \end{eqnarray}

Сега ще си заместим с новите представяние на $\sin kx, \cos kx$ в тригонометричния полином и получаваме:

(8)
\begin{align} \tau_n(x) = a_0 + \sum_{k=1}^{n} \left( a_k \frac{z^k + z^{-k}}{2} + b_k \frac{(-i)(z^{k} - z^{-k})}{2} \right) = \sum_{k=-n}^{n} c_k z^k \end{align}

където:

(9)
\begin{eqnarray} c_0 &=& a_0 \\ c_k &=& \frac{a_k - ib_k}{2} \quad k = 1,2,\cdots n \\ c_k &=& \frac{a_k + ib_k}{2} \quad k = -n, -n+1, \cdots, -1 \\ \end{eqnarray}

Получихме, че $z^n \tau_n(x) = P_{2n}(z) \in \pi_{2n}$. Тогава нулите на $\tau_n(x)$ ще бъдат нулите на полинома $P_{2n}(z)$. Но $P_{2n}$ има най-много $2n$ корена върху $\{ z \in \mathbb{C} | |z| = 1 \}$ - даже има максимум $2n$ корена за произволно подмножество на комплексните числа - все пак полинома е от $2n$та степен.
Следователно $\tau_n$ има най-много $2n$ корена в интервала $[0, 2\pi)$. Лесно се обобщава за произволен интервал с дължина $2\pi$ - $[\alpha, \alpha + 2\pi)$.

Теорема (тригонометричен интерполационен полином)

Нека $0 \leq x_0 < x_1 < \dots < x_{2n} < 2\pi$ са дадени възли и $y_0, y_1, \dots, y_{2n}$ са дадени числа.
Тогава съществува единствен тригонометричен полином от степен $n$: $\tau_n(x)$, такъв че

(10)
\begin{eqnarray} && \tau_n(x_i) = y_i \\ && i = 0, 1, \dots, 2n \end{eqnarray}

и той се задава с формулата

(11)
\begin{align} \tau_n(x) = \sum_{k = 0}^{2n} \lambda_k(x) y_k \end{align}

където

(12)
\begin{align} \lambda_k(x) = \prod_{i =0,\ i \neq k}^{2n} \frac{\sin \frac{x - x_i}{2}}{\sin \frac{x_k - x_i}{2}} \end{align}

Доказателство:
Ще докажем, че $\lambda_k$ е тригонометричен полином от ред $n$ - за целта трябва да проверим, че произведение от $2n$ на брой $\sin \frac{x - \alpha}{2}$ е тригонометричен полином от ред $n$.
Индукция по $2n$:
(1) $\sin \frac{x-\alpha}{2} \sin \frac{x - \beta}{2} = \frac{1}{2}(\cos \frac{\beta - \alpha}{2} - \cos (x - \frac{\alpha + \beta}{2})) = a_0 + a_1 \cos x + b_1 \sin x$
(2) Ще разглеждаме $n+1$ умножения, като $n$ умножения по още едно и ще използваме индукционното предположение за $n$-те.
Ще използваме формулите:

(13)
\begin{eqnarray} \sin kx . \cos x &=& \frac{1}{2}(\sin (k+1)x + \sin (k-1)x) \\ \sin x . \cos kx &=& \frac{1}{2}(\sin (k+1)x + \sin (k-1)x) \\ \cos kx . \cos x &=& \frac{1}{2}(\cos(k+1)x + \cos (k-1)x) \\ \sin kx . \sin x &=& \frac{1}{2}(\cos(k-1)x - \cos (k+1)x) \\ \end{eqnarray}

с това доказахме, че $\lambda_k$ е тригонометричен полином от ред $n$. Лесно се вижда, че удовлетворява условието $\tau_n(x_i) = y_i$.

Лема (ядро на Дирихле)

(14)
\begin{align} \frac{1}{2} + \cos x + \cos 2x + \cdots + \cos nx = \frac{\sin \frac{(2n+1)x}{2}}{2 \sin \frac{x}{2}} = D_n(x) \end{align}

Израза се нарича още Ядро на Дирихле.
Доказателство: Умножаваме лявата страна на израза по $2 \sin \frac{x}{2}$ и получаваме числителя на дясната страна.

Опростяване на интерполационния тригонометричен полином

Ще намерим малко по-проста форма за интерполационния тригонометричен полином в случая когато сме избрали равноотдалечени интерполационни възли.
Ако си изберем равноотдалечени възли $x_k = \frac{2k\pi}{2n + 1}$ за $i = 0, 1, \cdots, 2n$, тогава $\displaystyle{D_n(x_k) = \frac{\sin k\pi}{2\sin \frac{k\pi}{2n + 1}} = 0}$, за $k > 0$.
$D_n(x_0) = n + \frac{1}{2}$, ако го разпишем като израза в ляво в Лемата.
Дефинираме $\displaystyle{\lambda_k(x) = \frac{2D_n(x-x_k)}{2n+1}}$. Ще покажем, че тя удовлетворява интерполационните условия за построяване на полинома :

При $i = k$ : $\displaystyle{ \lambda_k(x_i) = \lambda_k(x_k) = \frac{2D_n(0)}{2n+1} = \frac{2}{2n+1}.(n+\frac{1}{2}) = 1}$ .

При $i \ne k$ : $\displaystyle{\lambda_k(x_i) = \frac{1}{2n + 1} \frac{\sin (k-i)\pi}{\sin \frac{(k-i)\pi}{2n+1}} = 0}$ .

Тогава:
$\tau_n(f; x)$ - тригонометричен полином от ред $n$.
$\tau_n(f; x_k) = f(x_k) \quad k = 0, 1, \cdots, 2n$.

(15)
\begin{align} \tau_n(f; x) = \sum_{k=0}^{2n} \lambda_k(x) f(x_k) = \frac{1}{2n + 1} \sum_{k=0}^{2n}\frac{\sin \frac{(2n+1)(x - x_k)}{2}}{\sin \frac{x - x_k}{2}} f(x_k) \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License