Метод хорд

Метод хорд

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

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

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

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

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

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

Выполнил:

студент 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

Конец

Начало