[_Ivana 0]

В продолжение эпического мыслевыражения :) Задача: имеем 3 точки при равномерной дискретизации. Надо придумать, какую мы хотим производную интерполирующего сплайна в средней точке. Катмулл и Ром предложили просто - линия через крайние точки, средняя точка игнорируется - получается относительно большая ошибка. Я сейчас подумал - мы можем интерполировать эти 3 точки какой-нибудь красивой гладкой функцией, и посчитать значение её производной в средней точке. На ум сразу приходит парабола. Но, похоже, это и есть то, что имеется в виду под "сплайнами, заканчивающимися параболой" :) http://alglib.sources.ru/interpolation/spline3.php Куда не сунься - все уже украдено до нас! Реалистичный Термит похоже снова прав...

[Timmy 1]

гладкой функцией, и посчитать значение её производной в средней точке. На ум сразу приходит парабола. Но, похоже, это и есть то, что имеется в виду под "сплайнами, заканчивающимися параболой" :) http://alglib.sources.ru/interpolation/spline3.php Куда не сунься - все уже украдено до нас! Реалистичный Термит похоже снова прав...

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

Ещё замечу, что тест надо делать до 100 точек на период синусоиды, так как ошибка в 0.001 при 20 точках - это просто порнография:). Для максимальной ошибки 10^-6 требуется около 50-60 точек при использовании полинома Лагранжа. И лучше использовать логарифмический масштаб по вертикали.

[_Ivana 0]

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

 

Про параболу и Катмулла-Рома: я с удивлением обнаружил, что если 3 точки интерполировать параболой, то производная в средней точке ВСЕГДА будет равна прямой через крайние :) Ну вот так Лагранж 2-го порядка проводит свои полиномы! Но я найду способ учесть положение средней точки, у меня уже есть идеи :)

 

А про 100 точек и логарифмический масштаб... Вы правы конечно, но пока я просто качественно проверяю разные алгоритмы, для оценки предпочтения одного перед другими, без особого упора на абсолютные значения, и надеюсь что кривые отклонений не пересекутся где-то там на 50-100 точках :) При более детальном количественном анализе конечно придется строить логарифмический масштаб и от 8 до 100 точек на период.

[_Ivana 0]

Пока все мои попытки придумать производную точнее чем Катмулл-Ром потерпели неудачу.

Но хотя бы выложу красивый график - как и просили, до 100 точек и в логарифмическом масштабе. Лагранж-4 обогнал-таки кубический сплайн с точными производными (если я нигде не ошибся). Да и сами графики какие-то подозрительно линейные, и весьма разнятся с представленными в недавней ссылке по сплайновой интерполяции... Хотя у меня и по оси абсцисс масштаб тоже логарифмический, а в тех графиках линейный, это может как-то объяснить красивую прямизну графиков :) Но сами значения у меня повыше, например для сплайна с точными производными.

Изменено 9 апреля, 2012 пользователем _Ivana

[_Ivana 0]

С интересом разглядывая последний график, я могу сказать следующее:

1) можно ввести параметр так называемой "мощности" алгоритма интерполяции - угол наклона прямой линии (или почти прямой) на графике.

2) сравнивать алгоритмы можно по погрешности при малых дискретизациях (стартовой погрешности) и мощности. Например, Лагранж-4 проигрывает сплайнам с производными при малом количестве точек, но за счет большей мощности обгоняет последний при где-то 28 точках и дальше только увеличивает свое преимущество. А Катмулл-Ром при малом количество точек близок к Фарроу (хотя и все равно хуже), но за счет меньшей мощности при увеличении количества точек все больше и больше отстает от него. Интересно поведение Фарроу и сплайна по производным - они имеют одинаковую (насколько можно судить по графикам) мощность, но сплайн по производным всегда на порядок (в 10 раз) точнее :)

3) из всего перечисленного можно предположить, что максимально достижимая мощность сплайнов с угадыванием производных (типа Катмулла-Рома и т.п.) равна мощности сплайна с известными производными, и следовательно мощности Фарроу (Лагранжа 3 порядка). А значит, как бы я не исхитрялся с алгоритмом угадывания производных, он уступит по мощности точным производным, и следовательно Фарроу :) Я могу получить выигрыш только на начальном этапе - при малом (относительно) количестве точек, но потом Фарроу обгонит (как Лагранж-4 обогнал точные производные). Значит, теоретические изыскания могут рассчитывать только на то, что этот обгон состоится как можно позже, и математика алгоритма будет при этом проще Фарроу. У меня есть некоторые сомнения в целесообразности и осуществимости таких поисков. Фарроу оказался сильным (мощным :) ). И он победил меня на поле кубических сплайнов как таковых, хотя сам им в какой-то степени и является. Остается только признать свое поражение... :smile3046:

