15.08.2024 18:34
kristina_ponomareva 28 6400 Источник

Введение

Карл Давид Тольме Рунге (30 августа 1856 - 3 января 1927) - выдающийся немецкий математик, физик и спектроскопист. Обучался в Берлинском университете, где получил степень PhD, являлся профессором математики в Ганноверском университете, а также главой кафедры прикладной математики в Гёттингене. [1]

в 1901 году Карл открыл "Феномен Рунге" - в численном анализе эффект нежелательных колебаний, возникающий при интерполяции полиномами высоких степеней - о котором пойдёт речь в данной статье. [2]

Но прежде, чем мы окунёмся глубже в изучение данного феномена, давайте поговорим об интерполяционном многочлене Лагранжа, на примере которого мы и разберём Феномен Рунге.

Интерполяционный многочлен Лагранжа

Полином Лагранжа - это математическая функция, позволяющая записать полином n-степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки. Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. [3]

Полином Лагранжа в общем виде выглядит следующим образом:

L(x) = \sum_{i=0}^n y_i * l_i (x)

где l_i (x) - это базисные полиномы Лагранжа, определяющиеся как

l_i(x) = \Pi \frac{x-x_j}{x_i-x_j}

где 0≤j≤n, j≠i

Так, например, интерполяционный многочлен в форме Лагранжа, проходящий через три заданных точки будет записываться вот так: [3]

L(x) = f(x_0) * \frac{x-x_1}{x_0-x_1}\frac{x-x_2}{x_0-x_2} +f(x_1) * \frac{x-x_0}{x_1-x_0}\frac{x-x_2}{x_1-x_2} +f(x_2) * \frac{x-x_0}{x_2-x_0}\frac{x-x_1}{x_2-x_1}

Погрешность интерполяционного многочлена Лагранжа описывается следующим образом:

f(x)-P_n(x)=\frac{f^{n+1}(\xi)}{(n+1)!}\Pi_{i=1}^{n+1}(x-x_i)

Пример полинома Лагранжа

Для лучшего понимания составления полинома Лагранжа, давайте рассмотрим простенький пример. Мы выберем три точки (-1, 1); (0,0); (1,1).

Начнём с составления базисных полиномов Лагранжа:

l_0(x)=\frac{(x-0)(x-1)}{(-1-0)(-1-1)} = \frac{x(x-1)}{2}l_1(x)=\frac{(x+1)(x-1)}{(0+1)(0-1)} = -x^2+1l_2(x)=\frac{(x+1)(x)}{(1+1)(1-0)} = \frac{x(x+1)}{2}

Таким образом, полином Лагранжа выглядит вот так:

L(x) = 1*\frac{x(x-1)}{2} + 0*(-x^2+1) + 1*\frac{x(x+1)}{2} = x^2

Демонстрация феномена Рунге через полином Лагранжа

Мы хотим аппроксимировать функцию f(x)=\frac{1}{1+25x^2}на

интервале [-1, 1] используя полином Лагранжа.

Используя функцию интерполяции Лагранжа SciPy, мы вычислим полином Лагранжа степени 6, 8, 10, 12.

Здесь мы рассматриваем узлы x_i = \frac{i}{n} для i = 0, 1, ... , n.

Мы построим графики различных полиномов и функции f(x) на интервале [-1, 1]. 

import numpy as np
from scipy.interpolate import lagrange
import matplotlib.pyplot as plt

def f(x):
  return 1/(1+25*x**2)
  
n=100
x_fine=np.linspace(-1, 1, 1000)
y_fine=f(x_fine)
plt.plot(x_fine, y_fine, color='black', label='f(x)') 

for degree in range(6,13,2):
  x_nodes=np.array([-1+(2*i/degree)for i in range(degree+1)]) 
  p_n=lagrange(x_nodes, f(x_nodes))
  y_nodes=p_n(x_fine)
  plt.plot(x_fine, y_nodes, label=f'Полином Лагранжа Степени {degree}')
  
plt.xlabel('x') 
plt.ylabel('f(x)')
plt.legend() 
plt.show()
результат прогонки кода
результат прогонки кода

На графике наглядно продемонстрирован Феномен Рунге - интерполирующий полином сильно колеблется на крайних точках интервала, причем большая степень полинома гарантирует большие колебания.

