Лабораторная работа № 2.2. Метод золотого сечения

Лабораторная работа № 2.2. Метод золотого сечения

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

Оборудование и программное обеспечение: Персональный компьютер под управлением операционной системы семейства Windows, пакет Microsoft Office, интегрированная среда программирования Turbo C.

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

(4.2.1)

Как правило, скорость сходимости определяется количеством вычислений значения функции f(x), так как процедура вычисления одного значения функции занимает вполне определенное время. Поэтому перед исследователями, решающими задачу (4.2.1), всегда стоит проблема сокращения временных ресурсов ЭВМ на получение решения, которая в итоге сводится к выбору наиболее эффективного метода решения. Таким образом, перед учеными стояла и стоит сейчас задача разработки целого арсенала методов численного решения уравнения (4.2.1). Одним из распространенных методов решения уравнения является метод золотого сечения, имеющего еще и второе название – метод Фибоначчи (в честь ученого предложившего его).

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

(4.2.2)

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

Рис. 4.2.1. Деление отрезка в золотом сечении

Рассмотрим подробно, каким образом получается выражение для определения координаты точки . Графическая иллюстрация процедуры деления отрезка показана на рис. 4.2.1. Согласно пропорции золотого сечения весь отрезок относится к большему как больший к меньшему. Эту пропорция запишем в виде, используя обозначения рис. 4.2.1.

.

(4.2.3)

Из соотношения (4.2.3) после несложных преобразований получаем квадратное уравнение относительно координаты точки .

,

(4.2.3)

корни которого находятся из теоремы Виета и определяются выражением

.

(4.2.4)

Выбирая геометрически верное решение, соответствующее знаку "+" в (4.24) и вводя обозначение

,

(4.2.5)

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

.

(4.2.6)

Кроме того, было показано, что существует и другая точка , которая делит исходный отрезок в пропорции золотого сечения, и ее координата вычисляется по формуле аналогичной (4.2.7), где вместо числа Фибоначчи F₁ стоит другое число Фибоначчи F₂

.

(4.2.7)

Так же было показано, что эти числа Фибоначчи удовлетворяют условию

,

(4.2.8)

из которого следует, что F₂ =0,618.

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

если
	(4.2.9)
если .

Такой итерационный процесс в общем случае является бесконечным, если только случайным образом точка не окажется корнем уравнения (4.2.1). Поэтому всегда определяется точность e, с которой требуется вычислить его значение. Если точность известна, то вычисления следует проводить до тех пор, пока длина интервала, содержащего корень, не станет меньше . В этом случае точка , определяемая одним из соотношений (4.2.6) или (4.2.7), полученного интервала и будет являться значением корня уравнения (4.2.1), удовлетворяющего требуемой точности e.

Сходимость метода. Метод Фибоначчи, так же как и метод деления отрезка пополам является простым и надежным. Он сходится к решению для любых непрерывных функций, в том числе и не дифференцируемых. Скорость его сходимости несколько выше, чем у метода бисекций. Это объясняется тем фактором, что на ряде итераций отбрасывается большая часть интервала, которая не содержит корень. Это в конечном итоге приводит к меньшему количеству вычислений значений функции при нахождении ее корня с необходимой точностью, чем в случае применения метода бисекций.

Рис. 4.2.2. Графики функций и

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

.

(4.2.10)

Оно имеет один корень равный нулю другой отличный от нуля, который принадлежит интервалу . Для того чтобы убедится в этом достаточно построить графики функций и (рис. 4.2.2).

Работу обсуждаемого метода можно проследить на основе результатов, приведенных в таблице 4.2.1.

Таблица 4.2.1

Результаты, полученные при использовании метода Фибоначчи

№ итер.	a	b	c=a+F1×(b-a)	f(a)×f(c)	|b-a|	f(c)
	1,0	3,14	1,817407	4.957793	2,14	-1,545758
	1,817407	3,14	2,322593	-2,692897	1,322593	1,742121
	1,817407	2,322593	2,010371	0,746713	0,505185	-0,483072
	2,010371	2,322593	2,129629	-0,142964	0,312222	0,295948
	2,010371	2,129629	2,055923	0,094806	0,119258	-0,196257
	2,055923	2,129629	2,084076	0,002418	0,073706	-0,012318
	2,084076	2,129629	2,101474	-0,001280	0,045553	0,103885
	2,084076	2,101474	2,090722	-0,000392	0,017400	0,031840
	2,084076	2,090722	2,086615	-0,000056	0,006646	0,004515
	2,084076	2,086615	2,085046	0,000073	0,002538	-0,005893
	2,085046	2,086615	2,085645	0,000011	0,001569	-0,001920
	2,085645	2,086615	2,086015	-0,000001	0,000970	0,000537
	2,085645	2,086015	2,085787	0,000002	0,000370	-0,000982
	2,085787	2,086015	2,085874	0,000000	0,000229	-0,000401
	2,085874	2,086015	2,085928	0,000000	0,000141	-0,000042
	2,085928	2,086015	2,085962	-0,000000	0,000087	0,000179

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

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

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

