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

СОДЕРЖАНИЕ



	ВВЕДЕНИЕ	4

	1. ПОСТАНОВКА ЗАДАЧИ	5

	2. МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ	6

	3 .СООТВЕТСТВИЕ МЕЖДУ ПЕРЕМЕННЫМИ, ПРИНЯТЫМИ ПРИ ОПИСАНИИ ЗАДАЧИ И В ПРОГРАМЕ	9

	4. СТРУКТУРНАЯ СХЕМА ПРОГРАММ И ЕЕ ОПИСАНИЕ	12

	5. ЛИСТИНГ ПРОГРАМЫ	20

	6. КОНТРОЛЬНЫЙ ПРИМЕР И АНАЛИЗ РЕЗУЛЬТАТА	21

	7. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ	26

	ЗАКЛЮЧЕНИЕ	27

	СПИСОК ЛИТЕРАТУРЫ	28

	ПРИЛОЖЕНИЯ	29

	ПРИЛОЖЕНИЕ А	30

	ПРИЛОЖЕНИЕ Б.	32

	ПРИЛОЖЕНИЕ Д.	33






ВВЕДЕНИЕ

Паскаль − один из наиболее распространенных процедурно-ориентированных языков программирования 80 - 90-х годов, имеет свою достаточно интересную историю, начало которой положило объявление в 1965 г. конкурса по созданию нового языка программирования - преемника Алгола - 60. Участие в конкурсе принял швейцарский ученый Николаус Вирт, который работал на факультете информатики Стэндфордского университета. Проект, предложенный им, был отвергнут комиссией в 1967 г. Но Вирт не прекратил работу. Вернувшись в Швейцарию, совместно с сотрудниками Швейцарского федерального института технологии в Цюрихе, он уже в 1968 г. разработал новую версию языка Паскаль, названного так в честь великого французского математика и механика Блеза Паскаля, создавшего в 1642 г. первую счетную машину. В 1971 г. Н. Вирт выпустил описание своего языка, а в 1975 г. было разработано руководство для пользователей версии Паскаля, которая практически легла в основу стандарта языка. Но стандарт языка появился только в 1982 г.

Предназначенный для обучения, язык оказался очень простым и одновременно строгим. Однако вскоре выяснилось, что он также является достаточно эффективным в самых различных приложениях. Pascal поддерживает самые современные методологии проектирования программ (нисходящее, модульное проектирование, структурное программирование). В связи с этим появились многочисленные реализации языка для разных машинных архитектур и наиболее удачной и популярной оказалась разработка фирмы Borland International для персональных IBM - совместимых ЭВМ. Эта реализация языка получила название Turbo Pascal (Турбо Паскаль) и имеет уже несколько версий.

Turbo Pascal представляет собой систему программирования, включающую в себя текстовый редактор, компилятор, компоновщик, загрузчик, отладчик, файловую систему, системную библиотеку, справочную систему. Все эти компоненты объединены в интегрированную среду с многооконным интерфейсом и развитой системой меню, что обеспечивает высокую производительность труда программиста при создании программ производственного, научного и коммерческого назначения.




1. ПОСТАНОВКА ЗАДАЧИ

	Написать программу на языке программирования Pascal, выполняющую решение нелинейного уравнения. Результат работы программы должен выводиться на экран и в файл.

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

1-Ввести данные из файла

2-Ввести данные с клавиатуры

3-Отобразить результат

4-Сохранить результат в файл

0-Выход

Отладить программу на уравнении f(x)=x2-x-6  с точностью 0,001






2. ВЫБОР И ОПИСАНИЕ МЕТОДОВ РЕШЕНИЯ

Процесс нахождения приближенного значения корней уравнения можно подразделить на два этапа 1) отделение корней; 2) уточнение корней до заданной степени точности. Корень ξ считается отделённым на отрезке [a,b], если на этом отрезке уравнение 



: метод половинного деления, Ньютона 

2.1. МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ

Пусть дано уравнение f(x) = 0, где f (х) – непрерывная функция. Требуется найти корень этого уравнения ξ с точностью до ε, где е – некоторое положительное достаточно малое число.