Феномен Рунге показывает, что переход к более высоким степеням не всегда повышает точность. Почему такое происходит? Давайте обратимся к погрешности Лагранжа.

\frac{f^{n+1}(\xi)}{(n+1)!}\Pi_{i=1}^{n+1}(x-x_i)

Для случая функции Рунге, интерполированной в равноудаленных точках, каждый из двух множителей в погрешности аппроксимации растет до бесконечности с ростом n. Хотя это часто используется для объяснения феномена Рунге, тот факт, что верхняя граница погрешности стремится к бесконечности, не обязательно подразумевает, конечно, что сама погрешность также расходится с n. [4]

Решение проблемы

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

Для натурального числа n узлы Чебышёва на отрезке [−1, 1] задаются формулой: [5]

x_k = \cos(\frac{2i+1}{2n})*\pi, i=1,…,n
import numpy as np
from scipy.interpolate import lagrange
import matplotlib.pyplot as plt

def f(x):
  return 1/(1+25*x**2)
 
def chebyshev_nodes(n): 
  nodes=np.zeros(n+1) 
  for i in range (n+1):
    nodes[i]=np.array(np.cos((2*i+1)*np.pi/(2*(n+1)))) 
  return nodes
  
n=100
x_fine=np.linspace(-1, 1, 1000)
y_fine=f(x_fine)
plt.plot(x_fine, y_fine, color='black', label='f(x)') 
for degree in range(6,13,2):
  x_nodes=np.array(chebyshev_nodes(degree)) 
  p_n=lagrange(x_nodes, f(x_nodes))
  y_nodes=p_n(x_fine)
  plt.plot(x_fine, y_nodes, label=f'Лаг Пол Ст {degree}')
  
plt.xlabel('x') 
plt.ylabel('f(x)')
plt.legend(loc='upper left') 
plt.show()
результат прогонки кода
результат прогонки кода

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

Заключение

Феномен Рунге подчеркивает ограничения интерполяции на равномерно распределенных узлах, показывая увеличение погрешности на крайних точках интервала интерполяции до бесконечности. Но, к нашему счастью, решение проблемы существует, стоит всего лишь обратиться к узлам Чебышёва.

Список Литературы

  1. https://dic.academic.ru/dic.nsf/ruwiki/491639

  2. https://ru.wikipedia.org/wiki/Феномен_Рунге

  3. http://simenergy.ru/mathematical-analysis/basic-data/lagrange-polynomial

  4. http://www.tlu.ee/~tonu/Arvmeet/Runge's%20phenomenon.pdf

  5. https://en.wikipedia.org/wiki/Chebyshev_nodes

