Метод половинного деления 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 (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 (b )) и найдем абсциссу точки пересечения касательной с осью 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. ПРИЛОЖЕНИЕ Б. МЕНЮ ПРОГРАММЫ ПРИЛОЖЕНИЕ Д. ДИСКЕТА С ПРОГРАММОЙ