Метод парабол (квадратичная аппроксимация)

Основная идея метода заключается в аппроксимации целевой функции F (x) алгебраическим полиномом 2 степени (квадратичной параболой) вида P ₂(x) = C ₀ + C ₁ x + C ₂ x ², где C ₀, C ₁, C ₂ - постоянные коэффициенты. Поскольку их число равно трем, то в общем случае для однозначного построения параболы необходимо задание трех точек на ней. Обычно – это крайние точки доверительного отрезка [ a,b ] и внутренняя его точка с (a < c < b)(рис.10.14). Метод имеет много вариантов.

Рис.10.14

Система уравнений, описывающих прохождение аппроксимирующей параболы P ₂(x) через точки (a, F (a)), (b, F (b)), (c, F (c)) c попарно различными значениями a, b, c (рис.10.14) имеет вид:

C ₀ + C ₁ a + C ₂ a ² = F (a);

C ₀ + C ₁ c + C ₂ c ² = F (c);

C ₀ + C ₁ b + C ₂ b ² = F (b).

Точка x_экстр локального экстремума параболы (при C ₂ > 0 - минимум, при C ₂<0- максимум) достигается при условии P¢ ₂(x_экстр) = 2C₂ x_экстр + C ₁ = 0. На рис.5.2 рассмотрен случай C ₂>0, при котором достигается минимум (x_{mi n}).

Из приведенных зависимостей величину x_экстр можно представить, например, следующим образом:

(10.4 а)

(10.4 б)

Метод парабол хорошо аппроксимирует дифференцируемую функцию F (x) в достаточной близости от точки экстремума х=c по следующей причине. Разложение функции в окрестности данной точки по формуле Тейлора 2-го порядка имеет вид:

F (x) = F (с) + F¢ (x)(х-с)+(1/2!) F¢¢ (x)(х-с)² + o ((х-с)²),

где o ((х-с)²) – величина малого порядка. Линейное слагаемое F¢ (x)(х-с)в данном разложении близко к нулю и основной вклад вносит квадратичная часть.

Однако в общем случае существует ряд проблем, затрудняющих практическое использование метода парабол. Основные из них в заключаются в следующем:

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

2. Если целевая функция F (x) не является дифференцируемой в точке экстремума х=c, то приведенное выше разложение по формуле Тейлора 2-го порядка не справедливо, поскольку не выполнены условия Теоремы Тейлора. При этом обычный метод парабол дает достаточно медленную сходимость и необходимо использовать дополнительные приемы для её ускорения. Отсутствие дифференцируемости обычно связано с использование модуля в целевой функции.

3. Если точки (a,F (a)), (b,F (b)),(c,F (c)) лежат на одной прямой (например, у функции, график которой имеет вид ломаной), то старший коэффициент параболы C ₂ теоретически равен нулю и величина x_экстр стремится к бесконечности (положительной или отрицательной). Следовательно, использовать вышеприведенные формулы невозможно.

4. При использовании метода парабол на доверительном отрезке [ a, b ] зачастую возникают ситуации, когда точки с,x_min в течение целого ряда выполняемых подряд итераций группируются у точки a либо у точки b, причем F (a) > F (c) >F (x_min) (рис.10.15) либо, соответственно, F (b) >F (c) > F (x_min). В этом случае сокращается относительно малая доля доверительного отрезка ([ a, с ] – на рис.10.15 - либо [ с, b ])и последовательность точек x_min медленно приближается к искомому минимуму функции F (х). Основная причина данного явления заключается в том, что одна из точек, по которым производится аппроксимация, довольно далеко удалена от искомого минимума – например, точка b на рис.10.15. Это вносит значительную погрешность в процесс аппроксимации исходной функции полиномом P ₂(x) и, соответственно, замедляет сходимость.

Рис.10.15

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

10.7.1. Метод парабол с использованием симметричной точки

Одним из предложений по ускорению сходимости метода парабол является вариант метода с использованием симметричной точки. У него, начиная со второй итерации по найденной при помощи квадратичной аппроксимации точке x_min (которая принимается в качестве новой промежуточной точки: x ₂ = x_min) из имеющихся точек a,с,b выбирается ближайшая, а третья рассчитывается симметрично ей относительно x_min. На рис.10.16 показан случай, когда ближайшей к х_min является точка с и х_min < с.

