ВУЗ:
Составители:
Рубрика:
7
Можно показать (выполнить это в качестве упражнения), что a)
F
n
=
1
√
5
[(
1+
√
5
2
)
n
− (
1 −
√
5
2
)
n
)],n=1, 2,...;
b)
lim
n→∞
F
n+1
F
n+2
=
√
5 − 1
2
;
lim
n→∞
F
n
F
n+2
=
3 −
√
5
2
Метод Фибоначчи также является симметричным и поэтому имеет много общего с методом золотого
сечения. В последнем выбираемые на каждом шаге точки x
1
,x
2
являются выпуклыми комбинаци-
ями концов текущего отрезка поиска:
x
1
=(1− λ)a + λb; x
2
= λa +(1− λ)b;
λ =
3−
√
5
2
;(1− λ)=
√
5−1
2
Величина остается постоянной в ходе поиска.
В методе Фибоначчи
x
1
=(1− λ
n−1+k
)a + λ
n−k+1
b;
x
2
=(λ
n−1+k
)a +(1−λ
n−k+1
)b
В этом методе λ
n−k+1
=
x
1
−a
b−a
изменяется на каждом шагу.
На первом шаге x
1
= a +
F
n
F
n+2
(b − a);
x
2
= a + b − x
1
= a +(1−
F
n
F
n+1
)(b − a)=a +
F
n+1
F
n+2
Как и в методе золотого сечения, точки x
1
,x
2
находятся на одинаковом расстоянии от середины
отрезка [a, b] и ближе к середине, чем к соответствующему концу.
На первом шаге λ
n
=
F
n
F
n+2
Число вычислений значений функции f(x) фиксировано, текущим параметром процесса будет па-
раметр k
Длина отрезка на втором шаге будет равна (∆
1
= b −a); ∆
2
= b −x
1
= x
2
−a =
F
n+1
F
n+2
(b−a)=
F
n+1
F
n+2
∆
1
Если на втором шаге будем иметь отрезок поиска [x
1
,b], то точка x
2
, будет левее середины нового от-
резка. Поэтому на новом отрезке [a, b]=[x
1
,b], тогда роль x
1
играет точка x
2
,т.е.x
1
= a+
F
n−1
F
n+1
(b−a),
а x
2
= a +
F
n
F
n+1
(b − a) ит.д.
На k-ом шаге
x
1
= a +
F
n−k+1
F
n+k+3
(b − a); x
2
= a +
F
n−k+2
F
n−k+3
(b − a),k =1, 2,...,n
Длина отрезка поиска
∆
n
=
F
n−k+2
F
n−k+3
∆
k−1
=
F
n−k+2
F
n−2
∆
1
При k = n процесс заканчивается, в этом случае x
1
= x
2
, длина отрезка поиска
∆
n
=
2
F
n+2
∆
1
Поэтому за приближение к точке x
∗
берем точку x = x
1
= x
2
Перед началом процесса поиска определяется наименьшее натуральное n, удовлетворяющее нера-
венству
εF
n+2
≥ b − a
Критерием остановки процесса служит выполнение условия k = n
7
Можно показать (выполнить это в качестве упражнения), что a)
√ √
1 1+ 5 n 1− 5 n
Fn = √ [( ) −( ) )], n = 1, 2, . . . ;
5 2 2
b)
√
Fn+1 5−1
limn→∞ = ;
Fn+2 2
√
Fn 3− 5
limn→∞ =
Fn+2 2
Метод Фибоначчи также является симметричным и поэтому имеет много общего с методом золотого
сечения. В последнем выбираемые на каждом шаге точки x1 , x2 являются выпуклыми комбинаци-
ями концов текущего отрезка поиска:
x1 = (1√− λ)a + λb; x2√ = λa + (1 − λ)b;
λ = 3−2 5 ; (1 − λ) = 5−1
2
Величина остается постоянной в ходе поиска.
В методе Фибоначчи
x1 = (1 − λn−1+k )a + λn−k+1 b;
x2 = (λn−1+k )a + (1 − λn−k+1 )b
В этом методе λn−k+1 = xb−a 1 −a
изменяется на каждом шагу.
Fn
На первом шаге x1 = a + Fn+2 (b − a);
x2 = a + b − x1 = a + (1 − FFn+1
n
)(b − a) = a + F n+1
Fn+2
Как и в методе золотого сечения, точки x1 , x2 находятся на одинаковом расстоянии от середины
отрезка [a, b] и ближе к середине, чем к соответствующему концу.
На первом шаге λn = FFn+2n
Число вычислений значений функции f (x) фиксировано, текущим параметром процесса будет па-
раметр k
Длина отрезка на втором шаге будет равна (∆1 = b − a); ∆2 = b − x1 = x2 − a = F Fn+1
Fn+2 (b − a) = Fn+2 ∆1
n+1
Если на втором шаге будем иметь отрезок поиска [x1 , b], то точка x2 , будет левее середины нового от-
резка. Поэтому на новом отрезке [a, b] = [x1 , b], тогда роль x1 играет точка x2 , т. е. x1 = a+ FFn−1
n+1
(b−a),
а x2 = a + FFn+1
n
(b − a) и т. д.
На k-ом шаге
Fn−k+1 Fn−k+2
x1 = a + (b − a); x2 = a + (b − a), k = 1, 2, . . . , n
Fn+k+3 Fn−k+3
Длина отрезка поиска
Fn−k+2 Fn−k+2
∆n = ∆k−1 = ∆1
Fn−k+3 Fn−2
При k = n процесс заканчивается, в этом случае x1 = x2 , длина отрезка поиска
2
∆n = ∆1
Fn+2
Поэтому за приближение к точке x∗ берем точку x = x1 = x2
Перед началом процесса поиска определяется наименьшее натуральное n, удовлетворяющее нера-
венству
εFn+2 ≥ b − a
Критерием остановки процесса служит выполнение условия k = n
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
