2.2. Метод равномерного поиска

Метод относится к параллельным стратегиям и заключается в следующем:

1. Задаётся начальный интервал неопределённости L₀=[a₀, b₀] и количество N вычислений функции.

2. L₀ разбивается на N+1 равных интервалов точками x_i=a₀+i вычисления функции.

3. Вычисляются значения функции в найденных точках: f(x_i), i=1, 2, …, N.

4. Среди точек x_i, i=1, 2, …, N находится точка x^* такая, в которой функция принимает наименьшее значение: f(x_k)= .

Пример II. Решить задачу

f(x)=x²6x+14min

методом равномерного поиска.

Решение. 1. Задаём начальный интервал неопределённости L₀=[1; 7] (см. решение примера I) и количество N=11 вычислений функции.

2. Найдём точки x_i=a₀+i =1+i =1+0,5i вычислений функции: x₁=1,5, x₂=2, x₃=2,5, x₄=3, x₅=3,5, x₆=4, x₇=4,5, x₈=5, x₉=5,5, x₁₀=6, x₁₁=6,5.

3. Вычислим значения функции в найденных точках: f(1,5)=7,25, f(2)=6, f(2,5)=5,25, f(3)=5, f(3,5)=5,25, f(4)=6, f(4,5)=7,25, f(5)=9, f(5,5)=11,25, f(6)=14, f(6,5)=17,25,

4. В точке x₄=3 функция принимает наименьшее значение: f(3)=5minf(x).

Ответ: f_min(x)f(3)=5.

2.3. Метод деления интервала пополам

Метод относится к последовательным и в общих чертах заключается в том, что на очередном шаге интервал делится на четыре равные части и, сравнивая в точках деления значения функции, оставляется та половина интервала, которая содержит точку с наименьшим значением. Процесс деления продолжается до тех пор, пока длина интервала не окажется меньше некоторой заданной величины . Более подробно:

1. Задать начальный интервал неопределённости L₀=[a₀, b₀] и >0  точность.

2. Положить k=0.

3. Разбиваем интервал [a_k, b_k] на 4 равные части точками = (середина интервала), y_k= (середина интервала [a_k, ]), z_k= (середина интервала [ , b_k])

4. Вычислить значения f(y_k), f( ), f(z_k) функции f(x) в точках y_k, , z_k соответственно.

5. Сравнить значения f(y_k) и f( ):

а) если f(y_k)<f( ), то полагаем b_k+1= , a_k+1=a_k (из рассмотрения исключается интервал ( , b_k]), =y_k (y_k становится серединой нового интервала). Перейти к шагу 7.

б) если f(y_k)f( ), то перейти к шагу 6.

6. Сравнить f(z_k) и f( ):

а) если f(z_k)<f( ), то полагаем a_k+1= , b_k+1=b_k, =z_k (из рассмотрения исключается интервал [a_k, ), z_k становится серединой нового интервала). Перейти к шагу 7.

б) если f(z_k)f( ), то полагаем a_k+1=y_k, b_k+1=z_k, = (из рассмотрения исключаются интервалы [a_k, y_k), (z_k, b_k], становится серединой нового интервала. Перейти к шагу 7.

7. Вычислить |b_k+1a_k+1| и проверить условие окончания:

а) если |b_k+1a_k+1|<, то поиск завершается, x*[b_k+1, a_k+1] и x* ;

б) если |b_k+1a_k+1|, то положить k=k+1 и перейти к шагу 3.

Пример III. Решить задачу методом деления пополам:

f(x)=x²6x+14min.

Решение. 1. Задаём начальный интервал неопределённости L₀=[1; 7] (см. решение примера I) и =1  точность.

2. Положим k=0.

3.0. Разбиваем интервал [1; 7] на 4 равные части точками = =4, y₀= =2,5, z₀= =5,5.

4.0. Вычисляем значения f(y₀)=5,25, f( )=6, f(z₀)=11,25 функции f(x) в точках y₀, , z₀ соответственно.

5.0. Сравним значения f(y₀) и f( ). Так как f(y₀)=5,25<6=f( ), то полагаем b₁= =4, a₁=a₀=1 и переходим к шагу 7.

7.0. Вычисляем |b₁a₁|=3>. Полагаем k=1 и переходим к шагу 3.

3.1. Разбиваем интервал [1; 4] на 4 равные части точками = =2,5, y₁= =1,75, z₁= =3,25.

4.1. Вычисляем значения f(y₁)=6,5625, f( )=5,25, f(z₁)=5,0625 функции f(x) в точках y₁, , z₁ соответственно.

5.1. Сравним значения f(y₁) и f( ). Так как f(y₁)=6,5625>5,25=f( ), то переходим к шагу 6.

6.1. Сравним f(z₁) и f( ). Так как f( )>f(z₁), то полагаем a₂= =2,5, b₂=b₁=4, =z₁=3,25 и переходим к шагу 7.

7.1. Вычисляем |b₂a₂|=1,25>. Полагаем k=2 и переходим к шагу 3.

3.2. Разбиваем интервал [2,5; 4] на 4 равные части точками = =3,25, y₂= =2,875, z₂= =3,625.

4.2. Вычисляем значения f(y₂)=5,015625, f( )=5,0625, f(z₂)=5,390625 функции f(x) в точках y₂, , z₂ соответственно.

5.2. Сравним f(y₂) и f( ). Так как f(y₂)<f( ), то полагаем a₃=a₂=2,5; b₃= =3,25, =y₂=2,875 и переходим к шагу 7.

7.2. Вычисляем |b₃a₃|=0,75<. Поиск завершается: x* =2,875.

f_min(x)f(2,875)=5,015625.

Ответ: f_min(x)5,015625.