Рис. 10.16

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

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

10.7.2. Универсальный алгоритм метода парабол

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

Исходные данные:

1) [ a,b ] – границы начального доверительного отрезка,

2) с - промежуточная точка, a<c<b,

3) F (a) ,F (c) ,F (b) - значения F (x)в точках a,b,с,

4) e - точность.

Выходные данные:

1)[ a,b ] – новые сокращенные границы исходного доверительного отрезка, b-a< e,

Начало цикла по условию (b-a > e).

Шаг 1. Проверка близости точки с к крайним a, b и соответствующий выбор новой пробной точки (отрыв точки с от краев доверительного отрезка).

Если (с-a)/(b-a) < 0,1; то x_min:= с + (b-с)/4,переход на Шаг 7.

Если (b-с)/(b-a) < 0,1; то x_min:= с - (с-а)/4,переход на Шаг 7.

Шаг 2. Расчет величины старшего коэффициента C ₂ по формуле (10.4 б). В зависимости от выполнения условия C ₂ = 0 переход на Шаг 3 либо 4.

Шаг 3. C ₂=0. Аппроксимирующая парабола вырождается в прямую линию, при этом целевая функция может не совпадать с данной прямой на всем отрезке [ a,b ]. В этом случае обычные формулы не применимы.

При F (a) < F (b): x_min:=(a+с)/2, b:=c; иначе: x_min: = (b+c)/2, а: =c. F_min = F (x_min).Переход на конец цикла.

Шаг 4. C ₂ ¹ 0. Аппроксимирующая кривая является параболой. Расчет величины x_экстр по формуле (10.4 а). В зависимости от выполнения условий C ₂< 0, C ₂ > 0 переход на Шаг 5 либо 6.

Шаг 5. C ₂<0. Ветви параболы направлены вниз – в точке x_min достигается локальный максимум.

При x_экстр < (а+b)/2: x_min:= (b+c)/2, а:=c; иначе: x_min:= (a+ с)/2, b:=c. F_min = F (x_min).Переход на конец цикла.

Шаг 6. C ₂>0. Ветви направлены вверх, в точке x_экстр достигается локальный минимум.

Проверка нештатных ситуаций и соответствующие действия.

1. Уход точки x_экстр с отрезка [ a,b ]:

а) при x_экстр £ а: { x_min:= (a+с)/2; b:=c; F_min = F (x_min);переход на конец цикла};

б) при x_экстр ³ b: { x_min:= (b+c)/2; a:=c; F_min = F (x_min);переход на конец цикла}.

2. Попадание точки x_экстр в промежуточную точку c (данная ситуация возникает, например, уже на втором шаге, если F (x) сама является квадратичной параболой). Если ½ x_экстр - c ½ < e/2, то:

а) при x_экстр < c, x_экстр» c: x _min = c – e/2.

б) при x_экстр > c, x_экстр» c: x _min = c + e/2.

x_min:= x_экстр. (присваивание будет выполнено, если не выполняются условия 1 и 2).

Шаг 7. Расчет значения функции в точке x_min: F_min = F (x_min).

Сокращение доверительного интервала.

Если x_min < c, то при F_min<F (c): b: =c, c: =x_min; иначе: а: =x_min.

Если x_min ³ c, то при F_min<F (c): а: =c, c: =x_min; иначе: b: =x_min.

Конец цикла.

Завершение поиска.

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

Пример 1. Найти минимум функции F (х) = 2х ³- 3 х ² на интервале [0,2; 2]при помощи универсального алгоритма метода парабол с заданной внутренней точкой интервала с = 0,4при точностиe = 0,5.

Решение. При последовательном выполнении шагов переходы к ним не оговариваются.

Шаг 0. Предварительные действия. Рассчитываем значения функции в точках a,b,c: F (a) = -0,10; F (с) = -0,35; F (b) = 4.

Цикл по условию ( b-a > e).

Итерация 1. Шаг 1. Условия (с-a)/(b-a) < 0,1 и (b-с)/(b-a) < 0,1не выполняются.

