СКАЧАТЬ:  laboratornaya-rabota1.zip [205,53 Kb] (cкачиваний: 23)

 СКАЧАТЬ:  laboratornaya-rabota-11.zip [529,11 Kb] (cкачиваний: 20)

О Т Ч Е Т

По лабораторной работе

По дисциплине «Оптимизация и оптимальное управление»

На тему: «Решение алгебраических уравнений с использованием численных методов»

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

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

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

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

Дано алгебраическое уравнение x³+x-1=0. Необходимо отделить корни данного уравнения и уточнить их методами итерации, деления отрезка пополам, касательных.

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

Краткие сведения из теории

Пусть функция f(x) имеет на отрезке [a,b] непрерывные первую и вторую производные. Т.е. f'(x) и f''(x) определены в любой точке отрезка [a,b]. Тогда уравнение (1) можно решить методом Ньютона. Для этого выбирают начальную точку, пусть это будет точка b. В этой точке к функции f(x) строят касательную. Точка x1 – точка пересечения касательной и оси абсцисс, считается уточненным значением корня. Далее уже в точке x1 строят касательную к функции f(x) и находят новое уточнение корня x2 и т.д. Процесс продолжается до тех пор, пока  не выполнится условие |x_n-x_n-1|<=ε. Тогда x_n-искомое решение.

Рис.1 Метод касательных

Определим формулу для уточнения корня. Для этого запишем уравнение касательной в точке x₀=b: y=f(x₀)+f' (x₀)(x-x₀). Уточненное решение будет в точке пересечения касательной и оси абсцисс, т.е. у=0. Тогда:                         f(x₀)+f' (x₀)(x-x₀)=0 или f(x₀)+f' (x₀)x- f' (x₀)x₀=0. Тогда

. Пусть x₁=x, тогда . Следовательно,

 и т.д.

Т.е. формула уточненного корня примет вид:

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

1. Начальной точкой выбирают тот конец отрезка, для которого выполняется условие:
2. Если выполняется условие , то начальной точкой выбирают точку a, а в противном случае – b.

Алгоритм метода касательных

Шаг 1. Задаются концы отрезка, т.е. числа a и b; задается точность метода ε.

Шаг 2. Выбирается начальная точка из условия  . Если условие верно, то начальная точка a, в противном случае – точка b.

Шаг 3. Определяется уточненное значение корня по формуле .

Шаг 4. Проверяется условие |x_n-x_n-1|<=ε. Если условие верно, то управление передается шагу 5, в противном случае управление передается шагу 3, используя при этом новые данные.

Шаг 5. Вывод x_n.

Шаг 6. Конец

Блок-схема:

Программа для вычисления корней алгебраического уравнения

Program niuton;

Uses CRT;

Label m;

Var a,b,e,x,y:real;

function f(x:real):real;

      begin

f:=х*х*х+х-1

       end;

function f1(x1:real):real;

      begin

f1:=3*х1*х1+1

      end;

BEGIN

              clrscr;

      write('a=');

       read(a);

      write('b=');

      read(b);

      write('e=');

      read(e);

      If (a-f(a))/f1(a)<b then x:=a

                                   else x:=b;

m:  y:=x-(f(x)/f1(x));

      If abs(y-x)>e then begin x:=y; goto m end;

      writeln('x=',y:4:8);

      writeln('f(x)=',f(x):4:8);

      repeat

      until keypressed;

END.

В итоге получаем следующие ответы для уравнения x³+x-1=0

1. 2.     Метод деления отрезка пополам 

Будем искать минимум функции f(x), непрерывно дифференцируемой и строго унимодальной на отрезке [a₁ , b₁ ]. В этом случае единственной точкой x₀ є [a₁ , b₁ ] минимума будет стационарная точка, в которой f '(x_* ) = 0 .

В данном методе используют простую идею: вычисляют производную

f '(x_1ср )= K₁ в средней точке x_1ср =(а₁+b₁)/2 исходного отрезка и, если K₁>0, то отрезок [x₁ , b₁ ] отбрасывают, так как на нем строго унимодальная функция

только возрастает, а если K1<0, то отбрасывают отрезок [a₁ , x₁ ], поскольку на нем строго унимодальная функция только убывает. В данном случае отбрасывание половины исходного отрезка [a₁ , b₁ ] аналогично процедуре исключения отрезка. Ясно, что в случае K=0 имеем x_* = x_ср .

