Численные методы решения нелинейных уравнений, используемые в прикладных задачах. 
Нахождение корня уравнения методами дихотомии и хорд

Федеральное агентство по образованию ФГОУ СПО «Уфимский авиационный техникум»

Курсовая работа Численные методы решения нелинейных уравнений, используемые в прикладных задачах. Нахождение корня уравнения методами дихотомии и хорд По дисциплине «Численные методы»

Студент: В.С. Гайдуков

Введение

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

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

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

Целью данной курсовой работы является изучение и реализация в программном продукте решения нелинейных уравнений при помощи методов дихотомии и хорд. Данная работа состоит из трёх разделов, заключения и приложения. Первый раздел — теоретический и содержит общие сведения о методах, упомянутых выше. Второй — это практическая часть. Здесь описываются методы, разобранные на конкретных примерах. Третий посвящён тестированию программы и анализу получившихся результатов. В заключении представлен вывод о проделанной работе.

корень дихотомия хорда программа

1. Теоретическая часть Пусть задана непрерывная функция f (х) и требуется найти все или некоторые корни уравнения

f (x)=0 (1)

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

Первая и вторая задачи решаются аналитическими и графическими методами.

Когда ищутся только действительные корни уравнения, то полезно составить таблицу значений f (x). Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки, то, скорее всего, корень между ними только один. Но выявить по таблице корни чётной кратности (совпадающие по значению корни. Например, известно, что уравнение y=x² имеет корень x=0, но правильнее утверждать, что это уравнение имеет 2 кратных корня x₁=0 и x₂=0) сложно. По таблице можно построить график функции у=f (х) и графически найти точки его пересечения с осью абсцисс. Этот способ более нагляден и дает неплохие приближенные значения корней. Во многих задачах техники такая точность уже достаточна. В технике еще популярны графические методы решения уравнений (номография). Построение графика позволяет выявить даже корни чётной кратности.

Иногда удается заменить уравнение (1) эквивалентным ему уравнением (х)=(х), в котором функции y₁=(х) и y₂=(х) имеют несложные графики. Например, уравнение хsinх-1=0 удобно преобразовать к виду sinx=l/x. Абсциссы точек пересечения этих графиков будут корнями исходного уравнения.

Приближенные значения корней уточняют различными итерационными методами. Рассмотрим наиболее эффективные из них.

1.1 Метод половинного деления (дихотомии)

