Численные методы решения уравнений

Цель работы:

Изучить численные методы решения уравнений: метод половинного  деления, метод итераций и метод  Ньютона.

Задание (словесная  постановка задачи):

Составить программы для  решения уравнения тремя методами:

1. метод итераций;
2. метод Ньютона;
3. метод половинного деления.

2. Вывести время выполнения алгоритма.

Уравнение:

Входные параметры:

• отрезок, содержащий корень уравнения;
• заданная точность, найденного корня.

 

Ход работы:

1. Итеративная реализация
1. Бинарный поиск

Блок-схема

Листинг

program Bin;

 

var

  a, b, minv, maxv, x, e, en: real;

  start, finish: integer;

 

function f(x: real): real;

begin

  f := 2 * x * sin(x) - cos(x);

end;

 

function bin_min_max(): real;

begin

  while (abs(en) > e) do

  begin

    if f(x) > 0 then maxv := x;

    if f(x) < 0 then minv := x;

    en := abs(maxv - minv);

    x := minv + (maxv - minv) / 2;

  end;

  bin_min_max := x;

end;

 

function bin_max_min(): real;

begin

  while (abs(en) > e) do

  begin

    if f(x) > 0 then minv := x;

    if f(x) < 0 then maxv := x;

    en := abs(maxv - minv);

    x := minv + (maxv - minv) / 2;

  end;

  bin_max_min := x;

end;

 

begin

  write('Введите границы:'); readln(a, b);

  write('Введите требуемую точность решения:'); readln(e);

  start := milliseconds();

  minv := min(a, b);

  maxv := max(a, b);

  x := minv + (maxv - minv) / 2;

  en := abs(b - a);

  if (((f(a) < 0) and (f(b) < 0)) or (((f(a) > 0) and (f(b) > 0)))) then writeln('На данном интервале нет корня!') else begin

    if f(minv) < f(maxv) then writeln('x=', bin_min_max())

    else if f(minv) > f(maxv) then writeln('x=', bin_max_min());

  end;

  finish := milliseconds();

  writeln('Время выполнения алгоритма t=', (finish - start) / 1000, 'с.');

end.

Результаты

2. Метод Ньютона

Блок-схема

 

Листинг

program MethodOfNewton;

 

var

  a, b, x, e, en: real;

  start, finish: integer;

 

function f(x: real): real;

begin

  f := 2 * x * sin(x) - cos(x);

end;

 

function f1(x: real): real;

begin

  f1 := 2 * sin(x) + 2 * x * cos(x) + sin(x);

end;

 

function Newton(): real;

begin

  while (abs(en) > e) do

  begin

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

    en := abs(x - b);

    b := x;

  end;

  Newton := x;

end;

 

 

begin

  write('Введите левую и правую границы интервала:');

  read(a, b);

  write('Введите требуемую точность решения:');

  read(e);

  start := milliseconds();

  en := abs(a - b);

  x := b;

  if (((f(a) < 0) and (f(b) < 0)) or (((f(a) > 0) and (f(b) > 0)))) then writeln('На данном интервале нет корня!') else begin

    writeln('x=', newton());

  end;

  finish := milliseconds();

  writeln('Время выполнения алгоритма t=', (finish - start) / 1000, 'с.');

end.

 

Результаты

 

3. Метод простой итерации

Блок-схема

 

Листинг

program MethodOfIteration;

 

var

  a, b, x, nx, e, ne: real;

  start, finish: integer;

 

function f(x: real): real;

begin

  f := 2 * sin(x) * x - cos(x);

end;

 

procedure iterat(x: real);

begin

  nx := x - f(x) * 0.33;

end;

 

function iteration(): real;

begin

  while(ne > e) do

  begin

    iterat(x);

    ne := abs(nx - x);

    x := nx;

  end;

  iteration := x;

end;

 

begin

  write('Введите границы:'); readln(a, b);

  write('Введите требуемую точность решения:'); readln(e);

  start := milliseconds();

  x := b;

  ne := abs(a - b);

  if (((f(a) < 0) and (f(b) < 0)) or (((f(a) > 0) and (f(b) > 0)))) then writeln('На данном интервале нет корня!') else begin

    writeln('x=', iteration());

  end;

  finish := milliseconds();

  writeln('Время выполнения алгоритма t=', (finish - start) / 1000, 'с.');

end.

 

Результаты

 

2. Рекурсивная реализация
1. Бинарный поиск

Блок-схема

 

Листинг

program Bin;

 

var

  a, b, minv, maxv, x, e, en: real;

  start, finish: integer;

 

function f(x: real): real;

begin

 

  f := 2 * x * sin(x) - cos(x);

 

end;

 

