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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Метод Фибоначчи предполагает разбиение на каждой итерации отрезка локализации минимума целевой
функции в отношении двух последовательных чисел Фибоначчи. Предположим, что для нахождения минимума
функции
f
0
(x) на отрезке [а
0
, b
0
] с точностью ε требуется выполнить N итераций. На первой итерации разобьем
отрезок [
a
0
, b
0
] точкой х
1
на два отрезка [a
0
, x
1
] и [х
1
, b
0
] такие, что отношение их длин равно отношению чисел
Фибоначчи
F
N –2
и F
N–1
(рис. 2.5), т.е.
.
1
2
10
01
−
−
=
−
−
N
N
F
F
xb
ах
Учитывая то, что F
N
= F
N–1
+ F
N–2
, получим
()
.
00
1
01
ab
F
F
bх
N
N
−−=
−
Точка х
2
выбирается симметрично х
1
относительно середины отрезка [a
0
, b
0
], т.е.
x
2
= a
0
+ F
N–1
(b
0
– a
0
)/F
N
.
Далее вычисляются значения f
0
(х
1
), f
0
(х
2
) и сравниваются между собой. Если f
0
(х
1
) < f
0
(х
2
), то новым отрез-
ком локализации [
a
1
, b
1
] становится отрезок [a
0
, x
2
], в противном случае – отрезок [х
1
, b
0
]. Из рис. 2.5 видно, что
после выполнения первой итерации
a
1
= a
0
, b
1
= x
2
, х
2
= x
1
. Необходимо вычислить точку х
1
, располагающуюся
симметрично
x
2
относительно середины отрезка [a
1
, b
1
].
a
1
b
1
x
1
x
2
(b
0
-a
0
)F
N-2
/F
N
x
f
0
a
0
x
1
x
2
b
0
(b
0
-a
0
)F
N-1
/F
N
(b
1
-a
1
)F
N-2
/F
N-1
(b
1
-a
1
)F
N-3
/F
N-1
Рис. 2.5. Метод Фибоначчи
Очевидно, что
()
00
2
11
ab
F
F
xb
N
N
−=−
−
.
С другой стороны
()
00
1
11
ab
F
F
ab
N
N
−=−
−
.
Отсюда следует, что
()
11
1
2
11
ab
F
F
bx
N
N
−−=
−
−
.
Для произвольной
k-й итерации, k = 1, …, N, точки х
1
или х
2
могут быть вычислены, соответственно, по
формулам:
()
;
11
1
11 −−
+−
−
−
−−=
kk
kN
kN
k
ab
F
F
bx
()
.
11
1
12 −−
+−
−
−
−+=
kk
kN
kN
k
ab
F
F
аx
Определим теперь количество итераций
N, необходимых для решения задачи минимизации функции f
0
(x)
на отрезке [
а
0
, b
0
] с точностью ε.
Принимая за критерий окончания поиска выполнение условия
b
N
– a
N
≤ ε или
()
,
1
00
ε≤− ab
F
N
получим число итераций
N, определяемое из условия
NN
F
ab
F ≤
ε
−
≤
−
00
1
.
Количество вычислений значений функции составит
N + l.
Порядок выполнения работы
1. Составить алгоритмы решения задачи минимизации функции одной переменной методами половинного
деления, «золотого» сечения и Фибоначчи.
2. Подготовить программы для вычислительной машины, реализующие алгоритмы из п. 1.

Страницы