Comments 34
Не должны ли быть "+" вместо "*" в паре мест формулы, которая идет после слов: "Так, например, интерполяционный многочлен в форме Лагранжа, проходящий через три заданных точки будет записываться вот так: [3]"?
Полином Лагранжа - это математическая функция, позволяющая записать полином минимальной степени, проходящей через заданное количество. Минимальной здесь ключевой момент, и осцилляции здесь появляются из-за знакочередующих производных. Существуют методы построения полиномов более высоких порядков с явным заданием производных.
Многочлены Чебышева достойны отдельной статьи, ну или хотя бы можно было пояснить, откуда там косинус взялся.
Ну и современное решение задачи интерполяции - это барицентрическая интерполяция рациональными полиномами, там проблемы с феноменом Рунге нету. Статью в википедию, правда, до сих пор не подвезли (а а школьную программу и подавно), но вот неплохая обзорная статья.
Люблю матешку ловите плюсик в карму
Как частный случай... Интерполировать, в случая колоколообразной функции, можно и функцией (обобщенной) Гаусса. Колебаний не будет.
Здравствуйте! Вы совершенно правы, интерполяция функцией Гаусса возможна, и она поможет избежать колебаний. Однако, всё зависит от конкретной задачи.
Полиномы Лагранжа и узлы Чебышёва это мощные инструменты в численном анализе, они помогают аппроксимировать функции на широких интервалах, в то время как Гаусса мы используем когда функция похожа на нее - колоколообразная, гладкая, убывающая.
Спасибо за комментарий!
Не знаю, есть ли здесь что-то общее, но наш профессор говорил, что при использовании в методе Рунге-Кутты слишком мелкого шага в решении появляется ложная колебательность.
Здравствуйте! Феномен Рунге и колебания при методе Рунге-Кутты происходят из-за разных причин в разных контекстах, однако, они оба связаны с численной нестабильностью и с неправильно выбранными параметрами.
В методе Рунге-Кутты слишком мелкий шаг может усиливать погрешности округления и другие численные эффекты.
В феномене Рунге при интерполяции полиномом высокой степени, коэффициенты перед членами полинома увеличиваются с огромной скоростью и это приводит к значительным колебаниям.
Спасибо за комментарий !
А если продолжить функцию по краям подальше, просто нулями например , и аппроксимировать эту функцию, то колебания в нужном диапазоне уйдут?
Здравствуйте! К сожалению, даже если на первый взгляд может показаться, что добавление нулей решит проблему, это не так.
Причина в том, что полиномы, в особенности высоких степеней, имеют большое влияние: изменение функции на одном участке, даже на маленьком интервале, может повлиять на поведение полинома на всей области. В результате, добавление нулей за пределами интервала может даже увеличить колебания внутри основного диапазона.
Спасибо за Ваш комментарий!
Я не спорю, просто не очень понятно.
полином n-степени, который будет соединять все заданные точки из набора значений
Если мы добавим по краям еще пару значений к существующему набору, разве значения полинома на существующих точках в середине диапазона начнут колебаться сильнее?
Ну это легко проверить, добавить в программе еще пару точек по краям и посмотреть.
Если добавляются новые точки, особенно на краях интервала, полином адаптируется, чтобы пройти через все новые узлы. Это приводит к усилению колебаний как в крайних точках, так и в середине интервала, особенно если степень полинома увеличивается. В результате, даже если новые точки находятся по краям, они могут повлиять на значения полинома на всем диапазоне, вызывая увеличение колебаний.
Что-то такое припоминаю с курса матанализа в университете. Там даже формально доказывалась ограничение на погрешность.
Скажу как экспериментатор, который постоянно сглаживает временные ряды. С философской точки зрения, корень зла - это требование, чтобы аппроксимационный полином прошел строго по точкам. Достаточно попросить, чтобы он прошел неподалеку от них - и жить сразу станет намного легче! В особенности в плане идущих в разнос колебаний полиномов высокой степени...
В отличие от чистых математиков, у нас (экспериментаторов) все либо почти все точки всегда известны с погрешностью. Поэтому нет абсолютно никакого смысла пытаться провести кривую строго по этим точкам. Осмысленная альтернатива - это попросить кривую пройти примерно по этим значениям. С погрешностью, которая адекватна погрешности измерений.
Поэтому вот эта вот фраза:
"...который будет соединять все заданные точки из набора значений, полученных опытным путём..."
(выделение мое) вызывает у меня очень большие сомнения в правильности цитирования. Во времена Лагранжа все выдающиеся ученые были широко эрудированы, и не могли не понимать физические (даже можно сказать философские) корни математических моделей. Поэтому для меня было бы удивительно, если Лагранж действительно ставил задачу, как провести аппроксимирующую кривую точно через значения экспериментальных данных. Ведь самопротиворечие такой постановки должно было быть вполне очевидным даже в то время.
На практике идея "аппроксимации с погрешностью" может быть реализована, например, за счет уменьшения степени полинома. Попросту говоря, она всегда должна быть меньше, чем количество точек данных. Желательно -
много меньше
Как вариант, можно построить зависимость погрешности аппроксимации Err от степени N и искать минимум какой-нибудь подходящей в данном случае функции типа Err*N. Который и даст нам оптимальное значение N.
Без этого самоограничения (погрешность не должна вырождаться в 0!) мы не добьемся ни устойчивости, ни робастности. Если малые изменения в данных влекут большие изменения в результатах, то такая модель может быть интересна лишь как предмет для игры ума (ну или в качестве образца для кунсткамеры). С научной точки зрения (если мы пытаемся описать объективную реальность) она гроша выеденного не стоит. Во всяком случае, в до-квантовой парадигме...
Здравствуйте!
Вы правы, при работе с реальными данными, содержащими погрешности, требование, чтобы аппроксимирующий полином строго проходил через все точки, может привести к ненужным колебания.
Методы, которые позволяют полиному приблизительно, а не точно проходить через точки, конечно, обеспечивают более устойчивые результаты.
Однако, в моей статье я исходила из классического подхода к интерполяции, где требуется точно пройти через все узлы. Это, конечно же, полезно для понимания феномена Рунге. Хотя этот метод может быть не до конца применим для настоящих данных, он важен с теоретической точки зрения.
В реальной практике, как вы правильно заметили, лучше использовать методы, которые учитывают погрешности данных.
Спасибо за комментарий!
в моей статье я исходила из классического подхода к интерполяции, где требуется точно пройти через все узлы
Так я же не критикую статью (свой плюс она получила). Это скорее мысли по поводу обсуждаемых методов. А вот про Лагранжа было бы интересно узнать, что именно он все-таки имел в виду в оригинале высказывания. Понимаю, что просьба не очень корректная... но ведь это Вы первая начали ;-)
Ваше замечание верно, но не относится к рассмотренной проблеме. Даже если допустить, что интерполируемые данные содержат погрешность и рассматривать не единственный интерполирующий полином, а всё их возможное множество, построенное по всем допустимым с учётом погрешности измерений данным, то каждый из них будет подвержен эффекту Рунге. Как правильно отметил автор, рост погрешности обусловлен не значениями интерполируемой функции в выбранных точках, а расположением этих точек и поведением высших производнвх функции, погрешность исходных данных тут глубоко вторична.
Даже если допустить, что интерполируемые данные содержат погрешность и рассматривать не единственный интерполирующий полином, а всё их возможное множество, построенное по всем допустимым с учётом погрешности измерений данным, то каждый из них будет подвержен эффекту Рунге.
Прошу прощения, если Вы поняли мои слова таким странным образом. Я совершенно не предлагаю строить ансамбль аппроксимаций, каждая из которых будет обладать обсуждаемым недостатком. Да даже если мы его вдруг построим, то что потом? Как искать среди них (или строить на базе ансамбля) тот единственный полином, который обеспечит наилучшую, в каком-то смысле, аппроксимацию? Не буду писать прямым текстом, какие аналогии мне приходят в голову, так как обсуждение таких извращений, даже если они сугубо математические, вряд ли впишется в тематику Хабра ;-)
Вместо этого попробую пояснить свою идею еще раз другими словами. Речь идет о том, чтобы СРАЗУ же (без мучений с ансамблем) построить ГЛАДКУЮ аппроксимирующую функцию, у которой производные высших порядков равны нулю. Я утверждаю, что отказ от требования точно пройти через все значения данных позволяет построить такую аппроксимацию (гораздо более гладкую, без "заскоков") тривиальным образом. Единственная дополнительная задача, которую при этом придется решить - это
выбрать оптимальный компромисс между гладкостью этой аппроксимации и ее близостью к заданным точкам
Подчеркну, что такой выбор - это содержательная (а не формальная) задача. Так как критерий оптимальности мы задаем произвольно (точнее, исходя из физических соображений). Для этого, во-первых, надо будет задать
критерий близости точек к кривой
например, это может быть сумма расстояний от точек данных до аппроксимирующей кривой, или сумма квадратов этих расстояний, или что-нибудь еще на наш вкус. Ну и само расстояние можно считать либо строго по вертикали (то есть брать дельта Y при одинаковом X) либо метрическое на плоскости, и т.д. А еще при решении практических задач очень часто бывает полезно придать разным точкам различный вес в зависимости от погрешности измерения (она же может быть разной у разных точек), и считать не простую "сумму квадратов", а взвешенную...
и, во-вторых, формализовать понятие "оптимума". Ведь чем менее гладкую кривую мы согласны строить, тем ближе она подойдет к нашим точкам.
Но после того, как мы выбрали критерий оптимальности полинома, дальше все просто. Пробуем сначала однопараметрическую аппроксимацию, потом двухпараметрическую и так далее. То есть, сначала пробуем аппроксимировать наши точки константой (можно сказать, что это полином нулевой степени). Это самая грубая аппроксимация, но и самая гладкая (все производные равны нулю, начиная с первой ;-) Потом пробуем обычную
прямую на плоскости
чаще всего ее строят методом наименьших квадратов, но вообще-то тут есть тьма вариантов в зависимости от того, что именно мы ходим оптимизировать - см.выше под спойлером "критерий близости точек к кривой"
На третьем шаге пробуем полином второй степени, то есть параболу, затем кубическую параболу и т.д.
Ну и теперь осталось выбрать среди этих полиномов наилучший. Понятно, что чем больше у нас свободных параметров (чем выше степень полинома) , тем менее гладкой получится аппроксимирующая функция, и
тем ближе к нашим точкам она пройдет
Когда количество свободных параметров сравняется с количеством данных, то и вовсе будет точное совпадение, т.е. ошибка станет равна 0. (Конечно, в вырожденном случае, т.е. при особом расположении точек, это может случиться и раньше, но с экспериментальными данными этого не бывает ;-)
Если к примеру, взять тривиальный критерий "чем точнее - тем лучше", то мы как раз и упираемся в описанную в статье ситуацию со всеми обозначенными там проблемами. Не хочу гнать бочку на теоретиков, но как экспериментатор, я бы предположил, что такая аппроксимация совершенно не является оптимальной в подавляющем большинстве практических приложений. И что поэтому то внимание, которое ей уделяется в разных курсах, является скорее данью традиции (ну и экивоком в сторону строгой теории), чем следствием ее полезности при анализе данных. Хотя освоить эти алгоритмы конечно не помешает, только не для прямого применения при работе с временными рядами, а в качестве базы для последующего освоения более полезных на практике инструментов.
Но вернемся к нашим баранам.
Мой тезис состоит в следующем. Я утверждаю, что если в данных имеются погрешности, то критерий "чем точнее - тем лучше" (который вынуждает нашу аппроксимирующую кривую посетить все точки) - абсурден с физической точки зрения. Нет никакого смысла уменьшать погрешность аппроксимации настолько, чтобы она стала меньше погрешности данных. Тем более, когда это приводит к огромным
паразитным эффектам
По сути, это не что иное, как сверхподгонка. А если мы решаем физическую задачу, то я бы еще грубее сказал: это издевательство над здравым смыслом. Ведь если нам позже потребуется значение аппроксимируемой функции где-нибудь между точками (очень часто аппроксимации для этого и нужны), то оно может оказаться совершенно бредовым.
Итого, имеем первый очевидный критерий остановки: как только ошибка аппроксимации сравнялась с ошибками измерений, оптимальный полином выбран.
Но, конечно, тут возможны и другие подходы (о чем я собственно и написал под спойлером своего первого комментария). Для примера вот еще один вариант. Берем число степеней свободы модели (= степень полинома +1), вычитаем его из числа степеней свободы данных (= количество точек), затем делим погрешность аппроксимации на эту разницу. В идеальном случае
минимум этой функции и даст оптимальное значение степени. Но будьте осторожны!
Неочевидная проблема состоит в том, что если данные взаимозависимы (а это почти всегда так), то реальное число степеней свободы Nэфф будет меньше, чем количество точек данных N. Иногда - много меньше! Например, для таких временных рядов, как глобальная температура или заболеваемость гриппом Nэфф часто отличается от N не в разы, а на порядки.
Кстати, если Вы слышали о проблеме "ложных корреляций", то в 2/3 случаев такие корреляции обнаруживаются именно
из-за игнорирования автокоррелированности сравниваемых рядов
А именно, в формулу для оценки значимости корреляций входит размер выборки N. Например, для выборки из 400 точек 95%-ный уровень значимости оценивается, как 2/sqrt(N)=0.1. Если это правильный уровень, то Rxy= 0.3 - это высокозначимая корреляция.
Но, если ваш сигнал автокоррелирован, то эффективное количество независимых значений данных будет не N, а гораздо меньше. Например, для фликкер-шумовых сигналов (а к этому классу относятся почти все геофизические ряды, а также почти вся социология и эконометрика после коррекции за тренд) при длине ряда N=400 измерений эффективное число степеней свободы вполне может оказаться Nэфф=25. Соответственно, 95%-ный уровень значимости будет равен 0.4. Это значит, что упомянутая выше корреляция значимой не является - наоборот, такие корреляции должны регулярно обнаруживаться для совершенно независимых данных.
А совсем катастрофа наступит, если в обоих рядах есть тренды. По сути, любой тренд (не обязательно линейный) тоже можно рассматривать как разновидность автокоррелированности. (Если сомневаетесь - просто постройте АКФ линейно растущей функции или параболы и посмотрите на результат). Для таких рядов даже корреляция Rxy=0.8 запросто может оказаться совершенно не значимой. За подробностями отсылаю к своей статье на Хабре про ложные корреляции. Еще одну статью на эту же тему (как правильно оценивать значимость корреляций) я сейчас готовлю; когда выйдет - добавлю ссылку на нее в комментариях там же.
В общем, если Вы когда-нибудь будете использовать этот критерий, то не забудьте, что эффективное число степеней свободы у экспериментальных рядов почти всегда много меньше, чем количество измерений.
Я вас как раз понял прекрасно, а вот вы меня не особо. Я отнюдь не предлагал вам СТРОИТЬ бесконечное множество интерполяционных полиномов вместо единственного. Не то, чтобы так вообще никогда не делалось, но речь в данном случае вообще не об этом. Моё замечание относилось только к тому, что источник проблем не в требовании выполнения условия интерполяции, то есть точного соответствия значений аппроксимирующей функции значениям аппроксимируемой в заданном множестве точек. Погрешности в данных тут вообще не при чём.
Далее, ссылаться на то, что "я ж практик" не стоит. Я тоже практик. Вот только опыт показывает, что практик, не владеющий и не понимающий теорию - это практик плохой. Не сочтите это за упрёк, это просто замечание к аргументации.
Ваше утверждение, что отказ от условия интерполяции делает задачу тривиальной, мягко говоря, не соответствует действительности. На самом деле в точности наоборот, поскольку содержательная часть задачи аппроксимации как раз и состоит в том, чтобы не просто построить некоторое приближение, но дать объяснение почему аппроксимацию следует искать именно в этом семействе функций, почему аппроксимация отклоняется от данных, почему эти отклонения мы имеем наглость считать допустимыми и почему из всех кривых с аналогичной мерой отклонений мы выбираем именно эту конкретную кривую. Формализовав понятие оптимума мы эту задачу не решим, поскольку это порождает океан дополнительных вопросов: достижим ли глобальный или хотя бы локальный оптимум, насколько он устойчив, насколько велик разброс "оптимальных" аппроксимаций и т.д. и т.п.
Ваше стремление взять "наиболее простую" аппроксимацию, "надёжно" описывающую данные, тоже приводит к нетривиальным проблемам. Почему мы, скажем, считаем параболу "сложнее", чем прямая? (На всякий случай, просто сказать про количество свободных параметров недостаточно). Что "сложнее", экспонента или гармоника? На эту тему есть целые разработанные теории, например, на основе принципа минимальной длины описания, и конкретные практические критерии -- например, критерий Акаике. Но тут всегда возникают дополнительные соображения и допущения о характере данных и выстраиваемой модели, которые нужно ЗНАТЬ, а не опираться на чуйку. Иначе вашему результату грош цена, даже если он случайно окажется правильным.
Внимание, которое уделяется вопросу интерполяции полиномами - это не "дань традиции", а необходимая часть теоретической подготовки для любого, кто хотя бы боком имеет дело с вычислительной математикой (в том числе с численной аппроксимацией). Поскольку а) такая интерполяция лежит в основе большинства классических численных методов, б) она наиболее полно изучена и в) на её примере можно проиллюстрировать массу проблем, характерных для решаемых в выч. мате задач вообще. Эффект Рунге, например, служит иллюстрацией того, что последовательность интерполяций совершенно не обязана сходиться к "истинной" функции при бесконечном увеличении количества доступных данных, даже если эти данные абсолютно точны. Это - нетривиальный и неинтуитивный результат. И похожие эффекты имеют место не только в случае полиномов. Никто в здравом уме не станет предлагать вам строить интерполяционный полином 100500й степени для зашумлённых данных. В курсах выч. мата как раз обоснованно рассказывается почему так делать не стоит (и когда стоит - тоже).
Ваш следующий тезис опять же ошибочен. Во-первых, никакой "сверхподгонки" тут нет. Например, если выбрать в качестве критерия качества минимизацию суммарных абсолютных отклонений от наблюдаемых данных, то оптимальное решение ТОЧНО пройдёт через определенное подмножество данных. То есть в сущности будет решена именно задача интерполяции по "опорному" набору данных. Такой критерий имеет большую практическую ценность, чем, например, МНК -- как минимум потому, что существенно сокращает объем вычислений, получаемая задача существенно лучше обусловлена, а получаемое решение менее чувствительно к выбросам в данных. Во-вторых -- а с чего вы решили, что а) оптимум в вашей задаче достижим практически (например, градиентным спуском) и что он единственен? Вы вполне можете получить (и почти наверняка будете получать) "оптимальные" в смысле выбранного критерия решения, которые не будут иметь практической ценности. Либо получить несколько возможных "оптимальных", удовлетворяющих вашему критерию останова, результатов, которые будут качественно отличаться друг от друга. И вас моментально спросят -- а почему вы утверждаете, что такой аппроксимацией можно пользоваться в практическом плане? Такие утверждения как раз и требуют знаний конкретной математики, а не "очевидных" практических критериев, которыми вы пользуетесь исходя из собственного удобства.
Резюмирую. Никаким корнем зла и вообще никаким злом условие интерполяции не является. Естественно, в том случае, если применять соответствующий инструментарий грамотно, с пониманием того, что и для чего вы делаете. Ваше предложение не снимает проблему, а заменяет её на порядок более сложной, которая исследуется даже не в рамках отдельной теории, а в рамках целых научных направлений. Не стоит опираться на свои "практические" соображения в таких вопросах, так как практика без теории слепа, а к вопросам численного анализа без уверенного знания теории вообще подходить на пушечный выстрел нельзя.
...источник проблем не в требовании (...) точного соответствия значений аппроксимирующей функции значениям аппроксимируемой в заданном множестве точек.
Ну как же не в этом. Откажитесь от этого требования - и мы сможем подобрать гораздо более гладкую аппроксимирующую функцию. Соответственно, описанные в статье проблемы если не исчезнут, то кардинально уменьшатся. Настолько, что для нам не придется изобретать какие-то трюки, чтобы эту аппроксимацию построить.
Погрешности в данных тут вообще не при чём.
Ну как же это ни при чем?
Мы же вроде согласны, что феномен Рунге возникает в силу требования
провести полином через все заданные точки?
Если есть какие-то сомнения - то напомню, что при аппроксимации точек прямой линией осцилляций не будет. По-моему, вполне очевидно, что уменьшая степень полинома, мы автоматически подавляем осцилляции. Вопрос только в поиске компромисса между качеством подгонки и величиной осцилляций.
Второй тезис: если данные известны с погрешностью, то требование провести кривую строго по этим точкам физически бессодержательно. Если измерительный прибор (программа) показал (вычислил) значение х=42.31415926535 +- 0.22222222222, то студент, который будет проводить аппроксимацию строго через точку 42.31415926535, получил бы у меня незачет за абсолютное непонимание предмета. И наоборот, я бы сказал, что в теме хорошо разбирается тот, кто сумеет объяснить, в каких случаях надо записать результат измерения как 42.3, а в каких - как 42.31.
Логика вообще-то очень простая: если мы знаем положение точки с погрешностью, то это надо учитывать при выборе метода обработки данных. Искусственно вводя нефизичное требование, чтобы кривая посетила все точки, мы ничего не улучшим, а лишь получим себе на голову целый ворох проблем. Которых бы не было вовсе, если бы мы от этого глупого и бессмысленного (при наличии погрешностей измерений) требования отказались.
Таким образом, наличие погрешностей дает нам право решать гораздо более устойчивую задачу вместо использования идеализированной, но неадекватной модели.
Аналогия
Рассмотрим задачу: как попасть из точки А в точку Б (карта имеется).
Вы исходите из того, что для этого перво-наперво надо научиться рисовать по линейке прямую (кратчайший путь). А что там на карте есть, на этом этапе не имеет значения. Если вдруг эта прямая пройдет через лес - будем рубить просеку. Если через озеро - построим мост. Мы же учимся проводить кратчайшую линию...
Только вот при решении реальной задачи добраться "к бабушке" мы почему-то не станем ломиться напрямик, а пойдем по полянке вокруг леса и озера. Что будет на порядок быстрее и проще. Да еще и топор/мостоотряд брать не надо.
Так что, получается, что умение проводить прямую не пригодилось? Да нет, пригодилось: ведь через ровное поле лучше всего идти по прямой, а не зигзагами. Если бы вся карта состояла из ровного поля, то этого и правда было бы достаточно.
Только вот в реальной жизни на карте всегда есть леса, озера и прочее. В моей аналогии это как раз и есть та погрешность, которая, по-Вашему, ни при чем. И с учетом этой погрешности задача должна решаться совершенно по-другому. Что заодно автоматически избавляет нас от кучи проблем (осцилляции), возникших из-за попытки приспособить эту искусственную идеализацию к реальному миру.
Итого: знать про полином Лагранжа (= умение провести прямую на карте) полезно, только вот не надо нам намекать, будто освоивший эту тему может спокойно идти из А в Б.
На самом деле в точности наоборот, поскольку содержательная часть задачи аппроксимации как раз и состоит в том, чтобы не просто построить некоторое приближение, но дать объяснение почему аппроксимацию следует искать именно в этом семействе функций,
Возражение не принимается, так как в изначальной постановке про выбор семейства функций не сказано вообще ничего. Изначально рассматриваются полиномы. Как Вы заметили, я остался в рамках этой же постановки. Поскольку это замечание в равной степени применимо к обоим обсуждаемым подходам, оно не может быть аргументом в пользу предпочтительности одного из них.
...почему аппроксимация отклоняется от данных?
Тут у меня есть встречный вопрос: а с чего это вдруг аппроксимация должна проходить через какие-то случайные точки, которые вовсе не лежат на аппроксимируемой функции?
Напомню, я изначально писал про экспериментальные данные. А это значит, что измеренные значения (наши точки) находятся в некоторой окрестности от истинных значений функции. Но с вероятностью единица на ней не лежат.
С этой точки зрения, предложение провести аппроксимацию точно через какие-то непонятные значения кажется гораздо более странным.
Впрочем, я согласен с тем, что это Ваше замечание было полезным. Этот вопрос (должна ли аппроксимация точно проходить через экспериментальные точки, или нет) де-факто оконтуривает границы применимости аппроксимации по Лагранжу. При работе с экспериментальными данными ее методологическая несостоятельность становится очевидной.
почему эти отклонения мы имеем наглость считать допустимыми
Тот же самый встречный вопрос: а почему мы имеем наглость считать, что оптимальной аппроксимаций будет та, которая ТОЧНО пройдет через какие-то случайные точки, заведомо НЕ лежащие на нужной нам функции? По-моему, именно эта абсолютизация как раз и обессмысливает описанную в статье модель при работе с экспериментальными данными.
почему из всех кривых с аналогичной мерой отклонений мы выбираем именно эту конкретную кривую.
А вот тут согласен: такой вопрос действительно возникает. Действительно, нам придется выбрать критерий оптимальности (о чем я написал изначально). Только вот если повнимательнее посмотреть на авторскую постановку, то она вовсе не избавляет нас от этого выбора. Просто он делается неявно: сама постановка уже предполагает, что мы выбрали критерий, обнуляющий отклонения. Проблема возникает чуть позже: оказывается, что этот критерий работает как-то странно, и приводит к неприятным осцилляциям. То есть, выбрав этот критерий оптимальности, мы сами создали себе проблему на ровном месте. А может, просто не нужно было использовать такой дурацкий критерий, который нас в это "болото" осцилляций загнал? ;-)
И это мы еще до физики не дошли. А физика (когда данные - экспериментальные) нам говорит, что мы никогда НЕ знаем, где точно проходит аппроксимируемая функция. Все что мы знаем - что экспериментальные точки лежат в ее некоторой окрестности. Имхо, тут уже пора включить логику и задать вопрос: а что мы все-таки аппроксимируем? Искомую функцию или же какой-то случайный набор точек?
Нет, я не спорю, что с точки зрения чистой математики задача проведения полинома через случайный набор точек вполне интересная и осмысленная. Только вот к решению физической задачи аппроксимации некоторой неизвестной функции (значения которой мы как-то измерили) эта математическая задача имеет очень косвенное отношение. Особенно если про устойчивость вспомнить...
Формализовав понятие оптимума мы эту задачу не решим, поскольку это порождает океан дополнительных вопросов: достижим ли глобальный или хотя бы локальный оптимум, насколько он устойчив, насколько велик разброс "оптимальных" аппроксимаций и т.д. и т.п.
Это верно. Но что Вы предлагаете взамен? Выбрать такой критерий оптимальности, который чуть-чуть облегчает решение этих вопросов (как это фактически сделано в постановке Лагранжа)? Или все-таки учитывать практическую полезность метода, а не только доказанность его оптимальных свойств?
В геофизике огромную практическую пользу принесли задачи, которые вообще не имеют корректной математической постановки. Например, одному и тому же набору кажущихся сопротивлений на установке ВЭЗ может соответствовать бесконечное множество моделей среды. Тем не менее, с помощью каких-то регуляризаций и априорных посылок такие задачи решаются, модели строятся, и очень часто оказываются полезными.
Почему мы, скажем, считаем параболу "сложнее", чем прямая? (На всякий случай, просто сказать про количество свободных параметров недостаточно).
Согласен, число свободных параметров - это не единственный критерий "сложности", хотя и один из важнейших. Но когда мы выбираем семейство кривых ("экспонента или гармоника" и т.д.), то нам неизбежно приходится выйти за рамки математики. Ведь математика работает со строго формализованными моделями. А одной и той же физической ситуации всегда можно сопоставить много разных формальных моделей. В одной из них будет оптимальной гипербола, а в другой экспонента. И как бы мы ни настаивали, что гипербола предпочтительна "согласно строгим критериям", по сути все определяется тем, как мы формализовали физическую задачу. А это вне математики.
Поэтому как бы мы ни надеялись на разные критерии, мы все равно в конечном итоге будем именно что "опираться на чуйку". Как бы Вам ни хотелось обратного. Иначе можно получить строго обоснованный математически результат с превосходным набором доказанных оптимальных свойств, но которому будет "грош цена" потому, что исходная формализация была не совсем адекватной. Собственно, хорошие математики это всегда понимали. А вот в учебнике такую мысль впервые акцентировал, вроде бы, В.Ю.Урбах [Математическая статистика для биологов и медиков. M.: Изд. АН СССР, 1963. 322 с]. Но это не точно.
Для примера
Всю вторую половину прошлого века огромная куча людей в разных странах проводила всевозможные эксперименты по мониторингу и строила все более хитрые методы поиска предвестников землетрясений, непрерывно совершенствуя критерии их выделения и доказывая оптимальность этих критериев. Теория обнаружения предвестников уже была близка к совершенству... а природа раз за разом тыкала нас, сейсмологов, мордой в грязь. А ключ к ответу оказался элементарным: все ждали, что шумы будут белыми, а на практике оказалось, что там фликкер-шум. Что автоматически обнулило абсолютно все построенные критерии в силу совершенно неадекватной формализации исходной задачи.
Так что да - стоит лишь выйти за калитку рая математических конструкций в ад физической реальности, и внезапно оказывается, что без "чуйки" ну совсем никуда. Такова се ля ви.
Внимание, которое уделяется вопросу интерполяции полиномами - это не "дань традиции", а необходимая часть теоретической подготовки для любого, кто хотя бы боком имеет дело с вычислительной математикой (в том числе с численной аппроксимацией). Поскольку а) такая интерполяция лежит в основе большинства классических численных методов, б) она наиболее полно изучена и в) на её примере можно проиллюстрировать массу проблем, характерных для решаемых в выч. мате задач вообще.
С этим я вполне согласен. О чем и написал изначально. Возможно, полемический стиль изложения несколько исказил мою мысль.
Эффект Рунге, например, служит иллюстрацией того, что последовательность интерполяций совершенно не обязана сходиться к "истинной" функции при бесконечном увеличении количества доступных данных, даже если эти данные абсолютно точны. Это - нетривиальный и неинтуитивный результат.
Возможно, хотя после функции Вейерштрасса, а также приколов с бесконечными множествами пора бы уже понять, что интуиции можно верить далеко не всегда ;-)
Ваш следующий тезис опять же ошибочен. Во-первых, никакой "сверхподгонки" тут нет (...).
Тут я не совсем уловил идею критики. Я вижу косвенную аналогию со сверхподгонкой в том, что при выходе за границы обучающей выборки качество аппроксимации резко ухудшится по сравнению с достигнутым на этой выборке. Я утверждаю, что если данные (измеренные значения аппроксимируемой функции) известны с погрешностью, то полиномиальная аппроксимация строго по измеренным значениям будет в общем случае хуже, чем более гладкая аппроксимация, проведенная примерно по измеренным значениям (с учетом погрешности). Да, я не могу это доказать строго (и даже не уверен, что оно верно всегда). Но в обычных ситуациях кажется, что все именно так. В частности, для простых функций оно выглядит очевидным.
Например, можно рассуждать так.
Возьмем за критерий близости интеграл от квадрата разности между искомой функцией и ее аппроксимацией. Теперь, если истинная функция это y=const, а ошибки гауссовы, то статистически наилучшее приближение функции (а не измеренных точек!) даст полином нулевой степени. Любые другие степени приведут к осцилляциям полинома, что лишь удалит его от истинной функции.
Аналогично с линейной функцией, и т.д.
Например, если выбрать в качестве критерия качества минимизацию суммарных абсолютных отклонений от наблюдаемых данных, то оптимальное решение ТОЧНО пройдёт через определенное подмножество данных.
Тут я не понял мысль. Вопрос о том, пройдет ли полином точно через заданные точки (в невырожденном случае), зависит вовсе не от критерия минимизации, а лишь от степени полинома. При любом разумном критерии минимизации. Поправьте, пожалуйста, формулировку, т.к. в таком виде Ваше утверждение ошибочно.
Вы вполне можете получить (и почти наверняка будете получать) "оптимальные" в смысле выбранного критерия решения, которые не будут иметь практической ценности.
Так в этом-то и вопрос: какой критерий оптимальности наилучший. Разумеется, этот вопрос - ключевой, и его надо ставить в первую очередь. А отвечать на него, исходя из физических и практических соображений (математика сама по себе ответа не даст). Я нигде не говорил, что знаю этот ответ. Однако я хотел обратить внимание на тот факт, что
оптимальность по Лагранжу
напомню, требование к кривой пройти через все экспериментальные точки - это фактически один из возможных критериев оптимальности аппроксимации
это совершенно неудовлетворительный выбор, который совершенно точно не имеет никакой практической ценности, если данные известны с погрешностью. Поэтому я совершенно согласен с этим Вашим замечанием. Оно очень уместно в этом контексте, потому что оптимальное по Лагранжу решение действительно не будет иметь практической ценности в большинстве случаев.
Разумеется, это еще не говорит о том, что любое другое решение (критерий оптимальности) лучше. Но недостатки оптимальности по Лагранжу (когда кривая посещает все точки) настолько очевидны, что мы просто обязаны попробовать что-то другое. (И очень во многих конкретных случаях действительно "есть способ лучше" (с)). Если бы это было сказано изначально, то половина моих вопросов отпала бы. Иначе получается, что мы
сначала погружаем читателя в мир розовых пони
а на следующем шаге, буквально по Райкину, оказывается, что в действительности все не так, как на самом деле
(...) а почему вы утверждаете, что такой аппроксимацией можно пользоваться в практическом плане?
Так я же не говорю, что тут есть какой-то простой ответ. Наоборот, вариантов и критериев - тьма. И какой из них лучше - это вопрос. Я лишь утверждаю, что
а) такой выбор есть,
б) аппроксимация по Лагранжу - это почти наверняка плохой выбор, и что
в) четких правил для выбора лучшей альтернативы не существует; эта задача неизбежно выводит нас за рамки математического формализма.
При чтении этой статьи (да и многих других подобных) невольно складывается впечатление, что перед нами некая панацея. Да что статья - даже при работе с учебниками часто возникает иллюзия, что хорошее владение математикой позволит нам строго и точно решать практические задачи. Я всего лишь хочу избавить читателей этого обсуждения от этой иллюзии. Нет, не позволит. Просто потому, что применимость и оптимальность любых математических методов обусловлена той моделью, в рамках которой они сформулированы. А реальный физический мир не построен на аксиомах. Поэтому мы никогда не знаем, адекватна наша модель, или нет. И это на всех уровнях так - начиная от философии и кончая аппроксимацией неизвестной функции.
Резюмирую. Никаким корнем зла и вообще никаким злом условие интерполяции не является. Естественно, в том случае, если применять соответствующий инструментарий грамотно, с пониманием того, что и для чего вы делаете.
Ключевые слова - "применять грамотно". Если бы статья с этого начиналась, то половина вопросов отпала бы. Всего-то надо было добавить, что хотя этот метод входит в "математический аналог" теор-минимума, но на практике (при работе с экспериментальными данными) он не нужен почти никогда. То есть, "грамотно применять" - это значит либо не применять почти никогда, либо ставить "подпорки" по Чебышеву или еще как-нибудь. Но точно так же, как при разработке ПО мы стремимся отрефакторить "костыли" (даже если они пока что позволяют коду работать), точно так же и при аппроксимации функции лучше сразу использовать что-то более адекватное. А не писать "код", который почти гарантированно потребует "костылей".
Более гладкую, чем полином? Вы видимо имеете ввиду что-то типа "менее подверженную осцилляциям" или ещё какой умозрительный критерий. Полином - бесконечно гладкая функция.
Нет, проблемы не уменьшатся. Взамен одной проблемы вы получите десяток других.
Нет, мы не согласны, что феномен Рунге возникает из этого требования. Иначе он проявлялся бы для любого интерполяционного полинома, а не для полинома по равноотстоящим узлам. Полином по узлам Чебышева эффектом Рунге не страдает, при иных способах выбора опорных узлов этот эффект также теряет силу. Эффект Рунге в сущности отражает характерное поведение при неподходящем выборе семейства аппроксимирующих функций.
Нет, оно не "физически бессодержательно", что бы вы под этим не подразумевали.
Ни в каких случаях не надо записывать результат как 42.31, если прибор показал 42.3 и установленная методология измерений не требует внесения поправок на методическую погрешность. В метрологии записывается доверительный интервал. И если вы поставили задачу так, как сказали -- то я соболезную студенту, поскольку возможность или невозможность проводить аппроксимацию посредством интерполяции по точкам зависит от оценки погрешности этой самой интерполяции, а не от вашего "понимания", если только нет априорной информации об аппроксимируемой функции. Если величина погрешности измеряется микронами, а интервал между точками метрами, то влияние погрешности измерений обычно ничтожно (что, в прочем, нужно доказать для выбранной схемы аппроксимации). Количество проблем, где в контексте аппроксимации погрешностью можно пренебречь, неисчислимо. Мне ваши соображения понятны, но они исходят из того, что есть некоторые обоснованные априорные соображения о виде закона, который требуется восстановить на основании наблюдаемых данных. Иными словами, вы рассуждаете об интерполяции имея ввиду задачу регрессии. Это методически неверно.
Я уже указал, что ваша простая логика неверна и базируется на странном ощущении, как будто вам кто-то предлагает в каждой задаче, связанной с обработкой данных, заниматься интерполяцией. Не предлагают. И совсем не из-за наличия погрешностей - которые в выч мате есть и УЧИТЫВАЮТСЯ всегда. Из этого вы по какой-то неведомой причине делаете вывод о несостоятельности интерполяции как метода вообще. Сударь, свет не сходится клином на том, чтобы просто провести гладкую кривую через набор точек. Предположим, что вам нужно вычислить интегральную характеристику некоторой меняющейся во времени величины. Большинство методов численного интегрирования предполагают интерполяцию по соседним точкам и вычисление приближения к интегралу по полученным кусочным интерполянтам. При этом зная а) погрешность аппроксимации и б) погрешность положения точек интерполяции мы можем также оценить и точность приближенного значения интеграла, а также поведение ошибки при, например, большей частоте измерений. Естественно, если погрешность измерений велика, функция ведёт себя "нехорошо" и т.п., то такой подход теряет смысл -- как и зачастую сама постановка задачи. Или вам нужно сделать "пристрелку" на следующий временной шаг при интегрировании дифура. Тогда простой способ сделать это -- использовать уже посчитанные значения по предыдущим временным шагам для построения интерполяционного полинома и экстраполировать значение. И да, эти значения известны с погрешностью -- но это не проблема, если эта погрешность контролируема.
Аналогия крайне странная и натужная.
Мы не считаем такую аппроксимацию "оптимальной", такая постановка вопроса вообще бессодержательна вне контекста задачи. Интерполяция удобна тем, что она единственна и имеет конструктивные оценки ошибки. Если вы подумали, что где-то утверждалось, что интерполяционный подход в каком-то смысле "оптимален" - вам показалось.
Взамен я предлагаю не искать серебряную пулю, а подбирать инструмент исходя из постановки задачи, пользуясь всем богатым арсеналом методов и теорий современной вычислительной математики. Вы набросились на интерполяционные полиномы, так как считаете их негодным средством для решения известных вам задач. Вероятно, вы в этом правы. Но в статье и не обещалось добиться успеха именно с вашими задачами. Не спешите объявлять что-то бесполезным только потому, что лично вам польза кажется не очевидной.
Поясню мыль, которую вы не поняли. Ваше утверждение заключается в том, что требование функции строго пройти через указанные точки является слишком обременительным, а полученное решение с практической точки зрения непригодно. Уже говорил, что вы по какой-то загадочной причине видите в этой задаче только проблему восстановления функции по данным, причем использоваться должны непременно ВСЕ имеющиеся данные. В такой постановке подход и правда малосодержателен. И, как также говорилось -- никто так и не делает. Но и ВСЕ данные использовать НЕ обязательно. Можно отобрать небольшой "характерный" набор из имеющихся данных и построить по нему интерполяцию. И такая модель в определенных ситуациях будет иметь ряд преимуществ, и даже в некотором смысле "оптимальной". Соответствующий набор можно выбрать оптимальным способом из имеющихся данных, можно выбрать эвристически, а можно вообще поставить задачу определить с учетом имеющихся данных положение точек, дополнительное измерение значений восстанавливаемой функции в которых даст приближение наилучшего качества. Таким образом, утверждение о практической бесполезности интерполяции беспочвенно.
Ещё раз замечу (поскольку вы к этому постоянно апеллируете), что ни автор данного поста, ни я не призывали вас применять интерполяцию полиномами при непосредственной работе с массивами экспериментальных данных. Тем более странно слышать про "подпорки" Чебышева, так как узлы Чебышева нужны не для того, чтобы "прикрыть" Рунге, а для того, чтобы обеспечить минимум погрешности в задачах, тесно связанных с интерполяцией полиномами -- дифференцирование, интегрирование и т.п. Постановка задачи, приводящей к корням полиномов Чебышева, является типичной в том числе и в других, не связанных с интерполяцией, методах приближения функций. Неужели вам об этом неизвестно?
Пост я считаю не нужным, поскольку этот материал излагается в любом учебнике по численным методам, его знание является обязательным для доброй половины технических специальностей, а никакой оригинальной мысли мне в нём увидеть не удалось. Но вы попытались примерить инструмент к не предназначенной для него задаче -- и по этой причине забраковали инструмент. Это максимально далёкий от инженерного подход.
По поводу соотношения математики и практики скажу следующее. Обычно пренебрежительным отношением к математическому фундаменту грешат те, кто ими попросту не владеет и не умеет должным образом применять. Им же свойственно превозносить свой личный опыт и "понимание" проблемной области, которое на поверку оказывается не слишком глубоким. Мне отнюдь не "хочется обратного", в силу рода деятельности мне хорошо понятна ограниченность "чистых" абстракций, важность обоснованных, хотя и недостаточно строго формализованных теорий, а также разница между теоретически значимым результатом и практически значимым методом. Как и, вероятно, вы, я скорее предпочту грубую, но дающую результат инженерную методику эстетически безупречной, но не имеющей практической значимости, теории. Вот только это не является поводом такими теориями пренебрегать. Без знания математики, которая стоит за применяемыми к практическим задачам методами, мы в сущности будем лишь с ничем необоснованной уверенностью пробираться методом проб и ошибок, слепо надеясь на то, что инструмент и интуиция нас не подведут. И не будем способны увидеть грань, за которой наш "здравый смысл", "опыт" и "инженерное чутьё" сыграют с нами злую шутку. А в том, что они подведут, можно не сомневаться. Знание математики не является панацеей и не наделит вас сверхсилой решать практические задачи на раз -- уж не знаю, кто и когда стремился посеять в вас эти иллюзии, которые вы теперь хотите развеять в окружающих. Но вот незнание математики с гарантией сузит круг задач, которые вы способны качественно решить и при этом ответить за своё решение, до посредственного минимума. Поскольку мощнее математики в арсенале современного учёного и инженера инструментов нет.
Полином - бесконечно гладкая функция.
Да, я имел в виду полином меньшей степени, менее подверженный осцилляциям (у которого меньше ненулевых производных).
Нет, проблемы не уменьшатся. Взамен одной проблемы вы получите десяток других.
Выше мы уже обсудили, что хотя такие проблемы действительно есть, но большинство из них в равной степени присущи обоим подходам. Просто когда мы подбираем по N точкам полином n-й степени, то "лишние" вопросы как бы заметаются под ковер (ответы на них вытекают из уже принятого решения n=N). Если же мы допускаем, что n может быть меньше N, то тогда действительно возникает вопрос: а на сколько меньше? И на него приходится отвечать, выдумывая и пробуя разные критерии. Чем это принципиально отличается от случая, когда мы априори ("волевым решением") постановили n=N? Только потерей гибкости во втором случае... ну и нехилыми шансами нарваться на случай, когда выбор n=N совершенно не оптимален.
Нет, мы не согласны, что феномен Рунге возникает из этого требования. Иначе он проявлялся бы для любого интерполяционного полинома, а не для полинома по равноотстоящим узлам.
Мне казалось, что мы изначально говорили про проблему, возникающую на равноотстоящих узлах, разве нет? Во всяком случае, фразу в статье "Феномен Рунге подчеркивает ограничения интерполяции на равномерно распределенных узлах" я понял именно так.
Я вполне понимаю, что эту проблему можно решать по-разному. Но у меня, вероятно, есть некая профдеформация из-за того, что в геофизике практически все временные ряды имеют фиксированный шаг наблюдений. Поэтому я предложил решение, которое не требует отказа от требования "равноотстоятельности" (или равноотстояния?) узлов (сорри, не знаю, как правильно извратить это слово ;-) Мне кажется, что в моем случае это наиболее естественное решение. При другой постановке задачи ответ, естественно, будет другим.
Нет, оно не "физически бессодержательно", что бы вы под этим не подразумевали.
Я не знаю как мне сформулировать этот тезис по-другому, чтобы прийти к взаимопониманию. Могу только сказать, что я не сумею выразить его математическим языком, так как это не математика, а скорее философия. Я исхожу из того, что критерием истины является практика. Мне кажется, что любую математическую концепцию можно рассматривать как минимум с двух точек зрения: а) ее внутренней цельности (красоты), обилия следствий, логической непротиворечивости и т.д. и б) применимости для практических нужд. Так вот, мне кажется, что модель, в рамках которой кривая обязана пройти через какие-то совершенно случайные точки, как минимум непрактична, а как максимум - противоречит логике научного метода. Ведь она де-факто будет в этом случае опираться не только на эмпирическое обобщение, но и на "генератор случайной помехи". Другими словами, при таком подходе мы фактически добавляем в данные какой-то неизвестный случайный шум, причем так, что он становится неотличимым от сигнала. Лично мне это кажется нелогичным.
В метрологии записывается доверительный интервал.
Именно так. Поэтому нет смысла выписывать 15 десятичных цифр после запятой, если доверительный интервал +-0.1. Вы не находите странным (в такой ситуации) требование, чтобы аппрокмсимирующая кривая прошла через измеренное значение с точностью до 15-й цифры? Я вот считаю, что при погрешности измерений +-0.1 это требование - совершенно бессмысленное. Но когда мы строим полином строго по точкам (вместо требования пройти к ним достаточно близко), то мы как раз и впадаем в этот абсурд. И ладно бы дело этим и ограничивалось. Но тут внезапно оказывается, что такое требование еще и провоцирует осцилляции, которых бы не было, используй мы n < N. По-моему, это уже однозначно выводит такой метод аппроксимации из игры. При решении обрисованного круга задач, разумеется.
Если величина погрешности измеряется микронами, а интервал между точками метрами, то влияние погрешности измерений обычно ничтожно
Как геофизик, должен Вас разочаровать. При мониторинге процессов в Земле ситуация с погрешностями обычно обратная :-((
(...) ваша простая логика неверна и базируется на странном ощущении, как будто вам кто-то предлагает в каждой задаче, связанной с обработкой данных, заниматься интерполяцией.
Ну не знаю. Мне кажется естественным оценивать любой метод с точки зрения его применимости к тем задачам, которые интересны читателю. Разве не для этого мы статьи читаем и пишем? В моей области такие задачи весьма типичны. Поскольку статья как бы претендует, что метод универсальный, то я не вижу нарушений логики в том, что я его "на себя" примеряю.
Из этого вы по какой-то неведомой причине делаете вывод о несостоятельности интерполяции как метода вообще.
???
Посмотрел свои сообщения, нигде такого утверждения не нашел. Наоборот, я довольно часто с задачей интерполяции сталкиваюсь. Например, у нас бывают пропущенные наблюдения сплошь и рядом. И иногда (при том же вычислении БПФ) надо туда обязательно какую-то "цифру" подставить.
Кстати, я был бы рад узнать Ваше мнение о той дюжине способов, которые мы для этого в разных случаях применяем
Если Вам интересно, конечно. Я исхожу из того, что любая конструктивная критика очень полезна, так как на ее основе можно что-то улучшить.
Но в статье-то описаны не эти способы, а еще один. И вот так получается, что для наших задач он не очень. Но примерно понятно, что именно надо там подкрутить, чтобы он стал вровень с другими. Я всего лишь честно написал свое мнение по этому поводу. Как из этого можно сделать вывод, что я вообще против интерполяции/аппроксимации - мне понять трудно.
(...) если погрешность измерений велика, функция ведёт себя "нехорошо"
Без дополнительных уточнений - довольно спорное утверждение! Конечно, если у нас есть N "плохих" (с большой погрешностью) точек, и мы будем их аппроксимировать n-параметрической функцией (где n почти равно N), то можно нарваться на неожиданности. А может быть, надо всего лишь взять в этом случае функцию чуть попроще? Да, она будет идти очень грубо, но зато без непредсказуемых странностей. Выбор семейства функций - это не только априорный вопрос; погрешность данных тоже надо учитывать. Я спорю лишь с тем, что функция, которая точно проходит через все значения данных, всегда лучше, чем та, которая через них не проходит. Такая иллюзия очень опасна именно потому, что она очень легко приводит к этим "нехорошо".
Аналогия:
у нас может быть страшно зашумленное облако точек, через которое вполне можно провести (причем достаточно надежно) прямую. И даже если мы разделим это облако точек на две половины (с четными номерами и с нечетными), то "четная" и "нечетная" прямые почти совпадут. А вот два полинома стопятьсотой степени, построенные по этим же точкам - совершенно не факт.
Надо всего лишь признать, что при большой погрешности данных отношение сигнал/шум (при прочих равных) ухудшается, и учитывать это при построении любой конструкции над этими данными.
(...) то такой подход теряет смысл -- как и зачастую сама постановка задачи.
Ну разумеется, есть разные ситуации. Я-то (в отличие от автора статьи) стараюсь приложить метод к конкретной задаче. И если в моем случае он не подходит, то это совершенно ничего не говорит о других задачах. А Вы зачем-то его защищаете даже в той ситуации, когда он
явно не оптимален
Говорят, что все споры - это споры о терминах. Оказывается, не только о терминах, но и о границах применимости методов ;-)
Если вы подумали, что где-то утверждалось, что интерполяционный подход в каком-то смысле "оптимален" - вам показалось.
Да, впечатление такое сложилось. Учту.
Не спешите объявлять что-то бесполезным только потому, что лично вам польза кажется не очевидной.
Разве я где-то говорил "за всех"? Прошу прощения, если меня так поняли. И второе: мой посыл был вовсе не в том, что аппроксимация полиномами плохо работает для каких-то конкретных задач. А в том, что в пределах этой области применения ее недостатки можно довольно легко исправить, просто уменьшив степень полинома. Вы почему-то посчитали, что это мое предложение оскорбительно для полиномов Лагранжа. Хотя на мой вкус, идея с узлами Чебышева сужает сферу применимости метода в значительно большей степени. Ведь понизить степень полинома мы можем почти всегда, а вот измерить значения искомой функции в произвольной точке - не очень. Для наших (экспериментальных) временных рядов - ну вот совсем никак не получится...
вы по какой-то загадочной причине видите в этой задаче только проблему восстановления функции по данным,
Нет, разумеется. Просто я сам занимаюсь именно этой задачей, поэтому не удивительно, что она меня беспокоит
больше других
(тут должна быть присказка про баню ;-)
причем использоваться должны непременно ВСЕ имеющиеся данные.
А вот это Вы верно подметили.
Да, у нас именно так
При геофизическом мониторинге каждое экспериментальное значение - уникально и невоспроизводимо, потому что мы имеем дело с нестационарными процессами. Повторить неудачное измерение на следующий день невозможно - система уже будет принципиально другой. Даже тот же самый прибор под той же самой горой покажет что-то другое. Этим наши измерения отличаются от обычных лабораторных экспериментов. И - да, это накладывает свой отпечаток на образ мышления.
Ещё раз замечу (поскольку вы к этому постоянно апеллируете), что ни автор данного поста, ни я не призывали вас применять интерполяцию полиномами при непосредственной работе с массивами экспериментальных данных.
Согласен. Но очень многие это делают, благо метод есть в куче статистических пакетов. И поскольку довольно часто это срабатывает, и неплохо (например, сплайны), то может возникнуть иллюзия, что так будет всегда. Вот с этим-то я и спорю. Тем более что статья к этому как бы подталкивает. Так что я скорее не критикую статью, а дополняю тему взглядом со своей стороны.
(...) узлы Чебышева нужны не для того, чтобы "прикрыть" Рунге, а для того, чтобы обеспечить минимум погрешности в задачах, тесно связанных с интерполяцией полиномами -- дифференцирование, интегрирование и т.п.
Математикам проще: они могут рассматривать такую модель, какую хотят. А в моей области (где измеренные значения - это часто плод многолетних усилий) данные - это святое. И "кощунство", предложенное Чебышевым, действительно выглядит, как подпорка ;-)
Но вы попытались примерить инструмент к не предназначенной для него задаче -- и по этой причине забраковали инструмент. Это максимально далёкий от инженерного подход.
Во-первых, статья как бы намекала - что и для этих задач "тоже можно". Ну или я неправильно понял ее посыл. Трижды прав peterpro18, который заметил, что в статье не хватает начала (=введения и постановки задачи).
А во-вторых, не забраковал, а предложил свой вариант решения. Подходящий в моей ситуации.
По поводу соотношения математики и практики скажу следующее (...) Без знания математики (...) мы не будем способны увидеть грань, за которой наш "здравый смысл", "опыт" и "инженерное чутьё" сыграют с нами злую шутку. (...) мощнее математики в арсенале современного учёного и инженера инструментов нет.
Тут не поспоришь ; -) Но к сожалению, я слишком часто сталкиваюсь с ситуацией, когда достаточно серьезные ученые вроде бы в совершенстве владеют математическим аппаратом (точнее, техникой вычислений), но применяют его
как-то странно
Так, однажды я рецензировал очень ярко написанную публикацию, просто усыпанную изощренными статистическими критериями и таблицами. Смущало только одно: там нигде не было ни намека, какие именно статистические гипотезы проверяются. А когда я попросил сформулировать хотя бы одну в явном виде, смысл ответа был примерно такой: сомневаться в выводах невозможно, потому что "расчеты значимости выполнены в самой последней версии самой лучшей программы" (включая чуть ли не сканы лицензии). И этот человек регулярно публикуется в разных журналах и получает хорошие гранты.
Так что сам я как раз не слишком подвержен (надеюсь!) иллюзии, что умение выбрать в меню программы алгоритм с красивым названием и подставить туда значения из своей таблицы дает нам сверхсилу. Но я постоянно сталкиваюсь с людьми, у которых такая иллюзия есть. Возможно, поэтому, когда я вижу на Хабре статьи, которые могут такие иллюзии спровоцировать, у меня начинается паника...
.
Например, у нас бывают пропущенные наблюдения сплошь и рядом. И иногда (при том же вычислении БПФ) надо туда обязательно какую-то "цифру" подставить.
Так есть же варианты алгоритмов БПФ для разрежённых данных, необязательно туда что-то подставлять. Для своих задач я делал слегка изменённый вариант метода наименьших квадратов,
пример с 13-ю синусоидами
Так есть же варианты алгоритмов БПФ для разрежённых данных
Спасибо за напоминание, посмотрю при случае повнимательнее. Но по старой памяти, эти алгоритмы вроде бы хороши, когда пропусков очень много? То есть ряд сплошь из нулей с редкими значениями данных. А у нас пропусков хоть и много, но не настолько. В типичных случаях их 2-10%. Или мои впечатления устарели?
P.S. Кстати, к вашему вопросу о внутренней противоречивости в формулировке задачи интерполяции применительно к экспериментальным данным. Никакого противоречия тут нет, а есть просто методичный подход к решению проблемы. Сначала исследуется вопрос приближения в предположении, что значения приближаемой функции в заданных точках известны точно. Это - допущение, оно вводится явным образом. Лагранж сотоварищи об этом в курсе. Такое исследование предполагает не только определение способа конструктивного построения приближения, но, что более важно, определение границ, в которых лежит ошибка приближения в неизвестных точках при разумных допущениях о свойствах интерполируемой функции. Без этого знания ваше приближение бесполезно. После того, как оценки получены, имеет смысл ставить вопрос о том, как ведёт себя ошибка при условии, что значения в опорных точках заданы с известной погрешностью. В том числе получает конструктивную постановку и вопрос, как оптимально выбрать значение в опорной точке из интервала, определяемого погрешностью, так, чтобы минимизировать ожидаемую ошибку приближения. Именно так до сих пор исследуется устойчивость численных методов, поскольку в них данные всегда заданы с погрешностью как минимум по причине конечной точности представления чисел в машинной арифметике.
(...) После того, как оценки получены, имеет смысл ставить вопрос о том, как ведёт себя ошибка при условии, что значения в опорных точках заданы с известной погрешностью (...).
Ну вот, Вы сами ответили на свой намек, что я со своими идеями переусложняю простую задачу ;-) Оказывается, когда данные известны с погрешностью, то "лобовая" аппроксимации полиномом уже не вполне достаточна, и кое-что придется "доработать напильником".
Так может быть, проще будет не делать из буханки троллейбус, а попробовать что-то другое? Ну или по крайней мере рассмотреть эти варианты наряду с первым?
В чём была цель написания статьи? Это ведь стандартная тема, которая обязательно рассматривается в курсе по численным методам или выч. мат-ке, представлена в практически любом учебнике и имеет скорее теоретическую ценность в контексте анализа сходимости интерполяций. На практике интерполяция полиномами высоких порядков практически не используется.
Ликбез? Или заметка, к которой планируется делать отсылки?
У меня в детстве была книжка "Физики шутят" и там была классификация научных статей, и одна из них называлась "Загадочная", потому что рождала ощущение, что автор продолжил в статье с середины фразы какую-то мысль, о которой долго думал.
Простите, но для обывателя было бы очень круто в начале хотя бы пару абзацев в стиле ELI5 😁
Феномен Рунге