Мотс. Задание № 2. Вариант № 10.

Задание:

Найти минимум унимодальной функции

F(X) = 3*(5 – X)^4/3+2*X²,

[a₀, b₀] = [1,5 ;2], e = 0,02.

Решение:

Метод дихотомии (деление отрезка пополам):

1. Делим интервал неопределенности пополам:

Х₀ = (a₀ + b₀)/2,

Х₀ = (1,5 + 2)/2 = 1,75.

2. Находим точки, отстоящие от Х₀ на e/2, и считаем значение функции в этих точках:

Х₀’ = Х₀ - e/2 = 1,74, F(Х₀’) = 20,55665,

Х₀” = Х₀ + e/2= 1,76. F(Х₀”) = 20,57815.

3. Сравнивая значения функций видим, что часть отрезка правее Х₀” не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₁ = a₀ = 1,5, b₁ = Х₀” = 1,76.

3. L₁ = b₁ – a₁ = 1,76 – 1,5 = 0,26. - Длина новго интервала неопределенности.

Так как L₁ > e, то экстремум не найден, делаем еше один шаг.

2.1 Делим интервал неопределенности пополам:

Х₁ = (a₁ + b₁)/2,

Х₁ = (1,5 + 1,76)/2 = 1,63.

2. Находим точки, отстоящие от Х₀ на e/2, и считаем значение функции в этих точках:

Х₁’ = Х₁ - e/2 = 1,62, F(Х₁’) = 20,466307,

Х₁” = Х₁ + e/2= 1,64. F(Х₁”) = 20,476767.

2. Сравнивая значения функций видим, что часть отрезка правее Х₁” не может содержать минимум, поэтому отбрасываем ее.

3. Новый интервал неопределенности:

a₂ = a₁ = 1,5, b₂ = Х₁” = 1,64.

2. L₂ = b₂ – a₂ = 1,64 – 1,5 = 0,14. - Длина новго интервала неопределенности.

Так как L₂ > e, то экстремум не найден, делаем еше один шаг.

1. Делим интервал неопределенности пополам:

Х₂ = (a₂ + b₂)/2,

Х₂ = (1,5 + 1,64)/2 = 1,57.

2. Находим точки, отстоящие от Х₂ на e/2, и считаем значение функции в этих точках:

Х₂’ = Х₂ - e/2 = 1,56, F(Х₂’) = 20,445947,

Х₂” = Х₂ + e/2= 1,58. F(Х₂”) = 20,450898.

3. Сравнивая значения функций видим, что часть отрезка правее Х₂” не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₃ = a₂ = 1,5, b₃ = Х₂” = 1,58.

5. L₃ = b₃ – a₃ = 1,58 – 1,5 = 0,08. - Длина новго интервала неопределенности.

Так как L₃ > e, то экстремум не найден, делаем еше один шаг.

1. Делим интервал неопределенности пополам:

Х₃ = (a₃ + b₃)/2,

Х₃ = (1,5 + 1,58)/2 = 1,54.

2. Находим точки, отстоящие от Х₃ на e/2, и считаем значение функции в этих точках:

Х₃’ = Х₃ - e/2 = 1,53, F(Х₃’) = 20,441958,

Х₃” = Х₃ + e/2= 1,55. F(Х₃”) = 20,444159.

3. Сравнивая значения функций видим, что часть отрезка правее Х₃” не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₄ = a₃ = 1,5, b₄ = Х₃” = 1,55.

5. L₄ = b₄ – a₄ = 1,55 – 1,5 = 0,05. - Длина новго интервала неопределенности.

Так как L₄ > e, то экстремум не найден, делаем еше один шаг.

1. Делим интервал неопределенности пополам:

Х₄ = (a₄ + b₄)/2,

Х₄ = (1,5 + 1,55)/2 = 1,525.

2. Находим точки, отстоящие от Х₄ на e/2, и считаем значение функции в этих точках:

Х₄’ = Х₄ - e/2 = 1,515, F(Х₄’) = 20,44151,

