Практическая работа 1. Анализ алгоритмов и программ. Задание
 Скачать 411.42 Kb.
|
Задание. Найти локальный минимум (максимум) функции вида f(x) =  на заданном интервале [a,b] с заданной точностью ε > 0 одним из способов:Методом «деления отрезка» пополам; Методом «золотого сечения»; Методом «Фибоначчи». Провестианализ разработанного алгоритма и программы и сравнить с аналогичным решением с помощью алгоритма «пассивного поиска». Вход: вид функции, границы отрезка, требуемая точность Выход (на экране и в файле): таблица пошаговых приближений, количество итераций (шагов поиска), значение точки минимума, значение функции в этой точке. Справочный материал к заданию. Время работы программы Директива препроцессора: include Начальное время работы программы:srand(time(0)) Конечное время работы программы(в секундах): clock()/1000.0 «Пассивный поиск» Графический вид для заданной в задаче функции:  Пример Программы, которая осуществляет поиск локального минимума функции на интервале  с шагом h = 1для функции f(x) = #include #include #include #include #include using namespace std; int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); srand(time(0)); // начальное время floatmin=0,x,y,k,h=1;// описание используемых в программе переменных intstep=0; for(x=-5.0;x<=-2.0;x=x+h)// основной цикл вычисления значений функции на { step++; // заданном промежутке y=x*x*x-x+exp(-x); printf(" %d. x = %fy = %f\n",step,x,y); // вывод на экран if(y { min=y; k=x; }; printf("минимальное значение функции на [-5,-2] \n"); printf("y = %f, точка минимума x = %f\n",min,k); printf("количество шагов = %d\n",step); cout<< "Время работы программы = " <<clock()/1000.0< } Ответы:
Очевидно, что с ростом количества вычислений пропорционально (с некоторым коэффициентом) растет и время работы программы. Легко подсчитать, что сложность алгоритма равна О(n). Также видно, что точные значения и функции, и точки, в которой эта функция достигает минимума можно определить только с некоторой погрешностью. Поэтому для вычисления экстремумов функций используют методы, которые определяют значение с некоторой, заранее заданной точностью. Например, чтобы приблизительное решение отличалось от «истинного» с погрешностью ε=0.001.Из примера «пассивного поиска» можно заметить, что искомый минимум лежит где-то в интервале |-3.679099  |.Метод «деления отрезка пополам» Поставим задачу: найти отрезок длины не более  , содержащий точку  локального минимума. Другими словами, найти точку  , с точностью до  приближающую точку :  . Д  ля удобства пояснения алгоритма метода обозначим исходный отрезок  =  (рис. 2.), возьмем  , построим точки  и вычислим  .Если  , то заключаем, что  . Если же  , то  .В первом случае в качестве приближения  точки возьмем  и примем обозначение  . Во втором случае – . Таким образом, в найден отрезок  , где содержится и указано приближение  . Если  , то поставленная задача решена. В противном случае отрезок следует подвергнуть аналогичному дроблению (схема 2) и продолжить процесс дробления до тех пор, пока на некотором шаге не выполнится неравенство  . При этом на отрезке  будет получено приближение  точка, в которой функция  достигает приближенное значение локального минимума:  .Приведенный алгоритм является классическим. Заметим, что в нем на каждом шаге необходимо произвести два вычисления значения функции: .  Пример. Определим с точностью  точку локального минимума функции  . Поиск будем производить на отрезке локализации  .Установим  .Первая итерация: вычислим  ,   ,  ;сравним  и  . Так как , то установим в качестве нового отрезка локализации отрезок  ;и так как условия Δ1= (и  ) не выполняются , то произведем очередную итерацию. Итерационный процесс будем продолжать до тех пор, пока для установленного вновь отрезка локализации данные условия не будут выполнены. Результаты итераций сведем в таблицу 1. Таблица 1
Из таблицы видно, что искомый результат на 14-ом шаге вычислений. При этом:  .Метод «золотого сечения» Отличие метода золотого сечения от метода деления отрезка пополам заключается в специальном разбиении отрезка локализации относительно его центра точками. Термин «золотое сечение» ввел Леонардо да Винчи. Принципы, заложенные в основу этого сечения, широко использовались при композиционном построении многих произведений искусства античности и эпохи Возрождения: особенно в живописи и архитектуре. Определение. Золотым сечениемотрезка  называется такое разбиение отрезка на две неравные части точками  и , что отношение длины всего отрезка  к длине его большей части  равно отношению длины большей части к длине  меньшей части:  . При этом (рис.2.5) точки и располагаются симметрично относительно центра отрезка и могут быть определены с помощью следующих соотношений: .Замечательно также, что точки и осуществляют золотое сечение не только всего отрезка , но и соответственно подотрезков  и  . Итерационный процесс локализации минимума функции на заданном числовом отрезке в данном методе ведется аналогично локализации минимума функции в методе деления отрезка пополам. В отличие от него точки  и  на очередном шаге итерации находятся по формулам: .Свойства золотого сечения позволяют также несколько упростить процедуру поиска точки локализации  на очередном шаге вычислений. Действительно, какой бы из отрезков  или  не был бы выбран за очередной отрезок локализации, точка (  , если  и  , если  ) совпадет с одной из точек  или  (рис 4). Поэтому на очередном шаге достаточно вычислить значение функции лишь в одной недостающей точке. Метод Фибоначчи Данный метод обеспечивает максимальное гарантированное сокращение отрезка локализации при заданном числе N вычислений функции и основан на использовании чисел Фибоначчи  таких, что:  для всех  при начальных значениях  Метод Фибоначчи состоит из  шагов. Вначале определяется такое число Фибоначчи , для которого справедливо условие где  .Очередной  -й шаг выполняется аналогично -й итерации метода деления отрезка пополам, но точки  и  находятся по формулам ,  где  – длина отрезка локализации  (рис.2.7).Аналогично методу деления отрезка пополам определяется новый отрезок локализации: если  , то  ;если  , то  .В первом случае за очередное приближение к точке минимума принимают , во втором случае – .  Примерная схема алгоритма:  Все 4 метода реализовать для поиска экстремальных точек в интервалах переменной x—[-5,-3], [0,3] —точки минимума и [-3,0] — точка максимума. |
