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

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

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

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

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

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

Сообщение отредактировал _Ivana - Apr 9 2012, 22:44

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

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

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

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


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

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

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

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


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

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

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

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

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