Х₄” = Х₄ + e/2= 1,535. F(Х₄”) = 20,442336.

3. Сравнивая значения функций видим, что часть отрезка правее Х₄” не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₅ = a₄ = 1,5, b₅ = Х₄” = 1,535.

5. L₅ = b₅ – a₅ = 1,535 – 1,5 = 0,035. - Длина новго интервала неопределенности.

Так как L₅ > e, то экстремум не найден, делаем еше один шаг.

1. Делим интервал неопределенности пополам:

Х₅ = (a₅ + b₅)/2,

Х₅ = (1,5 + 1,535)/2 = 1,5175.

2. Находим точки, отстоящие от Х₅ на e/2, и считаем значение функции в этих точках:

Х₅’ = Х₅ - e/2 = 1,5075, F(Х₅’) = 20,441672,

Х₅” = Х₅ + e/2= 1,5275. F(Х₅”) = 20,441811.

3. Сравнивая значения функций видим, что часть отрезка правее Х₅” не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₆ = a₅ = 1,5, b₆ = Х₅” = 1,5275.

5. L₆ = b₆ – a₆ = 1,5275 – 1,5 = 0,0275. - Длина новго интервала неопределенности.

Так как L₆ > e, то экстремум не найден, делаем еше один шаг.

1. Делим интервал неопределенности пополам:

Х₆ = (a₆ + b₆)/2,

Х₆ = (1,5 + 1,5275)/2 = 1,51375.

2. Находим точки, отстоящие от Х₆ на e/2, и считаем значение функции в этих точках:

Х₆’ = Х₆ - e/2 = 1,50375, F(Х₆’) = 20,44185,

Х₆” = Х₆ + e/2= 1,52375. F(Х₆”) = 20,441646.

3. Сравнивая значения функций видим, что часть отрезка левее Х₆’ не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₇ = Х₆’ = 1,50375, b₇ = b₆ = 1,5275.

5. L₇ = b₇ – a₇ = 1,5275 – 1,50375 = 0,02375. - Длина новго интервала неопределенности.

Так как L₇ > e, то экстремум не найден, делаем еше один шаг.

1. Делим интервал неопределенности пополам:

Х₇ = (a₇ + b₇)/2,

Х₇ = (1,50375 + 1,5275)/2 = 1,515625.

2. Находим точки, отстоящие от Х₈ на e/2, и считаем значение функции в этих точках:

Х₇’ = Х₇ - e/2 = 1,505625, F(Х₇’) = 20,441753,

Х₇” = Х₇ + e/2= 1,525625. F(Х₇”) = 20,44172.

3. Сравнивая значения функций видим, что часть отрезка левее Х₇’ не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₈ = X₇’ = 1,505625, b₈ = b₇ = 1,5275.

5. L₇ = b₇ – a₇ = 1,5275 – 1,505625 = 0,021875. - Длина новго интервала неопределенности.

Так как L₇ > e, то экстремум не найден, делаем еше один шаг.

1. Делим интервал неопределенности пополам:

Х₈ = (a₈ + b₈)/2,

Х₈ = (1,505625 + 1,5275)/2 = 1,5165625.

2. Находим точки, отстоящие от Х₈ на e/2, и считаем значение функции в этих точках:

Х₈’ = Х₈ - e/2 = 1,5065625, F(Х₈’) = 20,44171,

Х₈” = Х₈ + e/2= 1,5265625. F(Х₈”) = 20,441764.

3. Сравнивая значения функций видим, что часть отрезка правее Х₈” не может содержать минимум, поэтому отбрасываем ее.

4. Новый интервал неопределенности:

a₉ = a₈ = 1,505625, b₉ = X₈” = 1,5265625.

5. L₈ = b₈ – a₈ = 1,5265625 – 1,505625 = 0,0209375. - Длина новго интервала неопределенности.

Так как L₈ > e, то экстремум не найден, делаем еше один шаг.

И так далее пока не достигнем желаемой точности (L <= e).

Пусть (предположим) на девятом шаге мы достигли необходимой точности,то есть экстремум найден и равен

Х₉ = (a₉ + b₉)/2 = (1,505625 + 1,526525)/2 = 1,516075.

Ответ: F(X)min = 20,441507, при Х = 1,516075.

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

1. Определяем координаты точек Y₀ и Z₀:

Y₀ = a₀ + (3 - Ö5 ) / 2 * (b₀ - a₀), Y₀ = 1,5 + (3 - Ö5 ) / 2 * (2 – 1,5) = 1,691;

Z₀ = b₀ – (Y₀ - a₀) = a₀ + b₀ - Y₀, Z₀ = 1,5 + 2 – 1,691 = 1,809.

2. Вычисляем значение функции в точках Y₀ и Z₀:

F(Y₀) = 20,511758,

F(Z₀) = 20,638618.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₀.

Записываем новые координаты интервала:

a₁ = a₀ = 1,5,

b₁ = Z₀ = 1,809.

4. Находим длину нового интервала и сравниваем ее с e:

L₁ = b₁ – a₁ = 1,809 – 1,5 = 0,309.

Так как L₁ > e, то надо сделать еще один шаг.

2.1 Считаем координаты точек Y₁ и Z₁:

Z₁ = Y₀ = 1,691,

Y₁ = a₁ + b₁ - Z₁ = 1,5 + 1,809 – 1,691 = 1,618.

2. Вычисляем значение функции в точках Y₁ и Z₁:

F(Y₁) = 20,465363,

F(Z₁) = F(Y₀) = 20,511758.

2. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₁.

Записываем новые координаты интервала:

a₂ = a₁ = 1,5,

b₂ = Z₁ = 1,691.

2. Находим длину нового интервала и сравниваем ее с e:

L₂ = b₂ – a₂ = 1,691 – 1,5 = 0,191.

Так как L₂ > e, то надо сделать еще один шаг.

3.1 Считаем координаты точек Y₂ и Z₂:

Z₂ = Y₁ = 1,618,

Y₂ = a₂ + b₂ – Z₂ = 1,5 + 1,691 – 1,618 = 1,573.

2. Вычисляем значение функции в точках Y₂ и Z₂:

F(Y₂) = 20,448956,

F(Z₂) = F(Y₁) = 20,465363.

2. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₂.

Записываем новые координаты интервала:

a₃ = a₂ = 1,5,

b₃ = Z₂ = 1,618.

2. Находим длину нового интервала и сравниваем ее с e:

L₃ = b₃ – a₃ = 1,618 – 1,5 = 0,118.

Так как L₃ > e, то надо сделать еще один шаг.

1. Определяем координаты точек Y₃ и Z₃:

Z₃ = Y₂ = 1,573,

Y₃ = a₃ + b₃ – Z₃ = 1,5 + 1,618 – 1,573 = 1,545.

2. Вычисляем значение функции в точках Y₃ и Z₃:

F(Y₃) =20,443436,

F(Z₃) = F(Y₂) = 20,448956.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₃.

Записываем новые координаты интервала:

a₄ = a₃ = 1,5,

b₄ = Z₃ = 1,573.

4. Находим длину нового интервала и сравниваем ее с e:

L₄ = b₄ – a₄ = 1,573 – 1,5 = 0,073.

Так как L₄ > e, то надо сделать еще один шаг.

1. Определяем координаты точек Y₄ и Z₄:

Z₄ = Y₃ = 1,545,

Y₄ = a₄ + b₄ – Z₄ = 1,5 + 1,573 – 1,545 = 1,528.

5.2 Вычисляем значение функции в точках Y₅ и Z₅:

F(Y₄) =20,441838,

F(Z₄) = F(Y₃) = 20,443436.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₄.

Записываем новые координаты интервала:

a₅ = a₄ = 1,5,

b₅ = Z₄ = 1,545.

3. Находим длину нового интервала и сравниваем ее с e:

L₅ = b₅ – a₅ = 1,545 – 1,5 = 0,045.

Так как L₅ > e, то надо сделать еще один шаг.

1. Определяем координаты точек Y₅ и Z₅:

