g3 (542466), страница 2

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

Текст из файла (страница 2)

;

Из формул видно, что симметричны относительно середины отрезка .

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

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

Если , то полагают, что , в противном случае .

Посмотрим, как уменьшается отрезок неопределенности

;

....................................................................................

Таким образом, -й шаг метода Фибоначчи обеспечивает уменьшение длины отрезка неопределенности в раз.

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

Замечание 1.

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

Замечание 2.

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

Рисунок 3.3.11

Блок-схема метода Фибоначчи.

Пример.

Найти минимум на отрезке c

Начнем с определения :

Для решения поставленной задачи потребуется 9 шагов по методу Фибоначчи, при этом понадобится 9 раз вычислять . Заметим, что для решения этой же задачи методом дихотомии мы проделали 7 шагов, то есть вычисляли 14 раз.

1-й шаг.

;

.

2-й шаг.

.

3-й шаг.

;

.

4-й шаг.

;

.

5-й шаг.

;

.

6-й шаг.

;

.

7-й шаг.

.

8-й шаг.

;

.

9-й шаг.

;

.

Замечание.

Вычисления проводились с 5 знаками после запятой, поэтому точки последующего и предыдущего шага совпадают не полностью.

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

В теории чисел показано, что существует предел отношения соседних чисел Фибоначчи

показывает, как соотносятся длины отрезков неопределенности при применении метода Фибоначчи.

С другой стороны, рассмотрим следующую задачу. Возьмем отрезок , найдем внутри этого отрезка , образующие золотое сечение.

x₁ x₂

a b

Для этого необходимо выполнение следующих условий:

Найдем ,при котором возможны равенства

,

,

,

Поскольку

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

............................

Если - заданная точность, то число шагов метода золотого сечения следует находить как решение неравенства

Замечание.

Метод золотого сечения немного медленнее сходится, чем метод Фибоначчи.

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

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

Рисунок 3.3.12

Блок-схема метода золотого сечения.

Пример.

Найти минимум на отрезке c

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

Итак, потребуется 8 шагов метода золотого сечения, при этом значения придется вычислять 9 раз, то есть трудоемкость такая же, как была в методе Фибоначчи.

1-й шаг.

;

.

2-й шаг.

;

.

3-й шаг.

;

.

4-й шаг.

;

.

5-й шаг.

;

.

6-й шаг.

;

.

7-й шаг.

;

.

8-й шаг.

;

.

3.3.4Метод квадратичной интерполяции (парабол).

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

Итак, найти с точностью .

Выбираем .

Через точки проводим параболу, то есть строим интерполяционный многочлен 2-й степени:

Находим вершину параболы из условия ,

.

Если , то необходимо выяснить или нет.

Если , то по трем точкам строится следующая парабола.

Если , то следующая парабола строится по точкам:

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

Каждая новая вершина параболы принимается за очередное приближенное решение.

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

Рисунок 3.3.13

Блок-схема метода квадратичной интерполяции.

Пример.

Найти минимум на отрезке c точностью

Пусть

1-й шаг:

по трем точкам (-1, 1), (0.5, 0.25), (1, 1) строим параболу и находим ее вершину

,

Требование по точности не выполнено, поэтому необходимо продолжить вычисления

,

, следовательно, следующую параболу строим по трем точкам:

и находим

,

Вычисления завершены, в качестве приближенного решения получили .

Нетрудно убедится в том, что является точным решением задачи. Это совпадение объясняется тем, что есть многочлен 2-й степени, построенные интерполяционные многочлены, естественно, полностью совпали с .

Замечание.

В описанном алгоритме предполагалось, что унимодальна.

В случае, если этот метод применять для неунимодальной , алгоритм может зациклиться.

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

3.4Метод Ньютона.

Метод Ньютона относится к методам 2-го порядка и рекомендуется с применению в том случае, когда задача минимизации достаточно хорошо локализована.

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

Тогда если - k-е приближение к точке минимума, то расчетной формулой метода Ньютона будет формула

.

Метод Ньютона имеет высокую скорость сходимости:

где - точка минимума; С - некоторая положительная константа.

Процесс вычисления продолжается до тех пор, пока не будет достигнуто

На следующем рисунке приведена блок-схема алгоритма.

Рисунок 3.3.14

Блок - схема метода Ньютона.

Пример.

Найти минимум на отрезке c точностью .

Зададимся , например, возьмем середину отрезка :

Пусть

Для данного примера расчетной формулой метода Ньютона будет

1-й шаг.

2й шаг.

Решение.

Замечание.

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

4Численные методы минимизации многоэкстремальных функций.

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

Рисунок 3.4.15

Рисунок 3.4 .15 - пример такой функции, где - точка глобального минимума.

Ограничимся рассмотрением функций, удовлетворяющих условию Липшица на отрезке :

,

где M - константа Липшица.

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

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

Суть метода перебора состоит в следующем:

в точках отрезка

,

вычисляются значения функции и в качестве минимального значения принимается значение

.

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

Тогда с учетом условия Липшица

Таким образом, задаваясь необходимой величиной погрешности можно определить требуемое количество точек на отрезке :

Характеристики

Список файлов книги