f a f d , или к точке b, если f a f d . Будет получено наименьшее значение, не являющееся локальным минимумом (глобальный минимум).

Общая схема метода

Даны отрезок [a, d] и f x . Надо найти точку глобального минимума xmin

сточностью .

1)Найдём b a d a / 3 и c a 2 d a / 3 .

dd .

4)Переходим к п.1.

Здесь равенства подразумеваются как операторы присваивания.

Если поменять всюду знаки неравенств, то в процессе вычислений придём к точке максимума xmax . В случае f b f c можно оставить любую часть – или

[a, c], или [b, d]. Для компьютера числа с плавающей запятой типа REAL никогда не равны, и результат выбора будет случаен.

Метод прост, но сходится очень медленно – ещё медленнее, чем метод деле-

где d a – длина начального отрезка.

Пример. Найдём с точностью 0,1 точку глобального минимума функции f x x2 x на отрезке 0; 1 . Вычисления проведём с одной запасной цифрой.

1-й шаг. Длина отрезка 0; 1 равна 1, треть длины равна 1/3. Отрезок делится на три части точками a 0, b 0,33, c 0,67, d 1 .

Находим f 0,33 0,332 0,33 0,22 и f 0,67 0,672 0,67 0,22 .

Поскольку f 0,33 f 0,67 , можно взять как 0; 0,67 , так и 0,33; 1 .

2-й шаг. Возьмём отрезок 0; 0,67 . Треть его длины равна 0,22, поэтому те-

Поскольку f 0,22 f 0,44 , оставляем участок 0,22; 0,67 как новый отрезок.

Поскольку f 0,47 f 0,57 , считаем, что xmin 0,47 0,5 . Ответ: xmin 0,5 с точностью 0,1.

Легко видеть, что точка x = 0,5 – точное решение задачи как вершина параболы y x 2 x . Поэтому при выборе xmin 0,47 или xmin 0,57 результат был бы только хуже.

Схема неудобна тем, что каждый раз приходится искать 2 новые точки и 2 новых значения функции. Оказывается, если делить отрезок не на равные части, а в отношении 0,382 : 0,236 : 0,382, то при удалении участка [c, d] бывшая точка b на следующем шаге всегда будет становиться точкой c.

Наоборот, бывшая точка c станет точкой b, если удалить участок [a, b]. Тогда достаточно найти точку на расстоянии 0,382(d–a) от a или от d соответственно и найти значение функции в этой точке, а потом сравнить со значением, уже известным из предыдущего шага.

Указанное свойство объясняется тем, что точка b делит отрезок [a, c] в той же пропорции, что точка c – отрезок [a, d], а именно в отношении 0,5 5 1 0,618 . Такая пропорция называется "золотым сечением". Таким образом можно примерно в 2 раза ускорить вычисления, хотя число шагов почти не уменьшается. Уменьшается же число действий на каждом шаге. Для достижения точности

Общая схема метода золотого сечения

Даны отрезок [a, d] и f x . По-прежнему ищем точку глобального минимума xmin с точностью .

50

Иначе (если f b f c ) находим a b, b c, d d, c d a b ;

4)переходим к п.2.

Всхеме в п.3 при пересчёте b и c учитываются новые значения других точек. Формулы b a 0,382 d a и b a d c равносильны, поскольку b и c от-

стоят на одинаковом расстоянии от a и от d соответственно. Также равносильны формулы c a 0,618 d a и c d b a , то есть c d a b .

Пример. Найдём точку глобального минимума функции f x x 2 3x 3 на отрезке [0, 2] с точностью 0,1. Вычисления проведём с двумя запасными цифрами для наглядности.

Решение. Шаг 1. Длина отрезка [0, 2] равна 2. Делим его на три части точка-

ми a 0 , b 2 0,382 0,764 , c 2 0,618 1,236 , d 2 . Находим

Шаг 2. Отрезок 0,764; 2 делится на три части точками

a 0,764, b 1,236, d 2, c 2 0,764 1,236 1,528 .

Считаем f 0,764 1,292 (уже известно) и f 1,528 1,5282 31,528 3 0,751.

Поскольку f 1,236 f 1,528 , оставляем участок 1,236; 2 в качестве нового отрезка.

Шаг 3. Отрезок 1,236; 2 делится на три части точками

a 1,236, b 1,528, c 2 1,236 1,528 1,708, d 2 .

Поскольку f 1,528 f 1,708 , оставляем 1,236; 1,708 .

Шаг 4. Отрезок 1,236; 1,708 делится на три части точками

a 1,236, b 1,236 1,708 1,528 1,416, c 1,528, d 1,708

Вычислим f 1,416 1,4162 31,416 3 0,757 и учтём, что f(1,528) = 0,751.

Поскольку f 1,416 f 1,528 , оставляем 1,416; 1,708 для следующего шага. Шаг 5. Отрезок 1,416; 1,708 делим точками

51

a 1,416, b 1,528, c 1,708 1,416 1,528 1,596, d 1,708.

ваем xmin 1,528, округлив до 1,5. Ответ: xmin 1,5 с точностью 0,1.

Указывать в ответе 1,528 или 1,53 нет смысла, поскольку цифры после 5 неверные. Точное решение примера – также 1,5. Совпадение приближённого решения с настоящим при низкой точности вычислений случайно и объясняется отсутствием цифр после 5 в точном решении.

Замечание. При замене функции на f x x 2 3,008x 3 и решении его с точностью 0,1 или 0,01 мы бы получили (после округления) то же решение xmin 1,5, но погрешность по сравнению с точным решением 1,554 составила бы 0,004 .

§3. Численное интегрирование

3.1.Основные трудности точного интегрирования

Для функций f x , непрерывных на отрезке a; b , существует определённый интеграл ab f x dx . Если известна первообразная функция F(x), для которой во

b

f x dx F b F a .

a

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

Кроме того, первообразные многих функций вообще нельзя указать аналитически в виде элементарных функций. Хорошо известны интегралы