Z₅ = Y₄ = 1,528,

Y₅ = a₅ + b₅ – Z₅ = 1,5 + 1,545 – 1,528 = 1,517.

2. Вычисляем значение функции в точках Y₅ и Z₅:

F(Y₅) =20,44151,

F(Z₅) = F(Y₄) = 20,441838.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₅.

Записываем новые координаты интервала:

a₆ = a₅ = 1,5,

b₆ = Z₅ = 1,528.

4. Находим длину нового интервала и сравниваем ее с e:

L₆ = b₆ – a₆ = 1,528 – 1,5 = 0,028.

Так как L₆ > e, то надо сделать еще один шаг.

1. Определяем координаты точек Y₆ и Z₆:

Z₆ = Y₅ = 1,517,

Y₆ = a₆ + b₆ – Z₆ = 1,5 + 1,528 – 1,517 = 1,511.

2. Вычисляем значение функции в точках Y₆ и Z₆:

F(Y₆) =20,441564,

F(Z₆) = F(Y₅) = 20,44151.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₆.

Записываем новые координаты интервала:

a₇ = a₆ = 1,5,

b₇ = Z₆ = 1,517.

4. Находим длину нового интервала и сравниваем ее с e:

L₇ = b₇ – a₇ = 1,517 – 1,5 = 0,017.

L₇ < e, необходимая точность достигнута, решение найдено и равно

Х = (a₇ + b₇)/2 = (1,5 + 1,517)/2 = 1,5085.

Ответ: F(X)min = 20,441635, при Х = 1,5085.

Метод Фибоначчи.

Найдем необходимые числа Фибоначчи из неравенства:

F_n+1 < (b₀ – a₀ ) / e < F_n+2.

(b₀ – a₀ ) / e = (2 – 1,5) / 0,02 = 25 => F_n+2 = F₉ = 34, F_n+1 = F₈ = 21, F_n = F₇ = 13.

1. Определяем координаты точек Y₀ и Z₀:

Y₀ = a₀ + (b₀ – a₀)* F₇/ F₉, Y₀ = 1,5 + (2 – 1,5)*13 / 34 = 1,691;

Z₀ = b₀ – (Y₀ - a₀) = a₀ + b₀ - Y₀, Z₀ = 1,5 + 2 – 1,691 = 1,809.

2. Вычисляем значение функции в точках Y₀ и Z₀:

F(Y₀) = 20,511758,

F(Z₀) = 20,638618.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₀.

Записываем новые координаты интервала:

a₁ = a₀ = 1,5,

b₁ = Z₀ = 1,809.

4. Находим длину нового интервала и сравниваем ее с e:

L₁ = b₁ – a₁ = 1,809 – 1,5 = 0,309.

Так как L₁ > e, то надо сделать еще один шаг.

2.1 Считаем координаты точек Y₁ и Z₁:

Z₁ = Y₀ = 1,691,

Y₁ = a₁ + b₁ - Z₁ = 1,5 + 1,809 – 1,691 = 1,618.

2. Вычисляем значение функции в точках Y₁ и Z₁:

F(Y₁) = 20,465363,

F(Z₁) = F(Y₀) = 20,511758.

2. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₁.

Записываем новые координаты интервала:

a₂ = a₁ = 1,5,

b₂ = Z₁ = 1,691.

2. Находим длину нового интервала и сравниваем ее с e:

L₂ = b₂ – a₂ = 1,691 – 1,5 = 0,191.

Так как L₂ > e, то надо сделать еще один шаг.

3.1 Считаем координаты точек Y₂ и Z₂:

Z₂ = Y₁ = 1,618,

Y₂ = a₂ + b₂ – Z₂ = 1,5 + 1,691 – 1,618 = 1,573.

2. Вычисляем значение функции в точках Y₂ и Z₂:

F(Y₂) = 20,448956,

F(Z₂) = F(Y₁) = 20,465363.

2. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₂.

Записываем новые координаты интервала:

a₃ = a₂ = 1,5,

