50621

Дихотомия

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

Математика и математический анализ

Задание Минимизировать унимодальную функцию fx методом дихотомии: Пpостейшим методом минимизации функции одной пеpеменной является дихотомия деление отpезка пополам. Для успешной pеализации этого метода не тpебуется вычислять или оценивать пpоизводную функции. Обозначим через X множество точек минимума функции fx. Для унимодальной функции X=[ α β].

Русский

2014-01-27

177.5 KB

8 чел.

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

№1

Тема

Дихотомия

Ф.И.О.

Пастухова Светлана Владимировна

Группа

403

Вариант

15

Задание

Минимизировать унимодальную функцию f(x) методом дихотомии:

             

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

Определение. Функцию f(x) назовем унимодальной на отpезке X, где X={ x: a ≤ x ≤ b }, если она непpеpывна на X=[a,b], и существуют числа α, β такие что a ≤ α ≤ β ≤ b и

1) f(x) стpого монотонно убывает пpи a ≤ x ≤ α,

2) f(x) стpого монотонно возpастает пpи β ≤ x ≤ b,

3) f(x)=f*=inf{ f(x): x єX } пpи α ≤ x ≤ β.

Случай, когда один или два из отpезков [а, α], [ α, β], [ β,b] выpождаются в точку, здесь не исключается. Обозначим через X* - множество точек минимума функции f(x). Для унимодальной функции X*=[ α, β]. Если α=β, то f(x) называется стpого унимодальной на отpезке X=[a,b].

Опишем метод дихотомии, пpедполагая, что минимизиpуемая функция f(x) унимодальна на отрезке [a,b].

Поиск минимума функции f(x) начинается с выбоpа двух точек

x1=(a+b- δ)/2, x2=(a+b+ δ)/2,

где δ - параметр метода,0 < δ < b-a,выбирается вычислителем и может определяться целесообразным количеством верных десятичных знаков при задании аргумента. Ясно, что δ не может быть меньше машинного нуля ЭВМ,используемой при решении рассматриваемой задачи. Точки x1, x2 расположены симметрично на отрезке [a,b] относительно его середины и при малых δ делет его почти пополам.

После выбора точек x1, x2 вычисляются значения f(x1), f(x2) и сравниваются между собой. Если f(x1) ≤ f(x2), то полагают а1=а, b1=x2, если же f(x1) > f(x2),то a1=x1, b1=b. Так как f(x) унимодальна на [a,b], отрезок [a1,b1] имеет общую точку со множеством X* и его длина b1-a1=(b-a-δ)/2+δ

Пусть отрезок [a k-1 ,bk-1 ], имеющий непустое пересечение с X*, уже известен, и пусть bk-1 -ak-1=(b-a- δ)/2k-1+ δ> δ, k≥2. Тогда берем точки x=(a +b -)/2, x =(a+b+)/2, расположенные на отрезке [a,b] симметрично относительно его середины, и вычисляем значения f(x), f(x).

Если f(x) ≤ f(x), то полагаем a=a, b=x, если же f(x) > f(x), то a=x, b=b Длина получившегося отрезка [a,b] равна b-a=(b-a-)/2+ .

Описанный процесс деления отрезка пополам можно продолжать до тех пор пока не получится отрезок [a,b] длины b- a: где  - заранее заданная точность,ε>δ . Нетрудно получить, что для достижения точности ε требуется n > 2log2((b-a- )/( ε-δ)) вычислений функции f(x).

Выполнения лабораторной работы.

  1.  Графически определяем отрезок [a,b],на котором лежит точка минимума функции.

    

1

--0.3502

-0.2000

0.1502

2

-0.3502

-0.2749

0.0754

3

-0.3128

-0.2749

0.0379

10

-0.2894

-0.2886

0.0008

Локальный минимум функции t= -0.2627

PAGE  1


 

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

4571. Разработка учебная Базы Данных (БД) MusicShop 696 KB
  Введение В настоящие время в связи с развитием компьютерной техники появилась возможность автоматизировать многие процессы. Современные магазины музыки предлагают большой выбор музыки, в связи с чем, возникает проблема поиска необходимой композиции,...
4572. Решение задачи коммивояжера разными программными методами 84.06 KB
  Введение Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конст...
4573. Кратчайший путь в графе. Методы программирования 151 KB
  Программный продукт предназначен для нахождения кратчайшего пути между двумя любыми вершинами графа. Проектирование Алгоритм Дейкстры. Алгоритм Дейкстры строит кратчайшие пути, ведущие из исходной вершины графа к остальным вершинам этог...
4574. Инструментальная система моделирования Parallax 74 KB
  Общие характеристики системы Инструментальная система моделирования Parallax (далее — система) предназначена для моделирования и анализа система взаимодействующих параллельных процессов на основе аппарата PS-сетей. Система...
4575. Раскраска графа способом разработки программного продукта 403.33 KB
  Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кенигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Впервые...
4576. Создание программы для рисования кривых второго порядка в среде Borland C++ Builder 6 437 KB
  Введение В рамках данного курсового проекта требуется написать программу, рисующую кривые второго порядка. Для разработки была использована среда разработки BorlandC++ Builder 6. Формулировка поставленной задачи Написать программу, рисующую кр...
4577. Покрывающее дерево. Концепция алгоритма Краскала 252.41 KB
  Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево. Полный граф задается списком ребер. Перед работой список ребер сортируется по возрастанию длины....
4578. Философия человека 185 KB
  Философия человека Понятие философской антропологии. Проблема человека в истории философии. Проблема определения сущности человека. Философские проблемы антропосоциогенеза. Смысл и ценность жизни человека. Введение. С развитием общества ...
4579. Визначення максимальної енергії бета-частинок у спектрі 78 KB
  Визначення максимальної енергіїбета-частинок у спектрі Мета роботи: визначення максимальної енергії бета-частинок в спектрі. Короткі теоретичні відомості Бета-розпад — це самовільний процес, в якому нестабільне ядро перетворюєтьс...