Шаг 2. Расчет C ₂. C ₂ = [(F (b) -F (a))/(b-a) - (F (c)- F (a))/(c-a)] / (b-c) = [(4)/(1,8) - (-0,25)/ (0,2)]/ (1,6) = 2,2. Переход на Шаг 4.

Шаг 4. x_экстр = 0,58. Так как С ₂>0,то переход на Шаг 6.

Шаг 6. Точка x_экстр не выходит за пределы отрезка [ a,b ]и не близка к средней точке c, поэтому x_min:= x_экстр.

Шаг 7. Расчет значения функции в точке x_min: F_min = F (x_min)= -0,62. Сокращение доверительного интервала. Так как x_экстр ³ c и F_min < F (c), то а: =c= 0,4; c: =x_min= 0,58.

Итерация 2. Шаг 1. Условия не выполняются.

Шаг 2. C ₂ =2,96 > 0. Переход на Шаг 4.

Шаг 4. x_экстр = 0,74. Переход на Шаг 6.

Шаг 6. Условия 1 и 2 не выполняются, x_min: = x_экстр.

Шаг 7. F_min = F (x_min)= -0,83.

Так как x_min ³ c и F_min< F (c), то а: =c= 0,58; c: =x_min= 0,74.

Итерация 3. Шаг 1. Условия не выполняются.

Шаг 2. C ₂ = 3,66 > 0. Переход на Шаг 4.

Шаг 4. x_экстр = 0,84. Переход на Шаг 6.

Шаг 6. Условия 1 и 2 не выполняются, x_min:= x_экстр.

Шаг 7. F_min = F (x_min) = -0,93. Так как x_min ³ c и F_min < F (c), то а: =c= 0,74; c: =x_min= 0,84.

Итерация 4. Шаг 1. Так как (с-a)/(b-a) = (0,1)/(1,16) < 0,1, то: x_min: = с + 0,25 × (b-с)/2 = 1,13.Переход на Шаг 7.

Шаг 7. F_min = F (x_min)= -0,94. Так как x_min ³ c и F_min < F (c), то а: =c= 0,84; c: =x_min= 1,13.

Итерация 5. Шаг 1. Условия не выполняются.

Шаг 2. C ₂ = 4,95 > 0. Переход на Шаг 4.

Шаг 4. x_экстр = 0,99. Переход на Шаг 6.

Шаг 6. Условия 1 и 2 не выполняются, x_min:= x_экстр.

Шаг 7. F_min = F (x_min) = -0,9998. Так как x_min< c и F_min<F (c), то b: =c= 1,13; c: =x_min= 0,99.

Поскольку (b-а) = 0,29 < e, то цикл завершается.

Ответ: Выполнено 5 итераций, вычислено 8 значений функции, найден доверительный интервал [0,84;1,13].

Рассмотренный вариант метода парабол при масштабах порядка 10² – 10³ и выше в среднем работает быстрее метода Фибоначчи – наиболее быстрого регулярного метода. Поскольку сам он не является регулярным, для него в общем случае не может быть получено оценок скорости сходимости без наложения дополнительных условий на характер целевой функции.

10.7.3. Аппроксимация по лучшим точкам

Исследования на широком наборе однопараметрических целевых функций показали, что реально ускорить среднюю сходимость метода парабол по сравнению с универсальным алгоритмом (особенно – при больших масштабах задач) можно за счет перехода от обязательной аппроксимации по точкам { a, с, b }к аппроксимации по трем точкам { x ₁, x ₂, x ₃} из набора { a, с, x_min, b }, у которых наименьшие значения целевой функции.

Практически для унимодальной функции выбор осуществляется следующим образом. Если F (a) < F (b), то: x ₁: =а, x ₂: =с, x ₃:= x_min, иначе: x ₁: = с, x ₂: =x_min, x ₃:= b. Значения x ₁, x ₂, x ₃могут располагаться не по возрастанию. При таком выборе точек аппроксимации парабола P ₂(x) более точно приближает исходную функцию F (х)и сходимость метода в среднем возрастает. Данная модификация метода парабол названа аппроксимацией по лучшим точкам.