Оставшуюся после отбрасывания половину отрезка обозначим [a₂ , b₂ ]

и, вычислив производную f '(x_2ср ) = K₂ в его средней точке x_2ср =(а₂+b₂)/2

повторим процедуру отбрасывания половины отрезка и т. д. Условием прекращения вычислений на к-м шаге может быть выполнение неравенства  l_{k +1} < ε , где l_{k +1} = b_{k +1} - a_{k +1} - длина отрезка [a_{k +1},b_k+1 ] после отбрасывания половины отрезка [a_k ,b_k ]; ε- наибольшая допустимая длина интервала неопределенности.

Алгоритм метода деления отрезка пополам

Шаг 1. Задаются концы интервала а,b и погрешность метода ε

Шаг 2. За начальную точку выбирается точка а.

Шаг 3. Вычисляется значение функции f(a)

Шаг 4. Находится середина отрезка а,b: x=(a+b)/2

Шаг 5. Вычисляется значение функции f(x)

Шаг 6. Определяется новый интервал, на котором имеется корень. Это делается при помощи условия f(a)*f(a)<0. Если это условие выполнено, то b=x, в противном случае необходимо повторить шаг 3.

Шаг 8. Вывод x

Шаг 9. Конец.

Блок схема:

Программа для вычисления корней алгебраического уравнения

Program Delenie_popolam;

Uses crt;

label m;

var a,b,e,z:real;

x:real;

function f(x:real):real;

              begin

             f:=x*x*x+x-1=0;

             end;

BEGIN

 clrscr;

 write('a=');

 read(a);

 write('b=');

 read(b);

 write('e=');

 read(e);

 m:x:=(a+b)/2;

 if (f(a)*f(x))<0 then b:=x

                                        else a:=x;

 if (b-a)<=e then begin

                         writeln('x=',x:4:8);

                                   writeln('f(x)=',f(x):4:8) end

                         else goto m;

       repeat

       until keypressed;

 END.

В итоге получаем следующие ответы для уравнения x³+x-1=0

1. 3.    

 Метод итерации (последовательных приближений)

Пусть необходимо решить уравнение        f(х)=0 на интервале  [a,  b] с

точностью ε. Уравнение f(х)=0 некоторым     образом     преобразуется    к

равносильному уравнению х=φ(х) (*) имеющему корень t, на отрезке [a,b]. Функция φ предполагается непрерывной на этом отрезке. При этом,

чтобы метод сходился, необходимо выполнение условия: |φ'(х)|<1, для

любых х из интервала [a, b]. Чем меньше это значение (φ'(х)), тем быстрее сходится метод. Поэтому, обычно за начальное приближение выбирают тот конец интервала, в котором меньше абсолютное значение производной. Суть метода в том, что  для    значения    х_i-1вычисляется функция φ_(хi-1) и приравнивается к хi. Этот процесс выполняется до тех пор, пока не выполнится условие |х_i- х_i-1| ≤ ε.

      Метод итерации допускает простую геометрическую интерпретацию: строятся две линии: y=x(биссектриса угла х0y) и   y=φ(х) — некоторая кривая. Пересечение этих линий и есть корень уравнения f(х)=0. 

Если найденное каким-либо способом φ(х) не удовлетворяет условию |φ'(х)|<1, то прибегают к следующему простому искусственному приему:

Умножаем обе части уравнения f(х)=0 на α и прибавляем х. Получим:

x = x +a f (x)

φ(х)

Где      

Программа для вычисления корней алгебраического уравнения

program iteracii;

uses crt;

label m;

var a,b,e,z:real;

x:real;

function f(x:real):real;

begin

f:=х*х*х+х-1

end;

function g(x:real):real;

begin

g:=0.94*х-0.06*х*х*х+0.06

end;

function r(x:real):real;

begin

r:= 0.94*х-0.06*х*х*х+0.06

end;

BEGIN

clrscr;

write('a=');

read(a);

write('b=');

read(b);

write('e=');

read(e);

if abs(r(a))<abs(r(b)) then x:=a

    else x:=b;

if abs(r(x))<1 then

  begin

  m: z:=g(x);

if abs(z-x)<e then

  begin

  clrscr;

  writeln('x=',z:4:4);

  writeln('f(x)=',f(z):4:4);

  end

  else begin

  x:=z; goto m;

  end;

  end;

repeat

until keypressed;

END.

В итоге получаем следующие ответы для уравнения x³+x-1=0

4.  Сравнение результатов: