Задачи интерполирования функции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача интерполяции)
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 5 участников)
Строка 5: Строка 5:
 
}}
 
}}
  
Дана система узлов. Требуется найти полином <tex>P_n</tex> степени не выше <tex>n</tex> такой, что для любого <tex>k=\overline{0,n}</tex> верно, что <tex>P_n(x_k) = y_k</tex>.
+
Дана система узлов. Требуется найти полином <tex>P_n</tex> степени не выше <tex>n</tex> такой, что <tex>P_n(x_k) = y_k, k=\overline{0,n}</tex>.
  
 
Будем искать его в форме Лагранжа, хотя имеется ряд равносильных представлений, например, в  
 
Будем искать его в форме Лагранжа, хотя имеется ряд равносильных представлений, например, в  
 
форме Ньютона.
 
форме Ньютона.
  
Докажем от противного, что если такой полином существует, то только один. Допустим, что существует еще один такой полином <tex>T_n(x_k)</tex>, удовлетворяющий условию <tex>T_n(x_k) = y_k</tex>.
+
Докажем от противного, что таких полиномов не более одного. Допустим, что существует еще один такой полином <tex>\tilde P_n</tex>.
Рассмотрим полином <tex>M_n(x_k) = P_n(x_k) - T_n(x_k)</tex>. Тогда <tex>M_n(x_k) = y_k - y_k = 0, k = \overline{0,n}</tex>.
+
Рассмотрим полином <tex>M_n = P_n - \tilde P_n</tex>. Тогда&nbsp;<tex>M_n(x_k) = y_k - y_k = 0, k = \overline{0,n}</tex>,
То есть этот полином имеет  <tex>n+1</tex> корень, но <tex>deg M_n(x) \le n</tex>. Получили противоречие, значит наше предположение неверно, что и требовалось доказать.
+
то есть этот полином имеет  <tex>n+1</tex> корень, но <tex>\deg M_n \le n</tex>. Получили противоречие.
  
  
Строка 33: Строка 33:
 
Для его построения обозначим за <tex>\omega_n(x) = \prod\limits_{j = 0}^n (x - x_j)</tex>. Это полином степени <tex>n + 1</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 dpi = "150">\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 \to x_j</tex> получаем неопределённость <tex dpi = "150">\frac00</tex>. Раскроем её по правилу Лопиталя: <tex dpi = "150">\frac{\omega'_n(x)}{\omega_n'(x_j)} = 1</tex> при <tex>x \to x_j</tex>.
 
Тогда доопределим по непрерывности дробь единицей. Но при <tex>x \ne x_j</tex> &mdash; это полином <tex>n</tex>-й степени. Значит,  
 
