Метод хорд

Дата: 21.05.2016

		

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

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

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

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

Выполнил:
студент 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))<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 :
[pic] [pic]0,11
[pic] [pic]0,111
[pic] [pic]0,1119
[pic] [pic]0,11183
[pic] [pic]0,111833

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

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

[pic]

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

Алгоритм.
Пользуясь рекуррентной формулой (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;
будем иметь в виду, что один из способов найти производную[pic] — это взять
достаточно малые значения справа и слева на равном расстоянии от [pic] —
точке, в которой мы хотим найти производную.
[pic]
Таким образом, вычисляется производная в середине промежутка.
По значениям f' можно таким же способом найти производную от f', т.е.
f''. Можно выразить f'' непосредственно через f(x):

[pic]
[pic]
Для производной третьего порядка можно использовать следующую формулу:
[pic]
Здесь 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) – вычисление
второй производной, для определения точности вычисления,
используется вторая производная в точке [pic]
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 – наша заданная функция.

Блок-схема алгоритма.
[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

Конец

Начало

Метки:
Автор: 

Опубликовать комментарий