[kuzis 0]

В данный момент размышления следующие. Фарроу (Лагранж 3-го порядка) - это имхо по сути (хотя многие могут со мной не согласиться) тот же кубический сплайн. Локальный, определяемый для 4-х точек, но действующий только на средний интервал из 3-х. Точно так же, как и сплайны Эрмита, например. Тот факт, что Лагранж при построении проходит через все 4 точки, не дает значения интерполирующей функции в левом и правом интервалах, поскольку при интерполяции собственно самих этих боковых интервалов (когда они являются центральными) полином проходит совершенно не так, как проходит в случае если интервал является правым или левым относительно центрального. Значит нельзя считать условие прохождение полинома через крайние точки самым оптимальным с точки зрения построения сплайна. Я придумал (а Катмулл и Ром до меня) другие условия: сплайн проходит через 2 точки и имеет определенные производные в них же, так чтобы полученная функция имела непрерывную первую производную. Сначала я придумал считать значение этой производной, как тангенс угла-биссектрисы исходных двух (словами трудно объяснить, надо на графике показывать). Только что проверил этот вариант - при малых дискретизациях ошибка выше Катмулла-Рома, при увеличении начиная где-то с 12 точек почти полностью сливается с Катмуллом-Ромом (график ниже). Но само значение производной рассчитывается через тангенсы-арктангенсы и достаточно сложно. Это и была моя вторая идея, которую я проверил только что. А потом я придумал считать производную как тангенс наклона соседних точек - собственно то, что потом узнал как Катмулла-Рома.

 

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

 

[thermit 1]

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

[_Ivana 0]

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

Одно дело на лекциях, а другое пощупать и убедиться самому. И я сделал все из того что вы предложили - и алгоритмы свои (все варианты) рассказал, и спектр синуса 0.49 от частоты дискретизации ресемпленный в несколько раз выложил. А больше вы вроде ничего не предлагали.

 

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

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

[ViKo 1]

Одно дело на лекциях, а другое пощупать и убедиться самому. И я сделал все из того что вы предложили - и алгоритмы свои (все варианты) рассказал, и спектр синуса 0.49 от частоты дискретизации ресемпленный в несколько раз выложил. А больше вы вроде ничего не предлагали.

Предлагаю. Синус с частотой 1kHz оцифруйте с частотой 5kHz. А потом интерполируйте до частоты дискретизации 50kHz. И покажите спектр с полосе 0-25kHz.

[kuzis 0]

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

А где? Че-то не увидел

[_Ivana 0]

Предлагаю. Синус с частотой 1kHz оцифруйте с частотой 5kHz. А потом интерполируйте до частоты дискретизации 50kHz. И покажите спектр с полосе 0-25kHz.

Сделаю. Вечером, как дома буду. По Катмуллу-Рому. Хотя могу для сравнения ещё по Фарроу, Лагранжу 4 порядка, линейному...

 

А где? Че-то не увидел

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

[kuzis 0]

Понятно. Просто там такой ужОс изображен, что я сразу и не понял. Я так понимаю что наш синус - это пик в районе 4 кГц, и рядышком же стоит его алиас, практически того же уровня. А вот теперь уменьшая частоту синуса, найдите такую, при которой алиас будет ниже дБ на 40 - 45. Ну и всякий мусор тоже должен быть не выше этого уровня. И напишите ее значение относительно частоты дискретизации.

[NiceParty 0]

Понятно. Просто там такой ужОс изображен, что я сразу и не понял. Я так понимаю что наш синус - это пик в районе 4 кГц, и рядышком же стоит его алиас, практически того же уровня...

Этот "ужОс" вполне предсказуем, т.к. при таком соотношении исходных частот сигнала и дискретизации ни одна полиномиальная интерполяция не даст нормального результата.

Лично по моим наблюдениям для хоть какого-то приемлемого результата при полиномиальной интерполяции максимальная частота исходного сигнала не должна быть больше 1/4 частоты семплирования. А лучше 1/8. Именно поэтому прежде чем применять алгоритмы полиномиальной интерполяции (в частности Лагранж 3-й степени с оптимизацией расчета по Фарроу) рекомендуют апсемплинг в 2, 4 и т.д. раз.

Если Вы знаете вариант полиномиальной интерполяции, который хорошо справляется с сигналами 0,48 частоты дискретизации, то расскажите, я буду весьма признателен.

Заранее спасибо.

С уважением, Александр.

[rudy_b 4]

...Остается только признать свое поражение...

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

 

[_Ivana 0]

Предлагаю. Синус с частотой 1kHz оцифруйте с частотой 5kHz. А потом интерполируйте до частоты дискретизации 50kHz. И покажите спектр с полосе 0-25kHz.

Первый - Катмулл-Ром, второй - Фарроу