12248

Прямые методы минимизации функции одной переменной

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 1. Прямые методы минимизации функции одной переменной. В данной работе рассматриваются методы решения поставленной задачи не использующие вычисления производных прямые методы минимизации. Постановка задачи: Требуется найти безусловный ми...

Русский

2013-04-24

1 MB

69 чел.

Лабораторная работа 1.

Прямые методы минимизации функции одной переменной.

В данной работе рассматриваются методы решения поставленной задачи, не использующие вычисления производных (прямые методы минимизации).

Постановка задачи: Требуется найти безусловный минимум функции одной переменной f(x), т.е. такую точку , что . Значение точки минимума вычислить приближенно с заданной точностью ε.

Предполагается, что для функции f(x) предварительно определен начальный интервал неопределенности L0 = [a0, b0] (имеется априорная информация о положении точки минимума, а именно то, что точка минимума , но более точное положение ее неизвестно), причем на заданном интервале функция является унимодальной (для любых функция монотонно убывает, для любых функция монотонно возрастает).

Метод равномерного поиска (метод перебора).

Стратегия поиска: Метод относится к пассивным стратегиям.

Задается количество интервалов N, на которое разбивается исходный интервал
L0 = [a0, b0]. Вычисления производятся в N +1 равноотстоящих друг от друга точках. Путем сравнения величин f(xi), i = 0,1,…,N находится точка xk, в которой значение функции наименьшее. Искомая точка минимума считается заключенной в интервале [xk-1, xk+1].

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Задать количество интервалов разбиения .
  3. Вычислить точки ,  .
  4. Вычислить значения функции в найденных точках: f(xi) , .
  5. Среди точек найти такую, в которой функция принимает наименьшее значение: .
  6. Выбрать приближенно , . Поиск завершен.

Метод поразрядного поиска.

Стратегия поиска: Метод является усовершенствованным вариантом метода перебора. В этом методе перебор точек интервала неопределенности L0 происходит сначала с шагом , i = 0, 1, … (при этом точка x0 совпадает с концом отрезка a0) до тех пор, пока не выполнится условие , или пока очередная из точек xi не совпадет с концом отрезка b0. После этого шаг уменьшается в несколько (2, 4, 10) раз, и производится перебор точек в противоположном направлении (с новым шагом) до тех пор, пока значения f(x) не перестанут уменьшаться, или очередная точка не совпадет с концом отрезка a0. Процедура уменьшения шага и смены направления перебора на противоположное повторяется несколько раз. Поиск прекращается, если текущий шаг дискретизации при последнем проходе алгоритма  не превосходит заданной точности .

Следует отметить, что в данном методе интервал неопределенности может быть полубесконечным: L0 = [a0, +∞) или L0 = (-, b0] (во втором случае начальное направление перебора выбирается в сторону уменьшения значений x).

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Задать начальный шаг дискретизации .
  3. Положить i = 1, x0 = a0. Вычислить значение функции  f(x0).
  4. Определить точку xi = xi-1+Δ и значение функции  f(xi).
  5. Если и , то положить i = i +1 и вернуться к шагу 4.
  6. Задать новый шаг дискретизации .
  7. Если , то перейти к шагу 12.
  8. Вычислить точку xi = xi-1-Δ и значение функции  f(xi).
  9. Если и , то положить i = i +1 и вернуться к шагу 8.
  10. Задать новый шаг дискретизации и перейти к шагу 4.
  11. Если , то перейти к шагу 12.
  12. Выбрать приближенно , . Поиск завершен.

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

Стратегия поиска: Метод относится к последовательным стратегиям и является одним из вариантов метода исключения отрезков.

