Покритикуйте маленькую статейку по сплайнам

[_Ivana]

Написал её некоторое время назад, в стиле для домохозяек: много воды-мало формул. Потом почитал книжки по этой тематике и понял, что все уже придумано до нас, но все равно интересно мнение тематической общественности. http://www.onlinedisk.ru/file/872780/

[profrotter]

Цитата:

Разработан новый класс сплайнов

Это неправда. Сплайны с оценкой первой, второй, третьей, четвёртой и тд производной по дискретным значениям давно известны. Оценка производных основана на предварительном построении многочлена Лагранжа по нескольким (в зависимости от порядка производной) примыкающим отсчётам интерполируемой функции. Подробнее см., например, Денисенко А.Н. Сигналы. - М.: Изд. горячая линия-телеком, 2005. Ещё раньше Сухорученков Б.И. Математические модели и методы анализа характеристик летательных аппаратов. - М.: Изд.МО, 1989.

[_Ivana]

Спасибо за библиографию, если найду - почитаю. Однако, пока я встречал только именно

Цитата:

Оценка производных основана на предварительном построении многочлена Лагранжа по нескольким (в зависимости от порядка производной) примыкающим отсчётам интерполируемой функции.

, т.е. для оценки первой производной интерполируются по Лагранжу 3 точки, а по бОльшему количеству точек не оценивают, хотя получается точнее. Хотя эта идея лежит на поверхности и скорее всего давно опробована. Но тогда ответьте пожалуйста на вопрос - почему настолько широко при обработке сигналов применяется алгоритм Фарроу (оптимизированный Лагранж 3 порядка), когда есть сплайн который в 10 раз точнее (при достаточной частоте дискретизации), имеет непрерывную первую производную и требует столько же операций (хотя последнее справедливо только при последовательном движении по массиву данных)?

[ewert]

_Ivana в сообщении #615820 писал(а):

Покритикуйте маленькую статейку по сплайнам

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

Есть и фактические ошибки. Например:

Цитата:

кубический сплайн Эрмита, построенный по значениям точных первых производных, имеет на порядок большую точность, чем кубический многочлен Лагранжа

Это неправда: у них ровно один и тот же порядок точности -- четвёртый. Вообще сплайны строят вовсе не для повышения точности, а для повышения гладкости.

[profrotter]

_Ivana в сообщении #615839 писал(а):

а по бОльшему количеству точек не оценивают, хотя получается точнее.

Оценивают, если получается: Посмотрите в Антонью Цифровые фильтры: анализ и проектирование. - М.: "Радио и связь", 1983 или Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков Численные методы.

Что касается точности интерполирования, то она зависит от класса фнукции и исследуется методами функционального анализа, см., например, Методы сплайн-функций. Завьялов, Квасов, Мирошниченко. - М.: Наука. Главная редакция физико-математической литературы, 1980.

_Ivana в сообщении #615839 писал(а):

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

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

[_Ivana]

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

Цитата:

Это неправда: у них ровно один и тот же порядок точности -- четвёртый.

Однако, мои практические эксперименты на синусе показывают различие точности именно на порядок. Думаю, на практике при реальных сигналах будет то же самое.

Цитата:

Что касается точности интерполирования, то она зависит от класса фнукции и исследуется методами функционального анализа

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

Цитата:

Кстати, разница в десяток-другой операций нынче мало кому интересна.

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

Цитата:

А интерполирующий фильтр Вы в своей статье не построили, если что.

Не понял что вы имеете в виду. Я привел все необходимые формулы для одного из сплайнов и Фарроу. Построить по ним фильтр - это написать их в коде на Си?

[ewert]

_Ivana в сообщении #615873 писал(а):

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

Под "порядком" принято понимать степень шага, которой пропорциональна погрешность. Для кубических многочленов Эрмита и Лагранжа порядок один и тот же. Правда, масштаб погрешности у Эрмита и впрямь в девять раз меньше, но это мало что значит: поскольку порядок четвёртый, увеличение количества шагов всего лишь вдвое с большим запасом компенсирует этот девятикратный разрыв. При этом, однако, многочлен Эрмита и сам по себе не проще, и, что гораздо хуже, требует знания производной, которого при аппроксимации произвольных функций нет. Если же использовать конечноразностные производные, то их приходится считать не менее чем по четырём точкам (если мы не хотим потерять порядок); а это и резко увеличивает объём вычислений, и весь выигрыш в масштабе исчезает.

Так что все достоинства многочлена Эрмита по сравнению с Лагранжем сводятся лишь к тому, что Эрмит менее эффективен. Если стремиться именно к точности; если же речь о гладкости -- дело другое.

[_Ivana]

Цитата:

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

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

Цитата:

Если же использовать конечноразностные производные, то их приходится считать не менее чем по четырём точкам (если мы не хотим потерять порядок); а это и резко увеличивает объём вычислений, и весь выигрыш в масштабе исчезает.

