Интерполяционный многочлен: различия между версиями
[непроверенная версия] | [непроверенная версия] |
м шаблон, категория |
Нет описания правки |
||
Строка 1: | Строка 1: | ||
⚫ | |||
<!-- #REDIRECT [[Интерполяционный многочлен Лагранжа]]--> |
|||
⚫ | |||
== Задача интерполяции == |
== Задача интерполяции == |
||
Пусть в пространстве заданы <math>n</math> точек |
Пусть в пространстве заданы <math>n</math> точек <math>P_1, P_2,\dots, P_n</math>, которые в некоторой |
||
системе координат имеют радиус-векторы <math>\mathbf{r}_1, \mathbf{r}_2,\dots, \mathbf{r}_n</math>. |
системе координат имеют радиус-векторы <math>\mathbf{r}_1, \mathbf{r}_2,\dots, \mathbf{r}_n</math>. |
||
Задача интерполяции состоит в построении кривой, проходящей через указанные точки |
Задача интерполяции состоит в построении кривой, проходящей через указанные точки |
||
в указанном порядке. |
в указанном порядке. |
||
Конечно, через фиксированный набор точек можно провести бесконечное число кривых, |
Конечно, через фиксированный набор точек можно провести бесконечное число кривых, |
||
так что задача интерполяции не имеет единственного решения. |
так что задача интерполяции не имеет единственного решения. |
||
Будем строить кривые в виде <math>\mathbf{r}(t)</math>, где параметр <math>t</math> изменяется на некотором отрезке |
Будем строить кривые в виде <math>\mathbf{r}(t)</math>, где параметр <math>t</math> изменяется на некотором отрезке |
||
<math>~ [a, b] </math>: |
<math>~ [a, b] </math>: |
||
<math>~ a\leq t \leq b </math>. Введем на отрезке <math>~ [a, b] </math> |
<math>~ a\leq t \leq b </math>. Введем на отрезке <math>~ [a, b] </math> |
||
сетку <math>~ \{t_i\}</math> из <math>~ n </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>~ t=t_i </math> кривая проходила через точку <math>~ P_i </math>, так что <math>~ \mathbf{r}(t_i)=\mathbf{r}_i</math>. |
||
Введение параметризации и сетки может быть выполнено различными способами. Обычно выбирают либо равномерную сетку, полагая |
Введение параметризации и сетки может быть выполнено различными способами. Обычно выбирают либо равномерную сетку, полагая |
||
Строка 18: | Строка 18: | ||
\mathbf{r}_{i}</math>. |
\mathbf{r}_{i}</math>. |
||
Одним из распространенных способов интерполяции является использование кривой в виде многочлена от <math>~ t</math> |
Одним из распространенных способов интерполяции является использование кривой в виде многочлена от <math>~ t</math> |
||
степени <math>~ n-1</math>, |
степени <math>~ n-1</math>, то есть в виде функции |
||
<math>~ |
<math>~ |
||
Строка 25: | Строка 25: | ||
</math> |
</math> |
||
Многочлен |
Многочлен имеет <math>~ n</math> коэффициентов <math>~ \mathbf{a}_k</math>, которые можно найти из условий |
||
<math>~ \mathbf{r}(t_i)=\mathbf{r}_i</math>. |
<math>~ \mathbf{r}(t_i)=\mathbf{r}_i</math>. |
||
Эти условия приводят к системе линейных уравнений для коэффициентов <math>~ \mathbf{a}_k</math> |
Эти условия приводят к системе линейных уравнений для коэффициентов <math>~ \mathbf{a}_k</math> |
||
Строка 44: | Строка 44: | ||
</math> |
</math> |
||
Обратим внимание, что нужно решить три системы уравнений: для <math>~ x</math>, |
Обратим внимание, что нужно решить три системы уравнений: для <math>~ x</math>, <math>~ y</math> и |
||
<math>~ z</math> координат. Все они имеют одну матрицу коэффициентов, |
<math>~ z</math> координат. Все они имеют одну матрицу коэффициентов, |
||
обращая которую, по значениям радиус-векторов <math>~ \mathbf{r}_i</math> точек вычисляются векторы |
обращая которую, по значениям радиус-векторов <math>~ \mathbf{r}_i</math> точек вычисляются векторы |
||
Строка 68: | Строка 68: | ||
К достоинствам можно отнести его следующие свойства: |
К достоинствам можно отнести его следующие свойства: |
||
* Для заданного набора точек и сетки параметра кривая строится однозначно. |
* Для заданного набора точек и сетки параметра кривая строится однозначно. |
||
* Кривая является интерполяционной, |
* Кривая является интерполяционной, то есть проходит через все заданные точки. |
||
* Кривая имеет непрерывные производные любого порядка. |
* Кривая имеет непрерывные производные любого порядка. |
||
Строка 76: | Строка 76: | ||
;Пример |
;Пример |
||
[[ |
[[Файл:Runge01.svg|thumb|Интерполяция на последовательности сеток. Пример Рунге.]] |
||
Классическим примером ([[Рунге, Карл|Рунге]]), показывающим возникновение осцилляций у интерполяционного |
Классическим примером ([[Рунге, Карл|Рунге]]), показывающим возникновение осцилляций у интерполяционного |
||
многочлена, служит интерполяция на равномерной сетке значений функции |
многочлена, служит интерполяция на равномерной сетке значений функции |
||
Строка 84: | Строка 84: | ||
</math> |
</math> |
||
Введем на отрезке <math>~ [-5, 5]</math> равномерную сетку <math>~ x_i=-5+(i-1)h</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>~ h=10/(n-1)</math>, <math>~ 1 \leq i \leq n</math> и рассмотрим поведение многочлена |
||
Строка 90: | Строка 90: | ||
y(x) = \sum_{i=1}^n a_i x^{n-i} |
y(x) = \sum_{i=1}^n a_i x^{n-i} |
||
</math> |
</math> |
||
который в точках <math>~ x_i</math> принимает значения <math>~ y_i=1/(1+x_i^2)</math>. |
который в точках <math>~ x_i</math> принимает значения <math>~ y_i=1/(1+x_i^2)</math>. |
||
На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при <math>~ n=3, 5, 9</math>: |
На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при <math>~ n=3, 5, 9</math>: |
||
* интерполяция на сетке <math>~ x_1=-5, x_2=0, x_3=5</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=-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> |
* интерполяция на сетке <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> — многочлен восьмой степени. |
||
Мы видим, что значения интерполяционного многочлена даже для гладких функций в промежуточных точках |
Мы видим, что значения интерполяционного многочлена даже для гладких функций в промежуточных точках |
||
Строка 103: | Строка 102: | ||
{{rq|sources|topic=math}} |
{{rq|sources|topic=math}} |
||
[[Категория:Интерполяция]] |
[[Категория:Интерполяция]] |
||
[[Категория:Многочлены]] |
|||
[[Категория:Математический анализ]] |
Версия от 22:02, 22 февраля 2009
Необходимо перенести содержимое этой статьи в статью Интерполяция алгебраическими многочленами и заменить эту статью на перенаправление. |
Задача интерполяции
Пусть в пространстве заданы точек , которые в некоторой системе координат имеют радиус-векторы . Задача интерполяции состоит в построении кривой, проходящей через указанные точки в указанном порядке. Конечно, через фиксированный набор точек можно провести бесконечное число кривых, так что задача интерполяции не имеет единственного решения. Будем строить кривые в виде , где параметр изменяется на некотором отрезке : . Введем на отрезке сетку из точек: и потребуем, чтобы при значении параметра кривая проходила через точку , так что . Введение параметризации и сетки может быть выполнено различными способами. Обычно выбирают либо равномерную сетку, полагая , , , либо, что более предпочтительно, соединяют точки отрезками и в качестве разности значений параметра берут длину отрезка .
Одним из распространенных способов интерполяции является использование кривой в виде многочлена от степени , то есть в виде функции
Многочлен имеет коэффициентов , которые можно найти из условий . Эти условия приводят к системе линейных уравнений для коэффициентов
Обратим внимание, что нужно решить три системы уравнений: для , и координат. Все они имеют одну матрицу коэффициентов, обращая которую, по значениям радиус-векторов точек вычисляются векторы коэффициентов многочлена. Определитель матрицы
называется определителем Вандермонда. Если узлы сетки не совпадают, он отличен от нуля, так что система уравнений имеет решение.
Кроме прямого обращения матрицы, имеются несколько других способов вычисления интерполяционного многочлена, некоторые из которых мы рассмотрим далее. Подчеркнем, что в силу единственности многочлена, речь идет о различных формах его записи.
Обсудим достоинства и недостатки интерполяционного многочлена. К достоинствам можно отнести его следующие свойства:
- Для заданного набора точек и сетки параметра кривая строится однозначно.
- Кривая является интерполяционной, то есть проходит через все заданные точки.
- Кривая имеет непрерывные производные любого порядка.
Основные недостатки состоят в том, что:
- С ростом числа точек порядок многочлена возрастает, а вместе с ним возрастает число операций, которое нужно выполнить для вычисления точки на кривой.
- С ростом числа точек у интерполяционной кривой могут возникнуть осцилляции (см. пример ниже).
- Пример
Классическим примером (Рунге), показывающим возникновение осцилляций у интерполяционного многочлена, служит интерполяция на равномерной сетке значений функции
Введем на отрезке равномерную сетку , , и рассмотрим поведение многочлена
который в точках принимает значения . На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при :
- интерполяция на сетке — квадратичная парабола;
- интерполяция на сетке — многочлен четвертой степени;
- интерполяция на сетке — многочлен восьмой степени.
Мы видим, что значения интерполяционного многочлена даже для гладких функций в промежуточных точках могут сильно уклоняться от значений самой функции.
Для улучшения этой статьи по математике желательно:
|