Математика / Начала анализа

Параболическая интерполяция для поиска минимума функции

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

Опубликовано: 22 октября 2026 г.Обновлено: 22 октября 2026 г.

Оптимизация и исследование операций Численные методы Математический анализ Страницы с задачами и решениями Есть историческая справка

Формула

A=\frac{(f_3-f_2)/(x_3-x_2)-(f_2-f_1)/(x_2-x_1)}{x_3-x_1},\quad B=\frac{f_2-f_1}{x_2-x_1}-A(x_1+x_2),\quad x_p=-\frac{B}{2A}

Схема Парабола по трём значениям

Вершина модели становится ответом только после проверки исходной функции.

Обозначения

$x_1,x_2,x_3$: три различные упорядоченные точки, единица аргумента
$f_i$: значение функции в точке x_i, единица функции
$A$: квадратичный коэффициент интерполянта, единица функции / квадрат единицы аргумента
$B$: линейный коэффициент интерполянта, единица функции / единица аргумента
$x_p$: вершина интерполяционной параболы, единица аргумента

Условия применения

Точки различны и упорядочены, значения относятся к одной функции. Для использования вершины как кандидата минимума требуется A > 0. Обычно поддерживают скобку x₁ < x₂ < x₃ с f₂ ниже обеих крайних высот и принимают лишь внутренний, достаточно удалённый от прежних точек кандидат.

Ограничения

При A = 0 вершина не определена; малый A делает её крайне чувствительной к ошибкам высот. При A < 0 вершина соответствует максимуму модели. Даже выпуклая парабола не доказывает глобальной выпуклости исходной функции. Незащищённая повторная интерполяция может выйти за область определения или застрять.

Подробное объяснение

Квадратичный полином q(x) = Ax²+Bx+C единственным образом определяется тремя различными узлами. Разность соседних секущих определяет A, после чего из любой секущей восстанавливается B. Постоянный член C для положения вершины не нужен. Поэтому в рабочей формуле можно не вычислять его вовсе.

При A > 0 производная модели равна 2Ax+B и обращается в нуль в xₚ = −B/(2A). Эта точка минимизирует интерполянт, но ещё не исходную функцию. Следующий обязательный шаг — вычислить настоящую f(xₚ) и сравнить её с уже известными высотами.

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

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

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

Как пользоваться формулой

Расположите три различные точки по возрастанию аргумента и проверьте, что средняя высота ниже крайних для скобки минимума.
Найдите две соседние секущие, вычислите A по разности их наклонов и проверьте положительную кривизну модели.
Восстановите линейный коэффициент B и рассчитайте вершину −B/(2A); отклоните внешний или почти повторный кандидат.
Вычислите исходную функцию в новой точке, обновите скобку и при неудачной модели выполните безопасное сокращение.

Историческая справка

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

Историческая линия формулы

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

Пример

Даны значения функции в трёх безразмерных точках: x₁ = 0, f₁ = 4; x₂ = 1, f₂ = 1; x₃ = 3, f₃ = 1. Наклон первой секущей равен (1−4)/(1−0) = −3, второй — (1−1)/(3−1) = 0. Тогда A = (0−(−3))/(3−0) = 1, B = −3−1·(0+1) = −4. Вершина модели xₚ = −(−4)/(2·1) = 2. Если исходная функция действительно f(x) = (x−2)², подстановка даёт f(2) = 0, точный минимум. Три исходные высоты точно принадлежат этому квадрату. Для неизвестной функции ответ x = 2 был бы только кандидатом до нового измерения. Пример показывает, зачем разделять интерполяционную модель и проверку реального значения.

Частая ошибка

Не принимайте вершину вогнутой параболы за минимум. Не делите на почти нулевой A без проверки чувствительности. Не считайте три точки доказательством квадратичности функции. Не заменяйте реальный вызов f(xₚ) значением модели: интерполянт гарантированно совпадает с функцией только в исходных узлах.

Практика

Задачи с решением

Точный квадрат

Условие. Для f(x) = (x−1)²+2 возьмите узлы 0, 1, 2. Найдите вершину модели.

Решение. Высоты равны 3, 2, 3; наклоны −1 и 1. A = 1, B = −2, поэтому xₚ = 1 и f(1) = 2.

Ответ. xₚ = 1, значение 2.

Линейные данные

Условие. Высоты в точках 0, 1, 2 равны 1, 3, 5. Можно ли найти конечную вершину?

Решение. Обе секущие имеют наклон 2. A = 0, поэтому полином линейный и деление на 2A невозможно. Требуется другой шаг.

Ответ. Нет: A = 0.

Дополнительные источники

https://heath.cs.illinois.edu/iem/optimization/SuccessiveParabolic/
https://www.cs.cornell.edu/courses/cs4220/2014sp/CVLBook/chap8.pdf

Связанные формулы

Математика

Метод золотого сечения: сужение интервала минимума

$\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0$

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

Математика

Тернарный поиск минимума непрерывной унимодальной функции

$u=a+\frac{b-a}{3},\quad v=b-\frac{b-a}{3},\quad [a,b]\leftarrow\begin{cases}\left[u,b\right],&f(u)>f(v),\\\left[a,v\right],&f(u)\le f(v),\end{cases}\quad L_n=(2/3)^nL_0$

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

Математика

Градиентный спуск с постоянным шагом: условие убывания

$x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$

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

Математика

Правило Армихо: обратный поиск длины шага спуска

$f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$

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