[Xenia 45]

Полиномы Чебышева. Почему не ортогональны?

 

Среди ортогональных многочленов очень часто упоминаются полиномы Чебышева (первого рода). Везде пишут примерно следующее:

 

Свойства многочленов Чебышева.

1. Система {Tn(x)}_n=0,1,... ортогональна на отрезке [-1,1] с весом h(x)=1/sqrt(1-x²)

Готовых функций, которые генеруют эти полиномы, всюду завались, и по сути все они делают одно и тоже. Короче говоря, сгенерила я эти полиномы от n=0 до n=5 включительно, представляя отрезок [-1,1] в виде массива дискретных элементов, достаточно длинного, чтобы эффект дескретизации сказывался слабо. Например, массив из gap=101 элемента (нечетное количество элементов выбирала для того, чтобы иметь среднюю точку). Номер элемента (i) пересчитывается в значение x из отрезка [-1,1] по формуле:

x = (double)(2*i)/(gap-1) - 1.0;

где: gap - длина массива.

Т.е. 0-й элемент массива соответствует (x=-1.0), а последний 100-й соответствует (x=+1.0). Серединка (50-й элемент) соответствует x=0.

 

Получилась матрица F, размером gap x 6. Если построить графики по столбцам той матрицы, то получим картинку, индентичную той, что нарисована а Википедии:

(форум не хочет эту картинку показывать)

http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%...0%B0_%D0%A2.gif

 

Вроде бы теперь мне только жить, да радоваться :). Только дернуло меня проверить эти вектора на ортогональность - вычислив продукт F*F' (размерность 6 x 6):

    1.0000   -0.0000   -0.3200    0.0000   -0.0556   -0.0000
   -0.0000    0.3400   -0.0000   -0.1878    0.0000   -0.0364
   -0.3200   -0.0000    0.4722   -0.0000   -0.1686   -0.0000
    0.0000   -0.1878   -0.0000    0.4914   -0.0000   -0.1619
   -0.0556    0.0000   -0.1686   -0.0000    0.4981   -0.0000
   -0.0000   -0.0364   -0.0000   -0.1619   -0.0000    0.5016

Тут я этот продукт еще на число gap поделила, чтобы длина вектора не сказывалась.

 

И что вижу? Фигня какая-то... Ортогональны между собой лишь полиномы четных степеней с нечетными, а в остальных случах внедиагональные элементы слишком велики, чтобы их можно было списать на погрешность дискретизации. Впрочем, погрешность дискретизации можно еще понизить, увеличив длину вектора - тогда дискрета станет меньше. Проверила. При длине вектора gap=1001 имею:

    1.0000    0.0000   -0.3320    0.0000   -0.0656   -0.0000
    0.0000    0.3340   -0.0000   -0.1988   -0.0000   -0.0466
   -0.3320   -0.0000    0.4672   -0.0000   -0.1798    0.0000
    0.0000   -0.1988   -0.0000    0.4862    0.0000   -0.1734
   -0.0656   -0.0000   -0.1798    0.0000    0.4926   -0.0000
   -0.0000   -0.0466    0.0000   -0.1734   -0.0000    0.4955

А при gap=10001:

    1.0000   -0.0000   -0.3332    0.0000   -0.0666   -0.0000
   -0.0000    0.3334    0.0000   -0.1999    0.0000   -0.0475
   -0.3332    0.0000    0.4667   -0.0000   -0.1808   -0.0000
    0.0000   -0.1999   -0.0000    0.4858    0.0000   -0.1745
   -0.0666    0.0000   -0.1808    0.0000    0.4921    0.0000
   -0.0000   -0.0475   -0.0000   -0.1745    0.0000    0.4950

Куда еще дальше? Если отрезок [-1,1] представлен вектором, длиной в 10 тыс. элементов, то дискретизация становится исчезающе малой. А у меня корреляции от длины вектора практически не зависят. А корреляция между T0 и Т2 вообще ни в какие ворота не лезет -0.3332. Тем более что, если взять вместо полиномов Чебышева ряды Фурье, то даже на коротеньких массивах в 15-25 элементов ортогональность векторов очень хорошая.

 

Значит, это не погрешность дискретизации. Тогда что?

Где эта хваленая ортогональность, если я ее не вижу? :)

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

[_Ivana 0]

Глупый вопрос навскидку - вы учли

с весом h(x)=1/sqrt(1-x^2)

сразу при генерации матрицы?

[Xenia 45]

Глупый вопрос навскидку - вы учли

сразу при генерации матрицы?

 

Нет, не делила и не учитывала. Нормировкой заниматься не вижу смысла - если вектора ортогональны, то они при любой нормировке таковы. В лучшем случае, этим можно было бы достигнуть, чтобы по диагонали были точные единицы. Но тогда внедиагональное "гадости" становятся только больше, а не меньше! Да и искать ошибку было бы только труднее, если бы туда еще каких-то расчетов насовала.

 

Тут и без расчетов видны несуразности. Скажем, так бяка, что T0 и Т2 дают корреляцию = -0.3332.

Взглянем еще раз на картиночку: http://electronix.ru/redirect.php?http://r...0%B0_%D0%A2.gif

T0 - это красная прямая линия, уровень 1. А T2 - это желтенький, на параболу похожий. Их корреляция в уме вычисляется, т.к. умножение на 1 тривиально. В результате чего должен получиться интеграл желтого. А вы видите как широко он своим языком ниже нуля погрузился? А выше оси только по крашки чуть-чуть выпирают. Ежу ясно, что инетеграл будут не нулевой, а сильно отрицательный. Что и имеет место в расчетах.

 

 

