ВУЗ:
Составители:
Рубрика:
5
В случаях, когда число вычислении значения функции априори задано, следует, что при N =2k
точность вычисления точки минимума функции определяется величиной
b−a
2
k+1
+ δ, Замечание: Если
функция дифференцируема и её производные могут быть вычислены, то алгоритм несколько упро-
щается: если f
(
a
k
+b
k
2
) < 0, то, очевидно, что функция f(x) убывает в окрестности точки
a
k
+b
k
2
) и
искомая точка x
∗
лежит правее этой точки, т. е. новый отрезок поиска [
a
k
+b
k
2
,b
k
], если f
(
a
k
+b
k
2
),
то x
∗
∈ [
a
k
+b
k
2
,b
k
]. К недостатком этого метода относится тот факт, что информация о значении
функции в точках x
1
и x
2
используется только на одном шаге. Более подробно с этим методом мож-
но ознакомиться в [1. 2].
Метод золотого сечения
Золотым или гармоническим делением, называется такое деление отрез-
ка [a, b] точкой x на две неравные части, при котором отношение длины всего отрезка к длине его
большой части равно отношению длины большей части к длине меньшей части отрезка, длина боль-
шей части отрезка является средней пропорциональной между длиной всего отрезка и меньшой его
части. Для определения искомых точек необходимо составить уравнения:
b−a
x−a
=
x−a
b−x
, если [a, x]-большая часть отрезка, и
b−a
b−x
=
b−x
x−a
, если [x, b]-большая часть отрезка.
Отсюда, анализируя эти уравнения, мы получим две точки золотого сечения:
x
1
= a +
3 −
√
5
2
(b −a) ≈ a +0.382(b −a) − левая точка (∗)
x
2
= a +
√
5 −1)
2
(b −a) ≈ a +0.618(b −a) − правая точка (∗∗)
. При этом само соотношение, золотая пропорция ˜r =
1+
√
5
2
≈ 1.618034 Пользуясь свойством унимо-
дальности функции, сравниваем значения ее в этих точках: если f(x
1
) >f(x
2
), то новый отрезок
поиска есть [a
1
,b
1
],гдеa
1
= x
1
,b
1
= b, если f(x
1
) <f(x
2
), то новый отрезок поиска имеет концы
a
1
= a, b
1
= x
2
. Можно показать (выполнить в качестве упражнения), что выбранные точки облада-
ют следующими свойствами: 1. Точки x
1
,x
2
лежат на одинаковом расстоянии от середины отрезка;
2. Точки x
1
,x
2
расположены к середине отрезка, чем к своим концам; 3. Точка x
1
является точкой
золотого сечения отрезка [a, x
2
], а точка x
2
является точкой золотого сечения отрезка [x
1
,b].Из
последнего утверждения следует, что на последующем шаге мы уже будем иметь одну точку золо-
того сечения. Таким образом, на каждой итерации, кроме первой, метод золотого сечения требует
определения лишь одной точки отрезка и одного значения функции, что и определяет большую
эффективность этого метода по сравнению с методом половинного деления при заданной точности.
Если зафиксировать число n вычислений значений функции f(x), то методом золотого сечения
значение x
∗
может быть найдено в 1.144
n
раз точнее, чем методом деления отрезка пополам. Длина
отрезка по методу золотого сечения убывает последующему правилу:
∆
n
=(b −a)
√
5 −1
2
n
Приведем схему метода золотого сечения. Пусть ε-требуемая точность вычисления точки миниму-
ма.
0. Начальный шаг: находим точки x
1
и x
2
по формулам (*) (**)
1. Вычисляем f (x
1
),f(x
2
)
если f(x
1
) >f(x
2
),топереходимкшагу4.
если f(x
1
) <f(x
2
),топереходимкшагу3.
если f(x
1
)=f(x
2
),топереходимкшагу2.
2. Получаем новый отрезок [a, b], a = x
1
; b = x
2
.
Находим h =
b−a
2
;, если h ≤ ε,тоx
∗
≈
a+b
2
,f
min
≈ f(x
∗
) end, в противном случае переход к 0.
3. Получаем новый отрезок [a, b], a = a; b = x
2
.
Находим h =
b−a
2
, если h ≤ ε,тоx
∗
≈
a+b
2
,f
min
≈ f(x
∗
) end; в противном случае x
2
= x
1
, находим
x
1
по (*), переход к 1.
4. Получаем новый отрезок [a, b], a = x
1
; b = b.
Находим h =
b−a
2
, если h ≤ ε,тоx
∗
≈
a+b
2
,f
min
≈ f(x
∗
) end; в противном случае x
1
= x
2
, находим
5
В случаях, когда число вычислении значения функции априори задано, следует, что при N = 2k
точность вычисления точки минимума функции определяется величиной 2b−a k+1 + δ, Замечание: Если
функция дифференцируема и её производные могут быть вычислены, то алгоритм несколько упро-
щается: если f ( ak +b2
k
) < 0, то, очевидно, что функция f (x) убывает в окрестности точки ak +b 2
k
)и
∗ ak +bk ak +bk
искомая точка x лежит правее этой точки, т. е. новый отрезок поиска [ 2 , bk ], если f ( 2 ),
то x∗ ∈ [ ak +b
2
k
, bk ]. К недостатком этого метода относится тот факт, что информация о значении
функции в точках x1 и x2 используется только на одном шаге. Более подробно с этим методом мож-
но ознакомиться в [1. 2].
Метод золотого сечения Золотым или гармоническим делением, называется такое деление отрез-
ка [a, b] точкой x на две неравные части, при котором отношение длины всего отрезка к длине его
большой части равно отношению длины большей части к длине меньшей части отрезка, длина боль-
шей части отрезка является средней пропорциональной между длиной всего отрезка и меньшой его
части. Для определения искомых точек необходимо составить уравнения:
b−a x−a b−a b−x
x−a = b−x , если [a, x]-большая часть отрезка, и b−x = x−a , если [x, b]-большая часть отрезка.
Отсюда, анализируя эти уравнения, мы получим две точки золотого сечения:
√
3− 5
x1 = a + (b − a) ≈ a + 0.382(b − a) − левая точка (∗)
2
√
5 − 1)
x2 = a + (b − a) ≈ a + 0.618(b − a) − правая точка (∗∗)
2
√
. При этом само соотношение, золотая пропорция r̃ = 1+2 5 ≈ 1.618034 Пользуясь свойством унимо-
дальности функции, сравниваем значения ее в этих точках: если f (x1 ) > f (x2 ), то новый отрезок
поиска есть [a1 , b1 ], где a1 = x1 , b1 = b, если f (x1 ) < f (x2 ), то новый отрезок поиска имеет концы
a1 = a, b1 = x2 . Можно показать (выполнить в качестве упражнения), что выбранные точки облада-
ют следующими свойствами: 1. Точки x1 , x2 лежат на одинаковом расстоянии от середины отрезка;
2. Точки x1 , x2 расположены к середине отрезка, чем к своим концам; 3. Точка x1 является точкой
золотого сечения отрезка [a, x2 ], а точка x2 является точкой золотого сечения отрезка [x1 , b]. Из
последнего утверждения следует, что на последующем шаге мы уже будем иметь одну точку золо-
того сечения. Таким образом, на каждой итерации, кроме первой, метод золотого сечения требует
определения лишь одной точки отрезка и одного значения функции, что и определяет большую
эффективность этого метода по сравнению с методом половинного деления при заданной точности.
Если зафиксировать число n вычислений значений функции f (x), то методом золотого сечения
значение x∗ может быть найдено в 1.144n раз точнее, чем методом деления отрезка пополам. Длина
отрезка по методу золотого сечения убывает последующему правилу:
√ n
5−1
∆n = (b − a)
2
Приведем схему метода золотого сечения. Пусть ε-требуемая точность вычисления точки миниму-
ма.
0. Начальный шаг: находим точки x1 и x2 по формулам (*) (**)
1. Вычисляем f (x1 ), f (x2 )
если f (x1 ) > f (x2 ), то переходим к шагу 4.
если f (x1 ) < f (x2 ), то переходим к шагу 3.
если f (x1 ) = f (x2 ), то переходим к шагу 2.
2. Получаем новый отрезок [a, b], a = x1 ; b = x2 .
Находим h = b−a ∗ a+b ∗
2 ;, если h ≤ ε, то x ≈ 2 , fmin ≈ f (x ) end, в противном случае переход к 0.
3. Получаем новый отрезок [a, b], a = a; b = x2 .
Находим h = b−a ∗ a+b ∗
2 , если h ≤ ε, то x ≈ 2 , fmin ≈ f (x ) end; в противном случае x2 = x1 , находим
x1 по (*), переход к 1.
4. Получаем новый отрезок [a, b], a = x1 ; b = b.
Находим h = b−a ∗ a+b ∗
2 , если h ≤ ε, то x ≈ 2 , fmin ≈ f (x ) end; в противном случае x1 = x2 , находим
Страницы
- « первая
- ‹ предыдущая
- …
- 3
- 4
- 5
- 6
- 7
- …
- следующая ›
- последняя »
