2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 13:34 


06/08/13
131
Здравствуйте, уважаемы форумчане!
Во-первых, всех с праздником :-) !!!
Во-вторых, хочу задать пару-тройку вопросов по методу, указанному в теме. Встретил этот метод для поиска одномерного экстремума в книжке В.П. Дьяконова "Справочник по алгоритмам..." за 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 
Заслуженный участник


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

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

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

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

Да.

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

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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:07 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:10 
Заслуженный участник


11/05/08
31745
ex-math в сообщении #1010701 писал(а):
Ясно, что такая парабола (с единичным первым коэффициентом) не годится в общем случае.

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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:15 
Заслуженный участник
Аватара пользователя


11/03/08
6600
Москва
Пропущен коэффициент $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 
Заслуженный участник


11/05/08
31745
Если уж говорить о коэффициентах, то тупо $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 


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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:53 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 14:53 
Заслуженный участник


11/05/08
31745
robot80 в сообщении #1010718 писал(а):
Не совсем правда понятно, что делать если знаменатель равен нулю.

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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение03.05.2015, 15:44 


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

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


12/01/14
1104

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение04.05.2015, 09:45 
Заслуженный участник
Аватара пользователя


11/03/08
6600
Москва
Вообще, метод для "финишной обработки". Предполагается, что более грубым методом (золотого сечения, или просто перебором по точкам) локализовали место, где есть экстремум, и только тогда ищем интерполяцией. А для найденного места средняя точка больше (если ищем максимум) или меньше (для минимума) двух крайних, так что знаменатель ненулевой.
Кстати, программа вроде правильная. По-видимому, первична была программа, а уж потом писалось "обоснование". Жаль, что текст программы на 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 
Аватара пользователя


12/01/14
1104

(Оффтоп)

Евгений Машеров в сообщении #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 
Заслуженный участник
Аватара пользователя


11/03/08
6600
Москва

(Оффтоп)

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

 Профиль  
                  
 
 Re: Квадратичная интерполяция-экстраполяция для экстремума
Сообщение04.05.2015, 14:37 


06/08/13
131
Цитата:
Жаль, что текст программы на 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