ДОПОЛНЕНИЕ

Алгоритм отыскания экстремальных значений функции, использующий только значения этой функции

Предположим, что функция задана на сегменте мы располагаем значениями этой функции в узлах сетки, получающейся при делении сегмента на равных частей

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

При этом мы будем предполагать, что выполнены следующие два условия: 1) функция имеет на сегменте единственную точку минимума с; 2) при функция убывает на сегменте (т. е. убывает слева от точки минимума), а при функция возрастает на сегменте (т. е. возрастает справа от точки минимума).

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

Мы сейчас укажем алгоритм построения стягивающейся системы сегментов, содержащих точку с минимума функции

Остановимся на построении первого сегмента стягивающейся системы, имея в виду, что все последующие сегменты этой системы строятся по тому же принципу, что и первый ее сегмент.

Разделим сегмент при помощи точек на четыре равных частичных сегмента .

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

Так как функция имеет на сегменте единственную точку минимума с, то указанная точка минимума с принадлежит одному из четырех частичных сегментов

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

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

Но тогда можно утверждать, что тот частичный сегмент, который содержит точку минимума с, является либо самым правым сегментом убывания, либо самым левым сегментом возрастания, либо, наконец, частичным сегментом, на концах которого имеет равные значения.

Сформулированное утверждение позволяет указать алгоритм построения первого сегмента стягивающейся системы сегментов каждый из которых содержит точку минимума с.

Рассмотрим четыре возможных случая.

1) Среди частичных сегментов есть сегмент, на концах которого имеет равные значения. В этом случае этот сегмент содержит точку минимума с, и мы примем его за первый сегмент стягивающейся системы.

2) Все частичные сегменты являются сегментами убывания. В этом случае точка минимума с лежит на самом правом из частичных сегментов, т. е. на сегмецте и мы примем этот сегмент за

3) Все частичные сегменты являются сегментами возрастания. В этом случае точка минимума лежит на самом левом из частичных сегментов, т. е. на сегменте и мы примем этот сегмент за

4) Среди частичных сегментов имеются как сегменты убывания, так и лежащие правее их сегменты возрастания. В этом случае можно утверждать, что точка минимума с лежит на объединении самого правого сегмента убывания и самого левого сегмента возрастания. Указанное объединение двух частичных сегментов мы и примем за

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

Второй сегмент этой системы строится, отправляясь от точно так же, как сегмент строился, отправляясь от По такому же принципу, отправляясь от сегмента строится сегмент стягивающейся системы.

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

Аналогично строится алгоритм отыскания точки максимума функции имеющей на сегменте единственную точку максимума с при условии, что эта функция возрастает слева от с при и убывает справа от с при