Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции по матем. модел и оптим. технолог процессов.doc
Скачиваний:
8
Добавлен:
01.07.2025
Размер:
4 Мб
Скачать
☆

Лекция №34 Методы квадратичной интерполяции и полиномиальной аппроксимации

Методы квадратичной интерполяции

Метод квадратичной интерполяции используют для поиска точки минимума непрерывной функции f(x), определенной на множестве . Из области допустимых значений D выделяется подмножество D1, в котором расположена точка экстремума , и аппроксимируется функция f(x) (х принадлежит подмножеству D1) некоторой сильно выпуклой функцией вида:

.

Далее аналитическим методом находится точка минимума x4 функции из необходимого условия существования экстремума

.

Отсюда

, (34.1)

которая тем ближе к точке , чем ближе функция к на подмножестве D1.

Для нахождения множества D и коэффициентов a, b, c функции необходимо подобрать вблизи предполагаемого минимума x4 точки x1, x2, x3, такие, что крайние ординаты больше средней ординаты, т.е. при x1<x2<x3 было справедливо неравенство:

.

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

Далее находятся неизвестные коэффициенты по методу Крамера:

(34.2)

где

С учетом соотношений (34.1) и (34.2) получается выражение для определения точки x4 непосредственно через xi, fi,(i=1,2,3):

(34.3)

Следует заметить, что в (34.3) знаменатель x6 должен быть отличен от нуля. Если точки x1, x2, x3, близки друг к другу, то это условие нарушается.

Метод кубической аппроксимации

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

Предположим, что функция f(x) выпукла и непрерывно дифференцируема на отрезке [a,b], f'(a)<0, f'(b)>0. Аппроксимируем функцию многочлена 3-й степени:

,

где коэффициенты c0, c1, c2, c3 определяются из условий:

,

,

,

.

Найдем точку

Легко проверить, что

,

где

;

,

.

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

Лекция №35 Метод тяжелого шарика

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

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

Двухшаговая итерационная процедура поиска глобального минимума методом "тяжелого шарика" имеет следующий вид

, (35.1)

где k – номер итерации (k=1,2,...,). h, β параметры, которые подбираются в процессе решения задачи.

Скорость приближения {xk} к зависит не только от "крутизны" функции в точке xk, характеризуемой величиной , но и от "инерции" последовательности {xk}, которая пропорциональна слагаемому. При попадании точки в локальный минимум производная , но инерционная составляющая при этом должна отличатся от нуля, поэтому

и последовательность {xk} продолжит движение к . Подобная особенность итерационного метода "тяжелого шарика" позволяет "проскакивать" по инерции мелкие, неглубокие локальные минимумы и останавливаться в точках глобального экстремума. Окончание процесса итерации

.

Алгоритм поиска минимума методом тяжелого шарика:

1. Вводим два приближения х0 и х1, вычисляем значения критерия

и .

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

3. Вычисляем предполагаемую точку минимума х по формуле

.

4. Вычисляем . Проверяем условие улучшаемости ?

"Да" – проверяем условие , если выполняется, то переходим на п.6, иначе − на п.5; нет – за точку минимума принимаем точку х1, то есть х = х1 и переходим на п.6, либо можно изменить параметры h или β и продолжить поиск минимума в окрестности точки х1.

5. Переопределяем точки х0 = х1; х1 = х и переходим на п.2.

6. Печать "х*= ", х, оптимального значения критерия , для контроля правильности полученных данных – .

Блок-схема рассмотренного метода приведена на рис.35.1(а,б). В алгоритме предусмотрен выбор параметров в процессе решения задачи на ЭВМ. При величине шага меньшей заданной точности выполняется переход на п.6. Критерий цели и заданы функциями пользователя f и pr соответственно.

Рис.35.1а. Блок-схема поиска минимума методом тяжелого шарика

Рис.35.1б. Продолжение блок-схемы поиска минимума

методом тяжелого шарика