Интерполяция: Лагранж, Ньютон и феномен Рунге

Bilinear interpolation в `torch.nn.functional.grid_sample` - это Лагранж степени 1 в двух измерениях. RIFE интерполирует видеокадры через learned flow + билинейный сэмплинг. Гаусс-Чебышёвская квадратура в scipy использует корни полиномов Чебышёва как узлы. Интерполяция - не академический инструмент. Это алгоритмическое ядро компьютерной графики, численного интегрирования и обработки сигналов.

• **torch.nn.functional.grid_sample**: bilinear/bicubic интерполяция feature maps при spatial transformer, deformable convolution, RIFE video interpolation
• **scipy.interpolate**: CubicSpline, BarycentricInterpolator - формула Лагранжа в барицентрической форме для численной стабильности
• **Гаусс-Чебышёв квадратура**: scipy.integrate.fixed_quad использует корни полиномов Чебышёва как оптимальные узлы интегрирования
• **Компьютерная графика**: кривые Безье - частный случай полиномиальной интерполяции; сплайны для шрифтов TrueType и SVG
• **torch.autograd.gradcheck**: проверяет Jacobian численно через конечные разности - частный случай разделённых разностей 1-го порядка

Предварительные знания

• Погрешности и арифметика с плавающей точкой

Формула Лагранжа

1795 год. Лагранж публикует формулу, которая даёт явный полином через n+1 точку - без решения систем уравнений, без итераций. Идея элегантна: для каждой точки строится базисный полином, который равен 1 в этой точке и 0 во всех остальных. Нейросети используют ровно тот же принцип в билинейной интерполяции при масштабировании feature maps.

**Интерполяционный полином Лагранжа:** L(x) = sum(i=0..n) yi * li(x) где **базисные полиномы:** li(x) = product(j != i) (x - xj) / (xi - xj) **Свойство Кронекера:** li(xj) = 1 если i=j, иначе 0. Отсюда: L(xi) = yi - полином проходит через все точки.

В PyTorch `torch.nn.functional.grid_sample` реализует bilinear interpolation для трансформации feature maps: каждый новый пиксель вычисляется как взвешенная сумма четырёх ближайших - это и есть Лагранж степени 1 в каждом измерении. В RIFE (Real-time Intermediate Flow Estimation) для интерполяции видеокадров используется тот же механизм, только с learned flow fields.

Главный недостаток формулы Лагранжа: при добавлении новой точки нужно пересчитать **все** базисные полиномы. Это $O(n^2)$ работы. Форма Ньютона решает проблему радикально.

Форма Ньютона

Ньютон предложил другую запись того же полинома - через **разделённые разности**. Главное свойство: при добавлении новой точки $x_{n+1}$ вычисляется только один новый коэффициент, а все старые остаются. Это онлайн-обновление - то же, что Adam обновляет только нужные моменты при получении нового градиента.

**Разделённые разности (рекурсивно):** f[xi] = yi f[xi, xi+1] = (f[xi+1] - f[xi]) / (xi+1 - xi) f[xi, ..., xi+k] = (f[xi+1, ..., xi+k] - f[xi, ..., xi+k-1]) / (xi+k - xi) **Полином Ньютона:** N(x) = f[x0] + f[x0,x1]*(x-x0) + f[x0,x1,x2]*(x-x0)(x-x1) + ... Теорема единственности: Лагранж и Ньютон дают **один и тот же** полином.

Схема Горнера ($O(n)$ вместо $O(n^2)$ для вычисления полинома) - тот же принцип, что за быстрым forward pass нейросети: переиспользование промежуточных результатов. `torch.autograd.gradcheck` проверяет численный градиент именно через конечные разности первого порядка - это частный случай разделённых разностей при шаге $h \to 0$.

Узлы Чебышёва

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

**Узлы Чебышёва на [-1, 1]:** xk = cos((2k + 1) * pi / (2(n + 1))), k = 0, 1, ..., n На произвольном [a, b]: xk = (a + b)/2 + (b - a)/2 * cos((2k + 1) * pi / (2(n + 1))) **Почему они оптимальны:** минимизируют max|omega(x)| где omega(x) = product(x - xk) - «множитель ошибки» интерполяции.