Будем считать, что корень ξ отделен и находится на отрезке [а, b], т. е. имеет место неравенство а ≤ ξ ≤ b. Числа а и b – приближенные значения корня ξ соответственно с недостатком и с избытком. Погрешность этих приближений не превышает длины отрезка b – а. Если b – а ≤ε, то необходимая точность вычислений достигнута, и за приближенное значение корня ξ можно принять либо а, либо b. Но если b – а > ε, то требуемая точность вычислений не достигнута и необходимо сузить интервалов котором находится корень ξ, т. е. подобрать такие числа а и b, чтобы выполнялись неравенства a < ξ < b и . При  вычисления следует прекратить и за приближенное значение корня с точностью до ε принять либо а, либо b. Следует отметить, что значение корня будет более точным, когда за приближенное значение корня приняты не концы отрезка а и b, а середина этого отрезка, т.е. . Погрешность в этом случае не превышает величины .

Метод проб. Пусть дано уравнение f(x) = 0 [f(x) – непрерывная функция] и корень ε отделен на отрезке [а, b], т. е. f(а) ∙ f(b) < 0, причем b – а > ε. Требуется найти значение корня ξ с точностью до ε (рис. 2.1) 






Рис. 2.1

Принцип решения уравнения типа y=f(x) методом проб



Рис. 2.2

Принцип решения уравнения типа y=f(x) методом половинного деления




На отрезке [a, b] выберем произвольным образом точку a1, которая разделит его на два отрезка [a, a1] и [a1,b]. Из этих двух отрезков следует выбрать тот, на концах которого функция принимает значения, противоположные по знаку. В нашем примере f(а) ∙ f(a1) > 0, f(a1) ∙ f(b) < 0; поэтому следует выбрать отрезок [a1,b]. Затем на этом суженом отрезке опять произвольным образом возьмем точку а2 и найдем знаки произведений f(a1) ∙ f(a2) и f(a2) ∙ f(b). Так как f(a2)× f(b) < 0, то выбираем отрезок [a2, b]. Этот процесс продолжаем до тех пор, пока длина отрезка, на котором находится корень, не станет меньше ε. Корень ξ получим как среднее арифметическое концов найденного отрезка, причем погрешность корня не превышает ε/2.

Метод проб в таком виде на ЭВМ не применяется. Для составления программ и расчетов на ЭВM метод проб применяется в виде так называемого метода половинного деления.

Пусть корень ξ уравнения f(х) = 0 отделен и находится на отрезке [a, b], т.е. f(a) ∙ f(b) < 0, причем b – а > ε [здесь f(х) – непрерывная функция]. Как и ранее, возьмем на отрезке [a, b] промежуточную точку, однако не произвольным образом, а так, чтобы она являлась серединой отрезка [a, b], т. е. с = (а + b)/2. Тогда отрезок [a, b] точкой с разделится на два равных отрезка [а, с] и [с, b], длина которых равна (b – а)/2 (рис. 2.2). Если f(с) = 0, то с – точный корень уравнения f(х) = 0. Если же f(с) ≠ 0, то из двух образовавшихся отрезков [a, с] и [с, b] выберем тот, на концах которого функция f(х) принимает значения противоположных знаков; обозначим его [al, b1]. Затем отрезок [al, b1] также делим пополам и проводим те же рассуждения. Получим отрезок [а2, b2], длина которого равна (b – а)/22. Процесс деления отрезка пополам производим до тех пор, когда на каком-то n-м этапе либо середина отрезка будет корнем уравнения (случай, весьма редко встречающийся на практике), либо будет получен отрезок [an, bn] такой, что bn – аn = (b – а)/2n ≤ ε и аn ≤ ξ ≤ bn (число n указывает на количество проведенных делений). Числа аn и bn – корни уравнения f(х) = 0 с точностью до ε. За приближенное значение корня, как указывалось, выше, следует взять ξ = (an + bn)/2, причем погрешность не превышает (b – а)/2n+1.