Комментарии (28)


  1. DuhaTheBest
    15.08.2024 21:19
    #27169874

    Не должны ли быть "+" вместо "*" в паре мест формулы, которая идет после слов: "Так, например, интерполяционный многочлен в форме Лагранжа, проходящий через три заданных точки будет записываться вот так: [3]"?


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27169878

      Спасибо большое, сейчас исправлю!)


      1. caucAsian
        15.08.2024 21:19
        #27170092

        сначало офигел от формул в тексте а потом что в тёмной теме корректно картинки формул обработались


  1. Refridgerator
    15.08.2024 21:19
    #27170288
    +5

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

    Многочлены Чебышева достойны отдельной статьи, ну или хотя бы можно было пояснить, откуда там косинус взялся.

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


    1. Melirius
      15.08.2024 21:19
      #27171398

      Хмм, там в статье пишут, что есть же, см. заключение о выборе d.


  1. maksim_sitnikov
    15.08.2024 21:19
    #27170470
    +1

    Люблю матешку ловите плюсик в карму


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27171326

      Большое Спасибо:)


  1. Jury_78
    15.08.2024 21:19
    #27171136

    Как частный случай... Интерполировать, в случая колоколообразной функции, можно и функцией (обобщенной) Гаусса. Колебаний не будет.


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27171322

      Здравствуйте! Вы совершенно правы, интерполяция функцией Гаусса возможна, и она поможет избежать колебаний. Однако, всё зависит от конкретной задачи.

      Полиномы Лагранжа и узлы Чебышёва это мощные инструменты в численном анализе, они помогают аппроксимировать функции на широких интервалах, в то время как Гаусса мы используем когда функция похожа на нее - колоколообразная, гладкая, убывающая.

      Спасибо за комментарий!


  1. Berakningsingenjor
    15.08.2024 21:19
    #27171236

    Не знаю, есть ли здесь что-то общее, но наш профессор говорил, что при использовании в методе Рунге-Кутты слишком мелкого шага в решении появляется ложная колебательность.


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27171306
      +1

      Здравствуйте! Феномен Рунге и колебания при методе Рунге-Кутты происходят из-за разных причин в разных контекстах, однако, они оба связаны с численной нестабильностью и с неправильно выбранными параметрами.

      В методе Рунге-Кутты слишком мелкий шаг может усиливать погрешности округления и другие численные эффекты.

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

      Спасибо за комментарий !


  1. diakin
    15.08.2024 21:19
    #27172356
    +1

    А если продолжить функцию по краям подальше, просто нулями например , и аппроксимировать эту функцию, то колебания в нужном диапазоне уйдут?


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27172428

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

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

      Спасибо за Ваш комментарий!


      1. diakin
        15.08.2024 21:19
        #27172624

        Я не спорю, просто не очень понятно.

        полином n-степени, который будет соединять все заданные точки из набора значений

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


        1. kristina_ponomareva Автор
          15.08.2024 21:19
          #27172648

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


  1. wataru
    15.08.2024 21:19
    #27173528

    Что-то такое припоминаю с курса матанализа в университете. Там даже формально доказывалась ограничение на погрешность.


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27173542

      Возможно! Я тоже изначально познакомилась с этой темой на численном анализе в университете


  1. adeshere
    15.08.2024 21:19
    #27173620

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

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

    Поэтому вот эта вот фраза:

    "...который будет соединять все заданные точки из набора значений, полученных опытным путём..."

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

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

    много меньше

    Как вариант, можно построить зависимость погрешности аппроксимации Err от степени N и искать минимум какой-нибудь подходящей в данном случае функции типа Err*N. Который и даст нам оптимальное значение N.

    Без этого самоограничения (погрешность не должна вырождаться в 0!) мы не добьемся ни устойчивости, ни робастности. Если малые изменения в данных влекут большие изменения в результатах, то такая модель может быть интересна лишь как предмет для игры ума (ну или в качестве образца для кунсткамеры). С научной точки зрения (если мы пытаемся описать объективную реальность) она гроша выеденного не стоит. Во всяком случае, в до-квантовой парадигме...


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27173652

      Здравствуйте!

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

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

      Однако, в моей статье я исходила из классического подхода к интерполяции, где требуется точно пройти через все узлы. Это, конечно же, полезно для понимания феномена Рунге. Хотя этот метод может быть не до конца применим для настоящих данных, он важен с теоретической точки зрения. 

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

      Спасибо за комментарий!


      1. adeshere
        15.08.2024 21:19
        #27173676

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

        Так я же не критикую статью (свой плюс она получила). Это скорее мысли по поводу обсуждаемых методов. А вот про Лагранжа было бы интересно узнать, что именно он все-таки имел в виду в оригинале высказывания. Понимаю, что просьба не очень корректная... но ведь это Вы первая начали ;-)


        1. kristina_ponomareva Автор
          15.08.2024 21:19
          #27173694

          Хаха я знаю, что Вы не критикуете !) обязательно вернусь с ответом :)


    1. alexkolzov
      15.08.2024 21:19
      #27175018

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


      1. adeshere
        15.08.2024 21:19
        #27176972

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

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

        Вместо этого попробую пояснить свою идею еще раз другими словами. Речь идет о том, чтобы СРАЗУ же (без мучений с ансамблем) построить ГЛАДКУЮ аппроксимирующую функцию, у которой производные высших порядков равны нулю. Я утверждаю, что отказ от требования точно пройти через все значения данных позволяет построить такую аппроксимацию (гораздо более гладкую, без "заскоков") тривиальным образом. Единственная дополнительная задача, которую при этом придется решить - это

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

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

        критерий близости точек к кривой

        например, это может быть сумма расстояний от точек данных до аппроксимирующей кривой, или сумма квадратов этих расстояний, или что-нибудь еще на наш вкус. Ну и само расстояние можно считать либо строго по вертикали (то есть брать дельта 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 запросто может оказаться совершенно не значимой. За подробностями отсылаю к своей статье на Хабре про ложные корреляции. Еще одну статью на эту же тему (как правильно оценивать значимость корреляций) я сейчас готовлю; когда выйдет - добавлю ссылку на нее в комментариях там же.

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


        1. alexkolzov
          15.08.2024 21:19
          #27178562

          Я вас как раз понял прекрасно, а вот вы меня не особо. Я отнюдь не предлагал вам СТРОИТЬ бесконечное множество интерполяционных полиномов вместо единственного. Не то, чтобы так вообще никогда не делалось, но речь в данном случае вообще не об этом. Моё замечание относилось только к тому, что источник проблем не в требовании выполнения условия интерполяции, то есть точного соответствия значений аппроксимирующей функции значениям аппроксимируемой в заданном множестве точек. Погрешности в данных тут вообще не при чём.

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

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

          Ваше стремление взять "наиболее простую" аппроксимацию, "надёжно" описывающую данные, тоже приводит к нетривиальным проблемам. Почему мы, скажем, считаем параболу "сложнее", чем прямая? (На всякий случай, просто сказать про количество свободных параметров недостаточно). Что "сложнее", экспонента или гармоника? На эту тему есть целые разработанные теории, например, на основе принципа минимальной длины описания, и конкретные практические критерии -- например, критерий Акаике. Но тут всегда возникают дополнительные соображения и допущения о характере данных и выстраиваемой модели, которые нужно ЗНАТЬ, а не опираться на чуйку. Иначе вашему результату грош цена, даже если он случайно окажется правильным.

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

          Ваш следующий тезис опять же ошибочен. Во-первых, никакой "сверхподгонки" тут нет. Например, если выбрать в качестве критерия качества минимизацию суммарных абсолютных отклонений от наблюдаемых данных, то оптимальное решение ТОЧНО пройдёт через определенное подмножество данных. То есть в сущности будет решена именно задача интерполяции по "опорному" набору данных. Такой критерий имеет большую практическую ценность, чем, например, МНК -- как минимум потому, что существенно сокращает объем вычислений, получаемая задача существенно лучше обусловлена, а получаемое решение менее чувствительно к выбросам в данных. Во-вторых -- а с чего вы решили, что а) оптимум в вашей задаче достижим практически (например, градиентным спуском) и что он единственен? Вы вполне можете получить (и почти наверняка будете получать) "оптимальные" в смысле выбранного критерия решения, которые не будут иметь практической ценности. Либо получить несколько возможных "оптимальных", удовлетворяющих вашему критерию останова, результатов, которые будут качественно отличаться друг от друга. И вас моментально спросят -- а почему вы утверждаете, что такой аппроксимацией можно пользоваться в практическом плане? Такие утверждения как раз и требуют знаний конкретной математики, а не "очевидных" практических критериев, которыми вы пользуетесь исходя из собственного удобства.

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


        1. alexkolzov
          15.08.2024 21:19
          #27178572

          P.S. Кстати, к вашему вопросу о внутренней противоречивости в формулировке задачи интерполяции применительно к экспериментальным данным. Никакого противоречия тут нет, а есть просто методичный подход к решению проблемы. Сначала исследуется вопрос приближения в предположении, что значения приближаемой функции в заданных точках известны точно. Это - допущение, оно вводится явным образом. Лагранж сотоварищи об этом в курсе. Такое исследование предполагает не только определение способа конструктивного построения приближения, но, что более важно, определение границ, в которых лежит ошибка приближения в неизвестных точках при разумных допущениях о свойствах интерполируемой функции. Без этого знания ваше приближение бесполезно. После того, как оценки получены, имеет смысл ставить вопрос о том, как ведёт себя ошибка при условии, что значения в опорных точках заданы с известной погрешностью. В том числе получает конструктивную постановку и вопрос, как оптимально выбрать значение в опорной точке из интервала, определяемого погрешностью, так, чтобы минимизировать ожидаемую ошибку приближения. Именно так до сих пор исследуется устойчивость численных методов, поскольку в них данные всегда заданы с погрешностью как минимум по причине конечной точности представления чисел в машинной арифметике.


  1. alexkolzov
    15.08.2024 21:19
    #27174974

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

    Ликбез? Или заметка, к которой планируется делать отсылки?


    1. kristina_ponomareva Автор
      15.08.2024 21:19
      #27175086

      Статья была задумана как часть более крупного исследования, к ней будут делаться отсылки. Stay tuned :)))