403
правки
Изменения
Новая страница: «== Собственно интерполяция == Пусть есть числа <tex>x_1 < x_2 < x_3 < \ldots < x_n</tex> и <tex>y_1, y_2, y_3, \ldots ,y_n</tex>…»
== Собственно интерполяция ==
Пусть есть числа <tex>x_1 < x_2 < x_3 < \ldots < x_n</tex> и <tex>y_1, y_2, y_3, \ldots ,y_n</tex> (''система узлов'').
Требуется найти полином <tex>P_n</tex> степени не выше <tex>n</tex> такой, что <tex>P_n(x_k) = y_k</tex>.
Будем искать его в форме Лагранжа, хотя имеется ряд равносильных представлений, например, в
форме Ньютона.
Очевидно, что если такой полином существует, то только один.
Будем искать его в форме Лагранжа. Для этого построим ''фундаментальные полиномы'' <tex>\Phi_j(x)</tex> степени не выше <tex>n</tex>, отвечающие заданной
системе узлов <tex>x_0 < x_1 < \ldots < x_n</tex> такие, что
<tex>
\Phi_j(x_k) = \left\{
\begin{aligned}
1 & ,\quad k = j\\
0 & ,\quad k \ne j\\
\end{aligned}\right.
</tex>.
Для его построения обозначим за <tex>\omega_n(x) = \prod\limits_{j = 0}^n (x - x_j)</tex>. Это полином степени <tex>n + 1</tex>.
Составим выражение <tex>\frac{\omega_n(x)}{(x - x_j) \cdot \omega_n'(x_j)}</tex>, <tex>x \ne x_j</tex>. В этом случае дробь корректно определена
если <tex>x \to x_j</tex>. Получаем неопределённость <tex>\frac00</tex>. Раскроем её по правилу Лопиталя: <tex>\frac{\omega'_n(x)}{\omega_n'(x_j)} = 1</tex> при <tex>x \to x_j</tex>.
Тогда доопределим по непрерывности дробь единицей. Но при <tex>x \ne x_j</tex> это полином $n$-й степени. Значит,
<tex>\Phi_j(x) = \frac{\omega_n(x)}{(x-x_j) \cdot \omega_n'(x_j)}</tex>.
Тогда
<tex>
\Phi_j(x_k) = \left\{
\begin{aligned}
1 & ,\quad k = j\\
0 & ,\quad k \ne j\\
\end{aligned}\right.
</tex>, что и требовалось.
`
Обозначим <tex>L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)</tex>.
<tex>L_n(x_k) = \sum\limits_{j = 0}^n y_j \Phi_j(x_k) = y_k \Phi_k(x_k) = y_k</tex>.
Требуемый полином <tex>L_n(x)</tex> найден.
Замечание: из формулы для фундаментальных полномов <tex>\Phi_j(x)</tex> легко записать в развёрнутом виде:
<tex>
\Phi_j(x) = \frac
{(x-x_0)(x - x_1)\cdots(x - x_{j- 1})(x - x_{j + 1})\cdots(x - x_n)}
{(x_j - x_0)(x_j - x_0)\cdots(x_j - x_{j-1})(x_j - x_{j + 1})\cdots(x_j - x_n)}
</tex>
== TODO: заголовок ==
Выведенную ранее формулу Тейлора можно трактовать следующим образом:
<<Дано <tex>f(x)</tex>. Найти полином <tex>T_n</tex> степени не выше <tex>n</tex> такой, что <tex>f^{(k)}(x_0) = T_n^{(k)}(x_0)</tex>>>.
Ранее мы обнаружили, что это
<tex>T_N(x) = \sum\limits_{k = 0}^n \frac
{f^{(k)}(x_0)}
{k!}
\cdot (x - x_0)^k
</tex>.
Теперь другая задача: <<Дана функция и система узлов. Требуется найти полином степени не выше <tex>n</tex> такой, что
<tex>\forall x_j: j = \overline{0..n}\quad T(x_j) = f(x_j)</tex>
>>
Положим <tex>L_n(x) = \sum\limits_{j = 0}^n \Phi_j(x_j) \cdot f(x_j)</tex>. По пункту 1 этот полином решает поставленную задачу.
Для полинома Тейлора <tex>f(x) = T_n(x) + \frac
{f^{(n + 1)}(c_x)}
{(n + 1)!} \cdot (x - x_0)^{n + 1}
</tex>.
Сейчас будет доказана теорема аналогичная теореме об интерполяционном полиноме Лагранжа, после чего станет ясно, что это задачи одного класса.
Во втором случае это изложено на языке производных, а в первом~--- через значения функции в точках.
Эти два метода метода можно комбинировать, лишь бы информативных значений было <tex>n + 1</tex>. Такие промежуточные задачи называют
''интерполированием по Эрмиту''. <s>Но они никому не нужны.</s>
\newtheorem{Lagrange}{Lagrange}
\begin{Lagrange}
Пусть <tex>f</tex> <tex>n + 1</tex> раз дифференцируема на <tex>\langle a; b\rangle</tex>. На этом промежутке дана система узлов. Тогда для соответственного
интерполяционного полинома Лагранжа выполняется равенство
<tex>f(x) = L_n(x) + \frac{f^{n + 1}(c_x)}{(n+1)!} \cdot \omega_n(x)</tex>, где <tex>c_x</tex>~--- некоторая точка из <tex>\langle a; b \rangle</tex>, зависящая от <tex>x</tex>.
Доказательство
%%\begin{proof}
Случай <tex>x = x_k, k = \overline{1, n}</tex> тривиален.
Пусть тогда <tex>x \ne x_k</tex>.
Для доказательства применим теорему Ролля. Определим вспомогательную функцию <tex>g(t) = f(t) - L_n(t)- k \omega_n(t)</tex>, где <tex>k</tex>~--- коэффициент,
подлежащий определению, а <tex>x</tex> дано.
<tex>g(x_j) = f(x_j) - L_n(x_j) - k \omega_n(x_j) = 0</tex>
Для определения <tex>k</tex> потребуем, чтобы <tex>g(x)</tex> было равно <tex>0</tex>.
<tex>g(x) = f(x) - L_n(x) - k \omega_n(x) = 0</tex>
<tex>\omega_n(x) \ne 0</tex>, так как <tex>x \ne x_j</tex>.
<tex>k = \frac{f(x) - L_n(x)}{\omega_n(x)}</tex>
Итак, при выбранном <tex>k</tex> будет <tex>g(x_j) = 0</tex>, <tex>g(x) = 0</tex>, то есть <tex>g</tex> принимает нулевые значения в <tex>n + 2</tex> точках. Очевидно,
из узлов и точки <tex>x</tex> можно сделать <tex>n + 1</tex> последовательный отрезок. На конце каждого из них <tex>g</tex> принимает значение <tex>0</tex>.
Значит, по теореме Ролля на каждом из них найдётся по корню производной. Из полученных корней можно сделать <tex>n</tex> отрезков,
на каждом из них по теореме Ролля найдётся по корню второй производной\ldots В конце концов останется один отрезок, границами которого
будут корни <tex>g^{(n)}</tex>. Тогда по теореме Ролля на этом отрезке найдётся корень <tex>g^{(n + 1)}</tex>. Его и обозначим за <tex>c_x</tex>.
Подведём промежуточный итог: найдено <tex>c_x</tex> такое, что <tex>g^{(n + 1)}(c_x) = 0</tex>.
<tex>g(t) = f(t) - L_n(t) - k \omega_n(t)</tex>
Продифференцируем <tex>n + 1</tex> раз. <tex>\deg L_n(x) \leq n \Rightarrow L_n^{(n + 1) = 0}</tex>. <tex>\omega_n(t) = t^{n + 1} + \ldots \Rightarrow \omega'_n = (n + 1)!</tex>.
Таким образом, <tex>g^{(n + 1)}(t) = f^{(n + 1)}(t) - k\cdot (n + 1)!</tex>.
Подставим <tex>t = c_x</tex>.
<tex>0 = g^{(n + 1)}(c_x) = f^{(n + 1)}(c_x) - k\cdot (n + 1)!</tex>
<tex>k = \frac{f^{(n + 1)}(c_x)}{(n + 1)!}$, $k = \frac{f(x) - L_n(x)}{\omega_n(x)}</tex>
%%\end{proof}
\end{Lagrange}
Следствие: в условии теоремы было неравенство <tex>|f(x) - L_n(x)| \leq \frac{M_{n + 1}}{(n + 1)!} (b - a)^{n + 1}</tex>,
<tex>M_{n + 1} = \sup\limits_{\langle a; b \rangle} |f^{(n + 1)}|</tex>
Замечание:
Следует понимать, что на самом деле какую бы систему узлов мы не взяли на <tex>\langle a; b \rangle</tex> как по числу
точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить интерполяционный многочлен,
который будет отличаться от неё сколь угодно много(нипанянтна~--- прим. наборщика)
Пусть есть числа <tex>x_1 < x_2 < x_3 < \ldots < x_n</tex> и <tex>y_1, y_2, y_3, \ldots ,y_n</tex> (''система узлов'').
Требуется найти полином <tex>P_n</tex> степени не выше <tex>n</tex> такой, что <tex>P_n(x_k) = y_k</tex>.
Будем искать его в форме Лагранжа, хотя имеется ряд равносильных представлений, например, в
форме Ньютона.
Очевидно, что если такой полином существует, то только один.
Будем искать его в форме Лагранжа. Для этого построим ''фундаментальные полиномы'' <tex>\Phi_j(x)</tex> степени не выше <tex>n</tex>, отвечающие заданной
системе узлов <tex>x_0 < x_1 < \ldots < x_n</tex> такие, что
<tex>
\Phi_j(x_k) = \left\{
\begin{aligned}
1 & ,\quad k = j\\
0 & ,\quad k \ne j\\
\end{aligned}\right.
</tex>.
Для его построения обозначим за <tex>\omega_n(x) = \prod\limits_{j = 0}^n (x - x_j)</tex>. Это полином степени <tex>n + 1</tex>.
Составим выражение <tex>\frac{\omega_n(x)}{(x - x_j) \cdot \omega_n'(x_j)}</tex>, <tex>x \ne x_j</tex>. В этом случае дробь корректно определена
если <tex>x \to x_j</tex>. Получаем неопределённость <tex>\frac00</tex>. Раскроем её по правилу Лопиталя: <tex>\frac{\omega'_n(x)}{\omega_n'(x_j)} = 1</tex> при <tex>x \to x_j</tex>.
Тогда доопределим по непрерывности дробь единицей. Но при <tex>x \ne x_j</tex> это полином $n$-й степени. Значит,
<tex>\Phi_j(x) = \frac{\omega_n(x)}{(x-x_j) \cdot \omega_n'(x_j)}</tex>.
Тогда
<tex>
\Phi_j(x_k) = \left\{
\begin{aligned}
1 & ,\quad k = j\\
0 & ,\quad k \ne j\\
\end{aligned}\right.
</tex>, что и требовалось.
`
Обозначим <tex>L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)</tex>.
<tex>L_n(x_k) = \sum\limits_{j = 0}^n y_j \Phi_j(x_k) = y_k \Phi_k(x_k) = y_k</tex>.
Требуемый полином <tex>L_n(x)</tex> найден.
Замечание: из формулы для фундаментальных полномов <tex>\Phi_j(x)</tex> легко записать в развёрнутом виде:
<tex>
\Phi_j(x) = \frac
{(x-x_0)(x - x_1)\cdots(x - x_{j- 1})(x - x_{j + 1})\cdots(x - x_n)}
{(x_j - x_0)(x_j - x_0)\cdots(x_j - x_{j-1})(x_j - x_{j + 1})\cdots(x_j - x_n)}
</tex>
== TODO: заголовок ==
Выведенную ранее формулу Тейлора можно трактовать следующим образом:
<<Дано <tex>f(x)</tex>. Найти полином <tex>T_n</tex> степени не выше <tex>n</tex> такой, что <tex>f^{(k)}(x_0) = T_n^{(k)}(x_0)</tex>>>.
Ранее мы обнаружили, что это
<tex>T_N(x) = \sum\limits_{k = 0}^n \frac
{f^{(k)}(x_0)}
{k!}
\cdot (x - x_0)^k
</tex>.
Теперь другая задача: <<Дана функция и система узлов. Требуется найти полином степени не выше <tex>n</tex> такой, что
<tex>\forall x_j: j = \overline{0..n}\quad T(x_j) = f(x_j)</tex>
>>
Положим <tex>L_n(x) = \sum\limits_{j = 0}^n \Phi_j(x_j) \cdot f(x_j)</tex>. По пункту 1 этот полином решает поставленную задачу.
Для полинома Тейлора <tex>f(x) = T_n(x) + \frac
{f^{(n + 1)}(c_x)}
{(n + 1)!} \cdot (x - x_0)^{n + 1}
</tex>.
Сейчас будет доказана теорема аналогичная теореме об интерполяционном полиноме Лагранжа, после чего станет ясно, что это задачи одного класса.
Во втором случае это изложено на языке производных, а в первом~--- через значения функции в точках.
Эти два метода метода можно комбинировать, лишь бы информативных значений было <tex>n + 1</tex>. Такие промежуточные задачи называют
''интерполированием по Эрмиту''. <s>Но они никому не нужны.</s>
\newtheorem{Lagrange}{Lagrange}
\begin{Lagrange}
Пусть <tex>f</tex> <tex>n + 1</tex> раз дифференцируема на <tex>\langle a; b\rangle</tex>. На этом промежутке дана система узлов. Тогда для соответственного
интерполяционного полинома Лагранжа выполняется равенство
<tex>f(x) = L_n(x) + \frac{f^{n + 1}(c_x)}{(n+1)!} \cdot \omega_n(x)</tex>, где <tex>c_x</tex>~--- некоторая точка из <tex>\langle a; b \rangle</tex>, зависящая от <tex>x</tex>.
Доказательство
%%\begin{proof}
Случай <tex>x = x_k, k = \overline{1, n}</tex> тривиален.
Пусть тогда <tex>x \ne x_k</tex>.
Для доказательства применим теорему Ролля. Определим вспомогательную функцию <tex>g(t) = f(t) - L_n(t)- k \omega_n(t)</tex>, где <tex>k</tex>~--- коэффициент,
подлежащий определению, а <tex>x</tex> дано.
<tex>g(x_j) = f(x_j) - L_n(x_j) - k \omega_n(x_j) = 0</tex>
Для определения <tex>k</tex> потребуем, чтобы <tex>g(x)</tex> было равно <tex>0</tex>.
<tex>g(x) = f(x) - L_n(x) - k \omega_n(x) = 0</tex>
<tex>\omega_n(x) \ne 0</tex>, так как <tex>x \ne x_j</tex>.
<tex>k = \frac{f(x) - L_n(x)}{\omega_n(x)}</tex>
Итак, при выбранном <tex>k</tex> будет <tex>g(x_j) = 0</tex>, <tex>g(x) = 0</tex>, то есть <tex>g</tex> принимает нулевые значения в <tex>n + 2</tex> точках. Очевидно,
из узлов и точки <tex>x</tex> можно сделать <tex>n + 1</tex> последовательный отрезок. На конце каждого из них <tex>g</tex> принимает значение <tex>0</tex>.
Значит, по теореме Ролля на каждом из них найдётся по корню производной. Из полученных корней можно сделать <tex>n</tex> отрезков,
на каждом из них по теореме Ролля найдётся по корню второй производной\ldots В конце концов останется один отрезок, границами которого
будут корни <tex>g^{(n)}</tex>. Тогда по теореме Ролля на этом отрезке найдётся корень <tex>g^{(n + 1)}</tex>. Его и обозначим за <tex>c_x</tex>.
Подведём промежуточный итог: найдено <tex>c_x</tex> такое, что <tex>g^{(n + 1)}(c_x) = 0</tex>.
<tex>g(t) = f(t) - L_n(t) - k \omega_n(t)</tex>
Продифференцируем <tex>n + 1</tex> раз. <tex>\deg L_n(x) \leq n \Rightarrow L_n^{(n + 1) = 0}</tex>. <tex>\omega_n(t) = t^{n + 1} + \ldots \Rightarrow \omega'_n = (n + 1)!</tex>.
Таким образом, <tex>g^{(n + 1)}(t) = f^{(n + 1)}(t) - k\cdot (n + 1)!</tex>.
Подставим <tex>t = c_x</tex>.
<tex>0 = g^{(n + 1)}(c_x) = f^{(n + 1)}(c_x) - k\cdot (n + 1)!</tex>
<tex>k = \frac{f^{(n + 1)}(c_x)}{(n + 1)!}$, $k = \frac{f(x) - L_n(x)}{\omega_n(x)}</tex>
%%\end{proof}
\end{Lagrange}
Следствие: в условии теоремы было неравенство <tex>|f(x) - L_n(x)| \leq \frac{M_{n + 1}}{(n + 1)!} (b - a)^{n + 1}</tex>,
<tex>M_{n + 1} = \sup\limits_{\langle a; b \rangle} |f^{(n + 1)}|</tex>
Замечание:
Следует понимать, что на самом деле какую бы систему узлов мы не взяли на <tex>\langle a; b \rangle</tex> как по числу
точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить интерполяционный многочлен,
который будет отличаться от неё сколь угодно много(нипанянтна~--- прим. наборщика)
