Алгоритм метода поразрядного поиска

Шаг 1. Ввести исходные данные: a, b, e.

Шаг 2. Выбрать начальный шаг D = . Положить x0 = a. Вычислить f(x0).

Шаг 3. Положить x1 = x0 + D. Вычислить f(x1).

Шаг 4. Сравнить f(x0) и f(x1). Если f(x0) > f(x1), то перейти к шагу 5, иначе – к шагу 6.

Шаг 5. Положить x0 = x1 и f(x0) = f(x1).

Проверить условие x0 Î (a, b), т. е. a < x0 < b.

Если условие выполнено, перейти к шагу 3, иначе –к шагу 6.

Шаг 6. Проверка на окончание поиска.

Если êD ê£ e, то вычисления завершить, положив

x*» x0, f(x*)» f(x0), иначе – перейти к шагу

Шаг 7. Изменение направления и шага поиска.

Положить x0 = x1 и f(x0) = f(x1), D = – .

Перейти к шагу 3.

Реализация данной задачи в пакете MathCAD 14.

Данную задачу решаем для следующей функции:

Задание функции, реализующей метод поразрядного поиска с заданной точностью:

В результате решения данной задачи был найден минимум x* = -0.998, значение функции f(x*) = 0, количество итераций n = 18.

Метод дихотомии.

Найти минимум функции методом деления отрезка пополам с заданной точностью.В основе этого метода лежит свойство унимодальной функции, благодаря которому можно сокращать отрезок локализации точки минимума.

Пусть f(x) – непрерывная и унимодальная на отрезке [a, b] функция, принимающая во всех точках этого отрезка конечные значения. Пусть число пробных точек x1, x2, …, xn конечно, и для определения каждой точки xk можно использовать информацию о значениях функции во всех предыдущих точках x1, x2, …, xk – 1. Положим a0 = a, b0 = b. Середина отрезка [a, b] = [a0, b0] находится в точке . Выберем две симметричные точки x1 = , x2 = Величина d, удовлетворяющая условию 0 < d < b – a, является параметром метода, как правило, d – малая величина.Вычислим значения функции в выбранных точках: f(x1) и f(x2). Определим новый отрезок локализации [a1, b1] следующим образом:

если f(x1) £ f(x2), то a1 = a0, b1 = x2;

если f(x1) > f(x2), то a1 = x1, b1 = b0.

Далее процедура деления отрезка [a1, b1] повторяется.

Деление продолжают до тех пор, пока половина длины отрезка [an, bn] не станет меньше заданной точности решения задачи e, e > d, т. е. пока не выполнится неравенство

< e. Тогда за приближение x* принимают середину отрезка [an, bn], т.е. x*» .