Алгоритм опирается на анализ значений функции в двух точках. Для их нахождения текущий интервал неопределенности делится пополам и в обе стороны от середины откладывается по по δ/2, где δ < 2ε – малое положительное число. По результатам сравнения значений функции в этих точках из дальнейшего рассмотрения исключается часть текущего интервала неопределенности: из трех отрезков, полученных в результате разбиения интервала, выбирается тот отрезок, который не содержит точку с меньшим значением функции, и исключается из дальнейшего рассмотрения. Условия окончания итераций для всех вариантов метода исключения отрезков стандартные: поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины точности ε.

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Выбрать δ < .
  3. Положить k = 0 (k – номер итерации).
  4. Вычислить длину текущего интервала L0 = b0 - a0.
  5. Вычислить точки , и значения функции f(x1), f(x2).
  6. Сравнить f(x1) и f(x2).
  7. Если , то положить ak+1 = ak, bk+1 = x2.

  В противном случае () положить ak+1 = x1, bk+1 = bk.

  1. Вычислить длину нового интервала неопределенности Lk+1 = bk+1- ak+1.
  2. Если Lk+1 > ε, то перейти к шагу 5.
  3. Выбрать приближенно , . Поиск завершен.

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

Стратегия поиска: Метод относится к последовательным стратегиям и является одним из вариантов метода исключения отрезков.

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

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Положить k = 0 (k – номер итерации).
  3. Вычислить длину текущего интервала L0 = b0 - a0.
  4. Вычислить значение и точки , .
  5. Вычислить значения функции , .
  6. Сравнить значения , .
  7. Если , то положить , , , .
    В противном случае () положить , , , .
  8. Вычислить длину нового интервала неопределенности Lk+1 = bk+1- ak+1.
  9. Если Lk+1 > ε, то перейти к шагу 5.
  10. Выбрать приближенно , . Поиск завершен.

Вопросы и задания

  1. Реализовать функции для трех методов из приведенных выше: метода перебора, метода поразрядного поиска, метода дихотомии (либо метода золотого сечения вместо метода дихотомии).
  2. Выбрать для выполнения лабораторной работы тестовую функцию, номер которой соответствует последней цифре номера Вашего компьютера
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13. Для выбранной функции и для каждого реализованного метода изучить зависимость скорости работы (числа вычислений функции N) от заданного значения точности ε. Для этого необходимо определить число вычислений функции N при нескольких (от трех до пяти) значениях точности, например, при  и построить график зависимости .
  14.  Провести сравнение методов между собой: сравнить сложность реализации, скорость работы (точность). Какой из рассмотренных методов более оптимален для низкой точности () и для высокой точности ()?
  15.  Сохранить результаты для использования в лабораторной работе 2.

 

А также другие работы, которые могут Вас заинтересовать

85347. Методи корекції в системі психологічної допомоги людям з обмеженими можливостями 41.72 KB
  Одним із способів допомогти здоровим людям краще зрозуміти проблеми дітей з вадами здоровя навчитися надавати їм допомогу є програма Дитина дитині . Завданням цієї програми є навчити дітей шкільного віку та їх вчителів методам збереження свого здоровя й взаємодії з іншими дітьми особливо з тими хто має проблеми зі здоровям. Метою даної програми є допомогти дітям навчитися розрізняти різні види інвалідності і їх прояви; розуміти що незважаючи на те що людина у якої є фізичні вади може не справлятися з якоюсь роботою вона у той же...
85348. Загальні психолого-педагогічні аспекти реабілітації людини з обмеженими можливостями 35.77 KB
  Основними завданнями таких проектів психологореабілітаційного напрямку є відновлення та розвиток інтелектуальних функцій людини її емоційного стану навичок психічної саморегуляції комунікативної культури. Специфічними методами що використовуються у проектах для інвалідів є психологічні тренінги аутотренінг комунікативний тренінг тренінг креативності психотерапія ігротерапія бібліотерапія арттерапія та інше; соціальнокультурним який передбачає активізацію та розвиток творчохудожнього потенціалу дітей і дорослих засвоєння...
