Методы одномерной оптимизации. Метод золотого сечения

АГЕНТСТВО ПО ОБРАЗОВАНИЮ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 
 
 
 
 
 
 
 
 

КОНТРОЛЬНАЯ РАБОТА ПО КУРСУ

МЕТОДЫ  ОПТИМИЗАЦИИ 

КОНТРОЛЬНОЕ ЗАДАНИЕ №65

Методы  одномерной оптимизации.

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

№ зачетной книжки________________ 
 
 
 
 
 
 
 
 

     Выполнил:

студент гр. АУЗ-261с 
 
 

Проверил:

Яновский  Т.А. 
 
 
 
 
 
 
 

ВОЛГОГРАД 2010

 

Содержание

1. Текст задания  №65………………………………………………………………3 

2. Определение  унимодальности………………………………………………….3  

3. Алгоритм…………………………………………………………………………4 

4. Текст программы  на С++………………………………………………………..4 

5. Сводная таблица  результатов решения задач...……………………………….5 

6. Сводная таблица…………………………………………………………………8  
1. Текст задания №65: 

1.Самостоятельно  найти в литературе по “Методам  оптимизации” определение унимодальной функции и разобраться с его смыслом. Это важно, так как вычислительный процесс в любом методе одномерной оптимизации опирается на предположение об унимодальности .

2.Программно  реализовать на языке C++ процедуру одномерной оптимизации методом золотого сечения: (Программа должна обеспечить вывод на экран:

• границ начального отрезка , числа

на каждой итерации метода:

• номера итерации,
• границ текущего отрезка ,
• внутренних точек и и значений функции в них,

а затем 

• финальной оценки x* точки минимума функции f(x),
• соответствующего точке x* значения функции f(x*)).

3.С помощью  программы оценить точки минимума  для следующих тестовых функций

• f(x) = x² – 12x. Начальные отрезки [a, b]: [-10,  10],[0, 100],[1, 5]. ε = 0.01, 0.001
• f(x) = 2x²+(16/x) Начальные отрезки [a, b]:  [1,6,  2],[0,1, 2],[1, 4]. ε = 0.01, 0.001
• f(x) = (127/4)x²-(61/4)x+2. Начальные отрезки [a, b]:  [-1,  1],[-1, 2],[0,2, 10]. ε = 0.01, 0.001

 

2. Определение унимодальности 

     Унимодальной называется функция, имеющая на заданном отрезке [a,b] один максимум или минимум. Основное свойство унимодальных функций, таково. Если мы знаем значения f в точках x¹ и x² отрезка [a, b], x¹ < x², то мы можем определенно сказать на каком из отрезков [a, x²], [x¹, x²], [x¹, b] лежит минимум x* функции f (см. рис 1).

 
Рис. 1. 

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

     Метод дихотомии, методы золотого сечения  и Фибоначчи указывают на отрезок, на котором гарантированно лежит точка x*. Этот отрезок называют отрезком (или интервалом) неопределенности. Таким образом, если в качестве приближенного значения x* взять центр этого отрезка, то погрешность метода есть половина длины отрезка неопределенности. 

3. Алгоритм 

Шаг 1. Вычислить  .

Шаг 2. Найти  пробные точки  и .

Шаг 3. Вычислить  значения функции в пробных точках и .

Шаг 4. Сравнить и :

а) если , то положить .

б) если , положить .

Шаг 5. Вычислить  . Если , то положить и закончить поиск, иначе перейти к шагу 3. 

4. Текст программы на С++ 

#include <iostream.h>

#include <iomanip>

#include <stdlib.h> 

float division(double a, double b, double e);

double x;

char SomeChar;

double function(double x); 
 

int main()

{

      division(-1, 1, 0.00001); 

      cin.get(SomeChar);

      return 0;

} 

float division(double a, double b, double e)

{

      double x,l, x1, x2;

      double funX,funX1,funX2; 

      int k=0;

      cout<<"e= "<<e<<endl;

      cout<<"f(x)=(127/4)*x*x-(61/4)*x+2"<<endl; 

      do  

      {

            x1 = a;

            x2 = b;

            cout<<endl;

            cout<<"{"<<k<<"}:   ["<<x1<<" , "<<x2<<"]"<<endl;  

            k++;

            l=b-a;

            x = (x1 + x2)/2;

            funX=function(x);

            cout<<"x= "<<x;

            cout<<"     f(x)="<<funX<<endl; 

            x1=a+l/4;

            funX1=function(x1);

            cout<<"x1= "<<x1;

            cout<<"     f(x1)="<<funX1<<endl; 

            x2=b-l/4;

            funX2=function(x2);

            cout<<"x2= "<<x2;

            cout<<"     f(x2)="<<funX2<<endl; 

            if (funX1 < funX)  { b = x; x = x1;}     

            if (funX2 < funX)  { a = x; x = x2;}

            if (funX2 >= funX) { a = x1; b = x2;} 

      }  

      while (l > e);

      cout<< endl;

      cout<<"Znachenie x:"<<x<<endl;

      cout<<"Znachenie f(x):"<<function(x)<<endl;

       

      return x; 

} 

