Метод Ньютона, метод половинного деления

Пермский государственный  технический университет

 

 

 

 

 

Курсовая работа по информатике

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пермь,2011 
Содержание

 

 

 

Задание

Дано уравнение , вид для варианта № 1

В качестве изменяемой переменной выбрана величина . Примем .

Необходимо найти один из корней уравнения двумя методами:

• метод половинного деления;
• метод Ньютона (метод касательных).

Сведения из теории методов решения уравнения

Метод половинного деления

 

Предположим, что корень отделен на отрезке [a, b] .

Разделим этот отрезок пополам точкой . Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a, c] (Рис. 1), либо на отрезке [c, b] (Рис. 2)

 

Рис. 1	Рис. 2

 

Далее определяется значение функции в этой точке: если f(с)< 0, то [a,с], если наоборот, то [с, b], т.е происходит сужение интервала. Выбирая в каждом случае тот отрезок, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.

Таким образом, в результате формируется последовательность xi, где i – номер иттерации.

Вычисления прекращаются, когда разность (b – a) меньше требуемой погрешности.

Метод Ньютона (метод касательных)

 

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

Основная идея метода заключается  в следующем: задается начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берется в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Если  – начальное приближение корня уравнения f(x) = 0, то последовательные приближения находят по формуле

 Если f' и f'' непрерывны и сохраняют  определенные знаки на отрезке  [a, b], а f(a)f(b) < 0 , то, исходя из начального приближения удовлетворяющего условию можно вычислить с любой точностью единственный корень уравнения f(x) = 0.

 

Рис. 3. Иллюстрация метода Ньютона (пунктиром изображена функция , нуль которой необходимо найти, сплошной – касательная в точке очередного приближения ). Здесь можно увидеть, что последующее приближение лучше предыдущего .

 

 

Алгоритм

1. Задается начальное приближение x0.
2. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .

 

 

График функции 

 

В работе составлена программа на языке Pascal, которая выводит в текстовой файл data1.txt в два столбца значения переменной x и функции . (Шаг изменения аргумента принят постоянным). Текст данной программы и результат ее выполнения приведен в приложении.

Затем, используя программное приложение Excel, построен график функции по данным файла data1.txt (рис. 4).

 

Рис. 4. График функции

 

Графически был определен отрезок изменения переменной x вблизи корня уравнения .

Исходные данные для решения задачи:

• границы изменения величины x: а = 1, b = 4
• погрешность вычислений: е  = 0,01.

Границы отрезка и погрешность вычислений были заданы в текстовом файле data2.txt.

 

Блок-схема решения задачи

 

В программе на языке Pascal решения уравнения методами половинного деления и Ньютона (метод касательных):

• исходные данные считываются из файла data2.txt.
• вычисление оформлено в виде подпрограммы (функции)
• решение уравнения каждым методом оформлено в виде подпрограммы (процедуры).

 

Рис. 5. Блок-схема программы  решения

 

 

Рис. 6. Блок-схема процедуры «Метод Ньютона (метод касательных)» 

Рис. 7. Блок-схема процедуры «Метод половинного деления»

 

Исходный текст программы

 

PROGRAM Kurs;

function yn(y:real): real;

begin

yn:=abs(y - (sin(y)/cos(y)));

end;

 

function f(x,y:real): real;

begin

f:=(3*x*x*x-8*sqr(x)-1)/(1+sqr(x)*abs(yn(y)));

end;

 

function fp(x,y:real): real;

begin

fp:=((9*sqr(x)-16*x)*(1+sqr(x)*yn(y))-2*x*yn(y)*(3*x*x*x-8*sqr(x)-1))/sqr(1+sqr(x)*yn(y));

end;

 

Procedure Newt(a2,b2,e2:real);

   VAR i: integer;

   x0, x1, y : real;

   s1 : text;

      BEGIN

      i:=0;

      y:=Pi;

      x0:=a2;

      x1:=x0;

repeat

x0:=x1;

x1:=x0-f(x0,y)/fp(x0,y);

i:=i+1;

   until abs(x1-x0)<e2;

assign(s1,'result.txt');

reset(s1);

    rewrite(s1);

WRITELN (s1, 'Metod Newtona', '   x =', x1:0:3);

WRITELN (s1, ' kolichestvo iteracii  =  ', i);

close(s1);

end;

procedure pol(a1,b1, e1:real);

   VAR i: integer;

   c, x3,y: real;

   s1 : text;

      BEGIN

      c:=(a1+b1)/2;

      i:=0;

while abs (b1-a1)>e1 do

begin

i:=i+1;

if (f(a1,y)*f(c,y))< 0 then

b1:=c

else

a1:=c;

c:=(a1+b1)/2;

end;

x3:=(a1+b1)/2;

  assign(s1,'result.txt');

    reset(s1);

  append (s1);

  WRITELN (s1, 'Metod Polovinnogo delenia', '   x = ', x3:0:3);

   WRITELN (s1, 'kolichestvo iteracii =   ', i);

reset(s1);

  readln(s1);

  close(s1);

end;

VAR a, b : integer;

s: text;

e,y,x1,x3 : real;

BEGIN

y:=Pi;

assign(s,'DATA2.txt');

reset(s);

while not eof(s) do begin

read (s,e);

readln(s);

   read (s,a);

   readln(s);

   read (s,b);

end;

close(s);

newt(a,b,e);

pol(a,b,e);

END.

Результаты расчетов

 

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

Результаты расчетов записываются в текстовой файл result.txt.

 

Выводы по работе

 

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

• метод половинного деления;
• метод Ньютона (метод касательных).

Метод Ньютона более быстрый (необходимо меньшее количество итераций), по сравнению с методом половинного деления.

Метод половинного деления решения уравнений отличается тем, что для него не требуется выполнения условия, что первая и вторая производная сохраняют знак на интервале [a,b], единственным условием его применения является непрерывность исследуемой функции.

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

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

Список использованной литературы

 

1. Калиткин Н. Н. Численные методы. – СПб.: БХВ-Петербург, 2008. – 592 с.
2. Самарский А.А., Гулин А.В. Численные методы. – М.: Наука. 1989. – 432 с.
3. Турчак Л.И., Плотников П.В. Основы численных методов. – М.: Физматлит, – 304 с.
4. Численные методы: Учебное пособие для студентов направления «Прикладная математика и информатика» / М.Г. Бояршинов. – Пермь: ПГТУ, 1998. – 176 с.

 

 

Приложение

 

PROGRAM func;

 

VAR x, i: integer;

y, f : real;

s : text;

BEGIN

 

assign(s,'data1.txt');

rewrite(s);

WRITELN (s, '  x     f(x)');

for x:=-10 to 10 do

BEGIN

y:= Pi;

f:=(3*x*x*x-8*x*x-1)/(1+x*x*abs(y-(sin(y)/cos(y))));

 

WRITELN (s,x,'     ',f:0:2);

end;

close(s);

 

END.