[Xenia 45]

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

 

Я бы и еще таких поискала. Наверняка, есть еще что-то подобное. Просто классические полиномы постоянно на слуху, а более редкие прозябают в безвестности. Если где-то встретите - сигнализируйте. :)

[_Ivana 0]

Во-первых, обычные полиномы Лежандра (как и полиномы Чебышева) определены на отрезке [-1, +1], тогда как DLOP - исключительно на положительных значениях натурального аргумента, т.е. определены дискретно на векторе/массиве ровно этой длины, для которой они строятся. Это очень удобно тем, что избавляет от необходимости постоянно пересчитывать номера элементов в X-координату на отрезок [-1, +1] и обратно.

А до сего момента Вы разве не так получали вектора разной длины из отрезка полиномов Чебышева и Лежандра на отрезке [-1, 1]? Странно что вы отмечаете этот момент отдельно.

 

Во-вторых, центр симметрии у обычных полиномов Лежандра (как и у полиномов Чебышева) находится точно в начале координат (в середине отрезка [-1,1]), тогда как у DLOP тоже в середине, но уже в середине вектора! Например, если вектор у нас длиной в 15 элементов, но центр симметрии будет приходиться на 7-ой элемент массива.

Опять же, имхо это естественное следствие дискретизации непрерывной функции. Если бы дискретизировали четным количество точек, то центр был бы между точками. Снова не понимаю, почему вы придаете значение таким имхо очевидным вещам. Или вы все ваши предыдущие вектора строили из аналитического выражения на интервале [0, 1]? Тогда у вас не могла получиться ортогональность например полинома 1 или 3 степени с полиномом 0 степени....

 

В-третьих, обычные полиномы Лежандра (как и полиномы Чебышева) всегда пересекаются в точке (1,1), т.е. в правом верхнем углу графика. А DLOP пересекаются всегда в 1-ом элементе вектора (в языке C у него нулевой номер). Из-за этого некоторые полиномы нечетной степени (которые раньше упирались в точку(-1,-1)) оказались перевернутыми вверх ногами.

Здесь у вас получилась аналогия с аналитическим базисом от (-х) - который тоже базис и тоже ортогонален и нормирован. Ибо четные полиномы не поменялись а нечетные остались нечетными. И все они пересекаются в точке [-1, 1].

 

А вот бОльшая амплитуда размаха DLOP по сравнению с обычными аналитическими полиномами Лежандра (вплоть до вылетов за границы +-1) врядли является следствием просто отсутствия нормировки (кстати, ваша картинка внизу - из нормированных DLOP или нет?). Ссылки приведенные к сожалению платные и навскидку не получилось с ними ознакомиться.

[Xenia 45]

А вот бОльшая амплитуда размаха DLOP по сравнению с обычными аналитическими полиномами Лежандра (вплоть до вылетов за границы +-1) врядли является следствием просто отсутствия нормировки (кстати, ваша картинка внизу - из нормированных DLOP или нет?).

Моя картинка не нормированная, хотя практически я пользуюсь номированной. Не хотела вводить нормировку в картинку, чтобы ярче были видны отличия от классических полиномов Лежандра. И, похоже, я достигла своей цели, если вы без подсказки заметили, что значения некоторых из высших полиномов ВНУТРИ интервала определения зашкаливают за единицу. Очевидно, что это не является следствием нормировки, т.к. в этом случае исчезло бы касание +1 или -1 на краях. Ведь нормируются полиномы, как кривая вдоль оси Х, а не поперек. Поэтому, если бы я путем масштабирования вызвала тот зашкал, то и на краях кривая промахнулась бы мимо единицы. А этого нет!

 

То, что вы заметили, является одним из важнейших достоинств DLOP над обычными полиномами Лежандра, т.к. именно этим способом первые обеспечивают себе ортогональность всегда! Тут либо ортогональность, либо удержание себя в рамках приличия. :) И очень отрадно, что DLOP пренебрегли приличием ради ортогональности. :) Ведь если подумать, то главное достоинство базиса в его отогональности и ортонормированности, а вовсе не в ограничении амплитуды единицей. Ограниченостью единичной амплитудой нас Фурье заразил. :) Дурной пример заразителен, и теперь каждому начинает казаться, без всяких на то оснований, что ограниченность амплитуды единицей является необходимостью. Тогда как на самом деле единицей должна быть ограничена норма, а вовсе не амплитуда.

 