Принципы построения алгоритма те же, что и для универсального метода парабол - необходимо учитывать возможность приближения точки с к крайним точкам отрезка a и b, возможность C ₂ = 0, раздельный анализ случаев C ₂ < 0 и C ₂ > 0, возможность выхода точки x_экстр за границы доверительного отрезка и попадание ее в точку с.

Пример 2. Найти минимум функции F(х) =2 х ³- 3 х ² на интервале [0,2; 2]по методу парабол аппроксимацией по лучшим точкам при заданной внутренней точке интервала с = 0,4и точностиe = 0,5.

Решение.

Шаг 0. Предварительные действия. Начальное определение лучших точек: x ₁: = a, x ₂: = b, x ₃: = c. Расчет значений функции в точках a, b, c: F (a) = -0,10; F (с) = -0,35; F (b) = 4.

Цикл по условию ( b-a > e).

Итерация 1. C ₂ = 2,2 > 0. x_экстр = 0,58. F (x_экстр) = -0,62.

Выбор аппроксимирующих точек. Так как F (a) < F (b) и с < x_экстр, то x ₁: = a, x ₂: = с, x ₃: = x_экстр.

Анализ и сокращение доверительного интервала. Так как x_экстр > с и F (x_экстр) < F (с), то a: = c = 0,4; c: = x_экстр = 0,58.

Итерация 2. C ₂ = - 0,64. x_экстр = 0,49. F (x_экстр)= -0,49.

Выбор аппроксимирующих точек. Так как F (a) < F (b) и с > x_экстр, то x ₁: =a, x ₂: = x_экстр, x₃: = с.

Анализ и сокращение доверительного интервала. Так как x_экстр < с и F (x_экстр) > F (с), то a: = x_экстр = 0,49.

Итерация 3. Так как (с – а)/(b – а) < 0,09/1,51»0,060 < 0,1, то x_экстр = c + 0.25× (b-c) = 0,94. F (x_экстр) = -0,988.

Выбор аппроксимирующих точек. Т.к. F (a) < F (b) и с < x_экстр, то x ₁: = a, x ₂: = с, x ₃: = x_экстр.

Анализ и сокращение доверительного интервала. Так как x_экстр > с и F (x_экстр) < F (с), то a: = c = 0,58; c: = x_экстр = 0,94.

Итерация 4. C ₂ = 1,02. x_экстр = 1,27. F (x_экстр)= -0,75.

Выбор аппроксимирующих точек. Т.к. F (a)< F (b) и с < x_экстр, то x ₁ =a, x ₂ =с, x ₃ = x_экстр.

Анализ и сокращение доверительного интервала. Так как x_экстр > с и F (x_экстр) > F (с), то b: = x_экстр = 1,27.

Итерация 5. C ₂ = 2,57. x_экстр = 0,96. F (x_экстр)=-0,995.

Выбор аппроксимирующих точек. Так как F (a) > F (b) и с < x_экстр, то x ₁: = c, x ₂: = x_экстр, x ₃: =b.

Анализ и сокращение доверительного интервала. Так как x_экстр > с и F (x_экстр) < F (с), то a: = c = 0,94; c: = x_экстр = 0,96.

Поскольку (b-а) = 0,33 < e, то цикл завершается.

Ответ: Выполнено 5 итераций, вычислено 8 значений функции, найден доверительный интервал [0,94;1,27].

Замечание. При малых масштабах задач (Примеры 1,2) сравнение скорости сходимости различных вариантов метода парабол не достаточно показательно.

Тестовые проверки подтверждают в среднем более быструю и стабильную сходимость данного варианта метода парабол.

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

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

Вопросы для проверки знаний.

1. Какова основная идея метода парабол?

2. Почему по методу парабол необходимо задание трех точек аппроксимации?

3. Почему метод парабол хорошо аппроксимирует дифференцируемые целевые функции в достаточной близости от точки экстремума?

4. Каковы основные проблемы, затрудняющие практическое использование метода парабол?

5. В чем заключается идея метода парабол с использованием симметричной точки и в чем его недостатки?

6. Какие общие недостатки метода парабол устраняются при использовании универсального алгоритма данного метода?

7. В чем заключается идея метода парабол с аппроксимацией по лучшим точкам?

8. Каковы основные преимущества и недостатки метода парабол?