Теорема о минимаксе: среди всех полиномов степени n+1 с единичным старшим коэффициентом, полином Чебышёва $T_{n+1}(x)/2^n$ имеет наименьшее отклонение от нуля на [-1, 1]. Его корни - это и есть узлы Чебышёва. Именно поэтому они оптимальны. В `scipy.integrate.fixed_quad` Гаусс-Лежандровы узлы строятся по той же логике - корни ортогональных полиномов минимизируют ошибку.

Феномен Рунге

1901 год. Карл Рунге берёт функцию $f(x) = 1/(1 + 25x^2)$ и показывает парадокс: при увеличении числа равномерных узлов интерполяционный полином **расходится**. Не «точнее медленнее» - а буквально взрывается у краёв отрезка. Это означает: наивное «больше данных = точнее» для полиномиальной интерполяции на равномерной сетке - ложь.

**Феномен Рунге:** для f(x) = 1/(1 + 25x^2) на [-1, 1] полиномиальная интерполяция на равномерной сетке расходится при n -> inf. Максимальная ошибка растёт экспоненциально с числом узлов! **Решение:** узлы Чебышёва (сходимость) или сплайны (полиномы низкой степени на каждом отрезке).

Три способа борьбы с Рунге: 1. **узлы Чебышёва** - полиномиальная интерполяция сходится 2. **сплайны** - кусочные полиномы низкой степени, стандарт для scipy и sklearn preprocessing 3. **тригонометрическая интерполяция** - для периодических функций (FFT). В нейросетях та же логика: локальные операции (свёртки) работают лучше глобальных полиномов большой степени.

Ключевые идеи

• **Формула Лагранжа:** L(x) = sum yi * li(x), явная формула через базисные полиномы с delta-свойством
• **Форма Ньютона:** разделённые разности + схема Горнера; добавление точки = один новый коэффициент
• **Теорема единственности:** Лагранж и Ньютон дают один и тот же полином - только разные записи
• **Узлы Чебышёва:** xk = cos(...), сгущение у краёв, минимизируют max-ошибку по всему отрезку
• **Феномен Рунге:** равномерные узлы + высокая степень = экспоненциально растущие осцилляции у краёв
• **Callback:** bilinear в PyTorch = Лагранж 1-й степени; Чебышёвские узлы - в основе квадратур scipy

Связанные темы

Интерполяция - фундамент для сплайнов и численного интегрирования:

• Погрешности и floating point — Ошибки округления ограничивают практическую степень интерполяционного полинома
• Сплайны — Кусочная интерполяция - решение феномена Рунге: полиномы низкой степени на каждом отрезке
• Ряд Тейлора — Альтернативное полиномиальное приближение: локальное vs глобальная интерполяция

Вопросы для размышления

• Почему для тригонометрических функций (sin, cos) равномерные узлы работают хорошо, а для 1/(1+25x^2) - нет? Что общего у функций, где Рунге не возникает?
• torch.autograd.gradcheck вычисляет конечные разности (f(x+h) - f(x-h)) / 2h. Это разделённая разность 1-го порядка. Почему h нельзя брать слишком маленьким - и как это связано с catastrophic cancellation из урока nm-01?
• Bilinear interpolation в grid_sample - это тензорное произведение двух полиномов Лагранжа 1-й степени. Что произойдёт с качеством при bicubic (степень 3)? Когда степень 3 хуже степени 1?

Связанные уроки

• nm-01 — Ошибки float64 ограничивают точность полиномов высокой степени
• nm-03 — Сплайны - кусочная интерполяция, решение проблемы Рунге
• calc-16-taylor — Ряд Тейлора - тоже полиномиальное приближение, но локальное
• la-15-svd — SVD лежит в основе полиномиальных фитов и регрессии
• nm-04 — Квадратуры Гаусса - интегрирование через узлы Чебышёва
• calc-11-definite