2.2. МЕТОД ХОРД

Метод хорд является одним из распространенных методов решения алгебраических и трансцендентных уравнений. В литературе он также встречается под названиями «метода ложного положения» (regula falsi), «метода линейного интерполирования» и «метода пропорциональных частей».

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

Идея метода хорд состоит в том, что на достаточно малом промежутке [а, b] дуга кривой у = f (x) заменяется стягивающей ее хордой. В качестве приближенного значения корня принимается точка пересечения хорды с осью Ох.

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

Рассмотрим случаи, когда первая и вторая производные имеют одинаковые знаки, т. е, f'(х) ∙ f'' (х) > 0.

Пусть, например, f(a) < 0, f(b) > 0, f'(х) > 0, f''(х) > 0 (рис. 3.18, а). График функции проходит через точки А0 (a; f(a)), В(b; f(b))- Искомый корень уравнения f(х) = 0 есть абсцисса точки пересечения графика функции у = f(х) с осью Ох. Эта точка нам неизвестна, но вместо нее мы возьмем точку x1 пересечения хорды А и В с осью Ох. Это и будет приближенное значение корня.

Уравнение хорды, проходящей через точки А0 и В, имеет вид



Найдем значение х = х1, для которого у = 0:



Эта формула носит название формулы метода хорд. Теперь корень ξ находится внутри отрезка [x1, b]. Если значение корня х1 нас не устраивает, то его можно уточнить, применяя метод хорд к отрезку [х1, b]. 



Рис 


Соединим точку А1 (x1; f (x1) с точкой В (b; f (b)) и найдем х2 – точку пересечения хорды А1В с осью Ох:



Продолжая этот процесс, находим



и вообще 



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

По приведенным выше формулам вычисляются корни и для случая, когда f(а) > 0, f(b) < 0, f'(x) < 0, f''(x) < 0 (рис. 3.18, б).

Теперь рассмотрим случаи, когда первая и вторая производные имею разные знаки, т.е. f'(x) ∙ f'(x) < 0.

Пусть, например, f(a) > 0, f(b) < 0, f'(х) < 0, f''(х) > 0 (рис. 3.19, а). Соединим точки A (a; f (а)) и В0 (b; f (b)) и запишем уравнение хорды, проходящей через А и B0:



Найдем х1, как точку пересечения хорды с осью Ох, полагая у = 0:



Корень ξ теперь заключен внутри отрезка [a, x1]. Применяя меч од хорд к отрезку [а, x1], получим



и вообще



По этим же формулам находится приближенное значение корня и для случая, когда f(а) < 0, f(b)>0, f'(х) > 0, f''(х) < 0 (рис. 3.19, б).

Итак, если f'(х) ∙ f"(х) > 0, то приближенный корень вычисляется по формулам (1) и (2); если же f(х) ∙ f"(x) < 0, то – по формулам (3) и (4).

Однако выбор тех или иных формул можно осуществить, пользуясь простым правилом: неподвижным концом отрезка является тот, для которого знак функции совпадает со знаком второй производной.

Если f(b) ∙ f'' (х) > 0, то неподвижен конец b, а все приближения к корню ξ лежат со стороны конца а [формулы (1) и (2)]. Если f(а)×f''(x) > 0. то неподвижен конец а, а все приближения к корню ξ лежат со стороны конца b [формулы (3) и (4).

2.3. МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ)

Пусть корень уравнения f (х) = 0 отделен на отрезке [а, b], причем f'(х) и f"(x) непрерывны и сохраняют постоянные знаки на всем отрезке [а, b].

Геометрический смысл метода Ньютона состоит в том, что дуга кривой у = f(х) заменяется касательной к этой кривой (отсюда и второе название: метод касательных).

Первый случай. Пусть f(a) < 0, f(b) > 0, f’(х) > 0, f”(х) > 0 (рис. 1, а) или f(а) > 0, f(b) < 0, f’(х) < 0, f ''(х) < 0 (рис. 1, б). Проведем касательную к кривой у = f(x) в точке B0(b; f(b)) и найдем абсциссу точки пересечения касательной с осью Oх. Известно, что уравнение касательной в точке В0(b; f(b)) имеет вид





N

x

A

B0

b=x0

x1

x2

x3

B1

ξ

a

f(a)

0

y

f(b)

N

x

A

B0

b=x0

x1

x2

x3

B1

ξ

a

f(a)

0

y

f(b)

б)