procedure bin_min_max();

begin

  if f(x) > 0 then maxv := x;

  if f(x) < 0 then minv := x;

  en := abs(maxv - minv);

  x := minv + (maxv - minv) / 2;

  if (abs(en) <= e) then writeln('x=', x)

  else bin_min_max();

end;

 

procedure bin_max_min();

begin

  if f(x) > 0 then minv := x;

  if f(x) < 0 then maxv := x;

  en := abs(maxv - minv);

  x := minv + (maxv - minv) / 2;

  if (abs(en) <= e) then writeln('x=', x)

  else bin_max_min();

end;

 

begin

  write('Введите границы:'); readln(a, b);

  write('Введите требуемую точность решения:'); readln(e);

  start := milliseconds();

  minv := min(a, b);

  maxv := max(a, b);

  x := minv + (maxv - minv) / 2;

  en := abs(b - a);

  if (((f(a) < 0) and (f(b) < 0)) or (((f(a) > 0) and (f(b) > 0)))) then writeln('На данном интервале нет корня!') else begin

    if f(minv) < f(maxv) then bin_min_max()

    else if f(minv) > f(maxv) then bin_max_min();

  end;

  finish := milliseconds();

  writeln('Время выполнения алгоритма t=', (finish - start) / 1000, 'с.');

end.

 

Результаты

 

2. Метод Ньютона

Блок-схема 

Листинг

program MethodOfNewton;

 

var

  a, b, x, e, en, nx: real;

  start, finish: integer;

 

function f(x: real): real;

begin

  f := 2 * x * sin(x) - cos(x);

end;

 

function f1(x: real): real;

begin

  f1 := 2 * sin(x) + 2 * x * cos(x) + sin(x);

end;

 

function newx(x: real): real;

begin

  newx := x - f(x) / f1(x);

end;

 

procedure newton();

begin

  x := newx(x);

  en := abs(x - nx);

  nx := x;

  if  abs(en) <= e then writeln('x=', x)

  else newton();

end;

 

begin

  write('Введите левую и правую границы интервала:');

  read(a, b);

  write('Введите требуемую точность решения:');

  read(e);

  start := milliseconds();

  en := abs(a - b);

  x := b;

  nx := b;

  if (((f(a) < 0) and (f(b) < 0)) or (((f(a) > 0) and (f(b) > 0)))) then writeln('На данном интервале нет корня!') else begin

    newton();

  end;

  finish := milliseconds();

  writeln('Время выполнения алгоритма t=', (finish - start) / 1000, 'с.');

end.

 

Результаты

 

Листинг

program MethodOfIteration;

 

var

  a, b, x, nx, e, ne: real;

  start, finish: integer;

 

function f(x: real): real;

begin

  f := 2 * sin(x) * x - cos(x);

end;

 

procedure iterat(x: real);

begin

  nx := x - f(x) * 0.33;

end;

 

procedure iteration();

begin

  iterat(x);

  ne := abs(nx - x);

  x := nx;

  if ne <= e then writeln('x=', x)

  else iteration();

end;

 

begin

  write('Введите границы:'); readln(a, b);

  write('Введите требуемую точность решения:'); readln(e);

  start := milliseconds();

  x := b;

  ne := abs(a - b);

  if (((f(a) < 0) and (f(b) < 0)) or (((f(a) > 0) and (f(b) > 0)))) then writeln('На данном интервале нет корня!') else begin

    iteration();

  end;

  finish := milliseconds();

  writeln('Время выполнения алгоритма t=', (finish - start) / 1000, 'с.');

end.

 

Результаты

 

Вывод

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

Эмпирически определили время  нахождения корня  уравнения с  заданной точностью, на заданном уравнении на интервале [0.4,1] все алгоритмы работают с примерно одинаковой скоростью.

Скорость выполнения: t=0.016 с.

Значение корня: x= 0.653271187026168.

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

Приложение А

 

Список литературы

1. Ахо, А.В Струтуры данных и алгоритмы. [Текст] : Пер. с англ. : Уч. пос / А.В. Ахо, Д. Хопкрофт, Д.Д. Ульман. – М. : Издательский дом «Вильямс», 2000. – 384 с. : ил. – Парал. тит. англ.
2. Ключарев, А.А. Структуры и алгоритмы обработки данных [Текст]: учеб. пособие / А.А. Ключарев, В.А. Матьяш, С.В. Щекин. – СПб.: СПбГУАП, 2003. – 172 с. : ил.
3. Вирт, Н Алгоритмы и структуры данных [Текст]. – М. : Мир, 1989. – 360 с.
4. Википедия [Электронный ресурс]. – URL: http://ru.wikipedia.org/wiki/