Метод половинного деления или дихотомии (дихотомия — сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f (x)=0 состоит в делении пополам отрезка [a; b], где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка [a; b] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [a; b] становится меньше заданной погрешности нахождения корня ?, либо функция попадает в полосу шума ?1 — значение функции сравнимо с погрешностью расчетов.

Сначала поставим задачу. Дана монотонная, непрерывная функция f (x), которая содержит корень на отрезке [a, b], где b>a. Определить корень с точностью ?, если известно, что f (a)*f (b)<0.

Дано уравнение вида (1).

Необходимо найти удовлетворяющие ему значения x.

Итак, приступим к решению. Первым делом, определимся, что значит f (x)=0. Посмотрите на рис. 1. На нем изображен график некоей функции. В некоторых точках этот график пересекает ось абсцисс. Координаты x этих точек нам и нужно найти. Если вид уравнения простой или стандартный, например, квадратное уравнение или линейное, то применять численный метод здесь совершенно ни к чему. Но если уравнение у нас такое:

f (x)=x3−14×2+x+ex; (2)

то ни в каком учебнике вы не найдете метода аналитического решения этого кошмара. Здесь и приходит на помощь непобедимый численный метод. Метод половинного деления. Из самого названия метода можно предположить, что нам понадобится что-то делить пополам.

Рисунок 1. Метод дихотомии Если требуется найти корень с точностью, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций f (x), в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трех цифр требует 10 итераций (т.к. длина отрезка, на котором лежит корень, после 10 итераций равна ½¹⁰=1/102 410^-3). Зато точность ответа гарантируется.

Перечислим недостатки метода:

1. Для начала расчета надо найти отрезок, на котором функция меняет знак.

2. Если в этом отрезке несколько корней, то заранее неизвестно, к какому из них сойдется процесс (хотя к одному из них сойдется).

3. Метод неприменим к корням четной кратности.

4. Для корней высокой нечетной кратности он сходится, но менее точен и хуже устойчив к ошибкам округления, возникающим при вычислении f (x).

5. Наконец, на системы уравнений дихотомия не обобщается.

Утверждение 1. С помощью данного метода невозможно найти корни чётной кратности.

Доказательство.

Чётно кратный корень это корень уравнения вида

(x+a)²ⁿ=0, где n — целое, n[0,]. (2)

Решением этого уравнения будет корень x=-a кратности 2n. В общем виде уравнение может иметь как чётно, так и нечётно кратные корни. Можно записать общий вид уравнения имеющего (k+m) только действительных корней так:

(x+x₁)²ⁿ¹(x+x₂)²ⁿ²…(x+x_k)^2nk(x+x_k+1)^2n(k+1)+1(x+x_k+2)^2n(k+2)+1…(x+x_k+m)^2n(k+m)+1=0, (3)

где n1,…, n (k+m) [0,] - целые числа; x₁ x₂… x_k+m.

В уравнении (3) k чётно кратных и m нечётно кратных корней. Оно раскладывается на (k+m) уравнений, из которых легко получаются корни. Если задать начальный отрезок [-x₁-r,-x₁+r], где r — мало, и проверить условие смены знака функции на его границах, то обнаружим, что знак не меняется в силу чётности степени. А если аналогично проверить нечётно кратные корни, то получим обратную ситуацию.

Следствие 1.

Если корень имеет чётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет одинаковые знаки.

Следствие 2.

Если корень имеет нечётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет разные знаки.

Пусть на заданном отрезке [a, b] лежит 1 корень чётной кратности, тогда в силу следствия 1 на границах отрезка знак меняться не будет, что означает остановку выполнения итераций и недостижение необходимой точности. Если же на отрезке [a, b] лежит 1 чётно кратный корень и 1 нечётно кратный корень, то чётно кратный корень будет просто игнорирован методом, т.к. условие смены знака являющееся также основным условием, с помощью которого определяется корень на текущем полуотрезке, в силу следствия 1 не выполнится. Следовательно, чётно кратный корень не может быть найден с помощью данного метода.

Утверждение 2. Если на концах начального отрезка значения функции имеют один знак, то метод может не сойтись, то есть, возможно, ни один из корней не будет найден с заданной точностью.

Доказательство.

Первым вариантом постоянства знака функции на границах отрезка является отсутствие корня на нём, поэтому исключим этот случай как тривиальный, будем считать, что на отрезке хотя бы один корень существует. Вторым вариантом — существование чётного количества корней.

Если f (a)f (b)0, то продолжать итерации невозможно, т.к. условие смены знака не подтверждается. Если же, тем не менее, на первом шаге не проверять условие смены знака и разделить отрезок пополам, то может возникнуть ситуация, в которой корни распределяться по чётному количеству в каждой половине отрезка. А чётное количество корней означает чётное количество пересечений оси Ox, даже если существуют кратные корни.

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

Утверждение 3. Если на концах начального отрезка значения функции имеют разные знаки, то будет найден с заданной точностью один из корней лежащих на нём.

Доказательство.

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

Дихотомия применяется тогда, когда требуется высокая надежность счета, а скорость сходимости малосущественна.

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

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

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

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

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

.

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

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

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

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

(4)

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

(5)

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

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

или

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

2. Постановка и решение задачи

2.1 Формулировка задачи Нахождение корня уравнения методом дихотомии и методом хорд (на примере уравнения) с точностью .

2.2 Решение задачи методом дихотомии

Решить дифференциальное уравнение вида с точностью =0.01.

График функции (рис.4) принимает следующий вид на отрезке [-7;2]:

Рисунок 4. График функции f (x)=x*2^x-1

Из него видно, что функция меняет знак на промежутке [0;1].

Разделим этот отрезок на две части и проверим знак функции на концах каждой из них:

f (0)= -1 и f (0,5)=-0,29 289; f (0,5)=-0,29 289 и f (1)=1.

Отсюда видно, что функция меняет знак на отрезке [0,5;1].

Следовательно, следующим отрезком, который мы станем делить, будет именно он.

Аналогично: f (0,5)= -0,29 289 и f (0,75)= 0,261 345; f (0,75)= 0,26 134 и f (1)= 1.

Корень уравнения принадлежит отрезку [0,5;0,75].

Продолжив итерацию, получим:

f (0,5)= -0,29 289 и f (0,625)= -0,3 612; f (0,625)= -0,3 612 и f (0,75)= 0,26 134.

f (0,625)= -0,3 612 и f (0,6875)= 0,107 212; f (0,6875)= 0,107 212 и f (0,75)= 0,26 134.

f (0,625)= -0,3 612 и f (0,6563)= 0,34 352; f (0,6563)= 0,34 352 и f (0,6875)= 0,107 212.

f (0,625)= -0,3 612 и f (0,6407)= -0,109; f (0,6407)= -0,109 и f (0,6563)=0,34 352.

f (0,6407)= -0,109 и f (0,6485)= 0,16 548; f (0,6485)= 0,16 548 и f (0,6563)=0,34 352.

Длина отрезка [0,6407;0,6485] меньше 2. Значит, корнем уравнения можно считать значение его середины, т. е. 0,6446, т.к. оно удовлетворяет заданной погрешности.

2.3 Решение задачи методом хорд

Решить дифференциальное уравнение вида с точностью =0.01.

График функции (рис.5) принимает следующий вид на отрезке [-7;2] (с хордой, проходящей через начало координат и пересекающей график в точке (2;7)):

Рисунок 5. График функции f (x)=x*2^х-1

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

.

Подставив соответствующие значения в эту формулу, получим Х₁:

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

Соответствие значений функции значениям аргументов представлен в табл.1:

Таблица 1.

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

3. Программная реализация

3.1 Блок-схемы

Метод дихотомии

Метод хорд

3.2 Тексты программ

3.2.1 Метод дихотомии

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

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

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

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

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

c — середина отрезка,

d — половина последнего найденного отрезка,

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class (TForm)

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Edit1: TEdit;

Edit2: TEdit;

Button1: TButton;

Edit3: TEdit;

Edit4: TEdit;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1. Button1Click (Sender: TObject);

function f (x:real):real;

begin

f:=x*exp (x*ln (2))-1;

end;

Var b, a, c, d, e, x: real;

begin

a:=strtofloat (edit1.text);

b:=strtofloat (edit2.text) ;

e:=strtofloat (edit3.text) ;

c:=(a+b)/2 ;

d:=(b-a)/2 ;

while d>e do

begin

c:=(a+b)/2;

if f (c)>0 then b:=c

else a:=c;

d:=(b-a)/2;

end;

x:=(b+a)/2;

edit4.text:='x = '+floattostrf (x, fffixed, 10,8);

end;

end.

3.2.2 Метод хорд

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

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

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

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

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

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

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

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

Program metod_chord;

Uses crt;

Var

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

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

Function fx (x:real): real;

begin

fx:=x*(2*(exp (ln (x))))-1;

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))

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

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.