85349. Особливості розвитку людини з порушеннями інтелекту і психічними захворюваннями 42.36 KB
  Олігофренія одна з груп розумової відсталості різна за етіологією і патогенезом хворобливих змін обєднаних загальним клінічним проявом недорозвинення головного мозку. Олігофренія характеризується природженим або придбаним в ранньому дитинстві до 3 років загальним психічним недорозвиненням. У більшості з них спостерігалися недорозвинення мови й емоційновольова нестійкість. У структурі інтелектуального дефекту цієї групи дітей переважали недорозвинення зоровопросторових функцій труднощі встановлення послідовних умовиводів у розповідях...
85350. Депривація і особливості розвитку особистості дітей і підлітків із відхиленнями розвитку 38.99 KB
  Якщо подивитися на дітей з відхиленнями в дитинстві то емоційноособистісне спілкування з матірю не стає визначальним у розвитку дитини. Особливість психологічного статусу дитини з невеликими відхиленнями в розвитку це те що на ранньому етапі не залягали передумови становлення його психіки. Якщо не займатися з такою дитиною спеціальним розвитком і навчанням то зміни в емоційновольовій сфері дитини не відбудеться. Стрес повязаний з етапами шкільного життя з підвищенням вимог до дитини викликає певне психологічне напруження що часто...
85351. Основні завдання психологічної реабілітації людей з різними психофізичними порушеннями 39.57 KB
  Друга група завдань вивчення аномалії формування и розвитку конкретних форм психічної діяльності та її психічних процесів у різних груп аномальних дітей тобто вивчення закономірностей формування особистості розумової діяльності мови сприймання памяті. Діагностика психічного розвитку дитини містить у собі: o всебічне клінікопсихологічне вивчення особистості дитини та її батьків системи їхніх відносин; o аналіз мотиваційнопотребностної сфери дитини й членів її родини; o аналіз розвитку сенсорноперцептивних і інтелектуальних процесів...
85352. Методи корекції в системі психологічної допомоги людям із обмеженими можливостями 40.37 KB
  Розвиваючий Розвиток комунікативних навичок особистості o розвиток експресивномовленнєвих якостей; o розвиток соціальноперцептивних особистісних якостей; o розвиток інструментальних якостей. Закріплюючий Моделювання комунікативних навичок в актуальних соціальних для підлітків умовах розвиток комунікативних якостей в умовах навчальної діяльності; розвиток комунікативних якостей в сімейних умовах; розвиток комунікативних якостей в позашкільних умовах. Робота з педагогами та батьками. Просвітницький Розвиток психологічного просвітництва...
85353. Соціально-психологічні особливості людини із порушеннями слуху 40.78 KB
  Втрата слуху навіть часткова створює барєр між людиною і суспільством утруднює оволодіння знаннями і спеціальністю обмежує трудову і суспільну діяльність зтримує розвиток особистості. Відсутність слуху серйозно обмежує й естетичне виховання особи адже людина позбавляється можливості нормально сприймати музику...
85354. Компенсація, корекція і реабілітація як категорії спеціальної психології 37.42 KB
  Перша фаза виявлення того чи іншого порушення в роботі організму. Сигнал про порушення може бути повязаний і з самим розладом і з його наслідками з різними відхиленнями в поведінці і діяльності. Друга фаза оцінка параметрів порушення його локалізації та глибини виразності. Не випадково одне і те ж порушення у тварин і людини може призвести до різних наслідків.
85355. Особливості розвитку людини з порушенням зору 40.34 KB
  Вроджені: захворювання й аномалії розвитку органів зору: патологія судинної оболонки захворювання рогової оболонки ока вроджені катаракти глаукоми окремі форми патології сітківки і таке інше. Аномалії зору також можуть виникнути в результаті зовнішніх і внутрішніх негативних впливів що мали місце в період вагітності: перенесені матірю вірусні захворювання токсоплазмоз краснуха й таке інше.