Википедия

Интерполяция алгебраическими многочленами: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎Преамбула: исправил ошибку, оформление
м Удаление принудительных пробелов в формулах по ВП:РДБ.
Строка 14:
 
== Применение ==
 
Полученную интерполяционную [[Математическая формула|формулу]] <math>f(x) \approx P_n(x)</math> часто используют для приближённого вычисления значений функции ''f'' при значениях аргумента ''x'', отличных от узлов интерполирования. При этом различают ''[[Интерполяция|интерполирование]]'' в узком смысле, когда <math>x \in \left[ x_0, x_n \right]</math>, и ''[[Экстраполяция|экстраполирование]]'', когда <math>x \in \left[ a, b \right]</math>, <math>x \not\in \left[ x_0, x_n \right]</math>
 
Строка 24 ⟶ 23 :
 
== Решение задачи ==
 
Через фиксированный набор точек можно провести бесконечное число кривых, поэтому задача интерполяции не имеет единственного решения.
 
Будем строить кривые в виде <math>\mathbf{r}(t)</math>, где параметр <math>t</math> изменяется на некотором отрезке
<math>~ [a, b] </math>:
<math>~ a\leq t \leq b </math>. Введем на отрезке <math>~ [a, b] </math>
сетку <math>~ \{t_i\}</math> из <math>~ n </math> точек: <math>~ a=t_1 < t_2 < t_3<\dots < t_n=b </math> и потребуем, чтобы при значении параметра
<math>~ t=t_i </math> кривая проходила через точку <math>~ P_i </math>, так что <math>~ \mathbf{r}(t_i)=\mathbf{r}_i</math>.
 
Введение параметризации и сетки может быть выполнено различными способами. Обычно выбирают либо равномерную сетку, полагая
<math>~ a=0 </math>, <math>~ b=n-1</math>, <math>~ t_i=i-1</math>, либо, что более предпочтительно, соединяют точки отрезками и
в качестве разности значений параметра <math>~ t_{i+1}-t_i</math> берут длину отрезка <math>~ \mathbf{r}_{i+1}-
\mathbf{r}_{i}</math>.
 
Одним из распространенных способов интерполяции является использование кривой в виде многочлена от <math>~ t</math>
степени <math>~ n-1</math>, то есть в виде функции
 
<math>\mathbf{r}(t) = \mathbf{p}^{(n-1)}(t) =\sum_{k=1}^n \mathbf{a}_k t^{n-k}▼
<math>~
▲\mathbf{r}(t) = \mathbf{p}^{(n-1)}(t) =\sum_{k=1}^n \mathbf{a}_k t^{n-k}
</math>
 
Многочлен имеет <math>~ n</math> коэффициентов <math>~ \mathbf{a}_k</math>, которые можно найти из условий
<math>~ \mathbf{r}(t_i)=\mathbf{r}_i</math>.
 
Эти условия приводят к системе линейных уравнений для коэффициентов <math>~ \mathbf{a}_k</math>
 
<math>~\begin{pmatrix}
\begin{pmatrix}
1 & t_1 & t_1^2 & \ldots & t_1^{n-1} \\
1 & t_2 & t_2^2 & \ldots & t_2^{n-1} \\
Строка 65 ⟶ 61 :
</math>
 
Обратим внимание, что нужно решить три системы уравнений: для <math>~ x</math>, <math>~ y</math> и
<math>~ z</math> координат. Все они имеют одну матрицу коэффициентов,
обращая которую, по значениям радиус-векторов <math>~ \mathbf{r}_i</math> точек вычисляются векторы
<math>~ \mathbf{a}_k</math> коэффициентов многочлена. Определитель матрицы
 
<math>W(t_1, t_2, \ldots , t_n) = \begin{vmatrix}▼
<math>~
▲W(t_1, t_2, \ldots , t_n) = \begin{vmatrix}
1 & t_1 & t_1^2 & \ldots & t_1^{n-1} \\
1 & t_2 & t_2^2 & \ldots & t_2^{n-1} \\
Строка 79 ⟶ 74 :
</math>
 
называется [[Определитель Вандермонда| определителем Вандермонда]]. Если узлы сетки не совпадают, он отличен от нуля, так что
система уравнений имеет решение.
 
Строка 86 ⟶ 81 :
 
== Преимущества ==
 
* Для заданного набора точек и сетки параметра кривая строится однозначно.
* Кривая является интерполяционной, то есть проходит через все заданные точки.
Строка 92 ⟶ 86 :
 
== Недостатки ==
 
* С ростом числа точек порядок многочлена возрастает, а вместе с ним возрастает число операций, которое нужно выполнить для вычисления точки на кривой.
* С ростом числа точек у интерполяционной кривой могут возникнуть осцилляции (см. пример ниже).
Строка 101 ⟶ 94 :
Классическим примером ([[Рунге, Карл|Рунге]]), показывающим возникновение осцилляций у интерполяционного многочлена, служит интерполяция на равномерной сетке значений функции
 
<math>~f(x) = \frac{1}{1+x^2}
f(x) = \frac{1}{1+x^2}
</math>
 
Введем на отрезке <math>~ [-5, 5]</math> равномерную сетку <math>~ x_i=-5+(i-1)h</math>,
<math>~ h=10/(n-1)</math>, <math>~ 1 \leq i \leq n</math> и рассмотрим поведение многочлена
 
<math>y(x) = \sum_{i=1}^n a_i x^{n-i}▼
<math>~
▲y(x) = \sum_{i=1}^n a_i x^{n-i}
</math>
 
который в точках <math>~ x_i</math> принимает значения <math>~ y_i=1/(1+x_i^2)</math>.
На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при <math>~ n=3, 5, 9</math>:
* интерполяция на сетке <math>~ x_1=-5, x_2=0, x_3=5</math> — квадратичная парабола;
* интерполяция на сетке <math>~ x_1=-5, x_2=-2.5, x_3=0, x_4=2.5, x_5=5</math> — многочлен четвертой степени;
* интерполяция на сетке <math>~ x_1=-5, x_2=-3.75, x_3=-2.5, x_4=-1.25, x_5=0, x_6=1.25, x_7=2.5, x_8=3.75, x_9=5</math> — многочлен восьмой степени.
 
Значения интерполяционного многочлена даже для гладких функций в промежуточных точках могут сильно уклоняться от значений самой функции.
Строка 125 ⟶ 116 :
*[[Вейвлет]]
 
[[Категория: Интерполяция]]
[[Категория:Математический анализ]]
[[Категория:Многочлены]]
Источник — https://ru.wikipedia.org/wiki/Интерполяция_алгебраическими_многочленами