а)

Рис. 1.

Полагая у = 0, х = х1, получим

					(1)

Теперь корень уравнения находится на отрезке [а, х1]. Применяя снова метод Ньютона, проведем касательную к кривой в точке B1 (x1; f(x1)) и полечим



и вообще

						(2)

Получаем последовательность приближенных значений x1, х2, …, xn, …, каждый последующий член которой ближе к корню ξ, чем предыдущий. Однако все хn, остаются больше истинного корня ξ, т.е. хn – приближенное значение корня ξ с избытком.

Второй случай. Пусть f(а) < 0, f (b) > 0, f '(х) > 0, f ''(х) < 0 (рис. 2, а) или f(а)> 0, f(b) < 0, f '(х) < 0, f ''(x) > 0 (рис. 2, б). Если снова провести касательную к кривой у= f (x) в точке В, то она пересечет ось абсцисс в точке, не принадлежащей отрезку [a, b]. Поэтому проведем касательную в точке A0(a; f(а)) и запишем ее уравнение для данного случая:



Полагая у = 0, x = x1 находим

					(3)

Корень ξ находится теперь на отрезке [х1, b]. Применяя снова метод Ньютона, проведем касательную в точке A1 (x1; f(x1)) и получим



и вообще



						(4)



ξ

b

B

f(b)

f(a)

a=x0

x1

x2

x

y

N

0

A0

ξ

b

B

f(b)

f(a)

a=x0

x1

x2

x

y

N

0

A0

Рис. 2.

а)

б)

Получаем последовательность приближенных значений х1, х2, … ,хn,…, каждый последующий член которой ближе к истинному корню ξ, чем предыдущий, т.е. хn – приближенное значение корня ξ с недостатком.

Сравнивая эти формулы с ранее выведенными, замечаем, что они отличаются друг от друга только выбором начального приближения: в первом случае за х0 принимался конец b отрезка, во втором – конец а.

При выборе начального приближения корня необходимо руководствоваться следующим правилом: за исходную точку следует выбирать тот конец отрезка [а, b], в котором знак функции совпадает со знаком второй производной. В первом случае f(b) ∙ f ''(х) > 0 и начальная точка b = x0, во втором f(a) ∙ f "(x) > 0 и в качестве начального приближения берем а = х0.








3 .СООТВЕТСТВИЕ МЕЖДУ ПЕРЕМЕННЫМИ, ПРИНЯТЫМИ ПРИ ОПИСАНИИ ЗАДАЧИ И В ПРОГРАМЕ

Соответствие между переменными, используемыми в блок-схеме и в программном коде главной программы приведено в Таблице 1.

Соответствие между переменными, используемыми в блок-схеме и в программном коде процедуры Save приведено в Таблице 2.


Таблица 1



Соответствие между переменными, используемыми в блок-схеме и в программном коде главной программы

Обозначения принятые при описании задачи

Обозначения в

программе

Наименование



а

а

Левая граница интервала

b

b

Правая граница интервала

е

е

Точность

х

х

Корень

Key

Key

Содержит символ нажатой клавиши




Таблица 2



Соответствие между переменными, принятыми при описании задачи и в процедуре Save

Обозначения принятые при описании задачи

Обозначения в

программе

Наименование



f

f

Файловая переменная

S

S

Название файла






