Размещено на http://www.allbest.ru/

4

Размещено на http://www.allbest.ru/

1. Анализ предметной области. (Теория). Постановка задачи

Дано нелинейное уравнение на заданном отрезке [-2,0] c заданной точностью =0.0001, нужно реализовать его решение в виде процедуры-подпрограммы следующими методами:

1. методом хорд;

2. методом касательных (Ньютона);

3. методом простой итерации;

4. методом половинного деления.

Заданное уравнение: можно решить двумя методами решения уравнения:

1. Графический метод отделения корней уравнения;

2. Основные методы уточнения корней уравнения.

Основные методы уточнения корней уравнения

Метод половинного деления.

Дано нелинейное уравнение:

	(4.1)

уравнение нелинейный хорда алгоритм

Найти корень уравнения, принадлежащий интервалу [a, b], с заданной точностью .

Для уточнения корня методом половинного деления последовательно осуществляем следующие операции:

1. Делим интервал пополам:

2.

3. В качестве нового интервала изоляции принимаем ту половину интервала, на концах которого функция имеет разные знаки (рис. 1).

Рис. 1. Графический метод отделения корней уравнения методом половинного деления

Для этого:

a) Вычисляем значение функции f(x) в точках a и t.

b) Проверяем: если f(a) f(t) < 0, то корень находится в левой половине интервала [a, b] (рис. 1.а). Тогда отбрасываем правую половину интервала и делаем переприсвоение b=t.

c) Если f(a) f(t) < 0 не выполняется, то корень находится в правой половине интервала [a, b] (рис. 1.б). Тогда отбрасываем левую половину и делаем переприсвоение a=t. В обоих случаях мы получим новый интервал [a, b] в 2 раза меньший предыдущего.

4. Процесс, начиная с пункта 1, циклически повторяем до тех пор, пока длина интервала [a, b] не станет равной либо меньшей заданной точности, т.е.

Схема алгоритма уточнения корней по методу половинного деления представлена на рис. 2.



Рис. 2. Схема алгоритма уточнения корней по методу половинного деления

Метод простых итераций

В ряде случаев весьма удобным приемом уточнения корня уравнения является метод последовательных приближений (метод итераций).

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

Для применения этого метода исходное уравнение f(x)=0 должно быть приведено к виду

	(4.2)

В качестве начального приближения 0 выбираем любую точку интервала [a, b].

Далее итерационный процесс поиска корня строится по схеме:

	(4.3)

В результате итерационный процесс поиска реализуется рекуррентной формулой (4.3). Процесс поиска прекращается, как только выполняется условие

	(4.4)

или число итераций превысит заданное число N.

Для того, чтобы последовательность х₁, х₂,…, х_n приближалась к искомому корню, необходимо, чтобы выполнялось условие сходимости:

	(4.5)

Рис. 3. Геометрический смысл метода

Переходим к построению схемы алгоритма (рис. 4). Вычисление функции оформим в виде подпрограммы.

Рис. 4. Схема алгоритма уточнения корня методом итераций

Метод Ньютона (метод касательных).

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

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

Дано нелинейное уравнение:

f(x)=0

Найти корень на интервале [a, b] с точностью .

Метод Ньютона основан на замене исходной функции f(x), на каждом шаге поиска касательной, проведенной к этой функции. Пересечение касательной с осью Х дает приближение корня (Рис. 5).



Рис. 5. Графический способ отделения корней методом касательных

Выберем начальную точку x₀=b (конец интервала изоляции). Находим значение функции в этой точке и проводим к ней касательную, пересечение которой с осью Х дает нам первое приближение корня x₁.

x₁ = x₀ - h₀,

где

Поэтому



Рис. 6. Схема алгоритма уточнения корня методом Ньютона

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

	(4.6)

Процесс поиска продолжаем до тех пор, пока не выполнится условие:

	(4.7)

Упростим условие (4.7), исходя из (4.6). Получим:

	(4.8)

Метод обеспечивает быструю сходимость, если выполняется условие:



	(4.9)

т.е. первую касательную рекомендуется проводить в той точке интервала [a, b], где знаки функции f(x₀) и ее кривизны f» (x₀) совпадают.

Схема алгоритма уточнения корня метод Ньютона приведена на рис. 6.

