СОДЕРЖАНИЕ
ВВЕДЕНИЕ. 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
(a
1
) > 0, f
(a
1
) ∙ f
(b
) < 0; поэтому следует выбрать отрезок [a
1
,b
]. Затем на этом суженом отрезке опять произвольным образом возьмем точку а
2
и найдем знаки произведений f
(a
1
) ∙ f
(a
2
) и f
(a
2
) ∙ f
(b
). Так как f
(a
2
)× f
(b
) < 0, то выбираем отрезок [a
2
, 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
(х) принимает значения противоположных знаков; обозначим его [a
l
, b
1
]. Затем отрезок [a
l
, b
1
] также делим пополам и проводим те же рассуждения. Получим отрезок [а
2
, b
2
], длина которого равна (b
– а
)/22
. Процесс деления отрезка пополам производим до тех пор, когда на каком-то n-м этапе либо середина отрезка будет корнем уравнения (случай, весьма редко встречающийся на практике), либо будет получен отрезок [a
n
, b
n
] такой, что b
n
– а
n
= (b
– а)/2n
≤ ε и а
n
≤ ξ ≤ b
n
(число n
указывает на количество проведенных делений). Числа а
n
и b
n
– корни уравнения f
(х
) = 0 с точностью до ε. За приближенное значение корня, как указывалось, выше, следует взять ξ = (a
n
+ b
n
)/2, причем погрешность не превышает (b
– а
)/2n
+1
.
2.2. МЕТОД ХОРД
Метод хорд является одним из распространенных методов решения алгебраических и трансцендентных уравнений. В литературе он также встречается под названиями «метода ложного положения» (regulafalsi), «метода линейного интерполирования» и «метода пропорциональных частей».
Пусть дано уравнение 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
) в точке B
0
(b
; f
(
)) и найдем абсциссу точки пересечения касательной с осью O
х
. Известно, что уравнение касательной в точке В
0
(b
; f
(b
)) имеет вид
Полагая у = 0, х = х1, получим
(1)
Теперь корень уравнения находится на отрезке [а
, х
1
]. Применяя снова метод Ньютона, проведем касательную к кривой в точке B
1
(x
1
; f
(x
1
)) и полечим
и вообще
(2)
Получаем последовательность приближенных значений x
1
, х
2
, …, x
n
, …, каждый последующий член которой ближе к корню ξ, чем предыдущий. Однако все х
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]. Поэтому проведем касательную в точке A
0
(a
; f
(а
)) и запишем ее уравнение для данного случая:
Полагая у = 0, x = x1 находим
(3)
Корень ξ находится теперь на отрезке [х
1
, b
]. Применяя снова метод Ньютона, проведем касательную в точке A
1
(x
1
; f
(x
1
)) и получим
и вообще
(4)
Получаем последовательность приближенных значений х
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.
Блок 1: ввод клавиши выбора пункта меню;
Блок 2: если выполняется условие Key=’1’ то выполнить блок, 3 иначе выполнить блок 4;
Блок 3: обращение к процедуре ввода исходных данных Vvod;
Блок 4: если выполняется условие Key=’2’ то выполнить блок 5, иначе выполнить блок 6;
Блок 5: обращение к процедуре поиска корня и вывода его на экранVivRez;
Блок 6: если выполняется условие Key=’3’ то выполнить блок 7, иначе выполнить блок 8;
Блок 7: обращение к процедуре поиска корня и сохранения его в файл;
Блок 8: если выполняется условие Key=’0’ то выйти из программы, иначе вернуться к блоку 1.
Структурная схема подпрограммы функции f изображена на Рис. 4.2.
Блок 1: присваивание заголовку функции заданного варианта.
Структурная схема подпрограммы процедуры PolDelизображена на Рис. 4.3.
Блок 1: вычисление начального значения х;
Блок 2: если значение функции в точке х отстоит от 0 на величину превышающую заданную точность е то выполнить цикл уточнения – перейти к блоку 3, иначе выйти из подпрограммы;
Блок 3: если функция в точке а и в точке х имеет одинаковый знак то выполнить блок 4, иначе выполнить блок 5;
Блок 4: левая граница перемещается в точку х;
Блок 5: правая граница перемещается в точку х;
Блок 6: вычисление нового значения х.
Структурная схема подпрограммы процедуры Vvodизображена на Рис. 4.4.
Блок 1: вывод запроса на ввод левой границы интервала;
Блок 2: ввод а – левой границы интервала;
Блок 3: вывод запроса на ввод правой границы интервала;
Блок 4: ввод b– правой границы интервала;
Блок 5: вывод запроса на ввод точности вычисления корня уравнения;
Блок 6: ввод е – точности вычисления корня уравнения.
Структурная схема подпрограммы процедуры Vivrezизображена на Рис. 4.5.
Блок 1: обращение к процедуре вычисления корня уравнения PolDel;
Блок 2: вывод найденного корня.
Структурная схема подпрограммы процедуры Saveизображена на Рис. 4.6.
Блок 1: вывод запроса названия файла;
Блок 2: ввод названия файла;
Блок 3: обращение к процедуре подключения файла с введённым именем;
Блок 4: обращение к процедуре открытия файла для записи;
Блок 5: обращение к процедуре вычисления корня уравнения PolDel;
Блок 6: вывод в файл полученного значения корня;
Блок 7: обращение к процедуре закрытия файла.
5. ЛИСТИНГ ПРОГРАМЫ
Листинг программы находится в приложении А.
6. КОНТРОЛЬНЫЙ ПРИМЕР И АНАЛИЗ РЕЗУЛЬТАТА
Для контрольного примера найдём значение корня на интервале от 0 до 5. Найдём этот корень графически с использованием программы MicrosoftExcel (см. табл 6.1., рис. 6.1).
Найдём этот корень при помощи программы (см. рис 6.2.-6.3). Полученное при помощи программы значение корня соответствует расчётному.
Таблица. 6.1
Расчетные точки графика функции f(x)=x2
-x-6, полученные при помощи программы MicrosoftExcel
| 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) 1-Ввести данные
2) 2-Отобразить результат
3) 3-Сохранить результат в файл
4) 0-Выход
Для ввода исходных данных
необходимо в меню нажать 1 ввести по очереди значение левой границы интервала, затем правой, затем точности вычисления.
Для просмотра результата вычисления
необходимо в меню нажать 2. По окончанию просмотра нажмите любую клавишу.
Для сохранения результата
необходимо нажать в главном меню 3 и после появления запроса ввести имя файла, в который следует записать результат.
Для выхода из программы
необходимо в меню нажать 0.
ЗАКЛЮЧЕНИЕ
В данной курсовой работе была разработана программа, решающая нелинейное уравнение. Для его решения был выбран метод половинного деления.
СПИСОК ЛИТЕРАТУРЫ
1. Кетков Ю.Л., Кетков А.Ю. Практика программирования: Бейсик, Си, Паскаль. Самоучитель. – СПб.: БХВ-Петербург, 2001. 408 с.: ил.
2. Любиев О.Н., Филиппенко Л.Н., Филиппенко Г.Г. Методические указания к выполнению курсовой работы по дисциплинам «Программирование на ЯВУ, Информатика», Новочеркасск, ЮРГТУ, 2003г. – 256 с.
3. Фаронов В.В. «Турбо Паскаль 7.0» Начальный курс. Учебное пособие. Издание 7-е, переработанное. – М.: «Нлидж», издатель Молчалева С.В., 2001.-576 с. с ил.
4. Абрамов В.Г., Трифонов Н.П. Введение в язык Паскаль. – М. :Наука, 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.
ПРИЛОЖЕНИЕ Б.
МЕНЮ ПРОГРАММЫ
ПРИЛОЖЕНИЕ Д.
ДИСКЕТА С ПРОГРАММОЙ