Северин В.П. Методы ОП

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

Если на каждой итерации интервалом неопределенности становится левая половина предыдущего интервала неопределенности, то результате n вычислений функции получим конечный интервал не-

Если же на каждой итерации интервалом неопределенности становится не левая половина предыдущего интервала неопределенности, то результате n вычислений функции получим конечный интервал неопределенности длины

51

Здесь использовано неравенство 27 128 100 . Таким образом,

8 n 15 .

Если же интервал неопределенности необходимо уменьшить не менее чем в 1000 раз, то, используя неравенство 210 1024 1000 , по-

лучим 11 n 21 .

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

А л г о р и т м м е т о д а д е л е н и я и н т е р в а л а п о п о л а м .

шагу 7.

6.Положить a u , b v .

7.Если c a e , то перейти к шагу 2.

8.Остановиться.

В этом алгоритме на первых двух шагах вычисляются средние точки интервала и левой половины интервала, а на шаге 4 – средняя точка правой половины интервала. Точки сравниваются на шагах 3 и 5.

52

3.4. Числа Фибоначчи и их свойства

Леонардо Пизано Фибоначчи – известный математик эпохи Средневековья, который в 1202 году написал книгу «Liber abacci», содержащую почти все арифметические и алгебраические сведения того времени. В частности, по этой книге европейцы познакомились с индусскими или «арабскими» цифрами. Там же содержалась знаменитая «задача о размножении кроликов».

«Пусть в огороженном месте имеется пара кроликов (самка и самец) в первый день января. Эта пара кроликов производит новую пару кроликов в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорожденная пара кроликов становится зрелой уже через месяц и затем через месяц дает жизнь новой паре кроликов. Сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения?»

Решение этой задачи приводит к числам Фибоначчи:

F0 1, F1 1 , F2 2 , F3 3 , F4 5 , F5 8 , F6 13 , F7 21 , … ,

где индекс числа Фибоначчи соответствует номеру месяца, а значение числа – количеству пар кроликов в этом месяце. Такой последовательности чисел, начиная с F2 , отвечает закономерность: каждый член последовательности равен сумме двух предыдущих. Это правило мо-

жет быть записано в виде первой в истории математики рекуррентной формулы

Числа Фибоначчи Fn для номера n от 0 до 51 представлены в табл. 3.1.

Таким образом, по этой таблице получим решение приведенной «задачи о размножении кроликов»: через год в огороженном месте окажется F13 377 пар кроликов.

Числа Фибоначчи кроме описания количественных характеристик

53

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

Таблица 3.1 – Числа Фибоначчи

Числа Фибоначчи обладают многими интересными математическими свойствами. В частности,

Методом математической индукции докажем справедливость общей математической формулы

Пусть эта формула верна при некотором n k , то есть

54

Докажем справедливость формулы (3.5) и при n k 1 , то есть, что

На основании равенства (3.4) имеем

Fk2 1 Fk Fk 2 Fk 1(Fk Fk 1) Fk (Fk 1 Fk ) .

Раскрывая скобки в правой части, получим

Fk2 1 Fk Fk 2 Fk 1Fk Fk 1Fk 1 Fk Fk 1 Fk2 ,

и с учетом равенства (3.6)

Fk2 1 Fk Fk 2 (Fk2 Fk 1Fk 1) ( 1)k

приходим к равенству (3.7).

Докажем теперь справедливость формулы

На основании равенства (3.4) имеем

Fn 1Fn 2 Fn Fn 3 Fn 1(Fn Fn 1) Fn (Fn 1 Fn 2 ) .

Раскрывая скобки, получим

Fn 1Fn 2 Fn Fn 3 Fn 1Fn Fn2 1 Fn Fn 1 Fn Fn 2 .

С учетом равенства (3.5)

Fn 1Fn 2 Fn Fn 3 (Fn2 1 Fn Fn 2 ) ( 1)n 1 ,

откуда и следует формула (3.8).

Получим выражения для чисел Фибоначчи в явном виде. Для этого будем искать решение рекуррентного уравнения (3.4) среди геомет-

рических прогрессий с n -м членом xn

55

xn xn 1 xn 2 .

рентному уравнению (3.4). Ему же удовлетворяет и любая линейная

Решим эту систему уравнений по правилу Крамера:

56

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

бей, включающих иррациональное число 5 .

3.5. Метод Фибоначчи

Метод Фибоначчи основан на числах Фибоначчи и применяется для уменьшения интервала неопределенности точки минимума x целевой функции f (x) .

При рассмотрении метода дихотомии для интервала неопределенности [a, b] длины L b a двумя внутренними точками, показано, что точки деления целесообразно располагать симметрично относительно центра интервала на малом расстоянии между ними. Но в методе дихотомии на каждой итерации значения целевой функции необходимо вычислять в двух точках.

В методе Фибоначчи также две первые точки деления x1 и x2 расположим симметрично относительно центра интервала, вычислим в

57

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

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

Пусть на уменьшение интервала неопределенности отводится n вычислений целевой функции. Чтобы обеспечить наибольшее уменьшение интервала, последнюю точку поиска xn , как и в методе дихотомии, расположим симметрично относительно оставшейся внутренней точки xn 1 на малом расстоянии от нее. Обозначим конечную длину интервала неопределенности, полученную при n вычислениях

xn xn 1

Рис. 3.6. Окончание деления интервала методом Фибоначчи

58

Найдем длины интервалов неопределенности:

Перепишем эти равенства с использованием чисел Фибоначчи:

Отсюда получим, что при n вычислениях функции в методе Фибоначчи конечная длина интервала неопределенности станет равной

Для начала поиска необходимо найти положение первой точки деления исходного интервала, которая должна лежать на расстоянии

С учетом равенства (3.8) окончательно получим

59

Эффективность метода Фибоначчи определим отношением длин конечного и начального интервалов неопределенности:

Если интервал неопределенности необходимо уменьшить не менее чем в сто раз, то по числам Фибоначчи из табл. 3.1 получим:

Если же интервал неопределенности необходимо уменьшить не менее

60