Метод касательных

 
 
 
 
 
 
 
 
 
 
 

«Метод касательных»

курсовая  работа по дисциплине

методы  оптимизации 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Определение 1.  Точку называют точкой минимума на отрезке , если для всех ; величину называют минимальным значением .

     Определение 2. Последовательность называется минимизирующей для функции на отрезке  , если

     

.

     Из  определения и существования  нижней грани следует, что минимизирующая последовательность всегда существует.

     Задача  минимизации: заданы отрезок и функция , определенная на ; требуется найти точки минимума функции на ( ).

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

     Описание  метода.

     Пусть функция выпукла и дифференцируема на отрезке . Определим функцию – уравнение касательной к функции в точке .

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

Полагаем  и определяем из условия (ясно, что будет ).

2. Вычисляем  и . Строим новую функцию и определяем из условия и т.д..
3. …

   Если  точки  уже известны  ( ):

14. Вычисляем  и . Составляем функцию , и следующую точку определяем из условия ( ).

     Если  при каком-то , то и задача минимизации уже решена, итерации заканчиваются, также критерием останова может быть количество итераций или условие .

Реализация.

     Можно реализовать алгоритм, изложенный выше:

> restart:

> a:=-1: b:=3:

> k:=100:

> f:=(x)->x^2-2*x+1:

> x[1]:=a:f(x);

> g[1](x):=subs( x=x[1],f(x)) + subs(x=x[1],diff(f(x),x))*(x-x[1]):

> P[1](x):=g[1](x):

> r:=min(subs(x=a,P[1](x)), subs(x=b,P[1](x))):

> x[2]:=solve(P[1](x)=r,x):

> i:=2:

> while (i < k)   do

>     m:=subs(x=x[i],diff(f(x),x));

>     m1:=subs( x=x[i],f(x));

>     g[i](x):= m1 + m*(x - x[i]);

>     P[i](x):=convert( max( g[i](x), P[i-1](x)), piecewise);

>     if (i=2) then x[i+1]:=solve(g[i](x)=g[i-1](x),x);

>         else q:=solve(P[i-1](x)=g[i](x),x);             

>              w:=nops([q]); e:=Array(1..w);

>              for j from 1 to w do

>                  s:=subs(x=q[j],[P[i](x),piecewise]);

>                  e[j]:=s[1];

>              od:

>              qq:=min(e);

>              x[i+1]:=solve(P[i](x)=qq,x);

>     fi:

>     d:=subs(x=x[i],diff(f(x),x));

>     if (d < evalf(10^(-6))) then break fi:

>     i:=i+1;

> od:

> f(min):=evalf(subs(x=x[i],f(x))); xx:=evalf(x[i]);

> plot(f(x),x=a..b);

> ff:=[]:

> for y from 1 to i-1 do

> ff:=[op(ff),P[y](x)]:

> od:

>

> for y from 1 to i-1 do

> printf("%55s %d \n", "Шаг", y );

> plot(P[y](x),x=a..b);

> od;

> plot(ff,x=a..b,color=black);

      Можно предложить более удобную для  использования на ЭВМ вычислительную схему метода касательных, которая  не требует хранения в машинной памяти информации обо всей ломаной  при . А именно, возьмем . Вычислим . Если или , то или – задача решена.

      Поэтому, пусть , . Пусть отрезок   уже построен, причем  , . Обозначим через точку пересечения касательных и . Ясно, что . Явное выражение для :

      

, .

      Вычислим  . Если , то – задача решена, итерации заканчиваются. Если , то положим

               .

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

> restart:

> a:=-2: b:=3:

> k:=100:

> f:=(x)->3*x^2+5*x+12:f(x);

> s:=(y)->subs(x=y,diff(f(x),x)):

> i:=1: a1:=a: b1:=b:

> if (s(a) >=0 ) then u:=a; fi:

> if (s(b) <= 0) then u:=b; fi: 

> if (s(a) <0 and s(b) > 0) then

>     while (i < k) do

>          u:=(f(a1)-f(b1)+b1*s(b1)-a1*s(a1))/(s(b1)-s(a1));

>          if ( abs(s(u)) < 10^(-6)  ) then break; fi:

>          if ( s(u) > 0 ) then b1:=u: else  a1:=u: fi:

>          i:=i+1;

> od:

> fi:

> f(min):= evalf(f(u)); x(min):= evalf(u);

> plot(f(x), x=a..b); 
 
 
 

      Примеры выполнения программ.

      Первая  программа позволяет графически отобразить метод.

      Решим задачу

  _{– минимальное значение}

  _{– точка минимума}

График  минимизируемой функции

                                                       Шаг 1

                            
 
 
 
 
 
 

                                                         Шаг 2

                                                        Шаг 3

Все касательные, построенные в ходе вычислений

_{Второй программой решим задачу:}

 _{– минимальное значение}

 _{– точка минимума}

График  минимизируемой функции

 

      Анализ метода.

      Достоинство метода в том, что он сходится пи любом выборе начальной точки. Недостаток – в том, что он применим только в случае, когда минимизируемая функция выпукла и значения функции и её производных вычисляются достаточно просто. Но в отличие от схожего метода ломаных в данном методе при реализации на ЭВМ можно использовать схему вычислений, не требующую хранения в машинной памяти информации обо всей ломаной , и не нужно находить постоянную Липшица.