Метод дихотомии и золотого сечения

Введение

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

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

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

Современной формой методики математического моделирования, которая основана на мощнейшей вычислительной базе, то есть, на электронных вычислительных машинах (ЭВМ) и программном обеспечении, способном выполнять алгоритмы численного решения, является вычислительный эксперимент, выступающий в качестве новейшего теоретического метода исследования различных явлений и процессов. Эта теоретическая методика включает главные черты методов экспериментальных исследований, только эксперименты производятся не над реальными объектами, а над их математическими моделями, а в качестве экспериментальной установки используется компьютерное оборудование.

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

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

Чтобы выбрать подинтервал для хорошо дифференцируемой функции, следует вычислить в точке «c» производную и выполнить анализ её знака. Если значение производной функции больше нуля, то значит точка минимума функции расположена слева от точки «c», то есть на отрезке [а,с]. Если же значение производной функции меньше нуля, то это означает, что точка минимума функции расположена справа от точки «c», то есть на отрезке [с,b]. А если производная функции равняется нулю, то это означает, что определена точка минимума функции.

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

Здесь h>0 является малой величиной.

Далее следует вычислить ординату:

f0(с+h).

В случае, когда приращение функции меньше нуля:

Рисунок 1. Формула. Автор24 — интернет-биржа студенческих работ

то точка минимума функции расположена справа от точки «c», то есть находится на отрезке [с,b].

Если же приращение функции больше нуля:

Рисунок 2. Формула. Автор24 — интернет-биржа студенческих работ

то точка минимума функции находится слева от точки «c», то есть расположена на отрезке [a,c].

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

После того, как сделан выбор под интервала, в котором расположен минимум функции, к примеру, [с,b], следует переопределить левую границу а=с (при выборе [а,с] следует изменить правую границу b=с).

Затем нужно проверить величину отрезка, то есть значение разности «b-a», и если она меньше величины допустимой ошибки, то минимум функции найден. В противном случае нужно снова поделить отрезок [b-a] пополам и опять определить, в каком из подинтервалов находится точка минимума.

Метод золотого сечения

Метод золотого сечения может быть использован только с унимодальными функциями. Метод золотого сечения был открыт Евклидом, и заключается в разбиении интервала [а,b] при помощи точки x1 на два отрезка таким образом, чтобы отношение большей части к длине всего интервала равнялось отношению меньшего отрезка к большей оставшейся части, как показано ниже:

Рисунок 3. Формула. Автор24 — интернет-биржа студенческих работ

Необходимо представить интервал [а,b] как совокупность двух отрезков:

b – a = x1 – a + b - x1 (2)

Если разделить уравнение (2) на (b-а), то получится следующее выражение:

(x1 – a)/(b – a) + (b - x1)/ (b – a) = 1

После ряда преобразований можно провести золотое сечение относительно точки «а», которое отображается следующей формулой:

(x2 – a)/(b – a) = (b – x2)/(x2 – a) = τ (3)

Из уравнения (3) можно получить формулу для расчёта точки x2:

x2 = a + τ(b – a)

Следует отметить, что точка x1 производит золотое сечение интервала [а,x2], а точка x2 выполняет золотое сечение интервала [x1,b].

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