Программа поиска минимума функции N переменных

Автор работы: Пользователь скрыл имя, 17 Июня 2013 в 13:37, курсовая работа

Описание работы

Понятия минимум и максимум объединяются одним – экстремум (от латинского слова extremum – крайний). Задачи на отыскание максимума или минимума критерия оптимальности называют экстремальными или оптимизационными задачами. Оба эти названия эквивалентны, однако первое из них акцентирует внимание на математическую суть задачи, второе – на ее прикладную направленность.

Содержание работы

Введение 5
1. Постановка задачи 7
2. Математическая формулировка задачи 9
2.1 Принцип поиска минимумам функции нескольких переменных 9
2.2 Метод квадратичной интерполяции-экстраполяции 10
3. Алгоритмизация программы 11
4. Идентификаторы программы 12
5. Блок-схема алгоритма 13
6. Текст программы 19
7. Результаты выполнения программы 22
8. Анализ результата 23
9. Инструкция по работе с программой 24
Заключение 26
Список используемых источников 27

Скачать архив (171.36 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

ПЗ.doc

— 274.50 Кб (Скачать файл)

 

 

 


Белорусский национальный технический университет

Факультет горного дела и инженерной экологии

Кафедра «Горные машины»

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

по  дисциплине «Информатика»

 

Тема: Программа поиска минимума функции N переменных

 

 

 

 

 

 

   Исполнитель:                          студент факультета ГДЭ, 2 курса,

                                       группы 302510

                                       Новик Е. М.  

 

  Руководитель проекта:            преподаватель Петренко С. М.

                           

 

 

 

 

 

 

 

 

 

 

 

Минск 2012

 

Белорусский национальный технический университет

 

Кафедра «Горные машины»

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА 

 

 

к курсовой работе

по  дисциплине «Информатика»

 

 

Тема: Программа поиска минимума функции N переменных

 

 

 

 

Исполнитель: _____________ Новик Е. М.   .

студент 2-го курса, группы  302510

                        

 

Руководитель проекта: ____________  Петренко С. М.

преподаватель                                (подпись)                     

                        

 

 

 

 

 

 

 

 

 

 

Минск 2012 

Содержание

 

 

 

 

Введение

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

На протяжении своей деятельности человек сознательно и интуитивно стремится найти некоторые "наилучшие" решения возникающих перед ним задач и проблем. Процесс выработки наилучших решений называется оптимизацией. 

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

Понятия минимум и максимум объединяются одним – экстремум (от латинского слова extremum – крайний). Задачи на отыскание максимума или минимума критерия оптимальности называют экстремальными или оптимизационными задачами. Оба эти названия эквивалентны, однако первое из них акцентирует внимание на математическую суть задачи, второе – на ее прикладную направленность. 

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

Метод интерполяции-экстраполяции основан на представлении рассматриваемой функции в виде дискретного набора значений. Именно конечный набор значений y(x1,x2,..xn ) представляет на компьютерном языке математическую абстракцию непрерывной функции y(x1,x2,..xn). Задача интерполяции функции состоит в замене дискретной зависимости или, по-другому, узлов, некоторой непрерывной функцией. При этом основным условием является то, что функция должна проходить через узлы, а также возможность вычислить значение функции в любой точке, находящейся между узлами.

Когда искомое значение y (x1,x2,..xn) вычисляется в точке, которая находится между каких-либо узлов, говорят об интерполяции, а когда  точка лежит вне границ интервала, включающего все узлы – об экстраполяции функции y(x1,x2,..xn ).

 

  1. Постановка задачи

Необходимо составить программу поиска минимума функции двух переменных:

 

                  (1) 

методом квадратичной интерполяции-экстраполяции.

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

При реализации методов оптимизации исследуются необходимые условия локального экстремума функции F(x1,x2.. xn). Если F(x1,x2.. xn) является непрерывной функцией, имеющей непрерывные частные производные первого и второго порядка по всем переменным xi ( i= 1…n) , то необходимым условием экстремума в точке {x*} является равенство нулю в этой точке первых производных по всем переменным, т.е. точки, в которой функция F(x1,x2.. xn) может достигать экстремума, определяются решением системы уравнений

 

             (2) 

Предварительно исследуется функция (1) путем построения ее графика на указанном участке (рисунок 1).

Из графика видно, что функция  имеет локальный минимум в точке x*={0;1,25}. Функция определена в  окружении точки локального минимума и непрерывна.

Исходными данными программы являются: значение точки экстремума в первом  приближении и точность определения минимума.

Значения исходных данных вводится по запросу программы пользователем  с клавиатуры.

Программа будет состоять из следующих составных логически завершенных частей:

  • ввод исходных данных;
  • основная часть – поиск решения методом квадратичной  интерполяции-экстраполяции;
  • вычисления значения функции F(x1,x2);
  • вычисление частных производных функции dF(y)/dy, dF(x)/dx;
  • вычисления значения функции F(x);
  • вывод результатов.

 

 

 


 

 

 

 

 

 

 

 

 

  1. Математическая формулировка задачи

    1. Принцип поиска минимума функции нескольких переменных

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

После рассмотрения всех n координат выполняется возврат к первой и вновь производится поиск локального экстремума вдоль каждой из n координат до тех пор, пока экстремум не будет локализован с заданной точностью (рисунок 2).

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

    1. Метод квадратичной интерполяции-экстраполяции

Ниже описан метод квадратичной интерполяции-экстраполяции для одной координаты.

Если  задана последовательность точек i-ой координаты x1i, x2i, x3i и известны соответствующие им значения функции f(x1i), f(x2i), f(x3i), то функция f(x*) может быть аппроксимирована по одной xi переменной квадратичной функцией:

 

             (3)

 

Постоянные коэффициенты ai0, ai1, ai2 определяются из условия, что значения функции φ(x*) совпадают со значениями f(x*) в контрольных (узловых) точках.

Для x*=xi1 : fi1 =f(x*1)=φ(x*1)= ai0, т. е. ai0= fi1.

Для x*=xi2 : fi2 =f(x*2)=φ(x*2)= f(x*1)+ai1(x*2- x*1),  откуда

Для x*=xi3 : ,

откуда 

Для оценивания координаты точки оптимума используется  полученный квадратичный полином:

 

             (4)

Отсюда i –я координата  точки минимума аппроксимируется значением:

               (5)

  1. Алгоритмизация программы

Алгоритм, приведенного в п. 2 метода, для функции двух переменных f (x,y) можно описать следующим образом:

  1. исходные данные: координаты точки первого приближения x1 , y1, точность вычисления ε;
  2. шаги интерполяции: dx=0.1·ε, dy=0.1·ε;
  3. в первом приближении: fmin=f(x1,y1); n=0;
  4. n=n+1;
  5. x2=x1+dx;
  6. f1=f(x1,y1); f2=f(x2,y1);
  7. если f1>f2 то x3=x1+2·dx в противном случае x3=x1-dx;
  8. f3=f(x3,y1);
  9. a1=(f2-f1)/(x2-x1);  a2:=1/(x3-x1)·((f3-f1)/(x3-x1)-(f2-f1)/(x2-x1));
  10. x1=(x1+x2)/2-a1/2/a2 – координата x предполагаемой точки минимума;
  11. y2=y1+dy;
  12. f1=f(x1,y1);    f2:=f(x1,y2);
  13. если f1>f2 тогда y3=y1+2·dy  в противном случае y3=y1-dy;
  14. f3=f(x1,y3);
  15. a1=(f2-f1)/(y2-y1); a2=1/(y3-y1)·((f3-f1)/(y3-y1)-(f2-f1)/(y2-y1));
  16. y1=(y1+y2)/2-a1/2/a2 – координата предполагаемой точки минимума;
  17. d=|fmin-f(x1,y1| - текущая погрешность;
  18. fmin=f(x1,y1);
  19. если d<e и df/dx(x1,y1)<e и df/dy(x1,y1)<e (проверка достижения заданной точности), то происходит переход на t), в противном случае – на п. d.
  20. вывод на дисплей  значений:  y1, x1, fmin , df/dx(x1,y1), df/dy(x1,y1).

 

  1. Идентификаторы программы

Таблица 1 – Идентификаторы программы поиска минимума функции

 

Обозначение параметров

Смысл параметра

в формулах

в программе

x11, x12

x1,y1

значение координат точки минимума первого приближения

x21, x22 , x31, x32

x2,y2,x3,y3

координаты точек интерполяции-экстраполяции

f(x11), f(x21), f(x31),

f(x12), f(x22), f(x32)

f1, f2, f3

значение целевой функции

ε

e

заданная точность вычисления

a0, a1, a2

a0, a1, a2

коэффициенты интерполяционного  многочлена

-

d

текущая точность вычисления

-

dx, dy

шаги интерполяции

fmin

f_

значение функции в точке минимума

df/dxi

fdx, fdy

частные производные  целевой функции


 

 

  1. Блок-схема алгоритма

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Текст программы

Program MinF2pr;

{минимум функции 2-х  переменных методом квадратичной интерполяции-экстраполяции}

uses crt;

Var

  e,a1,a2,x1,x2,x3,y1,y2,y3,dx,dy,f_,f1,f2,f3,d: real;

  n: byte;

  v: char;

  err: boolean;

function f(x:real;y:real):real; {функция цели}

begin

  f:=sqr(sqr(x)+sqr(y)-1)-sqr(sqr(x)*x-y);

end;

 

function fdx(x:real;y:real):real; {первая  частная производная по x}

begin

  fdx:=6*sqr(x)*(y-x*sqr(x))+4*x*(sqr(x)+sqr(y)-1);

end;

 

function fdy(x:real;y:real):real; {первая  частная производная по y}

begin

  fdy:=2*sqr(x)*x-2*y+4*y*(sqr(x)+sqr(y)-1);

end;

 

procedure Title;

begin

 

  Gotoxy(3,1);

  Writeln(' ');

  Writeln('                 Министерство образования Республики Беларусь');

  Writeln('               Белорусский Национальный Технический  Университет');

  Gotoxy(15,8);

  Writeln('Программа нахождения  минимума функции нескольких  ');

  Writeln('               методом квадратичной интерполяции-экстраполяции ');

  Writeln;

  Writeln;

  Writeln('                             Курсовая работа          ');

  Writeln('                       по дисциплине "Информатика"   ');

  Gotoxy(1,18);

  Writeln('                                     Выполнил: ___________ ');

  Writeln('                                                               ');

  Writeln('                                     Проверил: Петренко C.М.');

Информация о работе Программа поиска минимума функции N переменных