Метод Фибоначчи

Метод Фибоначчи отличается от метода золотого сечения лишь выбором первых двух симметричных точек и формул их пересчета и гарантирует более точное приближение к точке xmin за n-1 шаг, чем метод золотого сечения за то же количество шагов. Согласно методу Фибоначчи, на нулевом шаге первые две симметричные точки вычисляют по формулам. В последующем, после сокращения интервала путем отбрасывания неблагоприятной крайней точки, одна из точек пересчитывается по одной из соответствующих формул. Выполняется n-1 шаг, при k = 1, 2, ..., n – 1. На последнем шаге две симметричные точки сливаются в одну, которая и принимается за точку минимума. за три вычисления функции (n=2) получают точку минимума с погрешностью, не превышающей 1/6 первоначального интервала, пять вычислений (n=4) – 1/16, девять (n=8) – 1/110. при достаточно больших n вычисления по методу Фибоначчи и золотого сечения начинаются практически из одной и той же пары симметричных точек.

Метод последовательного перебора

Этот метод не требует предварительного определения местоположения точки минимума. Идея метода состоит в том, что, спускаясь из точки x0 с заданным шагом h в направлении уменьшения функции, устанавливают интервал длиной 2h, на котором находится минимум, который затем последовательно уточняют, повторяя спуск с последней точки, уменьшив шаг и изменив его знак, пока не будет достигнута заданная точность (некое подобие затухающего маятника). Задаются x0, начальный шаг h, (h>0) и погрешность. Вычисляем f0.Определяем направление убывания функции и тд находим точки. Скорость сходимости данного метода существенно зависит от удачного выбора начального приближения x0 и шага h. Шаг h следует выбирать как половину оценки расстояния от x0 до предполагаемого минимума.

Метод квадратичной параболы

Для нахождения точки минимума с заданной точностью задают 3 точки x1, x2, x3 для которых выполняются условия f(x2)<f(x1) и f(x2)<f(x3). На этом интервале функцию аппроксимируют квадратичной параболой, минимум ко- торой известен. Cуть метода в следующем. Для заданных трех точек x1, x2, x3 вычисляются значения функции в них f1, f2, f3. Через эти точки проводится квадратичная парабола. Парабола имеет минимум в точке zm= - q/(2p). Следовательно, можно аппроксимировать положение минимума функции значением xm=x3+zm и, если точность не достигнута, следующий спуск производить, используя эту новую точку и две предыдущие, отбросив одну наихудшую точку. Получается последовательность xm1, xm2, xm3, … , сходящаяся к точке xmin. Данный метод сходится очень быстро и является одним из наилучших методов спуска. Следует, однако, отметить, что при очень малых расчет по приведенным здесь формулам для p и q вблизи минимума может привести к появлению большой погрешности из-за потери значащих цифр при вычитании близких чисел. Поэтому разные авторы предлагают свои эквивалентные формулы, вычисления по которым более устойчивы. Кроме того, в алгоритм вносятся некоторые поправки, позволяющие предусмотреть различные неприятные ситуации – переполнение разрядной сетки, деление на нуль, уход от корня.