Метод деления отрезка пополам

Метод деления отрезка пополам

Описание метода

Разделим интервал [a, b] на две равные части, а затем каждую из частей еще на две равные части.

  

Это первый этап поиска минимума. На нем после пяти вычислений функции (два - на краях и три - внутри интервала [a, b]) интервал неопределенности сужается вдвое, то есть на этом этапе α =0,5. Новый интервал неопределенности [x₄,x₅] снова разделим пополам, а затем каждую половину снова пополам. Теперь значения функции по краям и в его середине уже известны. Поэтому для завершения поиска на этом этапе требуется вычислить только два значения функции, после чего интервал неопределенности снова уменьшится вдвое. Это преимущество рассмотренного метода сохранится и в дальнейшем. После N вычислений функции коэффициент дробления интервала составляет 
 
  (2.2) 
 
 
Здесь N=5,7,9,..., так как интервал неопределенности, начиная со второго этапа, уменьшается только после двух вычислений функции. Из (2.1),(2.2) видно, что метод деления пополам эффективнее, чем общий поиск 

Параметры на входе: - достаточно малые положительные константы.

1. Повторять: 

2. ;

3. Если  , то ;

4. Если  , то ;

5. пока  ;

6. .

Анализ метода

Считаем, что один шаг - это один этап цикла (п. 2-4).

Изначальная длина отрезка составляет .

После первого шага: ,

После -го шага: .

Если  мы останавливаемся на -м шаге, то погрешность результата составит:

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

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

Недостаток:

Информация  о значении функции в точках и используется только на одном шаге.  
 
 

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

Определение:

Говорят, что точка  осуществляет золотое сечение отрезка , если

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

Описание метода

Параметр  на входе: - достаточно малая положительная константа, погрешность метода.

1.

2. Повторять: 

3. Если  , то ;

4. Если  , то ;

5. пока  ;

6. .  

Анализ метода

Считаем, что один шаг - это один этап цикла (п. 3-4), . Тогда, считая длину отрезка на каждом шаге , получаем:

;

;

;

Нетрудно  проверить, что 

(1)

, где  -числа Фибоначчи.

С другой стороны, выполняется равенство:

(2)

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

Тогда значение будет вычисляться в  точках.

Недостаток:

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

Пусть вычисляется с погрешностью

Тогда имеем:

Из (1):

.

Подставляем (2):

(3)

.

Известно, что последовательность сходится при , В то же время , поэтому .

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