2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 12:10 
Имеется ряд заданных узлов аппроксимации - фактических данных (100-200-300 точек). По ним я могу построить обычный полином степени допустим 3-й, оценив зависимость с помощью МНК, ММП, ММ или ещё каким образом.

Возникает вопрос, а зачем нужны ортогональные полиномы - Чебышева, Лежарра и т.п.? Допустим, я строю полиномы Чебышева первого рода $1; x; 2\cdot x^2-1; 4\cdot x^3-3\cdot x$. Далее, я строю зависимость с помощью такого же метода, но по полиномам. Получается модель точно такого же качества, а если в ней вместо полиномов поставить функции от x - коэффициенты при x будут такие же, как в первом случае.

В чём тогда преимущество ортогональных полиномов? Почему считается оптимальным разлагать функции по ним, если результат тот же? Возможно, я чего то недопонимаю, например, это связано с тем, что эти полиномы требуют особый неслучайный выбор узлов интерполяции и описывают не точки, а в целом некую исходную функцию типа sin(x), на заданном отрезке?

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 12:24 
tgv в сообщении #541859 писал(а):
В чём тогда преимущество ортогональных полиномов?

В их ортогональности. Это позволяет обойтись без решения системы уравнений, вычисляя коэффициенты разложения напрямую как коэффициенты Фурье.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 12:34 
Есть такая формула Гаусса-Якоби.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 12:45 
ewert в сообщении #541866 писал(а):
tgv в сообщении #541859 писал(а):
В чём тогда преимущество ортогональных полиномов?

В их ортогональности. Это позволяет обойтись без решения системы уравнений, вычисляя коэффициенты разложения напрямую как коэффициенты Фурье.


Не очень понимаю про преимущество,

мы оцениваем модели
$y = a_0+a_1\cdot x+a_2\cdot x^2+a_3\cdot x^3$ - просто полином от $x$ или
$y = b_0\cdot T_0(x)+b_1\cdot T_1(x)+b_2\cdot T_2(x)+b_3\cdot T_3(x)$, где $Т(x)$ - полиномы Чебышева

Зависимость линейная, 4 неизвестных, 100-200 уравнений - в обоих случаях. Метод используем один и тот же, допустим, МНК. В Eviews обе модели делаются и считаются за 2 минуты, результат один и тот же

 i  AKM:
Замечу, что эти старательно выписанные точечки-умножения (\cdot) в данном случае не особо нужны: $y = b_0 T_0(x)+\ldots$ вполне приемлемо.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 14:01 
Аватара пользователя
 !  tgv, исправьте написание формул в соответствии с Правилами.
Здесь рассказано, как набирать формулы. Используйте кнопку Изображение для редактирования своего сообщения.

Тема перемещена из "Математики (общие вопросы)" в карантин. Как исправите - пишите сюда, чтобы тему вернули.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 16:34 
Аватара пользователя
Вернул в учебный раздел.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 20:18 
Аватара пользователя
В задаче дискретной аппроксимации (по конечному числу точек) использовать ортогональные многочлены необязательно и их преимущество неочевидно. Хотя улучшается обусловленность. А для других задач (например, непрерывной аппроксимации) - см. сообщение ewerta.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение23.02.2012, 21:02 
Аватара пользователя
И в дискретном случае полезно. Только полиномы, ортогональные на дискретном множестве точек и на непрерывном - разные.
А в чём польза? Ну, вот решаем задачу МНК. Матрицу обращаем nxn. $O(n^3)$ операций. А если регрессоры ортогональны - обращаются только диагональные элементы. Для 4х4 разница и незаметна. А для больших размерностей? Далее. Добавляя или удаляя полином - надо всю матрицу переобращать. Для ортогональных - каждый сам по себе, можно независимо рассматривать. Получили коэффициенты модели, интересуемся их ошибками. В общем случае они через обратную матрицу выражаются. В ортогональном - ошибки разных коэффициентов не связаны.
Ну и обусловленность. По мере роста степени полинома положение становится катастрофическим.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение25.02.2012, 11:46 
А откуда у полиномов на дискретном случае возьмётся ортогональность? Когда мы считаем по узлам - корням Чебышева - то понятно, что она выполняется автоматически, т.к. узлы подобраны соответствующим образом. Когда же мы берем фактический дискретный ряд x, то его наверное надо как-то грамотно нормировать от -1 до 1?

Я проверил - загнал в Eviews обычные x и полиномы от x и посмотрел зависимость y от x. Отмечу, что все x лежат в довольно ограниченном интервале где-то около 0-0,3. Качество моделей, значимость коэффициентов (соответственно, ошибки) не меняется. Если же я добавляю дополнительный полином, то коэффициенты при всех предыдущих полиномах меняются! То есть x надо по идее как-то нормировать, а возможно и y? Но позволит ли это тем не менее улучшить качество модели, построенной от полиномов?

