Метод хорд


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



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



                   Пояснительная записка к курсовой работе
                        по дисциплине ,,Информатика”



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



                                                                   Выполнил:
                                                          студент 351 группы
                                                               Литвинов Е.П.
                                                                   Проверил:
                                                               Скворцов С.В.



                                Рязань 2004г.
Контрольный пример к курсовой работе студента 351 группы Литвинова Евгения.
      Задание: Разработать программу, которая выполняет уточнение корня
нелинейного уравнения отделенного на заданном интервале [a,b], заданным
методом.
       Решить нелинейное уравнение с использованием разработанной программы
и средств системы  MathCAD. Сравнить полученные результаты.
      Определить количество необходимых итераций для следующих значений
погрешностей результата: Eps=[pic];[pic];[pic];[pic];[pic].
      Используемый метод: метод хорд.
      Контрольный пример: [pic] ;
      Интервал [a,b]: [0,1].

Вариант: 2.2
Задание принял:
Число выдачи задания:
Число выполнения задания:
Проверил: Скворцов С.В.



                                 Метод хорд.

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



      Уравнение хорды - это уравнение прямой, проходящей  через  две  точки
(a, f(a)) и (b, f(b)).
    Общий вид уравнения прямой, проходящей через две точки:
                                    [pic]
    Подставляя в эту формулу значения, получим уравнение хорды AB:

                                   [pic].

    Пусть x1 - точка пересечения хорды с осью x, так как y = 0, то
                                    [pic]
      x1 может считаться приближенным значением корня.
      Аналогично для хорды, проходящей через точки [pic] и [pic],
вычисляется следующее приближение корня:
                                    [pic]

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



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



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



                           Список идентификаторов.
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*=[pic]}
 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))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))/mind Then – сравнение значений модуля производной.

      Функция для указания точности вычисления:
                      Function utoch(eps:real):integer;
      Применяется в выводе корня x для уточнения его порядка относительно
погрешности.
      Здесь  k:=k+1 – оператор, подсчитывающий степень погрешности и
             порядка корня x.

      Заданную функцию запишем так:
                          Function fx(x:real):real;
    Здесь fx:=exp(x)-10*x – наша заданная функция.



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

                                    [pic]


Список используемой литературы:
1) Математическое обеспечение САПР: Методические указания к практическим
занятиям. Рязань, РРТИ, 1990 (№1706).
2) Математическое обеспечение САПР: Методические указания к лабораторным
работам. Рязань, РРТИ, 1991 (№1890).
3) Бахвалов Н.С., Шадков И.П., Кобельников Г.М., Численные методы. М.:
Наука, 1987.
4) Волков Е.А., Численные методы. М.: Наука, 1988.
5) Элементы вычислительной математики, под ред. С.Б.Норкина. М.: Высшая
школа, 1966.

-----------------------
y

x

0

0

x

y

Рис. 1

Рис. 2

[pic]

                                   Начало

                                Введите a и b


                                 Введите eps

Вычисление наименьшего значения функции

                            minimum(a,b,eps,min)

                                    Конец

                                 Корень х= ,
                               x:6:utoch(eps)

                            minimum(a,b,eps,min)

                                  a:=a+eps
                                  b:=b-eps


                             chord(a,b,eps,min)

Уточнение корня методом хорд

Вывод значения x с количеством точек после запятой относительно погрешности
eps

                                   Начало

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


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


                                   min:=d


                                   min >d

Да

                                   Начало

                             chord(a,b,eps,min)

                                    Конец

Нет

                                    t:=k


Нет

Да

                                    min=0

                                    x1:=a


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


                                    x1:=x


                             Abs(fx(x))/min>=eps

Да

Нет

                                    Конец

                            abs(dy/2(2*dx))>=eps

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


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


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


                                  dx:=dx/2


                                    dx:=1


Да

Нет

                                   Начало

                               proizv(x0,eps)


                                    Конец

                                    fx(x)


Нет

Да

                                   eps<=1

                                   k:=k+1


                                 eps:=eps*10


                                    k:=-1


                                   Начало

                                 utoch(eps)


Вычисление
значений модуля производной на концах
промежутка

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

                    Процедура нахождения минимума функции

Количество знаков после запятой в выводе корня  x



Подсчет степени погрешности

                                  a:=a-eps
                                  b:=b+eps


                                proizv:=dy/dx


Сравнение значений производной на концах отрезка

                                    Конец

Ввод значений концов отрезка

Применение рекуррентной формулы уточнения корня

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


Вычисление второй производной

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

Первоначальная величина промежутка

                   Функция уточнения знаков после запятой

                           Описание данной функции

Данная функция

                               fx:=exp(x)-10*x



                                    Конец

                                   Начало