Придумал алгоритм интерполяции. Протестируем результаты?, вызов от дилетанта Опции

[_Ivana]

Пару дней назад пришлось вникнуть в азы ЦОС на примере ресемплинга. Почитал пару-тройку страничек в инете, про двойной апсемплинг, оконные функции, полиномы Лагранжа-Фарроу и т.п. И придумал свой алгоритм Без таблиц, на чистой математике. По объему операций существенно меньше Фарроу. Реализовал его, как обычно, сначала на 1С Посмотрел графики. Потом перевел в целочисленную математику и с помощью коллеги наваял программку - ресемплер wav файлов. С заданием частоты ресемплинга и выбором варианта - своего или Фарроу.

Собственно, предлагаю: заинтересованные лица выкладывают вавки, я их ресемплю с нужной частотой двумя вариантами и выкладываю на всеобщее скачивание/заслушивание. Желающие делятся своими мнениями по поводу

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

Графические примеры работы алгоритмов: точки 50, 70, 20, края диапазона добиты нулями. График - ось абсцисс вниз, ординат - вправо.
Фарроу:

CODE

      *--- 0
     *
    *
   *
   *
  *
  *
   *
   *
    *
      *--- 0
          *
              *
                   *
                        *
                             *
                                   *
                                        *
                                             *
                                                   *
                                                        *--- 50
                                                            *
                                                               *
                                                                  *
                                                                     *
                                                                        *
                                                                          *
                                                                           *
                                                                            *
                                                                            *
                                                                            *--- 70
                                                                        *
                                                                    *
                                                               *
                                                          *
                                                     *
                                                *
                                          *
                                    *
                               *
                          *--- 20
                      *
                   *
                 *
              *
            *
           *
         *
        *
      *
      *--- 0
     *
     *
    *
    *
    *
    *
     *
     *
     *

Мой алгоритм:

CODE

      *--- 0
     *
     *
    *
   *
  *
  *
  *
  *
   *
      *--- 0
         *
             *
                  *
                       *
                             *
                                   *
                                         *
                                               *
                                                   *
                                                        *--- 50
                                                           *
                                                               *
                                                                  *
                                                                     *
                                                                        *
                                                                          *
                                                                            *
                                                                            *
                                                                            *
                                                                            *--- 70
                                                                         *
                                                                      *
                                                                 *
                                                           *
                                                     *
                                               *
                                         *
                                   *
                              *
                          *--- 20
                      *
                   *
                 *
              *
            *
           *
         *
        *
       *
      *--- 0
     *
    *
    *
    *
    *
     *
     *
     *
     *

За качество обоих графиков извиняйте - они в псевдографике с грубым "разрешением", на самом деле они более красивые

Сообщение отредактировал _Ivana - Apr 7 2012, 12:31

[_Ivana]

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

[rudy_b]

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

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