Метод хорд

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

При этом в процессе поиска семейство хорд может строиться:

а) при фиксированном левом конце хорд, т.е. z=a, тогда начальная точка х₀=b (рис. 7а);

б) при фиксированном правом конце хорд, т.е. z=b, тогда начальная точка х₀=a (рис. 7б);

Рис. 7. (а, б) Графический способ отделения корней методом хорд

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

для случая а)

	(4.11)

для случая б)



	(4.12)

Процесс поиска продолжается до тех пор, пока не выполнится условие

	(4.13)

Метод обеспечивает быструю сходимость, если f(z) f» (z) > 0, т.е. хорды фиксируются в том конце интервала [a, b], где знаки функции f(z) и ее кривизны f» (z) совпадают. Схема алгоритма уточнения корня методом хорд представлена на рис. 8.

Рис. 8. Схема алгоритма уточнения корня методом хорд

2. Спецификация.

Входные данные:

· E (точность, с которой должен быть вычислен результат)

· a (левая граница промежутка)

· b (правая граница промежутка)

Выходные данные:

· Меню с предлагаемыми методами решения уравнения.

Программа должна:

· Запросить входные данные

· Вывести меню с предлагаемыми методами решения.

· Вывести численное значение результата и количество итераций.

3. Метод решения.

Задачу о нелинейном уравнении можно разбить на три блока:

блок ввода , a, b

блок выбора решения

блок вывода результата

Процесс определения корней алгебраических и трансцендентных уравнений состоит из 2 этапов:

1. отделение корней, - т.е. определение интервалов изоляции [a, b], внутри которого лежит каждый корень уравнения;

2. уточнение корней, - т.е. сужение интервала [a, b] до величины равной заданной степени точности.

Для алгебраических и трансцендентных уравнений пригодны одни и те же методы уточнения приближенных значений действительных корней:

1. метод половинного деления (метод дихотомии);

2. метод простых итераций;

3. метод Ньютона (метод касательных);

4. метод хорд

4. Организация данных.

A, - Левая граница отрезка

B, - Правая граница отрезка

EPS, - Точность нахождения корня

X, - для хранения значения функции

Y, - Для записи конечного результата вычисления

N, - Количество цифр в дробной части при выводе результата N=lg()

Q:integer; - Номер текущего (выбранного) пункта меню

Iter:byte; - Число итераций

CH:char; - Для хранения кода нажатой клавиши

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

Procedure Fon; - {Процедура заполнения всего экрана фоном (символом 'Ш')}

Procedure Pause; - {Процедура, организующая задержку выполнения программы до нажатия любой клавиши}

Procedure Okno (x1, y1, x2, y2:integer); - {Процедура устанавливает окно с координатами верхнего левого угла (x1, y1), правого нижнего - (x2, y2) и устанавливает цвет фона Blue, цвет текста LightRed, очищая окно}

Procedure BiSect (A, B, Eps: Real; Var Iter: Integer; Var Y: Real); - {Процедура, реализующая метод половинного деления}

Procedure Xorda (A, B, Eps: Real; Var Iter: Integer; Var Y: Real); - {Процедура, реализующая метод хорд}

Procedure Newton (A, B, Eps: Real; Var Iter: Integer; Var Y: Real); - {Процедура, реализующая метод касательных (Ньютона)}

Procedure SimIter (A, B, Eps: Real; Var Iter: Integer; Var Y: Real); - {Функция, реализующая метод простой итерации}