3.3 Тестовый пример

3.3.1 Метод дихотомии

В качестве тестового примера (рис.6) возьмем промежуток [-5;5] и погрешность равную 0,1:

Рисунок 6. Тестовый пример метода дихотомии

3.3.2 Метод хорд

В качестве тестового примера (рис.7) возьмем промежуток [-5;5] и погрешность равную 0,1:

Рисунок 7. Тестовый пример метода хорд

3.4 Решение задачи с помощью ЭВМ

Метод дихотомии

При решении заданного уравнения на языке программирования Borland Delfi, мы получаем следующие результаты (рисунок 8):

Рисунок 8. Реализация на ЭВМ метода дихотомии

Метод хорд

При решении заданного уравнения на языке программирования Turbo Pascal, мы получаем следующие результаты (рисунок 9):

Рисунок 9. Реализация на ЭВМ метода дихотомии

Заключение

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

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

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

1. Калиткин Н. Н. Численные методы. — М.: Наука, 1978. — 512с.

2. Самарский А. А.

Введение

в численные методы. — М.: Наука, 1982. — 272с.

3. Хемминг Р. В. Численные методы/ Пер. с англ. М.: Наука, 1968. — 400с.

4. Численные методы анализа Б. П. Демидович, И. А. Марон и Э. З. Шувалова. — М.: Наука, 1967. — 368с.

5. Баранов А. В., Рябчук Э. В. Численные методы в инженерных задачах. — Волгоград.: Политехник, 1988. — 128с.

6. Фильчаков П. В. Справочник по высшей математике. — Киев: Наукова думка, 1975. — 500с.