Ссылки приведенные к сожалению платные и навскидку не получилось с ними ознакомиться.

Написали бы вы, _Ivana, заявку в "Свои", тем паче, что по всем критериям вы давно того достойны. Я на здешнем ftp такую потрясную библиотку книг по ЦОС собрала (разделы DSP и Image_processing)! И эти платные статьи тоже туда положила (вместе с другими по DLOP, которых в своих сообщениях не упоминала). ЦОС - вообще великая наука, от одного только соприкосновения с которой весь мир начинает восприниматься по-другому.

 

P.S. Вот здесь http://www.mathworks.com/matlabcentral/fil...expansions.html в разделе "Drawing orthogonal polynomials" только что нашла графики пронормированных полиномов Лежандра (обычные, не DLOP):

 

 

Как-то странно они их пронормировали, что сохранилось T0=1 всюду, но остальные полиномы настолько "выпучились", что перестали касаться единицы на концах. Ну, а за пределы единичного корридора вылезли кажется все, кроме нулевого.

 

Кстати, там я уже вижу еще новых претендентов на гладкие ортогональные полиномы. Это

 

полиномы Якобы (Jacobi polynomials)

и

полиномы Эрмита (Hermite polynomials)

Интересно, существуют ли их дискретные аналоги?

[_Ivana 0]

Изначально я вам предложил Лежандра потому что в аналитическом виде они ортогональны с единичной весовой функцией, именно то что вас не устроило в Чебышеве. Дискретные аналоги Чебышева вы читали, Лежандра тоже. У Эрмита и Якоби тоже должны существовать дискретные аналоги, но в аналитическом виде они ортогональны с отличной от единицы весовой функцией, то есть в этом смысле "не лучше" Чебышева. Если вы в вашем методе сможете использовать такие "условно" ортогональные дискретные полиномы - тогда сможете попробовать и Чебышева и Эрмита с Якоби.

 

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

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

 

Про отличие DLOP от Лежандра у меня есть некие ассоциации. Во первых, я подозреваю что чем больше точек в векторе, тем эти отличия меньше (по крайней мере, в окрестности нуля). Во вторых, это очень похоже (метафизически :) ) на интерполяцию через обрезанный синк и синк с окном - обрезанный синк дает плохое качество интерполяции, а те же полиномы Лагранжа при увеличении своего порядка представляют собой синк умноженный на окно Гаусса (что я случайно обнаружил). Так если мы возьмем мало точек, посчитаем по ним обрезанный синк - будет плохо, а догадаться умножить эти значения на некоторое окно, которое "подправит" этот дискретный массив в нужную сторону - надо ещё суметь, к тому же Гаусс - далеко не единственное окно в природе. Мне кажется что примерно по аналогичному принципу рассчитываются DLOP из обычного Лежандра. Поэтому вполне возможно (хотя и не факт), что можно придумать ещё другие дискретные ортогональные базисы с единичной весовой функцией. Хотя мне кажется ваша задача легко решится и с помощью DLOP.

 

ЗЫ я тоже думал насчет заявки в "Свои", но не решался. Спасибо за приглашение и доверие :)

[Xenia 45]

Тут есть еще одно перспективное направление для копания. Суть лежит в некоем родстве полиномов с ... рядами Фурье. В самом деле, если и далее растягивать тот "гамак" :), сплетенный из полиномов, увеличивая одновременно число точек в векторе и количество степеней полиномов, то они все больше становятся похожими на гармоники. Разве что с деформацией на "краевой эффект". Вот такая у них получается огибающая:

 

 

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

 

