Получение оптимальных проектных решений и их анализ с использованием математических моделей. Литовка Ю.В. - 41 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Таким образом, на каждой последующей итерации длина отрезка локализации минимума уменьшается на
25 % по сравнению с длиной отрезка на предыдущей итерации. Критерием окончания поиска в методе поло-
винного деления является выполнение условия b
k
– a
k
≤ ε, где ε – точность вычисления минимума.
Оценка числа итераций
N, необходимых для нахождения минимума функции f
0
(x) на отрезке [a
0
, b
0
] с точ-
ностью ε, может быть получена из следующих соображений. После выполнения 1-й итерации отрезок локали-
зации минимума будет иметь длину, равную 0,75(
b
0
– a
0
). После выполнения 2-й итерации – 0,75(0,75(b
0
– a
0
)) =
0,75
2
(b
0
– a
0
), после выполнения N-й итерации – 0,75
N
(b
0
– a
0
).
Поиск заканчивается тогда, когда выполняется условие:
0,75
N
(b
0
– a
0
) ≤ ε.
Отсюда
ab
N
−
ε
≤75,0
, или
ab
N
−
ε
≥ln75,0ln , или
ε
−
−≥
75,0ln
ln
ab
N
.
Здесь [ ] означает округление до ближайшего большего целого. При этом оценка числа вычислений значений
функции составляет 2
N.
Метод «золотого» сечения. Лучшие результаты могут быть получены, если деление отрезка [a
0
, b
0
], на ко-
тором отыскивается минимум, производить в определенном иррациональном отношении (рис. 2.4). Определим от-
ношение длины отрезков [
a
0
, x
1
] и [х
2
, b
0
] к длине отрезка [a
0
, b
0
] из условия того, чтобы на всех итерациях отре-
зок локализации разбивался бы в одном и том же отношении, и при этом начиная со второй итерации на каждой
итерации вычислялась бы только одна новая точка (
х
1
или x
2
), а вторая из них использовалась бы от предыду-
щей итерации. Очевидно, что эти условия будут выполнены тогда, когда справедливо следующее:
.
02
12
00
20
ax
xx
ab
xb
−
−
=
−
−
Положим
s = b
0
– a
0
;
s
1
= b
0
– x
2
= x
1
– a
0
; s
2
= x
2
– x
1
= s – 2s
1
Тогда
1
11
2
ss
ss
s
s
−
−
=
.
Разделим числитель и знаменатель правой части последнего равенства на
s:
s
s
s
s
s
s
1
1
1
1
21
−
−
=
или
.38,0
2
53
1
≈
−
== y
s
s
x
f
0
a
0
x
1
x
2
b
0
s
1
s
2
s
1
Рис. 2.4. К методу «золотого» сечения
Полученное значение носит название «золотого» сечения. При его использовании на очередной итерации
минимум функции
f
0
локализуется на отрезке, длина которого равна 1 – y ≈ 0,62 от длины отрезка локализации
на предыдущей итерации. Таким образом, за одну итерацию отрезок локализации минимума уменьшается при-
близительно на 38 %.
Оценка числа итераций
N, необходимых для нахождения минимума функции f
0
(x) на отрезке [а
0
, b
0
] с точ-
ностью ε может быть получена аналогично рассмотренному выше подходу и составит
.
2
15
ln
ln
−
ε
−
−≥
ab
N
При этом число вычислений значений функции составит N + 1.
Метод Фибоначчи основан на использовании свойств последовательности чисел Фибоначчи. Последова-
тельность чисел Фибоначчи задается рекуррентной формулой:
F
k+1
= F
k–1
+ F
k
, k = 1, 2, …, F
0
= F
1
= 1.

Страницы