Методы компьютерных вычислений и их приложение к физическим задачам

|xk+1 – xk| ≤ ξ . (1)

Данный метод является одним из самых медленных для поиска минимума. Основное достоинство данного алгоритма – возможность использования в программах управления экспериментальными исследованиями, когда значения функции f(x) последовательно измеряются с шагом h ≥ hmin.

<

b>Метод золотого сечения.

Пусть f(x) задана и кусочно-непрерывна на [xL, xR], и имеет на этом отрезке только один локальный минимум. Золотое сечение, о котором упоминал ещё Евклид, состоит в разбиении интервала [xL, xR] точкой x1 на две части таким образом, что отношение длины всего отрезка к его большей части равно отношению большей части к меньшей:

. (2)

Таким образом, возьмем на отрезке две точки x1 и x2, симметрично относительно границ делящие исходный отрезок в отношении золотого сечения:

,

,

где коэффициент .

Если f(x1) < f(x2), мы должны сузить отрезок справа, т.е. новое значение xR = x2, в противном случае xL = x1. Оставшаяся внутри нового отрезка точка является первым приближением к минимуму и делит этот отрезок в отношении золотого сечения. Таким образом, на каждой итерации приближения к минимуму (см. рисунок) нам нужно ставить только одну точку (x1 или x2), в которой считать значение функции и сравнивать его с предыдущим. Условием выхода из итерационного процесса будет, подобно предыдущему случаю, условие |x2 – x1| ≤ ξ.

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

Метод парабол.

Пусть f(x) имеет первую и вторую производную. Разложим f(x) в ряд Тейлора в некоторой точке xk, ограничиваясь при этом тремя членами разложения:

. (3)

Иными словами, аппроксимируем нашу функцию в точке xk параболой. Для этой параболы можно аналитически вычислить положение экстремума как корень уравнения первой производной от (3): . Пусть минимум аппроксимирующей параболы находится в точке xk+1. Тогда вычислив значение функции f(xk+1), мы получаем новую точку приближения к минимуму.

Обычно в практических реализациях данного метода не используют аналитический вид первой и второй производных f(x). Их заменяют конечно-разностными аппроксимациями. Наиболее часто берут симметричные разности с постоянным шагом h:

;

.

Это эквивалентно аппроксимации функции параболой, проходящей через три близкие точки xk+h, xk, xk–h. Окончательное выражение, по которому можно строить итерационный процесс, таково:

. (4)

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

1) знаменатель формулы (4) должен быть >0. Если это не так, нужно сделать шаг в обратном направлении, причем достаточно большой. Обычно в итерационном процессе полагают . Иногда ради упрощения расчетов полагают , однако это существенно уменьшает скорость сходимости.

2) . Если это не так, то от xk следует сделать шаг с τ = ½. Если и при этом условие убывания не выполнено, уменьшают τ и вновь делают шаг.

Численные методы поиска минимума функции нескольких переменных.

Будем рассматривать методы поиска минимума в многомерных задачах на примере функции двух переменных f(x, y), так как эти методы легко аппроксимировать на случай трех и более измерений. Все эффективные методы поиска минимума сводятся к построению траекторий, вдоль которых функция убывает. Разные методы отличаются способами построения таких траекторий, так как метод, приспособленный к одному типу рельефа, может оказаться плохим для рельефа другого типа. Различают следующие типы рельефа:

Метод координатного спуска.

Пусть требуется найти минимум f(x, y). Выберем нулевое приближение (x0, y0). Рассмотрим функцию одной переменной f(x, y0) и найдем ее минимум, используя любой из рассмотренных выше способов. Пусть этот минимум оказался в точке (x1, y0). Теперь точно так же будем искать минимум функции одной переменной f(x1, y). Этот минимум окажется в точке (x1, y1). Одна итерация спусков завершена. Будем повторять циклы, постепенно приближаясь ко дну котловины, пока не выполнится условие .

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

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

 Скачать реферат