.

(2.1.9)

Для вычисления координаты точки из выражения (2.1.9) получаем квадратное уравнение

,

(2.1.10)

решая которое находим для

.

(2.1.11)

Иначе полученное выражение (2.1.11) можно переписать в виде

.

(2.1.12)

Так как координата точки не должна выходить за пределы самого отрезка , то в выражении (2.1.12) следует взять знак "-". Вводя обозначение

,

(2.1.13)

получаем

,

(2.1.14)

где - число Фибоначчи. Если предположить, что большим отрезком будет являться , а не , то пропорция (2.1.9) будет иметь вид

.

(2.1.15)

Решая соответствующее ей квадратное уравнение, получаем второе выражение для координаты точки

, .

(2.1.16)

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

Графическая интерпретация метода золотого сечения приведена на рис. 2.1.2, на котором последовательность стремится к корню.

Рис. 2.1.1. Графическое представление работы метода Фибоначчи (золотого сечения)

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

1 шаг ввод начальных данных: точности вычислений , начала и , и конца для интервала, содержащего корень;

2 шаг вычисляем значение функции в точке ;

3 шаг определяем координату точки и вычисляем в точке значение функции ;

4 шаг если выполнено неравенство , то точка вычисленный корень функции и идем к 6 шагу, иначе к следующему шагу;

5 шаг если , то , иначе и , а затем перейти к шагу 3;

6 шаг вывод корня функции и ее значения в этой точке .

Рассмотрим работу метода Фибоначчи на примере нахождения корня для функции (2.1.5).

Все вычисления представлены в таблице 2 с точностью .

Таблица 2

Пример, иллюстрирующий работу метода Фибоначчи

№ итерации						Знак
			0.763932	-1.0	-0.175925	+
	0.763932		1.236110	-0.175925	0.401080	-
	0.763932	1.236110	0.944304	-0.175925	0.062198	-
	0,763932	0.944304	0.832834	-0.175925	-0.083350	+
	0.832834	0.944304	0.875416	-0.083350	-0.026997	+
	0.875416	0.944304	0.901731	-0.026997	0.007393	-
	0.875416	0.901731	0.885468	-0.026997	-0.013817	+
	0.885468	0.901731	0.891680	-0.013817	-0.005699	+
	0.891680	0.901731	0.895519	-0.005699	-0.000692	-

Итак, получено, что корень функции равен 0.895519, при котором значение самой функции равно -0.000692. Обращаем внимание на то, что длина интервала, которому принадлежит корень меньше .

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

ТЕСТ

1))Чему приблизительно равна величина золотого сечения?

А 1,4

б 1,6

в 1,2

г 2,0

2))Каким из приведенных ниже рекуррентных соотношений можно вычислить число Фибоначчи?

а F_n = F_n-1+F_n-2

б F_n = F_n-1+2F_n-2

в F_n = 2F_n-1+2F_n-2

г F_n = (F_n-1+F_n-2)/2

3) Поставьте в соотвествие с n, значение числа Фибоначчи.

А 3

Б 5

В 9

Г 8

· 34

· 21

· 2

· 5

4) Поставьте в соотвествие с n, значение числа Фибоначчи.

А

Б

В

Г

5) С помощью метода Фибоначчи найти минимум функции f(x)=x²+2x на интервале (-3,5). Длина конечного интервала неопределенности не должна превосходить 0,2.

-0,9987

6) Расставьте правильно пункты алгоритма

Алгоритм минимизации функции f(x) с использование, чисел Фибоначчи.

1. По заданной точности рассчитывается вспомогательное число

2. Для полученного значения N находится такое число Фибоначчи F_S, для которого выполняется неравенство: N=(b-a)/ἐ

3. F_s-1<N<F_s

4. По формуле (9) определяется длина конечного интервала неопределенности l.

5. Вычисляются значения x₁=a+l∙F_S-2, x₂=b-l∙F_S-2.

6. В зависимости от соотношения f(x₁) и f(x₂) выбирается новый интервал локализации минимума.

7. Внутри полученного интервала находится новая точка (x₁ или x₂), симметричная к уже имеющейся точке и отстоящая от конца интервала на величину l∙F_S-1-k, где k - номер шага. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 5, до тех пор, пока k не станет равно S-1. Тогда переходят к пункту 7.

8. Полагают x₂=x₁+δ, находят f(x₂). Если f(x₂) > f(x₁) то минимум реализуется на интервале (a, x₁), в противном случае - на интервале (x₁ , b).

7). Какие критерии существуют для окончания алгоритма?

8). Возможно ли использовать метод Фибоначчи для оптимизации функции x₁+x₂=2?

9). У какого из указанных методов эффективность выше: метод Фибоначчи, метод Бисекций. Почему?

10) Метод Фибоначчи относится к методам?

1. Одномерным

2. Метод прямого поиска

3. Метод деформируемого многогранника

4. Метод вращающихся координат

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

11) Выполните соотвествие между формулами для начального и конечного значения интервала

Дата добавления: 2015-11-05