Тогда доопределим по непрерывности дробь единицей. Но при <tex>x \ne x_j</tex> &mdash; это полином <tex>n</tex>-й степени. Значит,  
<tex>\Phi_j(x) = \frac{\omega_n(x)}{(x-x_j) \cdot \omega_n'(x_j)}</tex>.
+
<tex dpi = "150">\Phi_j(x) = \frac{\omega_n(x)}{(x-x_j) \cdot \omega_n'(x_j)}</tex>.
  
 
Тогда  
 
Тогда  
Строка 46: Строка 46:
 
\end{aligned}\right.
 
\end{aligned}\right.
 
</tex>, что и требовалось.
 
</tex>, что и требовалось.
`
+
 
 
Обозначим <tex>L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)</tex>.
 
Обозначим <tex>L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)</tex>.
  
Строка 55: Строка 55:
 
Замечание: из формулы для фундаментальных полиномов <tex>\Phi_j(x)</tex> легко записать в развёрнутом виде:
 
Замечание: из формулы для фундаментальных полиномов <tex>\Phi_j(x)</tex> легко записать в развёрнутом виде:
  
<tex>
+
<tex dpi = "150">
 
\Phi_j(x) = \frac
 
\Phi_j(x) = \frac
 
{(x-x_0)(x - x_1)\cdots(x - x_{j- 1})(x - x_{j + 1})\cdots(x - x_n)}
 
{(x-x_0)(x - x_1)\cdots(x - x_{j- 1})(x - x_{j + 1})\cdots(x - x_n)}
Строка 62: Строка 62:
  
 
== Трактовки и другие задачи ==
 
== Трактовки и другие задачи ==
Выведенную ранее формулу Тейлора можно трактовать следующим образом:  
+
Выведенную ранее [[Формула Тейлора для произвольной функции|формулу Тейлора]] можно трактовать следующим образом:  
«Дано <tex>f(x)</tex>. Найти полином <tex>T_n</tex> степени не выше <tex>n</tex> такой, что <tex>f^{(k)}(x_0) = T_n^{(k)}(x_0), k = \overline{0, n}</tex>».
+
«Дана функция <tex>f(x)</tex>. Найти полином <tex>T_n</tex> степени не выше <tex>n</tex> такой, что <tex>f^{(k)}(x_0) = T_n^{(k)}(x_0), k = \overline{0, n}</tex>».
  
 
Ранее мы обнаружили, что это  
 
Ранее мы обнаружили, что это  
Строка 82: Строка 82:
 
</tex>.
 
</tex>.
  
Сейчас будет доказана теорема аналогичная теореме об интерполяционном полиноме Лагранжа, после чего станет ясно, что это задачи одного класса.
+
Сейчас будет доказана теорема, аналогичная теореме об интерполяционном полиноме Лагранжа, после чего станет ясно, что это задачи одного класса.
 
Во втором случае это изложено на языке производных, а в первом &mdash; через значения функции в точках.
 
Во втором случае это изложено на языке производных, а в первом &mdash; через значения функции в точках.
  
Строка 94: Строка 94:
 
Лагранжа
 
Лагранжа
 
|statement=  
 
|statement=  
Пусть <tex>f</tex> <tex>n + 1</tex> раз дифференцируема на <tex>\langle a; b\rangle</tex>. На этом промежутке задана система узлов. Тогда для соответственного  
+
Пусть <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> &mdash; некоторая точка из <tex>\langle a; b \rangle</tex>, зависящая от <tex>x</tex>.  
+
<tex>f(x) = L_n(x) + \frac{f^{(n + 1)}(c_x)}{(n+1)!} \cdot \omega_n(x)</tex>, где <tex>c_x</tex> &mdash; некоторая точка из <tex>\langle a; b \rangle</tex>, зависящая от <tex>x</tex>.  
 
|proof=
 
|proof=
Случай <tex>x = x_k, k = \overline{1, n}</tex> тривиален.
+
Случай <tex>x = x_k</tex> тривиален.
 
Пусть тогда <tex>x \ne x_k</tex>.
 
Пусть тогда <tex>x \ne x_k</tex>.
  
Строка 104: Строка 104:
 
подлежащий определению, а <tex>x</tex> дано.
 
подлежащий определению, а <tex>x</tex> дано.
  
<tex>g(x_j) = f(x_j) - L_n(x_j) - k \omega_n(x_j) = 0</tex>
+
<tex>\forall j = \overline{0, n}:\quad 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>k</tex> потребуем, чтобы <tex>g(x)</tex> было равно <tex>0</tex>.  
Строка 112: Строка 112:
 
<tex>\omega_n(x) \ne 0</tex>, так как <tex>x \ne x_j</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 = \frac{f(x) - L_n(x)}{\omega_n(x)}\quad (1)\, .</tex>
  
 
Итак, при выбранном <tex>k</tex> будет <tex>g(x_j) = 0</tex>, <tex>g(x) = 0</tex>, то есть <tex>g</tex> принимает нулевые значения в <tex>n + 2</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>x</tex> можно сделать <tex>n + 1</tex> последовательный отрезок. На конце каждого из них <tex>g</tex> принимает значение <tex>0</tex>.
Значит, по теореме Ролля на каждом из них найдётся по корню производной. Из полученных корней можно сделать <tex>n</tex> отрезков,  
+
Значит, по теореме Ролля на каждом из них найдётся по корню [[Дифференциал и производная|производной]]. Из полученных корней можно сделать <tex>n</tex> отрезков,  
 
на каждом из них по теореме Ролля найдётся по корню второй производной… В конце концов останется один отрезок, границами которого
 
на каждом из них по теореме Ролля найдётся по корню второй производной… В конце концов останется один отрезок, границами которого
 
будут корни <tex>g^{(n)}</tex>. Тогда по теореме Ролля на этом отрезке найдётся корень <tex>g^{(n + 1)}</tex>. Его и обозначим за <tex>c_x</tex>.
 
будут корни <tex>g^{(n)}</tex>. Тогда по теореме Ролля на этом отрезке найдётся корень <tex>g^{(n + 1)}</tex>. Его и обозначим за <tex>c_x</tex>.
Строка 124: Строка 124:
 
<tex>g(t) = f(t) - L_n(t) - k \omega_n(t)</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>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 + 1)}_n = (n + 1)!</tex>.
  
 
Таким образом, <tex>g^{(n + 1)}(t) = f^{(n + 1)}(t) - k\cdot (n + 1)!</tex>.  
 
Таким образом, <tex>g^{(n + 1)}(t) = f^{(n + 1)}(t) - k\cdot (n + 1)!</tex>.  
Строка 132: Строка 132:
 
<tex>0 = g^{(n + 1)}(c_x) = f^{(n + 1)}(c_x) - k\cdot (n + 1)!</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>
+
<tex>k = \frac{f^{(n + 1)}(c_x)}{(n + 1)!}\quad (2)\, .</tex>
 +
 
 +
Утверждение теоремы напрямую следует из равенств <tex>(1)</tex> и <tex>(2)</tex> .
 
}}
 
}}
  
 
=== Следствие ===
 
=== Следствие ===
  
В условии теоремы было неравенство <tex>|f(x) - L_n(x)| \leq \frac{M_{n + 1}}{(n + 1)!} (b - a)^{n + 1}</tex>,  
+
В условиях теоремы выполняется неравенство <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>M_{n + 1} = \sup\limits_{\langle a; b \rangle} |f^{(n + 1)}|.</tex>
 +
 
 +
Оно следует из того, что для всех <tex>x</tex> на <tex>\langle a; b \rangle\,|x - x_j| \le b - a.</tex>
  
 
=== Замечание ===
 
=== Замечание ===
  
 
Следует понимать, что на самом деле какую бы систему узлов мы не взяли на <tex>\langle a; b \rangle</tex> как по числу
 
Следует понимать, что на самом деле какую бы систему узлов мы не взяли на <tex>\langle a; b \rangle</tex> как по числу
точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить интерполяционный многочлен,
+
точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить непрерывную функцию, для которой ее интерполяционный многочлен будет отличаться от неё сколь угодно много.
который будет отличаться от неё сколь угодно много(нипанянтна &mdash; прим. наборщика)
 
  
 
[[Категория:Математический анализ 1 курс]]
 
[[Категория:Математический анализ 1 курс]]

Текущая версия на 19:27, 4 сентября 2022

Задача интерполяции

Определение:
Система узлов — набор из чисел [math]x_0 \lt x_1 \lt x_2 \lt \ldots \lt x_n[/math] и [math]y_0, y_1, y_2, \ldots ,y_n[/math].


Дана система узлов. Требуется найти полином [math]P_n[/math] степени не выше [math]n[/math] такой, что [math]P_n(x_k) = y_k, k=\overline{0,n}[/math].

Будем искать его в форме Лагранжа, хотя имеется ряд равносильных представлений, например, в форме Ньютона.

Докажем от противного, что таких полиномов не более одного. Допустим, что существует еще один такой полином [math]\tilde P_n[/math]. Рассмотрим полином [math]M_n = P_n - \tilde P_n[/math]. Тогда [math]M_n(x_k) = y_k - y_k = 0, k = \overline{0,n}[/math], то есть этот полином имеет [math]n+1[/math] корень, но [math]\deg M_n \le n[/math]. Получили противоречие.


Будем искать его в форме Лагранжа. Для этого построим фундаментальные полиномы.


Определение:
Фундаментальные полиномы [math]\Phi_j(x)[/math] степени не выше [math]n[/math] — полиномы, отвечающие заданной

системе узлов [math]x_0 \lt x_1 \lt x_2 \lt \ldots \lt x_n[/math] такие, что

[math] \Phi_j(x_k) = \left\{ \begin{aligned} 1 & ,\quad k = j\\ 0 & ,\quad k \ne j\\ \end{aligned}\right. [/math].


Для его построения обозначим за [math]\omega_n(x) = \prod\limits_{j = 0}^n (x - x_j)[/math]. Это полином степени [math]n + 1[/math].

Составим выражение [math]\frac{\omega_n(x)}{(x - x_j) \cdot \omega_n'(x_j)}[/math], [math]x \ne x_j[/math]. В этом случае дробь корректно определена. При [math]x \to x_j[/math] получаем неопределённость [math]\frac00[/math]. Раскроем её по правилу Лопиталя: [math]\frac{\omega'_n(x)}{\omega_n'(x_j)} = 1[/math] при [math]x \to x_j[/math]. Тогда доопределим по непрерывности дробь единицей. Но при [math]x \ne x_j[/math] — это полином [math]n[/math]-й степени. Значит, [math]\Phi_j(x) = \frac{\omega_n(x)}{(x-x_j) \cdot \omega_n'(x_j)}[/math].

Тогда [math] \Phi_j(x_k) = \left\{ \begin{aligned} 1 & ,\quad k = j\\ 0 & ,\quad k \ne j\\ \end{aligned}\right. [/math], что и требовалось.

Обозначим [math]L_n(x) = \sum\limits_{j = 0}^n y_j \Phi_j(x)[/math].

[math]L_n(x_k) = \sum\limits_{j = 0}^n y_j \Phi_j(x_k) = y_k \Phi_k(x_k) = y_k[/math].

Требуемый полином [math]L_n(x)[/math] найден.

Замечание: из формулы для фундаментальных полиномов [math]\Phi_j(x)[/math] легко записать в развёрнутом виде:

[math] \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)} [/math]

Трактовки и другие задачи

Выведенную ранее формулу Тейлора можно трактовать следующим образом: «Дана функция [math]f(x)[/math]. Найти полином [math]T_n[/math] степени не выше [math]n[/math] такой, что [math]f^{(k)}(x_0) = T_n^{(k)}(x_0), k = \overline{0, n}[/math]».

Ранее мы обнаружили, что это [math]T_n(x) = \sum\limits_{k = 0}^n \frac {f^{(k)}(x_0)} {k!} \cdot (x - x_0)^k [/math].

Теперь другая задача: «Дана функция [math]f[/math] и система узлов. Требуется найти полином [math]L_n[/math] степени не выше [math]n[/math] такой, что [math]\forall x_j: j = \overline{0..n}\quad L_n(x_j) = f(x_j)[/math] »

Положим [math]L_n(x) = \sum\limits_{j = 0}^n \Phi_j(x_j) \cdot f(x_j)[/math]. По пункту 1 этот полином решает поставленную задачу. Для полинома Тейлора [math]f(x) = T_n(x) + \frac {f^{(n + 1)}(c_x)} {(n + 1)!} \cdot (x - x_0)^{n + 1} [/math].

Сейчас будет доказана теорема, аналогичная теореме об интерполяционном полиноме Лагранжа, после чего станет ясно, что это задачи одного класса. Во втором случае это изложено на языке производных, а в первом — через значения функции в точках.

Эти два метода метода можно комбинировать, лишь бы информативных значений было [math]n + 1[/math]. Такие промежуточные задачи называют интерполированием по Эрмиту. Но они никому не нужны.

Теорема Лагранжа

Теорема (Лагранжа):
Пусть [math]f[/math] [math]n + 1[/math] раз дифференцируема на [math]\langle a; b\rangle[/math]. На этом промежутке задана система узлов.

Тогда для соответственного интерполяционного полинома Лагранжа выполняется равенство

[math]f(x) = L_n(x) + \frac{f^{(n + 1)}(c_x)}{(n+1)!} \cdot \omega_n(x)[/math], где [math]c_x[/math] — некоторая точка из [math]\langle a; b \rangle[/math], зависящая от [math]x[/math].
Доказательство:
[math]\triangleright[/math]

Случай [math]x = x_k[/math] тривиален. Пусть тогда [math]x \ne x_k[/math].

Для доказательства применим теорему Ролля. Определим вспомогательную функцию [math]g(t) = f(t) - L_n(t)- k \omega_n(t)[/math], где [math]k[/math] — коэффициент, подлежащий определению, а [math]x[/math] дано.

[math]\forall j = \overline{0, n}:\quad g(x_j) = f(x_j) - L_n(x_j) - k \omega_n(x_j) = 0[/math]

Для определения [math]k[/math] потребуем, чтобы [math]g(x)[/math] было равно [math]0[/math].

[math]g(x) = f(x) - L_n(x) - k \omega_n(x) = 0[/math]

[math]\omega_n(x) \ne 0[/math], так как [math]x \ne x_j[/math].

[math]k = \frac{f(x) - L_n(x)}{\omega_n(x)}\quad (1)\, .[/math]

Итак, при выбранном [math]k[/math] будет [math]g(x_j) = 0[/math], [math]g(x) = 0[/math], то есть [math]g[/math] принимает нулевые значения в [math]n + 2[/math] точках. Очевидно, из узлов и точки [math]x[/math] можно сделать [math]n + 1[/math] последовательный отрезок. На конце каждого из них [math]g[/math] принимает значение [math]0[/math]. Значит, по теореме Ролля на каждом из них найдётся по корню производной. Из полученных корней можно сделать [math]n[/math] отрезков, на каждом из них по теореме Ролля найдётся по корню второй производной… В конце концов останется один отрезок, границами которого будут корни [math]g^{(n)}[/math]. Тогда по теореме Ролля на этом отрезке найдётся корень [math]g^{(n + 1)}[/math]. Его и обозначим за [math]c_x[/math].

Подведём промежуточный итог: найдено [math]c_x[/math] такое, что [math]g^{(n + 1)}(c_x) = 0[/math].

[math]g(t) = f(t) - L_n(t) - k \omega_n(t)[/math]

Продифференцируем [math]n + 1[/math] раз. [math]\deg L_n(x) \leq n \Rightarrow L_n^{(n + 1)} = 0[/math]. [math]\omega_n(t) = t^{n + 1} + \ldots \Rightarrow \omega^{(n + 1)}_n = (n + 1)![/math].

Таким образом, [math]g^{(n + 1)}(t) = f^{(n + 1)}(t) - k\cdot (n + 1)![/math].

Подставим [math]t = c_x[/math].

[math]0 = g^{(n + 1)}(c_x) = f^{(n + 1)}(c_x) - k\cdot (n + 1)![/math]

[math]k = \frac{f^{(n + 1)}(c_x)}{(n + 1)!}\quad (2)\, .[/math]

Утверждение теоремы напрямую следует из равенств [math](1)[/math] и [math](2)[/math] .
[math]\triangleleft[/math]

Следствие

В условиях теоремы выполняется неравенство [math]|f(x) - L_n(x)| \leq \frac{M_{n + 1}}{(n + 1)!} (b - a)^{n + 1}[/math], где [math]M_{n + 1} = \sup\limits_{\langle a; b \rangle} |f^{(n + 1)}|.[/math]

Оно следует из того, что для всех [math]x[/math] на [math]\langle a; b \rangle\,|x - x_j| \le b - a.[/math]

Замечание

Следует понимать, что на самом деле какую бы систему узлов мы не взяли на [math]\langle a; b \rangle[/math] как по числу точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить непрерывную функцию, для которой ее интерполяционный многочлен будет отличаться от неё сколь угодно много.