Кроме того, разве возможности нынешних компьютеров не позволяют пренебрегать всеми этими проблемами в расчёте матриц для полиномов наиболее востребованных степеней, этак 3-5 порядка? Все эти методы создавались довольно давно, когда проблема наиболее точного и быстрого расчёта была более актуальной.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение25.02.2012, 12:06 
Аватара пользователя
tgv в сообщении #542398 писал(а):
А откуда у полиномов на дискретном случае возьмётся ортогональность?
Сама по себе ортогональность ниоткуда не возьмётся, если, конечно, Вы изначально не возьмёте дискретно-ортогональные многочлены (ортогональные на конечном множестве точек) :mrgreen: .

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение25.02.2012, 17:52 
profrotter в сообщении #542402 писал(а):
tgv в сообщении #542398 писал(а):
А откуда у полиномов на дискретном случае возьмётся ортогональность?
Сама по себе ортогональность ниоткуда не возьмётся, если, конечно, Вы изначально не возьмёте дискретно-ортогональные многочлены (ортогональные на конечном множестве точек) :mrgreen: .


Так вопрос как раз и был - полиномы Чебышева - ортогональные на (-1;1) в непрерывном случае и в дискретном, когда считаем по узлам-корням. Но мы же берём произвольный дискретный набор точек, и ортогональность исчезает. Можно ли тогда говорить о преимуществах полиномов Чебышева в дискретном случае? Или, может, ряд x нужно как-то преобразовывать?

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение25.02.2012, 18:43 
Аватара пользователя
tgv в сообщении #542488 писал(а):
Так вопрос как раз и был - полиномы Чебышева - ортогональные на (-1;1) в непрерывном случае и в дискретном, когда считаем по узлам-корням.

Это будут разные полиномы Чебышёва.
tgv в сообщении #542488 писал(а):
Но мы же берём произвольный дискретный набор точек, и ортогональность исчезает.

Для каждого набора точек будут свои многочлены Чебышёва и своё понятие ортогональности.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение25.02.2012, 21:24 
Аватара пользователя
tgv, ортогональность надо понимать иначе. Вот когда мы рассматриваем систему многочленов, ортогональных на отрезке $[a,b]$, мы вводим скалярное произведение вида $$(p_k,p_m)=\int\limits_a^b p_k(x)p_m(x)w(x)dx,$$ где $w(x)$ - весовая функция.
Когда рассматриваем дискретно-ортогональные многочлены на отрезке $[a,b]$ с сеткой $a=x_0<x_1<...<x_{N-1}=b$, то скалярное произведение $$(p_k,p_m)=\sum\limits_{i=0}^{N-1}p_k(x_i)p_m(x_i)w(x_i),$$ а ортогональными во всех случаях называются такие многочлены, для которых скалярное произведение равно нулю: $$(p_k,p_m)=0$$ и достигаться это равенство нулю вовсе не обязано за счёт того, что многочлены обращаются в нуль на всём наборе точек $\{x_i\}_{i=0}^{N-1}$, более того, этого и не должно быть, ибо такие многолены будут иметь нулевую норму.

Подробнее см. Г.Бейтмен, А.Эрдейи Высшие трансцендентные функции. Функции Бесселя, функции параболического цилиндра, ортогональные многочлены. (Серия "Справочная математическая библиотека") М.: Наука, 1966г., п.10.22 "Ортогональные многочлены дискретного переменного", стр. 219.

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение21.08.2014, 20:06 
profrotter в сообщении #542585 писал(а):
tgv, ортогональность надо понимать иначе. Вот когда мы рассматриваем систему многочленов, ортогональных на отрезке $[a,b]$, мы вводим скалярное произведение вида $$(p_k,p_m)=\int\limits_a^b p_k(x)p_m(x)w(x)dx,$$ где $w(x)$ - весовая функция.
Когда рассматриваем дискретно-ортогональные многочлены на отрезке $[a,b]$ с сеткой $a=x_0<x_1<...<x_{N-1}=b$, то скалярное произведение $$(p_k,p_m)=\sum\limits_{i=0}^{N-1}p_k(x_i)p_m(x_i)w(x_i),$$ а ортогональными во всех случаях называются такие многочлены, для которых скалярное произведение равно нулю: $$(p_k,p_m)=0$$


Если говорить конкретно про многочлены Чебышева, и отобразить экспериментальные точки $\{x_i\}_{i=0}^{N-1}$ на $[-1, 1]$, $a=x_0<x_1<...<x_{N-1}=b$, то получим, что $a \rightarrow -1$, a $b \rightarrow 1$, но многочлены Чебышева нуждаются в весовой функции для ортогональности, возможно такой $w(x_i) = \frac{1}{\sqrt{ 1 - x_i^2}}$, но что на концах $[-1,1]$, на которых мы отразили $a$ и $b$ весовая функция бесконечна? Как быть в этом случае?

 
 
 
 Re: Аппроксимация ортогональными полиномами
Сообщение24.12.2015, 14:05 
Бейтман Эрдейи это сложно ньюбам. Хемминг - численные методы, там кстати очень внятно расписано трехчленное
рекуррентное соотношение Ланкоза- Форсайта. Без которого метод вряд ли осуществИм.
И лучше найти английский оригинал- в переводе встречаются описки.

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group