Ввод a, b, 

h := (b – a) / k

x := x+h

f_min := f(x)

h := -h/4

да

нет

Вывод значений xmin, fmin

Рис. 7.1. Алгоритм поиска минимума функции одной переменной методом последовательного приближения.

f_min := f(x_min)

Должно выполняться

условие - b > a,  > 0.

x_min := b

x_min := x+4h

да

нет

Значение k находится в пределах от 5 до 10

x := a

f_min := f(x)

нет

Пример 1. Найти минимум функции методом равномерного приближения с точностью 0.025.

Имеем , . Следовательно, данная функция во всей области ее определения имеет только один локальный (он же и глобальный) минимум. Поскольку при x=0 производная функции отрицательна (равна -6), то в ней наша функция еще убывает. В точке x=5 она положительна (равна +4), то в ней она уже возростает. Следовательно, между этими точками и находится искомый нами минимум функции. Поэтому, примем a =0 и b = 5. По ним вычислим h=1. Дальнейшие вычисления будем проводить в Excel и результаты вычислений представим в виде таблицы.

i	x	f(x)	h
0	0,0000	-5,0000	1,0000
1	1,0000	-10,0000	1,0000
2	2,0000	-13,0000	1,0000
3	3,0000	-14,0000	1,0000
4	4,0000	-13,0000	-0,2500
5	3,7500	-13,4375	-0,2500
6	3,5000	-13,7500	-0,2500
7	3,2500	-13,9375	-0,2500
8	3,0000	-14,0000	-0,2500
9	2,7500	-13,9375	0,0625
10	2,8125	-13,9648	0,0625
11	2,8750	-13,9844	0,0625
12	2,9375	-13,9961	0,0625
13	3,0000	-14,0000	0,0625
14	3,0625	-13,9961	-0,0156
15	3,0469	-13,9978	-0,0156
16	3,0313	-13,9990	-0,0156
17	3,0156	-13,9998	-0,0156
18	3,0000	-14,0000	-0,0156
19	2,9844	-13,9998

Так как на 19-м шаге при очередной смене величины шага его абсолютное значение оказалось меньше заданной точности - процесс приближения прекращен и получены следующие результаты

x_min = 3.000, f_min = -14.000.

Метод дихотомии (другое название - метод половинного деления) предназначен для поиска локального экстремума функции на заданном интервале. Способ достижения цели - в некотором смысле аналогичен ранее описанному методу половинного деления при поиске корней нелинейных уравнений. Исходный отрезок [a, b] делят пополам точкой с с координатой . После этого из двух образовавшихся половинок отрезка одну отбрасывают, а имеено ту, в середине которой значений функции меньше (при поиске максимума) или больше (при поиске минимума). Для этого находят значения функции в точках и , сравнивают их между собой и определяют “отбрасываемую” половину отрезка. Отбрасывание производят посредством переноса в среднюю точку отрезка (точку с) другого конца отбрасываемого отрезка (т.е. точки a или b). Так производят до тех пор, пока длина оставшегося отрезка станет меньшей заданной точности. В таком случае за найденное приближенное значение точки достижения функцией экстремума принимают средину этого (последнего) отрезка.

Процес поиска значения экстремума этим методом удобно проводить с занесением результатов расчетов в таблицу следующего вида

i	a	b	c	ca	f(ca)	cb	f(cb)	b-a
0
1
…

,

Подробный алгоритм поиска экстремума по этому методу приведен на рис. 7.2.

Пример 2. Найти минимум функции методом половинного деления с точностью 0.02.

Определение интервала поиска обосновано в примере 1, но мы его несколько увеличим для наглядности метода. Решение примера приведем в таблице.

i	a	b	c	ca	f(ca)	cb	f(cb)	b-a
0	0,000	7,000	3,500	3,490	-13,7599	3,510	-13,7399	7,000
1	0,000	3,500	1,750	1,740	-12,4124	1,760	-12,4624	3,500
2	1,750	3,500	2,625	2,615	-13,8518	2,635	-13,8668	1,750
3	2,625	3,500	3,063	3,053	-13,9972	3,073	-13,9947	0,875
4	2,625	3,063	2,844	2,834	-13,9724	2,854	-13,9786	0,438
5	2,844	3,063	2,953	2,943	-13,9968	2,963	-13,9986	0,219
6	2,953	3,063	3,008	2,998	-14,0000	3,018	-13,9997	0,109
7	2,953	3,008	2,980	2,970	-13,9991	2,990	-13,9999	0,055
8	2,980	3,008	2,994	2,984	-13,9997	3,004	-14,0000	0,027
9	2,994	3,008	3,001	2,991	-13,9999	3,011	-13,9999	0,014

Ответ - x_min = 3.00, f_min = -14.000.