В своей статье я именно и привожу пример сплайна Эрмита с оценкой производных по 5 точкам - и он требует ровно столько же операций (с учетом последовательного движения по массиву), что и оптимизированный по Фарроу Лагранж 3-го порядка - что я и пытаюсь донести, и делаю большой акцент на этом в конце статьи. А его гладкость в моей статье - это дополнительный бонус.
ЗЫ Я провел эксперименты, получил результаты, оформил их в статейку где показано, что Эрмит с оцененными производными по Лагранжу 4-го порядка (по 5 точкам) как это ни странно не сложнее Лагранжа 3-го порядка! А вы (наверное справедливо) покритиковали общую идеологию но не отметили этот момент, но так и остались при своих спорных представлениях о "резком увеличении объема вычислений".

UPD

Цитата:

Под "порядком" принято понимать степень шага, которой пропорциональна погрешность. Для кубических многочленов Эрмита и Лагранжа порядок один и тот же.

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

[profrotter]

_Ivana в сообщении #615873 писал(а):

Не понял что вы имеете в виду. Я привел все необходимые формулы для одного из сплайнов и Фарроу. Построить по ним фильтр - это написать их в коде на Си?

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

Кстати, насколько я понял, приведённые вами формулы отчего то записаны лишь для первого интервала интерполяции.

_Ivana в сообщении #615873 писал(а):

при разработке высокочастотных устройств реального времени

Неужели разработчики не учитывают, что обработка радиосигналов производится по комплексной огибающей?

[_Ivana]

profrotter, попробую по порядку, в меру своего незнания.

Цитата:

Построить фильтр - значит найти его коэффициенты.

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

Цитата:

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

Допустим, мы увеличиваем частоту дискретизации ровно в 64 раза - значит нам необходимо рассчитать значения в 63 точках внутри каждого интервала. По формулам мы можем один раз (и за малое количество операций) рассчитать 3 коэффициента полинома на весь интервал а далее 63 раза только рассчитывать значения этого полинома в зависимости от точки внутри интервала. Это гораздо быстрее, чем для каждой точки рассчитывать по отдельному КИХ фильтру, или я не прав?

Цитата:

Неужели разработчики не учитывают, что обработка радиосигналов производится по комплексной огибающей?

Я не специалист, но давайте не будем вдаваться в подробности, тем более ради вопроса "имеют ли значение лишние десяток-другой операций". Я думаю что есть приложения, когда имеют.

[profrotter]

_Ivana в сообщении #615929 писал(а):

Я могу найти коэффициенты интерполирующего фильтра по описанным сплайнам для любого постоянного сдвига сетки

Ну конечно можете. Надо просто найти базисные функции, соответствующие вашему методу интерполяции и их дискретизировать в зависимости от кратности интерполяции. А базисные функции приведены в Денисенко и Сухорученкове, о чём я уже и писал.

[_Ivana]

Хорошо, давайте я рассчитаю коэффициенты КИХ фильтров для пары кубических сплайнов для точки - середины интервала дискретизации и выложу сюда значения? Для другой точки интервала они будут другие. Но фильтр по Лагранжу 3 порядка будет содержать 4 коэффициента, а по кубическим сплайнам, о которых я писал - 6, 8 и более, при той же сложности расчета - если считать по полиному в явном виде.
Вы хотите посмотреть АЧХ и ФЧХ, точнее ГВЗ? АЧХ будет лучше чем у Лагранжа 3 порядка, ГВЗ - та же, я проверял, все это для любых точек интервала.

[profrotter]

_Ivana в сообщении #615929 писал(а):

Допустим, мы увеличиваем частоту дискретизации ровно в 64 раза - значит нам необходимо рассчитать значения в 63 точках внутри каждого интервала. По формулам мы можем один раз (и за малое количество операций) рассчитать 3 коэффициента полинома на весь интервал а далее 63 раза только рассчитывать значения этого полинома в зависимости от точки внутри интервала. Это гораздо быстрее, чем для каждой точки рассчитывать по отдельному КИХ фильтру, или я не прав?

Вы правы. Просто в этом случае существует рекурсивный фильтр (как правило находящийся на границе устойчивости), который может быть реализован и окажется в вычислителном плане более эффективным. Например, кусочно-линейному интерполятору в L раз соответствует алгоритм:

$$y_n=0.2x_{n-1}-0.4x_{n-(L+1)}+0.2x_{n-(2L+1)}+2y_{n-1}-y_{n-2},$$

где $x_n$ сигнал на входе фильтра, $y_n$ - сигнал на выходе.

-- Пт сен 07, 2012 18:18:36 --

_Ivana в сообщении #615933 писал(а):

Для другой точки интервала они будут другие.

Это некрасиво: у вас получется, что разные точки интервала оказываются в разных условиях. Интерполяция становится нерегулярной и возникает вопрос: А чем вот эта точка интервала лучше вон той?

[_Ivana]

Цитата:

Это некрасиво: у вас получется, что разные точки интервала оказываются в разных условиях. Интерполяция становится нерегулярной и возникает вопрос: А чем вот эта точка интервала лучше вон той?

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

[profrotter]

Из Денисенко Сигналы: