Интерполяция

[coll3ctor]

Доброго времени суток! Пишу сюда за поомщью уже не первый раз, и всегда я получал отличные ответы и всё понимал. На это раз надеюсь всё будет так же
На этот раз нужно реализовать (запрогать) задачу интеполяции. Численных методов у нас не было (а это в какую сферу вообще?), поэтому за простым объяснением решил обратиться сюда (книжки проштудировал, и некое представление имею). В общем, само задание:

Интерполированиее функции, заданной в ${n+1}$ точках, тригонометрическим полиномом.

1. Что такое интерполяция и зачем она нужна?
Ну, как я понял, интерполяция (простым языком), позволяет разбить функцию на более простые, что нам всё существенно упростит.
2. Интерполировать можно не только функции, ведь так?
3. Заданной в ${n+1}$ точках. В смысле неизвестно какой функция "длины"?
4. Тригонометрический полином. Вот с этим совсем тяжко. вот ссылка http://www.machinelearning.ru/wiki/index.php?title=%D0%A2%D1%80%D0%B8%D0%B3%D0%BE%D0%BD%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D1%8F, это "то", скажите пожалуйста ?

[ewert]

coll3ctor в сообщении #480152 писал(а):

Что такое интерполяция

Это подбор такого многочлена $P_n(x)$, что $P_n(x_i)=y_i$ в каждой из заданных $(n+1)$ точек, где $x_i$ -- сами точки ("узлы") и $y_i$ -- заданные "узловые значения". Технически самый простой способ решения -- записать эти равенства как систему линейных уравнений для коэффициентов многочлена и решить её. Правда, для алгебраических или тригонометрических многочленов есть и явные формулы, но они удобны скорее для теоретических целей, чем для получения численного ответа.

coll3ctor в сообщении #480152 писал(а):

В смысле неизвестно какой функция "длины"?

Если под "длиной" понимается промежуток $[a;b)$, на котором расположены эти точки, то -- да, для тригонометрического многочлена $P_{2m}(x)=a_0+\sum\limits_{k=1}^m(a_k\cos\frac{2\pi k(x-a)}{b-a}+b_k\sin\frac{2\pi k(x-a)}{b-a})$ этот промежуток должен быть указан явно, иначе постановка задачи бессмысленна. Кроме того, количество точек обязано быть нечётным (в вещественном случае, но комплексный практически и малоинтересен): $n+1=2m+1$, в противном случае задача некорректна.

[coll3ctor]

ewert, благодарствую! А периодичность исходной функции влияет на что-то или нет?

[ewert]

coll3ctor в сообщении #480166 писал(а):

А периодичность исходной функции влияет на что-то или нет?

Формально -- нет. Просто для разных задач целесообразно использовать разные типы многочленов, и если приближаемая функция периодична, то наиболее адекватны многочлены именно тригонометрические. Потому что если точек достаточно много, то алгебраический многочлен начнёт приплясывать на концах, ему ведь самому по себе периодичность ну никак не свойственна.

[coll3ctor]

ясно. теперь попробую перейти к сути:

Пусть $n=6$, тогда (количество точек) $q=n+1=6+1=7$ $\Rightarrow$ $m=3$.
Пусть $\exists f(y) = y^2 , y\epsilon \mathbb{R}$
Тогда, $P_6(x) = a_0+\sum\limits_{k=1}^{3}({a_k\cos{\frac{2\pi k(x-a)}{b-a}}+b_k\sin{\frac{2\pi k(x-a)}{b-a}}})$

я правильно понял? (впервые сталкиваюсь с такой задачей)

то есть, мы получили тригонометрический полином. Как я понял, задача интерполяции в упрощении, т.е. есть ф-я с набором значений, то мы по этому набору ищем другую функцию.верно? то есть, исходая ф-я (игрик квадрат) $y^2$, можно выписать значения и подставлять в полином чтоли ? или как ?

[Circiter]

2coll3ctor

Цитата:

т.е. есть ф-я с набором значений, то мы по этому набору ищем другую функцию.верно?

Исходная функция вам неизвестна, вы только можете посветить фонариком в узлах интерполяции, фактически в нескольких точках, и узнать чему она в этих точках равна. И потом вы подбирате другую функцию, уже полностью известную, которая бы в тех же узлах давала те же самые значения, то есть в этих точках она бы не отличалась от интерполируемой функции. Таким образом, готовый результат интерполяции --- в виде функции, например полинома --- задан уже не только в узлах, но и между ними, отсюда название -- интерполяция.

Цитата:

можно выписать значения и подставлять в полином чтоли ? или как ?

Перечитайте самый первый ответ ewert'а по вашему вопросу. Там даются почти-что пошаговые инструкции. Суть в выписывании СЛАУ с последующим её решением относительно коэффициентов полинома.

[coll3ctor]

ewert
Circiter,
Спасибо вам за помощь! Я учёл всё, что вы написали, ещё тщательнее порылся в литературе, и кажется, окончательно понял суть этой интерполяции...

$P_{2m}(x)=a_0+\sum\limits_{k=1}^m(a_k\cos\frac{2\pi k(x-a)}{b-a}+b_k\sin\frac{2\pi k(x-a)}{b-a})$ (1)

Пусть, на будущее:
$ a_k\cos\frac{2\pi k(x-a)}{b-a} = \alpha_k $
$ b_k\sin\frac{2\pi k(x-a)}{b-a} = \beta_k $

1. Получаем 2 массива точек $X$ и $Y$ ( только тут вопрос: почему в задании сказано $ n+1 $? странно как то...)
2. $ X.lenght() / 2 = m $;
3. Строим СЛАУ с $ 2m+1 $ уравнениями и $ 2m+1 $ неизвестными:
$ a_0 + \sum\limits_{k=1}^m(a_k\alpha_k) + \sum\limits_{i=1}^m(b_k\beta_k) = y_i $

После преобразования вышестоящей строчки к СЛАУ (нормальному виду), мы его решаем, получаем неизвестные коэффиценты и подставляем их в (1), после чего расписываем, упрощаем, и, то, что получится - это и есть наш продукт интерполяции! (ведь так? то есть там получится ф-ия с сочной тригонометрической начиночкой)

либо же можно наподставлять точек $x$ и $y$ и построить график (ведь мне нужно это запрогать, а $\Rightarrow$ проще будет график)

Вследствие всего вышесказанного спрашиваю:
1. Всё ли я верно написал?
2. И как перейти к "нормальной" СЛАУ? Она будет квадратная же?

[coll3ctor]

+ к прошлому сообщению:

3. что такое $a_0$ ? Ясно, что это какая то константа, но какую роль она играет и как её определять?
4. вообще, для интерполяции другой функцией, алгоритм остаётся примерно таким же ?

[worm2]

coll3ctor писал(а):

что такое $a_0$ ?

Это то, что останется от $a_k\cos\frac{2\pi k(x-a)}{b-a}+b_k\sin\frac{2\pi k(x-a)}{b-a}$, если подставить $k=0$.

Цитата:

для интерполяции другой функцией, алгоритм остаётся примерно таким же ?

Да.

[coll3ctor]

а на позапрошлое то сообщение то и не ответили :( это не так важно для меня с практической точки зрения