Вот какой любопытный алгоритм я надыбала в интернете, хотя далеко не уверена, что он рабочий. Привожу его код (на MatLab'е) полностью, поскольку исполнямых в нем всего 3 строки.

 

function uh = fct(u)
% Fast Chebyshev Transform 
%
%    uh : Discrete Chebyshev Transform Coefficients.
%    u  : Function values evaluted at Chebyshev Gauss Lobatto nodes
%         with nodes ordered increasingly x_i=[-1,...,1}
%         for i=1,2...,N
%
% By Allan P. Engsig-Karup, [email protected].

N  = length(u);
u  = ifft([u([N:-1:1 2:N-1])]); % reverse ordering due to Matlab's fft
uh = ([u(1); 2*u(2:(N-1)); u(N)]);
return

http://www.mathworks.com/matlabcentral/fil...t/content/fct.m

Это якобы быстрое преобразование Чебышева. Одно только название чего стоит! Суть алгоритма состоит в том, что к преобразуемому массиву слева дописывают его зеркальное отражение (первый элемент остается в центре, не удваиваясь), а справа последний элемент удаляют (его отражение сохранится в отражении). А потом то, что получилось, скармливают обратному преобразованию Фурье (функция ifft). Результат увеличивают в масштабе вдвое, за исключением крайних точек, и дело в шляпе. Неужели так просто?

 

Несмотря на очевидность стадий алгоритма, его суть мне совершенно непонятна, хотя очень здОрово, если это работает.

[Alexey Lukin 0]

Суть в том, что на специальной сетке точек, для которой полиномы Чебышева ортогональны, умножение на полином Чебышева сводится к умножению на косинус. Соответственно, преобразование Чебышева сводится к ДКП 2 рода, что и продемонстрировано в вашем коде, где ДКП (неэффективно) вычисляется через ДПФ.

[Xenia 45]

Суть в том, что на специальной сетке точек, для которой полиномы Чебышева ортогональны, умножение на полином Чебышева сводится к умножению на косинус. Соответственно, преобразование Чебышева сводится к ДКП 2 рода, что и продемонстрировано в вашем коде, где ДКП (неэффективно) вычисляется через ДПФ.

 

Отрадно, что вы упомянули в этой связи DCT-2. Я к нему тоже приглядывалась, но отвергла из-за отсутствия в их базисе "линейного" полинома - прямой наклонной линии:

 

 

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

 

Базис Лежандра хорош тем, что линейный наклон полностью ложится на "линейный" полином T1 (наклонную линию). Достаточно обнулить вклад этого полинома, чтобы тренд исчез, не повредив ничего остального. А вот в базисах, где наклонной линии нет, всем базисам полного набора приходится совместно трудиться над тем, чтобы воспроизвести наклонный тренд. И это очень плохо для меня! Хотелось бы, чтобы в отсутствии полезного сигнала (линейный тренд полезным сигналом не считается) высшие полиномы нагрузки не несли. Лежандр или Чебышев в этом отношении хороши - младшие полиномы T0 (горизонталь) и T1 (наклонная линия) берут на себя аппроксимацию тренда. А при анализе их вклады можно было просто не учитывать.

 

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

 

К моему глубокому сожалению, базис DCT-2, хотя и лучше Фурье, но полностью этого недостатка не лишен. Причина в том, что его собственный T1, хотя и похож на наклонную линию, но на самом деле представляет собой половинку периода косинуса. Поэтому его загибание на концах приходится компенсировать возбуждением всех остальных участников базиса.

 

Может быть, вам известны какие-либо фурье-подобные базисы, в которых младшие два элемента базиса были бы горизонтальной (T0) и наклонной линией (T1)? А то, судя по названию DCT-2, возможны и другие DCT. Вдруг среди них есть требуемое? Сама же я нашла лишь описание базисов от DCT-1 до DCT-4, которые требуемым качеством не обладают.

[Xenia 45]

P.S. Отчего бы не сотворить такой базис на отрезке [-1,+1]: T0 - прямая линия (уровень +1), T1 - наклонная линия от точки (-1,-1) через начало координат до точки (+1,+1), а остальные - косинусы с целым числом периодов (чтобы были четными функциями). Т.е. то, что получится, если удалить из базиса DCT элементы, изображенные на рисунке справа (т.к. они нечетные), добавив наклонную линию. На мой взгляд, такой базис должен быть ортогональным, поскольку наклонная линия, пересекающая начало координат, ортогональна любой четной функции, а косинус - именно такая функция.

 

Известен ли в мире такой базис? И если да, то как он называется? Или же я ошиблась относительно его ортогональности?

 

P.P.S. Кажется, я чушь сморозила - базисом с одними четными функциями (одного нечетного T1 среди них недостаточно) нечетные функции вряд ли аппроксимируешь.