Квадратичная интерполяция-экстраполяция для экстремума

[robot80]

Здравствуйте, уважаемы форумчане!
Во-первых, всех с праздником !!!
Во-вторых, хочу задать пару-тройку вопросов по методу, указанному в теме. Встретил этот метод для поиска одномерного экстремума в книжке В.П. Дьяконова "Справочник по алгоритмам..." за 1989 г. Больше ни в одном из учебников по методам оптимизации я этот алгоритм не встречал (вроде... ). В итернете этот алгоритм есть, но является по сути перепечаткой книги Дьяконова В. П.
Вопрос 1. Может кто-нибудь где-нибудь встречал этот алгоритм? Или это алгоритм, разработанный, Дьяконовым В. П.?
Вопрос 2. В алгоритме предлагается по трём точкам $x_0 = x_1 -h$, $x_1$, $x_2 = x_1 +h$ строить параболу вида $y = x^2 + bx +c$ (не понятно, как ищут эти два коэффициента, ведь точек три), а затем ищут положение её экстремума по формуле (может это опечатка?) $xm = \frac{-b}{2c}$. Числа $b$, $c$ вычисляются по формулам, которые тоже непонятно откуда взялись.

[ewert]

Дьяконова под рукой нет (хотя где-то в дебрях винчестеров валяется), однако попробую угадать.

robot80 в сообщении #1010693 писал(а):

параболу вида $y = x^2 + bx +c$ (не понятно, как ищут эти два коэффициента, ведь точек три)

Скорее всего, разделили на старший коэффициент.

robot80 в сообщении #1010693 писал(а):

(может это опечатка?) $xm = \frac{-b}{2c}$

Да.

robot80 в сообщении #1010693 писал(а):

Числа $b$, $c$ вычисляются по формулам, которые тоже непонятно откуда взялись.

Формул не знаю, но это не может быть ничего, кроме результата преобразования стандартного интерполяционного многочлена (по Лагранжу, но скорее всего -- по Ньютону, т.к. в этом случае и преобразовывать-то ничего практически не надо).

[ex-math]

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

[ewert]

ex-math в сообщении #1010701 писал(а):

Ясно, что такая парабола (с единичным первым коэффициентом) не годится в общем случае.

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

[Евгений Машеров]

Пропущен коэффициент $a$ при $x^2$
Без этого по трём точкам параболу не провести. Кроме того, положение экстремума от значения $c$ просто не зависит.
По-видимому, автор напутал при переносе. Предположу, что в (неизвестном мне) оригинале было что-то наподобие $y=cx^2+bx+a$ и экстремум параболы был в точке $x_{ext}=-\frac b {2c}$, появляющейся у него же далее.
Сами коэффициенты в этом случае проще найти, приняв $h=1$ и $x=0$ (полученное положение экстремума затем домножить на h и прибавить исходный x)
$y(0)=a$
$y(1)=c+b+a$
$y(-1)=c-b+a$
$b=(y(1)-y(-1))/2$
$c=(y(1)+y(-1)-2y(0))/2$
Приведенные же в книге выражения, даже без тщательной проверки явно неверны. Оба (несовпадающие!) выражения для b симметричны относительно "левого" и "правого" значений функции, тогда как смысл данного коэффициента - выражение сдвига в сторону.

[ewert]

Если уж говорить о коэффициентах, то тупо $y(x)=f(x_1)+\frac{f(x_2)-f(x_1)}h(x-x_1)+\frac{f(x_0)-2f(x_1)+f(x_2)}{2h^2}(x-x_1)(x-x_2)$, т.е. $a=\frac{f(x_0)-2f(x_1)+f(x_2)}{2h^2}$, $b=\frac{f(x_2)-f(x_1)}h-a(x_1+x_2)$, а $c$ никому и не нужен. Ну или можно симметризовать формулу, усреднив её с $y(x)=f(x_1)+\frac{f(x_1)-f(x_0)}h(x-x_1)+\frac{f(x_0)-2f(x_1)+f(x_2)}{2h^2}(x-x_1)(x-x_0)$.

[robot80]

Спасибо за отзывы. Похоже, действительно в книге Дьяконова именно в этом методе - несколько опечаток. Я посмотрел издания этой книги 1987 и 1989 годов. К сожалению (или специально ) он их не исправил. Получается, что это какая-то упрощённая версия метода Пауэлла.
Не совсем правда понятно, что делать если знаменатель равен нулю.

[Евгений Машеров]

Если знаменатель равен нулю,то три точки лежат на одной прямой. То есть либо игреки равны, либо максимум (или минимум) на границе отрезка $(x-h, x+h)$
В обоих случаях квадратическая интерполяция на отрезке для поиска экстремума бессмысленна. Его на отрезке нет.

[ewert]

robot80 в сообщении #1010718 писал(а):

Не совсем правда понятно, что делать если знаменатель равен нулю.

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