4. СТРУКТУРНАЯ СХЕМА ПРОГРАММ И ЕЕ ОПИСАНИЕ



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

		ввод клавиши выбора пункта меню;

		если выполняется условие Key=’1’ то выполнить блок, 3 иначе выполнить блок 4;

		обращение к процедуре ввода исходных данных Vvod;

		если выполняется условие Key=’2’ то выполнить блок 5, иначе выполнить блок 6;

		обращение к процедуре поиска корня и вывода его на экран VivRez;

		если выполняется условие Key=’3’ то выполнить блок 7, иначе выполнить блок 8;

		обращение к процедуре поиска корня и сохранения его в файл;

		если выполняется условие Key=’0’ то выйти из программы, иначе вернуться к блоку 1.



Структурная схема подпрограммы функции f изображена на Рис. 4.2.

		присваивание заголовку функции заданного варианта.



Структурная схема подпрограммы процедуры PolDel изображена на Рис. 4.3.

		вычисление начального значения х;

		если значение функции в точке х отстоит от 0 на величину превышающую заданную точность е то выполнить цикл уточнения – перейти к блоку 3, иначе выйти из подпрограммы;

		если функция в точке а и в точке х имеет одинаковый знак то выполнить блок 4, иначе выполнить блок 5;

		левая граница перемещается в точку х;

		правая граница перемещается в точку х;

		вычисление нового значения х.



Структурная схема подпрограммы процедуры Vvod изображена на Рис. 4.4.

		вывод запроса на ввод левой границы интервала;

		ввод а – левой границы интервала;

		вывод запроса на ввод правой границы интервала;

		ввод b – правой границы интервала;

		вывод запроса на ввод точности вычисления корня уравнения;

		ввод е – точности вычисления корня уравнения.



Структурная схема подпрограммы процедуры Vivrez изображена на Рис. 4.5.

		обращение к процедуре вычисления корня уравнения PolDel;

		вывод найденного корня.



Структурная схема подпрограммы процедуры Save изображена на Рис. 4.6.

вывод запроса названия файла;

ввод названия файла;

обращение к процедуре подключения файла с введённым именем;

обращение к процедуре открытия файла для записи;

обращение к процедуре вычисления корня уравнения PolDel;

вывод в файл полученного значения корня;

обращение к процедуре закрытия файла.






НАЧАЛО



Key=ReadKey



Save

Key=’1’

Key=’2’

Key=’3’

Key=’0’



VivRez



Vvod

КОНЕЦ

1

Ø

1

Ø

1

Ø

1

Ø

1

2

3

4

6

7

5

8

Рис. 4.1.




Рис. 4.2.

НАЧАЛО



F=x2-x-6

1

КОНЕЦ




Рис. 4.3.

КОНЕЦ

│F(x)│

>e

F(a)* F(x)>0

1

Ø



x:=(a+b)/2

НАЧАЛО



a:=x



b:=x



x:=(a+b)/2

1

2

3

4

5

6






Рис. 4.4.

НАЧАЛО

КОНЕЦ

Вывод:

"а="

Ввод: а

Вывод:

"b="

Ввод: b

Вывод:

"e="

Ввод: e

1

2

3

4

5

6




Рис. 4.5.

НАЧАЛО

КОНЕЦ

Вывод:

"X=",X

PolDel (a,b,e,x)

1

2






Close(f)



PolDel (a,b,e,x)

Рис. 4.6.

НАЧАЛО

КОНЕЦ

Вывод:

"S="

Вывод: f,x



Assign (f,S)



1

Ввод: S



ReWrite(f)



2

3

4

5

6

7




5. ЛИСТИНГ ПРОГРАМЫ

Листинг программы находится в приложении А.




6. КОНТРОЛЬНЫЙ ПРИМЕР И АНАЛИЗ РЕЗУЛЬТАТА

Для контрольного примера найдём значение корня на интервале от 0 до 5. Найдём этот корень графически с использованием программы Microsoft Excel (см. табл 6.1., рис. 6.1).

Найдём этот корень при помощи программы (см. рис 6.2.-6.3). Полученное при помощи программы значение корня соответствует расчётному.




Таблица. 6.1

Расчетные точки графика функции f(x)=x2-x-6, полученные при помощи программы Microsoft Excel

x

y

0

-6

1

-6

2

-4

3

0

4

6

5

14












Рис. 6.1.






Рис. 6.1.