double function(double x)

{  

      return (127/4)*x*x-(61/4)*x+2; 

} 
 

5. Сводная таблица результатов решения задач

e= 0.1

f(x)=(127/4)*x*x-(61/4)*x+2 

{0}:   [-1 , 1]

x= 0     f(x)=2

x1= -0.5     f(x1)=17.25

x2= 0.5     f(x2)=2.25 

{1}:   [-0.5 , 0.5]

x= 0     f(x)=2

x1= -0.25     f(x1)=7.6875

x2= 0.25     f(x2)=0.1875 

{2}:   [0 , 0.5]

x= 0.25     f(x)=0.1875

x1= 0.125     f(x1)=0.609375

x2= 0.375     f(x2)=0.734375 

{3}:   [0.125 , 0.375]

x= 0.25     f(x)=0.1875

x1= 0.1875     f(x1)=0.277344

x2= 0.3125     f(x2)=0.339844 

{4}:   [0.1875 , 0.3125]

x= 0.25     f(x)=0.1875

x1= 0.21875     f(x1)=0.202148

x2= 0.28125     f(x2)=0.233398 

{5}:   [0.21875 , 0.28125]

x= 0.25     f(x)=0.1875

x1= 0.234375     f(x1)=0.187256

x2= 0.265625     f(x2)=0.202881 

Znachenie x:0.234375

Znachenie f(x):0.187256

x*x-12*x

e= 0.01

{0}:   [-10 , 10]

x1= -2.36068     f(x1)=33.901

x2= 2.36068     f(x2)=-22.7553

l=12.3607 

{1}:   [-2.36068 , 10]

x1= 2.36068     f(x1)=-22.7553

x2= 5.27864     f(x2)=-35.4796

l=7.63932 

{2}:   [2.36068 , 10]

x1= 5.27864     f(x1)=-35.4796

x2= 7.08204     f(x2)=-34.8292

l=4.72136 

{3}:   [2.36068 , 7.08204]

x1= 4.16408     f(x1)=-32.6294

x2= 5.27864     f(x2)=-35.4796

l=2.91796 

{4}:   [4.16408 , 7.08204]

x1= 5.27864     f(x1)=-35.4796

x2= 5.96748     f(x2)=-35.9989

l=1.8034 

{5}:   [5.27864 , 7.08204]

x1= 5.96748     f(x1)=-35.9989

x2= 6.3932     f(x2)=-35.8454

l=1.11456 

{6}:   [5.27864 , 6.3932]

x1= 5.70437     f(x1)=-35.9126

x2= 5.96748     f(x2)=-35.9989

l=0.688837 

{7}:   [5.70437 , 6.3932]

x1= 5.96748     f(x1)=-35.9989

x2= 6.13009     f(x2)=-35.9831

l=0.425725 

{8}:   [5.70437 , 6.13009]

x1= 5.86698     f(x1)=-35.9823

x2= 5.96748     f(x2)=-35.9989

l=0.263112 

{9}:   [5.86698 , 6.13009]

x1= 5.96748     f(x1)=-35.9989

x2= 6.02959     f(x2)=-35.9991

l=0.162612 

{10}:   [5.96748 , 6.13009]

x1= 6.02959     f(x1)=-35.9991

x2= 6.06798     f(x2)=-35.9954

l=0.1005 

{11}:   [5.96748 , 6.06798]

x1= 6.00587     f(x1)=-36

x2= 6.02959     f(x2)=-35.9991

l=0.0621124 

{12}:   [5.96748 , 6.02959]

x1= 5.9912     f(x1)=-35.9999

x2= 6.00587     f(x2)=-36

l=0.0383876 

{13}:   [5.9912 , 6.02959]

x1= 6.00587     f(x1)=-36

x2= 6.01493     f(x2)=-35.9998

l=0.0237248 

{14}:   [5.9912 , 6.01493]

x1= 6.00026     f(x1)=-36

x2= 6.00587     f(x2)=-36

l=0.0146627 

{15}:   [5.9912 , 6.00587]

x1= 5.9968     f(x1)=-36

x2= 6.00026     f(x2)=-36

l=0.00906208 
 

Znachenie x:6.00133

Znachenie f(x):-36 
 
 
 

 

6. Сводная таблица