2.Примеры реализации алгоритмов в среде Excel. Задача 1.

Постановка задачи. Cоставить алгоритм нахождения в заданном интервале [a, b] с требуемой точностью  экстремума функции f(x) одной переменной методом половинного деления.

Алгоритм метода.

Начальный этап. Выбрать константу  > 0, допустимую конечную длину интервала l > 0, начальный интервал [a₀, b₀]. Задать k = 0 и перейти к основному этапу.

Основной этап. Шаг 1. Если b_k - a_k < l то остановиться. Точка минимума принадлежит интервалу [a_k, b_k]. Иначе вычислить

и перейти к шагу 2.

Шаг 2. Если f(x_k) < f(y_k), то a_k+1 = a_k и b_k+1 = y_k. В противном случае положить a_k+1 = y_k и b _k+1= b_k. Заменить k = k + 1 и перейти к шагу 1.

Реализация метода. На рис. 2.1 приведено содержание ячеек рабочего листа, используемых для осуществления первых двух итераций при нахождении данным методом минимума функции f(x) = (x - 2)² + 7 при начальном интервале [‑20, 20], конечной длине интервала 0,005 и константе различимости 0,001.

Рис. 2.1. Содержание ячеек при реализация метода половинного деления

Результаты решения задачи для условий, описанных выше, приведены на рис. 2.2.

Рис. 2.2. Результаты поиска минимума функции методом половинного деления

Задача 2.

Постановка задачи. Cоставить алгоритм нахождения с требуемой точностью  экстремума функции f(X) двух переменной симплекс-методом с изменяемой длиной ребра. Начальное расположение симплекса – одна из вершин в начале координат.

Алгоритм метода.

1. Начальный этап. Расчет координат симплекса в соответствии с таблицей

№ вершины	x1	x2
1	0	0
2	P	Q
3	Q	P

где , .

Задать k = 0.

2. Определение вершин с максимальным и минимальным значением функции. Определяют те вектора X многогранника, которые дают максимальное и минимальное значение f(X), а именно

f(X_h^(k)) = maxf(X₁^(k)), ..., f(X_n+1^(k))};

f(X_l^(k)) = minf(X₁^(k)), ..., f(X_n+1^(k))}.

3. Расчет координат центра тяжести. Координаты центра тяжести рассчитываются по формуле

, j =1, …, n,

где индекс j обозначает координатное направление.

Если на k-1 этапе произошла редукция, то перейти к шагу 5, иначе к шагу 4.

4. Определение зацикливания. Зацикливание происходит в случае, если номера вершин с максимальным значением f(X) совпадают на k-ом и (k-1)-ом шагах, т.е.

h^(k) = h^(k-1).

Если зацикливание не обнаружено, то переход к этапу 5, в противном случае происходит проверка условия окончания поиска

В случае выполнения условия переход к этапу 7, иначе к этапу 6.

5. Отражение. Представляет проектирование X_h^(k) через центр тяжести в соответствии с соотношением

.

Установить k = k + 1 и перейти к этапу 2.

6. Редукция. Расчет координат вершин симплекса осуществляется в соответствии с формулой

X_i^(k+1) = X_l^(k) + 0,5(X_i^(k) - X_l^(k)), i = 1, …, n + 1.

Установить k = k + 1 и перейти к шагу 2.

7. Выдача полученных результатов. В качестве решения задачи взять вершину с минимальным значением f(X).

Реализация метода. На рис. 2.3 приведено содержание ячеек рабочего листа, используемых для осуществления первых двух итераций при нахождении данным методом минимума функции f(X) = (x₁ - 2)² + (x₂ - 3)² при начальной длине ребра, равной 1, и точности поиска 0,01

Результаты решения задачи для условий, описанных выше, приведены на рис. 2.4.