Метод хорд

Метод хорд

Министерство образования и науки РФ

Рязанская Государственная Радиотехническая Академия

Кафедра САПР ВС

Пояснительная записка к курсовой работе

по дисциплине ,,Информатика” 

Тема: ,,Метод хорд” 

Выполнил:

студент 351 группы

Литвинов Е.П.

Проверил:

Скворцов С.В.

Рязань 2004г.

Контрольный пример к курсовой работе студента 351 группы Литвинова Евгения.

         Задание: Разработать программу, которая выполняет уточнение корня нелинейного уравнения отделенного на заданном интервале [a,b], заданным методом.

          Решить нелинейное уравнение с использованием разработанной программы и средств системы  MathCAD. Сравнить полученные результаты. 

Определить количество необходимых итераций для следующих значений погрешностей результата: Eps=;;;;.

         Используемый метод: метод хорд.

            Контрольный пример:  ;

            Интервал [a,b]: [0,1].

Вариант: 2.2

Задание принял:

Число выдачи задания:

Число выполнения задания:

Проверил: Скворцов С.В.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Метод хорд.

Пусть дано уравнение  , где  - непрерывная функция, имеющая в интервале (a,b) производные первого и второго порядков. Корень считается отделенным и находится на отрезке [a,b].

Идея метода хорд состоит в том, что на достаточно малом промежутке [a,b] дугу кривой можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай (рис.1), когда первая и вторая производные имеют одинаковые знаки, т.е. .



  Уравнение хорды - это уравнение прямой, проходящей через две точки (a, f(a)) и (b, f(b)). 

Общий вид уравнения прямой, проходящей через две точки: 



Подставляя в эту формулу значения, получим уравнение хорды AB: 

.

Пусть x1 - точка пересечения хорды с осью x, так как y = 0, то 



x1 может считаться приближенным значением корня. 

Аналогично для хорды, проходящей через точки  и , вычисляется следующее приближение корня:



В общем случае формулу метода хорд имеет вид:

                                                                (1)

Если первая и вторая производные имеют разные знаки, т.е. , то все приближения к корню  выполняются со стороны правой границы отрезка  (рис.2) и вычисляются по формуле: 

                                                                (2)



Выбор формулы в каждом конкретном случае зависит от вида функции  и осуществляется по правилу: неподвижной является такая граница отрезка   изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (1) используется в том случае, когда . Если справедливо неравенство , то целесообразно применять формулу (2).

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

Если обозначить через m наименьшее значение |f'(x)| на промежутке     [a, b], которое можно определить заранее, то получим формулу для оценки точности вычисления корня:            

  или  

где - заданная погрешность вычислений.

Список идентификаторов.

a – начало отрезка,

b – конец отрезка,

eps – погрешность вычислений,

x – искомое значение корня,

min – модуль значения производной функции в начале отрезка,

d – модуль значения производной функции в конце отрезка,

x0 – точка, в которой мы ищем производную.

****************************************************************

Program kursovaia;

 uses crt;

 Var

  a,b,eps,x,min: real;

{Вычисление данной функции}

 Function fx(x:real): real;

  begin

   fx:=exp(x)-10*x;

  end;

----------------------------------------------------------------

{Функция вычисления производной и определение точности вычислений}

{Для определения точности вычисления берем значение 2-й производной в точке x*=}

 Function proizv(x0,eps: real): real;

  var

   dx,dy,dy2: real;

  begin

   dx:=1;

   Repeat

    dx:=dx/2;

    dy:=fx(x0+dx/2)-fx(x0-dx/2);

    dy2:=fx(5*x0/4+dx)-2*fx(5*x0/4);

    dy2:=dy2+fx(5*x0/4-dx);

   Until abs(dy2/(2*dx))<eps;

    proizv:=dy/dx;

  end;

----------------------------------------------------------------

{Уточнение количества знаков после запятой}

 Function utoch(eps:real): integer;

  var

   k: integer;

  begin

   k:=-1;

   Repeat

    eps:=eps*10;

    k:=k+1;

   Until eps>1;

  utoch:=k;

 end;

----------------------------------------------------------------

{Процедура определения наименьшего значения производной на

 заданном промежутке}

 Procedure minimum(a,b,eps: real; var min: real);

  var

   d: real;

  begin

   a:=a-eps;

   b:=b+eps;

    Repeat

     a:=a+eps;

     b:=b-eps;

     min:=abs(proizv(a,eps));

     d:=abs(proizv(b,eps));

     If min>d Then min:=d

    Until min <>0

  end;