b₃ = Z₂ = 1,618.

2. Находим длину нового интервала и сравниваем ее с e:

L₃ = b₃ – a₃ = 1,618 – 1,5 = 0,118.

Так как L₃ > e, то надо сделать еще один шаг.

4.1 Определяем координаты точек Y₃ и Z₃:

Z₃ = Y₂ = 1,573,

Y₃ = a₃ + b₃ – Z₃ = 1,5 + 1,618 – 1,573 = 1,545.

2. Вычисляем значение функции в точках Y₃ и Z₃:

F(Y₃) =20,443436,

F(Z₃) = F(Y₂) = 20,448956.

2. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₃.

Записываем новые координаты интервала:

a₄ = a₃ = 1,5,

b₄ = Z₃ = 1,573.

2. Находим длину нового интервала и сравниваем ее с e:

L₄ = b₄ – a₄ = 1,573 – 1,5 = 0,073.

Так как L₄ > e, то надо сделать еще один шаг.

5.1 Определяем координаты точек Y₄ и Z₄:

Z₄ = Y₃ = 1,545,

Y₄ = a₄ + b₄ – Z₄ = 1,5 + 1,573 – 1,545 = 1,528.

5.2 Вычисляем значение функции в точках Y₅ и Z₅:

F(Y₄) =20,441838,

F(Z₄) = F(Y₃) = 20,443436.

5.3 Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₄.

Записываем новые координаты интервала:

a₅ = a₄ = 1,5,

b₅ = Z₄ = 1,545.

5.4 Находим длину нового интервала и сравниваем ее с e:

L₅ = b₅ – a₅ = 1,545 – 1,5 = 0,045.

Так как L₅ > e, то надо сделать еще один шаг.

1. Определяем координаты точек Y₅ и Z₅:

Z₅ = Y₄ = 1,528,

Y₅ = a₅ + b₅ – Z₅ = 1,5 + 1,545 – 1,528 = 1,517.

2. Вычисляем значение функции в точках Y₅ и Z₅:

F(Y₅) =20,44151,

F(Z₅) = F(Y₄) = 20,441838.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₅.

Записываем новые координаты интервала:

a₆ = a₅ = 1,5,

b₆ = Z₅ = 1,528.

4. Находим длину нового интервала и сравниваем ее с e:

L₆ = b₆ – a₆ = 1,528 – 1,5 = 0,028.

Так как L₆ > e, то надо сделать еще один шаг.

1. Определяем координаты точек Y₆ и Z₆:

Z₆ = Y₅ = 1,517,

Y₆ = a₆ + b₆ – Z₆ = 1,5 + 1,528 – 1,517 = 1,511.

2. Вычисляем значение функции в точках Y₆ и Z₆:

F(Y₆) =20,441564,

F(Z₆) = F(Y₅) = 20,44151.

3. Отбрасываем ту часть интервала, где минимума быть не может, то есть правее точки Z₆.

Записываем новые координаты интервала:

a₇ = a₆ = 1,5,

b₇ = Z₆ = 1,517.

4. Находим длину нового интервала и сравниваем ее с e:

L₇ = b₇ – a₇ = 1,517 – 1,5 = 0,017.

L₇ < e, необходимая точность достигнута, решение найдено и равно

Х = (a₇ + b₇)/2 = (1,5 + 1,517)/2 = 1,5085.

Ответ: F(X)min = 20,441635, при Х = 1,5085.

Сравнительная таблица.

\ Шаги Методы \	0	1	2	3	4	5
Дихотомии	[1,5; 2]	[1,5; 1,76]	[1,5; 1,64]	[1,5; 1,58]	[1,5; 1,55]	[1,5; 1,535]
“Зол. cечения”	[1,5; 2]	[1,5; 1,809]	[1,5; 1,691]	[1,5; 1,618]	[1,5; 1,573]	[1,5; 1,545]
Фибоначчи	[1,5; 2]	[1,5; 1,809]	[1,5; 1,691]	[1,5; 1,618]	[1,5; 1,573]	[1,5; 1,545]