Рис. 6.2.




7. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ

Для работы с программой нужно запустить программу POLDEL.EXE, находящийся на дискете в приложении D, занимающий 20 кБ.

После запуска программы на экране появляется меню программы в котором содержатся следующие пункты (см. Прил. Б).

1-Ввести данные

2-Отобразить результат

3-Сохранить результат в файл

0-Выход

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

Для просмотра результата вычисления необходимо в меню нажать 2. По окончанию просмотра нажмите любую клавишу.

Для сохранения результата необходимо нажать в главном меню 3 и после появления запроса ввести имя файла, в который следует записать результат.

Для выхода из программы необходимо в меню нажать 0.




ЗАКЛЮЧЕНИЕ

В данной курсовой работе была разработана программа, решающая нелинейное уравнение. Для его решения был выбран метод половинного деления. 




СПИСОК ЛИТЕРАТУРЫ

Кетков Ю.Л., Кетков А.Ю. Практика программирования: Бейсик, Си, Паскаль. Самоучитель. – СПб.: БХВ-Петербург, 2001. 408 с.: ил.

Любиев О.Н., Филиппенко Л.Н., Филиппенко Г.Г. Методические указания к выполнению курсовой работы по дисциплинам «Программирование на ЯВУ, Информатика», Новочеркасск, ЮРГТУ, 2003г. – 256 с.

Фаронов В.В. «Турбо Паскаль 7.0» Начальный курс. Учебное пособие. Издание 7-е, переработанное. – М.: «Нлидж», издатель Молчалева С.В., 2001.-576 с. с ил.

Абрамов В.Г., Трифонов Н.П. Введение в язык Паскаль. – М. :Наука, 1988.-320 с.






ПРИЛОЖЕНИЯ








ПРИЛОЖЕНИЕ А



ЛИСТИНГ ПРОГРАМЫ



Program PolD;

Uses

  CRT;

Var

  a,b,e,x:real;

Function F(var x:real):real;

begin

  f:=sqr(x)-x-6;

end;

{================================}

Procedure PolDel(a,b,e:real; var x:real);

begin

    x:=(a+b)/2;

    while abs(F(x))>e do

        begin

    if F(a)*F(x)>0 then  a:=x

	                            else b:=x;

    x:=(a+b)/2;

        end;

end;

{===============================}

Procedure Vvod;

begin

  Clrscr;

  Writeln('Vvedite levuju granicu intervala');

  Readln(a);

  Writeln('Vvedite pravuju granicu intervala');

  ReadLn(b);

  Writeln('Vvedite tochnost');

  ReadLn(e);

end;

{===============================}

Procedure Vivrez;

begin

  Clrscr;

  PolDel(a,b,e,x);

  Writeln('Uravnenie x^2-x-6 na intervale (',a:0:2,',',b:0:2,')');

  Writeln('Imeet reshenie ',x:0:2);

  ReadKey

end;

{===============================}

Procedure Save;

var

  f:text;

  S:string;

begin

  Clrscr;

  Writeln('Vvedite nazvanie faila');

  ReadLn(S);

  Assign(f,s);

  {$I-}

  ReWrite(f);

  {$I+}

  PolDel(a,b,e,x);

  Writeln(f,'Uravnenie x^2-x-6 na intervale (',a:0:2,',',b:0:2,')');

  Writeln(f,'Imeet reshenie ',x:0:2);

  Close(f)

end;

{===============================}

var

  Key:Char;

Begin

  repeat

    Clrscr;

    Writeln('1-Vvesti dannie');

    Writeln('2-Otobrazit rezultat');

    Writeln('3-Sohranit rezulat v fail');

    Writeln('0-Vihod');

    Key:=ReadKey;

    Case Key of

    '1':Vvod;

    '2':VivRez;

    '3':Save;

    end;

  until Key='0';


end.








ПРИЛОЖЕНИЕ Б. 

МЕНЮ ПРОГРАММЫ








ПРИЛОЖЕНИЕ Д.

ДИСКЕТА С ПРОГРАММОЙ







12