На этой картинке (ее формум показывать не отказывается) T2 - зелененький.

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

[Alexey Lukin 0]

Ксения, ортогональность этих полиномов надо понимать не в обычном смысле, а после домножения на корректирующую функцию:

 

В дискретном же случае они ортогональны на специальной "кривой" сетке, но не на равномерной сетке.

[Xenia 45]

Ксения, ортогональность этих полиномов надо понимать не в обычном смысле, а после домножения на корректирующую функцию:

В дискретном же случае они ортогональны на специальной "кривой" сетке, но не на равномерной сетке.

 

А вы мне можете этим способом показать, что T0 и T2 ортогональны друг другу? Тем более для такого простого случая, когда T0 единичен в любой своей точке, а T2 = 2x²-1.

[_Ivana 0]

Те полиномы, которые нечетны, автоматически ортогональны с Т0 даже без веса (Т0 и Т1, Т0 и Т3 и т.д.) - домножение на четную функцию не изменит общий ноль интерграла - как у Вас и получилось. А другим требуется все-таки домножение на весовую функцию, как и написано выше.

[Xenia 45]

Те полиномы, которые нечетны, автоматически ортогональны с Т0 даже без веса (Т0 и Т1, Т0 и Т3 и т.д.) - домножение на четную функцию не изменит общий ноль интеграла - как у Вас и получилось. А другим требуется все-таки домножение на весовую функцию, как и написано выше.

 

А есть ли какие-нибудь "разумные" полиномы, у которых ортогональность понимается в обычном смысле? Т.е. в виде простого скалярного произведения обоих векторов, содержащих в себе расписанные по дискретам полиномы? Чтобы FF' была диагональной без всяких оговорок?

А то я такие большие планы с полиномами Чебышева связывала, и всё коту под хвост...

[_Ivana 0]

На Лагранжа не хотите возложить надежды и проверить его на обычную ортогональность?

[Xenia 45]

На Лагранжа не хотите возложить надежды и проверить его на обычную ортогональность?

 

Про полиномы Лагранжа я знаю только то, что их для интерполяции используют (даже когда-то их для этой цели использовала сама). Но мне сейчас не интерполировать надо, а нужен подходящий ортогональный базис из гладких функций. Поближе к обычным степенным полиномам, но только, а отличие от них, ортогональный. И чтобы его на МК можно было вычислить, а не через Гамму-фунцию или что-то еще более уродливое. Поэтому на полиномы Чебышева и запала.

 

Если из полиномов Лагранжа можно сотворить ортогональный базис, то меня это возможно заинтересовало бы. Что-то посоветуете конкретнее?

[_Ivana 0]

Насчет базиса из Лагранжа не знаю. Простите если напрасно обнадежил. Но у Лежандра вроде единичная весовая функция http://ru.wikipedia.org/wiki/%D0%9E%D1%80%...%B5%D0%BD%D1%8B

[Xenia 45]

Насчет базиса из Лагранжа не знаю. Простите если напрасно обнадежил. Но у Лежандра вроде единичная весовая функция http://ru.wikipedia.org/wiki/%D0%9E%D1%80%...%B5%D0%BD%D1%8B

 

Слава вам! :) Похоже на то, что полиномы Лежандра первого рода (Legendre Polynomial of the First Kind) мне бы сгодились.

Смотрим на картинку, которую я надыбала среди картинок с помощью Google:

 

Это отсюда - http://www.efunda.com/math/legendre/legendre.cfm

 

Тут зелененький T2 торчит много выше - здесь я уже поверю, что его интеграл на отрезке нулевой.

 

Сильно похоже на полиномы Чебышева! Только формулы там какие-то страшные, чтобы их построить.

[_Ivana 0]

Только формулы там какие-то страшные, чтобы их построить.

С той же ссылки Вики первые несколько многочленов

Не такие уж и страшные. А дальше вроде рекуррентная формула последующих дает надежду что и там страх нарастает не сильно.

ЗЫ картинки у меня тоже красиво не загружаются или я не умею - в общем, посмотрите сами по ссылке - очень милые полиномы.

Изменено 24 июля, 2012 пользователем _Ivana

[andrewn 0]

Чтобы FF' была диагональной без всяких оговорок

Есть небольшая разница между функциональным (например L_2) бесконечномерным пространством и векторным конечномерным пространством. Отличие в определении метрики и нормы. То, что годится для векторного пространства (сумма произведений компонент векторов) не годится для бесконечномерного пространства, где скалярное произведение определяется как интеграл произведения комплексно сопряжённой функции на функцию (возможно, с весом).

 

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

 

Кстати, интересный факт: система обычных полиномов {1, x, x^2, ...} - оказывается, линейно независима. Следовательно к ней можно применить процесс Грама-Шмидта. Вот сюрприз-то...

 

 

 

[Alexey Lukin 0]

А вы мне можете этим способом показать, что T0 и T2 ортогональны друг другу? Тем более для такого простого случая, когда T0 единичен в любой своей точке, а T2 = 2x²-1.

Конечно: Подставляем -1 и +1 и получаем 0.

 

Точнее, надо подставлять -1+eps и 1-eps, т.к. ортогональность берётся на интервале (-1, +1), а не на отрезке.

[andrewn 0]

интервале (-1, +1), а не на отрезке

А что, уже опять поменяли определение определённого интеграла?????