----------------------------------------------------------------

{Процедура уточнения корня методом хорд}

Procedure chord(a,b,eps,min: real; var x:real);

 Var

  x1: real;

 begin

  x1:=a;

   Repeat

    x:=x1-((b-x1)*fx(x1))/(fx(b)-fx(x1));

    x1:=x

   Until abs(fx(x))/min<eps

 end;

----------------------------------------------------------------

{Основная программа}

 Begin

  clrscr;

  Writeln ('Введите начало отрезка a, конец отрезка b');

  Readln (a,b);

  Writeln ('Введите погрешность измерений eps');

  Readln (eps);

  minimum(a,b,eps,min);

  chord(a,b,eps,min,x);

  Writeln ('Корень уравнения x= ',x:3:utoch(eps));

End.

****************************************************************

После работы программы для различных значений погрешностей, получим результаты корня x :

    0,11

    0,111

    0,1119

    0,11183

    0,111833

Результат вычислений в программе MathCAD  дал следующее значение корня x:

x=0.112

График функции выглядит так:



Поведение функции вблизи точки пересеченья с осью ОХ выглядит так:



 

 

 

 

 

 

 

 

 

 

Алгоритм.

Пользуясь рекуррентной формулой (2) и формулой  для оценки точности вычисления, составим процедуру уточнения корня методом хорд: 

Procedure chord(a, b, eps, min : real; var x : real);

Здесь  x:=x1-((b-x1)*fx(x1))/(fx(b)-fx(x1)) – рекуррентная формула,

          abs(fx(x))/min < eps – формула для оценки точности вычислений.

При вычислении производной функции

Function proizv(x0, eps : real) : real;

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



Таким образом, вычисляется производная в середине промежутка. 

По значениям f' можно таким же способом найти производную от f', т.е. f''. Можно выразить f'' непосредственно через f(x): 





Для производной третьего порядка можно использовать следующую формулу: 



Здесь dx:=1 - первоначальная величина промежутка,

         dx:=dx/2 – для уточнений делим промежуток на 2,

dy:=fx(x0+dx/2 -fx(x0-dx/2) – вычисление первой производной в точке x0 ,

dy2:=fx(5*x0/4+dx)-2*fx(5*x0/4)+fx(5*x0/4-dx) – вычисление второй производной, для определения точности вычисления, используется вторая производная в точке 

abs(dy2/(2*dx))<eps  -  формула для оценки погрешности 

дифференцирования,

proizv:=dy/dx – значение первой производной.

Для оценки точности вычисления корня необходимо вычислять наименьшее значение производной f'(x) на промежутке [a, b], поэтому надо найти производную в точке x0.

Так как мы вычислили значение производной, то составим процедуру определения модуля ее наименьшего значения на промежутке [a, b]:

Procedure minimum(a,b,eps:real;var min:real);

Для этого достаточно сравнить модуль значения производной на концах промежутка и выбрать среди этих двух значений меньшее. Это можно сделать , так как по условию, функция на промежутке строго монотонна вместе со своими производными первого и второго порядков. Следует брать значение очень близкое к a, но справа от нее, аналогично для точки b - брать близкое значение слева от b, так как если в точке a или b производная будет равна нулю, тогда деление на нуль станет невозможным и в программе будет получена ошибка.

Здесь  min:=abs(proizv(a,eps))- модуль значения производной функции в начале отрезка,

d:=abs(proizv(b,eps))- модуль значения производной функции в конце отрезка,

If min>d Then – сравнение значений модуля производной.

         Функция для указания точности вычисления:

Function utoch(eps:real):integer;

     Применяется в выводе корня x для уточнения его порядка относительно погрешности.

Здесь  k:=k+1 – оператор, подсчитывающий степень погрешности и  порядка корня x.

Заданную функцию запишем так:

Function fx(x:real):real;

Здесь fx:=exp(x)-10*x – наша заданная функция.

         

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Блок-схема алгоритма.













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

1) Математическое обеспечение САПР: Методические указания к практическим занятиям. Рязань, РРТИ, 1990 (№1706).

2) Математическое обеспечение САПР: Методические указания к лабораторным работам. Рязань, РРТИ, 1991 (№1890).

3) Бахвалов Н.С., Шадков И.П., Кобельников Г.М., Численные методы. М.: Наука, 1987.

4) Волков Е.А., Численные методы. М.: Наука, 1988.

5) Элементы вычислительной математики, под ред. С.Б.Норкина. М.: Высшая школа, 1966.