2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 13:34 
Здравствуйте, уважаемы форумчане!
Во-первых, всех с праздником :-) !!!
Во-вторых, хочу задать пару-тройку вопросов по методу, указанному в теме. Встретил этот метод для поиска одномерного экстремума в книжке В.П. Дьяконова "Справочник по алгоритмам..." за 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$ вычисляются по формулам, которые тоже непонятно откуда взялись.

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:05 
Дьяконова под рукой нет (хотя где-то в дебрях винчестеров валяется), однако попробую угадать.

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

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

robot80 в сообщении #1010693 писал(а):
(может это опечатка?) $xm = \frac{-b}{2c}$

Да.

robot80 в сообщении #1010693 писал(а):
Числа $b$, $c$ вычисляются по формулам, которые тоже непонятно откуда взялись.

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

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:07 
Аватара пользователя
Ясно, что такая парабола (с единичным первым коэффициентом) не годится в общем случае.
Поэтому либо это алгоритм для специфических задач, либо множественные опечатки в формулах.
В любом случае нужны подробности.

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:10 
ex-math в сообщении #1010701 писал(а):
Ясно, что такая парабола (с единичным первым коэффициентом) не годится в общем случае.

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

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:15 
Аватара пользователя
Пропущен коэффициент $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 симметричны относительно "левого" и "правого" значений функции, тогда как смысл данного коэффициента - выражение сдвига в сторону.

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:30 
Если уж говорить о коэффициентах, то тупо $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)$.

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

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

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:53 
robot80 в сообщении #1010718 писал(а):
Не совсем правда понятно, что делать если знаменатель равен нулю.

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

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

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение04.05.2015, 00:43 
Аватара пользователя

(Оффтоп)

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

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

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

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

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

(Оффтоп)

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

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


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

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение04.05.2015, 11:50 
Аватара пользователя

(Оффтоп)

Евгений Машеров в сообщении #1011079 писал(а):
prof.uskov в сообщении #1011009 писал(а):
robot80 в сообщении #1010718 писал(а):
Похоже, действительно в книге Дьяконова именно в этом методе - несколько опечаток. Я посмотрел издания этой книги 1987 и 1989 годов. К сожалению (или специально :-) ) он их не исправил.

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


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

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

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение04.05.2015, 13:15 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение04.05.2015, 14:37 
Цитата:
Жаль, что текст программы на GW-Basic уже малополезен, в отличие от описания сути метода.
Да уж, текст на старом (настоящем) бейсике по запутанности очень похож на текст на фортране-66 :D. И всё дело в операторе
Код:
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 иетраций.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group