[robot80]

В учебниках, где изложен метод Пауэлла для поиска минимума функции в случае равенства нулю знаменателя (скажем, шаг случайно взят такой, что значения функции во всех трёх точках занулились) выбирают в качестве центральной точку с наименьшим значением функции из трёх. Алгоритм же в книге Дьконова ищет точку экстремума и поэтому и не ясно левую или правую границу отрезка $[x_1 -h; x_1 +h]$ брать.

[prof.uskov]

(Оффтоп)

robot80 в сообщении #1010718 писал(а):

Похоже, действительно в книге Дьяконова именно в этом методе - несколько опечаток. Я посмотрел издания этой книги 1987 и 1989 годов. К сожалению (или специально ) он их не исправил.

Так получилось, что я знаком с Владимиром Павловичем лично, он был у меня оппонентом по докторской...
Просто оцените объем, четыре вкладки на ozone :)
http://www.ozon.ru/person/249401/#detf

[Евгений Машеров]

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

-- 04 май 2015, 10:30 --

prof.uskov в сообщении #1011009 писал(а):

(Оффтоп)

robot80 в сообщении #1010718 писал(а):

Похоже, действительно в книге Дьяконова именно в этом методе - несколько опечаток. Я посмотрел издания этой книги 1987 и 1989 годов. К сожалению (или специально ) он их не исправил.

Так получилось, что я знаком с Владимиром Павловичем лично, он был у меня оппонентом по докторской...
Просто оцените объем, четыре вкладки на ozone :)
http://www.ozon.ru/person/249401/#detf

Да уж, прямо какой-то Кальдерон де ла Барка, "Феникс Испании", писавший пьесу в три дня...
Хотя тут скорее напрашивается директор советского НИИ Юрий Стручков, лауреат Шнобелевской премии, написавший за десятилетие 948 статей (в среднем 3.9 дня на статью).

[prof.uskov]

(Оффтоп)

Евгений Машеров в сообщении #1011079 писал(а):

prof.uskov в сообщении #1011009 писал(а):

robot80 в сообщении #1010718 писал(а):

Похоже, действительно в книге Дьяконова именно в этом методе - несколько опечаток. Я посмотрел издания этой книги 1987 и 1989 годов. К сожалению (или специально ) он их не исправил.

Так получилось, что я знаком с Владимиром Павловичем лично, он был у меня оппонентом по докторской...
Просто оцените объем, четыре вкладки на ozone :)
http://www.ozon.ru/person/249401/#detf

Да уж, прямо какой-то Кальдерон де ла Барка, "Феникс Испании", писавший пьесу в три дня...
Хотя тут скорее напрашивается директор советского НИИ Юрий Стручков, лауреат Шнобелевской премии, написавший за десятилетие 948 статей (в среднем 3.9 дня на статью).

Но Дьяконов не директор и даже последние годы не завкафедрой, т.е. сотрудников, которых можно заставить пахать на себя, у него нет. Я тоже у него спрашивал секрет, но он мне не сказал... :)

[Евгений Машеров]

(Оффтоп)

Ну, или "чудо трудолюбия" или "организатор и вдохновитель", раздающий студентам/аспирантам "уроки" и затем делящийся полученным авторским гонораром. Что, кстати,хорошо объясняет странное описание при работоспособной программе. Программу отладили, а описание (в курсовой?) небрежно переписали, хорошо, что ещё про "катушки индуктивности, намотанные шёлковыми нитками и с сердечником из осины" или "смазка подшипников производится духами Шанель №5" не прибавили.

[robot80]

Цитата:

Жаль, что текст программы на GW-Basic уже малополезен, в отличие от описания сути метода.

Да уж, текст на старом (настоящем) бейсике по запутанности очень похож на текст на фортране-66 . И всё дело в операторе

goto

Что касается самой программы, то алгоритм в принципе рабочий (мы со студентами на scilab'e практику по численным методам реализуем), но, если использовать как основной, то требует доработки, которая переведёт его в стандартный метод Пауэлла. Для "финишной обработки", как указал Евгений Машеров, можно наверно его применять, если целевая функция сложная и её вычисление отнимает много времени. Например, для функции $y = 0.5x^4 - 4x^3 +11x^2 -12x +4$ метод золотого сечения на интервале $[0.5; 1.5]$ с точностью $10^{-7}$ даёт ответ $x=1.000000$ за 57 итераций, а связка золотое сечение с точностью $10^{-4}$ и квадратичная интерполяция с точностью $10^{-7}$ и шагом $0.1$ даёт менее точный ответ $1.0000087$ за $18 +5 = 23$ итерации. А если сразу применить метод квадратичной интерполяции с точностью $10^{-7}$ и шагом $ 0.1$, то из точки 0.5 он уйдёт в точку $x= 1$ за 6 итераций, а из точки 1,5 уйдёт в точку $x=3$ за те же 6 иетраций.