Procedure Input (Var A, B, Eps: Real); - {Процедура ввода исходной информации (границ отрезка [a, b] и точности Eps}

Function F (x:real):real; - {Процедура-функция, описывающая решаемое уравнение, предварительно приве-дённое к виду f(x)=0}

Function F1 (x:real):real; - {Процедура-функция, описывающая решаемое уравнение, предварительно приведённое к виду f (x), первая производная функции f(x)}

Function U (x:real):real; - {Процедура-функция, описывающая решаемое уравнение, предварительно приведённое к виду U(x)=x}

Function U1 (x:real):real; - {Процедура-функция, описывающая решаемое уравнение, предварительно приведённое к виду U (x), первая производная функции U(x)}

6. Описание алгоритма

Общий алгоритм

Рис. 9. Блок-схема работы программы

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

Program NonLine; {Заголовок программы решения нелинейных уравнений}

Uses Crt; {Подключение библиотечного модуля CRT}

Var {Начало блока описания переменных}

A, {Левая граница отрезка}

B, {Правая граница отрезка}

EPS, {Точность нахождения корня =10 ^-N}

Y: Real; {Искомое приближённое значение корня}

X: Real; {}

ITER, {Число итераций}

q, {Номер текущего (выбранного) пункта меню}

N: Integer; {Количество цифр в дробной части при выводе результата N=lg()}

Ch: Char; {Для хранения кода нажатой клавиши}

Procedure Fon; {Процедура заполнения всего экрана фоном (символом

'Ш')}

Var i, j: Integer;

Begin

For j:=1 to 25 do begin {Заголовок цикла с параметром j}

GoToXY (1,1); InsLine;

For i:=1 to 80 do Write('Ш') {Вывод заполняющего символа в цикле с параметром i. Этот цикл вложен в предыдущий}

end {Цикла с параметром j}

End; {Процедуры Fon}

Procedure Pause; {Процедура, организующая задержку выполнения программы до нажатия любой клавиши}

Var Ch: Char;

Begin

While KeyPressed do Ch:=ReadKey; {Цикл с предусловием}

Repeat until KeyPressed; {Цикл с постусловием}

While KeyPressed do Ch:=ReadKey; {Цикл с предусловием}

End; {Процедуры Pause}

Function F (x:real):real; {Процедура-функция, описывающая решаемое уравнение, предварительно приве-дённое к виду f(x)=0}

Begin

F:=2-x+x*SQR(x) End; {Функции F}

Function U (x0:real):real; {Процедура-функция, описывающая решаемое уравнение, предварительно приведённое к виду U(x)=x}

Begin

U:=exp (ln(abs (x-2))*(1/3))*(-1);

End;

Function U1 (x:real):real; {Процедура-функция, описывающая уравнение, приведённое к виду U (x) - производная функции U(x)}

Begin

U1:=exp (ln(sqr (x-2))*(-1/3));

End;

Function F1 (x:real):real;

{Процедура-функция, описывающая решаемое уравнение, предварительно приведённое к виду f (x), первая производная}

Begin

f1:=3*x*x-1;

End;

Procedure Okno (x1, y1, x2, y2:integer);

{Процедура устанавливает окно с координатами верхнего левого угла (x1, y1), правого нижнего - (x2, y2) и устанавливает цвет фона Blue, цвет текста LightRed, очищая окно}

Begin

Window (x1, y1, x2, y2);

TextBackGround(Blue); TextColor(LightRed); ClrScr

End; {Процедуры Okno}

Procedure BiSect (A, B, Eps: Real; Var Iter: Integer; Var Y: Real);

{Процедура, реализующая метод половинного деления}

Var {Начало блока описания переменных}

c, {Середина постоянно изменяющегося отрезка [a, b]}

Fa, {Значение функции в точке a}

Fc: Real; {Значение функции в точке c}

Begin {Начало тела процедуры BiSect}

Fa:=F(A); {Вычислить значение функции в левой границе отрезка}

Iter:=0; {Начальное значение количества итераций}

Repeat {Начало цикла деления отрезка пополам. Цикл с постусловием}

c:=(A+B)/2; {Вычислить середину интервала}

Iter:=Iter+1; {Увеличить число итераций на единицу. Эквивалентно

Inc(Iter);}

Fc:=F(c); {Вычислить значение функции в середине отрезка}

If Fa*Fc<=0 {Если значения функции в точках а и с имеют разные знаки}

then B:=c {То конец отрезка перенести в середину}

else A:=c {В противном случае начало отрезка перенести в середину}

until (B-A)<Eps; {Конец цикла деления отрезка пополам, когда его

длина станет меньше заданной точности}

Y:=(A+B)/2 {В качестве возвращаемого результата взять середину последнего, самого короткого отрезка}

End; {Процедуры BiSect}

Procedure Xorda (A, B, Eps: Real; Var Iter: Integer; Var Y: Real);

{Процедура, реализующая метод хорд}

Var Fx, Fz, z, h: Real;

begin

Iter:=0; {Начальное значение количества итераций}

If (F(b)*F2 (b))>0 {Если значение функции и ее кривизны в точке b совпадают}

then begin x:=b z:=a end {Если да}

else begin x:=a z:=b end; {Если нет}

Fz:=F(z); {Находим значение функции в точке z}

repeat {Начало цикла приближения корня. Цикл с постусловием}

Fx:=F(x); {Находим значение функции в точке x}

h:=(x-z)*Fx/(Fx-Fz); {Длина интервала}

x:=x-h; {Приближение корня равно разности текущего значения с длиной интервала}

Iter:=Iter+1; {Увеличить число итераций на единицу. Эквивалентно Inc(Iter)}

until ABS(h)<EPS; {Конец цикла, когда длина отрезка станет меньше заданной точности}

y:=x; {В качестве возвращаемого результата взять последнее значение хорды}

end; {Конец Процедуры Xorda}

Procedure Newton (A, B, Eps: Real; Var Iter: Integer; Var Y: Real);

{Процедура, реализующая метод касательных (Ньютона)}

var h:real;

Begin

Iter:=0; {Начальное значение количества итераций}

If (F(b)*F2 (b))>0 {Если значение функции и ее кривизны в точке b совпадают}

then x:=b; {Начальная точка правый конец интервала}

If (F(a)*F2 (a))>0 {Если значение функции и ее кривизны в точке a совпадают}

then x:=a {Начальная точка левый конец интервала}

else x:=(a+b)/2; {Начальная точка середина интервала}

Repeat {Начало цикла. Цикл с постусловием}

h:=f(x)/f1 (x); {Длина интервала}

x:=x-h; {Приближение корня равно разности текущего значения с длиной интервала}

Iter:=Iter+1; {Увеличить число итераций на единицу}

Until abs(h)<eps; {Конец цикла, когда |h| станет меньше или равным заданной точности}

y:=x; {Результату присвоить значение x}

end; {Конец Процедуры Newton}

Procedure SimIter (A, B, Eps: Real; Var Iter: Integer; Var Y: Real);

{Функция, реализующая метод простой итерации}

Var x0:real;

begin

X0:=a; {Начальное приближение корня, одна из точек интервала}

x:=0; {Значению x присвоим значение, которому равно x0, для того чтобы в цикле, в качестве первого значения x0, было значение x=a=0}

Iter:=0; {Начальное значение количества итераций}

if abs (U1 (x0))<1 then {Если значение производной функции U(x), в точке приближения <1, то поиск корня будет сходиться к искомому корню}

begin

repeat {Начало цикла. Цикл с постусловием. Выполнять, пока не выполнится условие: модуль разности предыдущего значения Х со следующим значением меньше заданной точности}

begin

x0:=x; {В качестве следующего x0 примем предыдущее значение x}

x:=U(x0); {Значению Х присвоить очередное значение, вычисленное из функции U(x)}

Iter:=Iter+1; {Увеличить число итераций на единицу}

end;

until abs (x-x0)<eps

y:=x; {Результату присвоить значение x}

end; {Конец процедуры SimIter}

Procedure Input (Var A, B, Eps: Real);

{Процедура ввода исходной информации (границ отрезка [a, b] и точности Eps}

Var

K: Integer;

M: String;

Begin {Начало тела процедуры Input}

Okno (25,3,55,6);

Repeat {Начало цикла ввода левой границы a}

GoToXY (5,1); ClrEol;

Write ('Введите A=',#7); ReadLn(M); Val (M, A, K)

until (K=0); {Конец цикла ввода левой границы a}

Repeat {Начало цикла ввода правой границы b}

GoToXY (5,2); ClrEol;

Write ('Введите B=',#7); ReadLn(M); Val (M, B, K)

until (K=0) and (B>A); {Конец цикла ввода правой границы b}

Repeat {Начало цикла ввода точности Eps}

GoToXY (5,3); ClrEol;

Write ('Введите Eps=',#7); ReadLn(M); Val (M, EPS, K)

until (K=0) and (Eps>0) and (Eps<1) {Конец цикла ввода точности Eps}

End; {Процедуры Input}

BEGIN {Начало тела программы NonLine}

TextBackGround(LightGray); {Установить цвета фона}

TextColor(Magenta); {и текста}

ClrScr; Fon; {Очистить экран и заполнить его фоном}

Input (A, B, EPS); {Ввести исходные данные}

N:=-Round (Ln(EPS)/Ln(10)); {Вычислить количество значащих цифр в дробной части результата}

q:=2; {Установить начальное значение пункта (строки) меню}

While True do begin {Начало бесконечного цикла регенерации меню}

Okno (25,10,55,16); {Открыть окно для вывода строк меню}

WriteLn (' Укажите МЕТОД вычисления:'); {Вывести шесть строк меню,}

WriteLn (' 1. Деления отрезка пополам '); {включая его заголовок}

WriteLn (' 2. Хорд ');

WriteLn (' 3. Касательных (Ньютона) ');

WriteLn (' 4. Простой итерации ');

WriteLn (' 5. Выход ');

GoToXY (1, q); Write ('=>'); {Вывести в q-й строке стрелку}

Repeat {Начало цикла движения по меню и выбора необходимого пункта}

CH:=ReadKey; {Ожидать нажатия любой клавиши}

GoToXY (1, q); Write (' '); {Вывести в q-й строке пробелы, убрав стрелку}

Case CH of {Проверить, что нажали, и выполнить выбранное действие}

#72,#73:q:=q-1; {Стрелка или клавиша PgUp}

#80,#81:q:=q+1; {Стрелка vили клавиша PgDn}

#71:q:=2; {Клавиша Home}

#79,#27:q:=6 {Клавиши End или Esc}

end; {Для Case}

If q=1 then q:=6; {Проверить, не выбрана ли первая строка (заголовок) меню}

If q=7 then q:=2; {Проверить, не вышли ли за последнюю строку меню}

GoToXY (1, q); Write ('=>'); {Вывести в выбранной q-й строке стрелку}

until CH in [#13,#27]; {Конец цикла движения по меню, если была нажата клавиша Enter или Esc}

Case q of {Проверить, какой пункт меню выбран, выполнить подпрограмму, его реализующую}

2: BiSect (A, B, EPS, ITER, Y); {Если q=2, то метод половинного деления}

3: Xorda (A, B, EPS, ITER, Y); {Если q=3, то метод хорд}

4: Newton (A, B, EPS, ITER, Y); {Если q=4, то метод Ньютона}

5: SimIter (A, B, EPS, ITER, Y); {Если q=5, то метод простой итерации}

6:begin {Если q=6, то закончить работу программы}

Window (1,1,80,25); ClrScr; Halt

end

end; {Для Case}

Okno (25,18,55,21); {Открыть окно для вывода результатов}

GoToXY (1,1); WriteLn ('КОРЕНЬ=', Y:4:N); {Вывести корень}

GoToXY (1,2); WriteLn ('Количество итераций=', ITER:5); {Количество итераций}

GoToXY (1,3); WriteLn ('F(', Y:4:N, ')=', F(Y):10:15); {Значение функции}

Pause; ClrScr {Приостановка выполнения программы с последующей очисткой окна результатов}

end; {Конец бесконечного цикла регенерации меню}

END. {Программы NonLine

Результаты

В ходе работы программы получены следующие результаты:

	X c точностью 0.0001	Количество итераций
1 Метод дихотомии	-1.5214	12
2 Метод хорд	-1.5214	8
3 Метод касательных	-1.5214	6
4 Метод простой итерации	-1.5214	5



Рис. 11. Метод простой итерации

Рис. 12. Метод касательных



Рис. 13. Метод хорд

Рис. 14. Метод половинного деления

Вывод: в результате решения уравнения четырьмя способами: метод половинного деления(дихотомии), хорд, касательных(Ньютона), простой итерации; был выбран наиболее эффективный метод нахождения корня - это метод простой итерации.

Список использованных источников

1. Алгоритмизация и программирование на Турбо Паскале. Новичков В.С., Парфилова Н.И., Пылькин А.Н., «Горячая линия-Телеком, Радио и связь» 2005, 462 стр.

2. Методические указания по подготовке отчета по учебной практике.

3. Численные методы решения нелинейных уравнений.

4. Фаронов В.В. «Программирование на персональных ЭВМ в среде Турбо-Паскаль.» - М.: Изд-во МГТУ, 1990. - 446 стр.

Размещено на Allbest.ru