Содержание
Введение
1 Постановка задачи
2 Решение системы уравнения методомГаусса
3 Решение уравнения методами Ньютона,Хорд
4 Разработка блок схемы решениясистемы уравнения методом Гаусса
5 Разработка блок схемы решенияуравнения методом Ньютона
6 Разработка блок схемы решенияуравнения методом Хорд
7 Язык программирования Turbo Pascal
8 Разработка программы решениясистемы уравнения методом Гаусса при помощи Turbo Pascal
9 Разработка программы решенияуравнения методом Ньютона при помощи Turbo Pascal
10 Разработка программы решенияуравнения методом Хорд при помощи Turbo Pascal
Заключение
Список используемых источников
Введение
В основе того или иногоязыка программирования лежит некоторая руководящая идея, оказывающаясущественное влияние на стиль соответствующих программ.
Исторически первой былаидея структурирования программ, в соответствии с которой программист должен былрешить, какие именно процедуры он будет использовать в своей программе, а затемвыбрать наилучшие алгоритмы для реализации этих процедур. Появление этой идеибыло следствием недостаточной изученности алгоритмической стороны вычислительныхпроцессов, столь характерной для ранних программных разработок (сороковые —пятидесятые годы). Типичным примером процедурно-ориентированного языка являетсяФортран – первый и всё ещё один из наиболее популярных языков программирования.Последовательное использование идеи процедурного структурирования программпривело к созданию обширных библиотек программирования, содержащих множествосравнительно небольших процедур, из которых, как из кирпичиков, можно строить«здание» программы.
По мере прогресса в областивычислительной математики акцент в программировании стал смещаться с процедур всторону организации данных. Оказалось, что эффективная разработка сложныхпрограмм нуждается в действенных способах контроля правильности использованияданных. Контроль должен осуществляться как на стадии компиляции, так и припрогоне программ, в противном случае, как показала практика, резко возрастаюттрудности создания крупных программных проектов. Отчётливое осознание этойпроблемы привело к созданию Ангола-60, а позже Паскаля, Модулы-2, Си имножества других языков программирования, имеющих более или менее развитыеструктуры типов данных. Логическим следствием развития этого направления сталмодульный подход к разработке программ, характеризующийся стремлением «спрятать»данные и процедуры внутри модуля.
Начиная с языкаСимула-67, в программировании наметился новый подход, который получил название объектно-ориентированногопрограммирования (в дальнейшем ООП). Его руководящая идея заключается в стремлениисвязать данные с обрабатывающими эти данные процедурами в единое целое – объект.Характерной чертой объектов является инкапсуляция (объединение) данных иалгоритмов их обработки, в результате чего и данные, и процедуры во многомтеряют самостоятельное значение.
1 Постановка задачи
Цель решения задачи курсовой работы – автоматизациярешения системы уравнения методом Гаусса, а так же решения уравнения методамиХорд и Ньютона.
Выходная информациязадачи выводиться наэкран монитора.
Входная информациязадачи поступает путемввода пользователем данных для решения поставленной задачи
Прекращение решениязадачи выполняетсяпри выходе нового программного обеспечения, связанного с решением данной задачиили появление новой версии данного продукта.
2 Решение системыуравнения методом Гаусса
Метод Гаусса— классический метод решения системылинейных алгебраических уравнений (СЛАУ). Состоит в постепенном понижениипорядка системы и исключении неизвестных.
Хотя внастоящее время данный метод повсеместно называется методом Гаусса, он былизвестен и до К. Ф. Гаусса. Первое известное описание данного метода — вкитайском трактате «Математика в девяти книгах», составленном между I в. дон.э. и II в. н. э.Описание метода
Пустьисходная система выглядит следующим образом
/>
Тогда согласносвойству элементарных преобразований над строками эту систему можно привести кступенчатому виду:
/>
Переменные />называются главными переменными. Все остальныеназываются свободными.
Если />, то рассматриваемая система несовместна.
Предположим,что />.
Перенесёмсвободные переменные за знаки равенств и поделим каждое из уравнений системы насвой коэффициент при самом левом />(/>, где />— номер строки):
/>,
где />
Еслисвободным переменным системы (2) придавать все возможные значения и вычислитьчерез них главные переменные, то мы получим все решения. Так как эта системаполучена путём элементарных преобразований над исходной системой (1), то потеореме об эквивалентности при элементарных преобразованиях полученное намирешение является решением системы (1).
/>Следствия:
1: Если в совместнойсистеме все переменные главные, то такая система является определённой.2: Есликоличество переменных в системе превосходит число уравнений, то такая системаявляется либо неопределённой, либо несовместной.Условие совместности.
Упомянутоевыше условие />может бытьсформулировано в качестве необходимого и достаточного условия совместности:
Напомним, чторангом совместной системы называется ранг её основной матрицы (либорасширенной, так как они равны).
/>/>Алгоритм решения СЛАУ методом Гаусса подразделяется на дваэтапа.
1) На первом этапеосуществляется так называемый прямой ход, когда путём элементарныхпреобразований над строками систему приводят к ступенчатой или треугольнойформе, либо устанавливают, что система несовместна. А именно, среди элементовпервого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнееположение перестановкой строк и вычитают получавшуюся после перестановки первуюстроку из остальных строк, домножив её на величину, равную отношению первогоэлемента каждой из этих строк к первому элементу первой строки, обнуляя темсамым столбец под ним. После того, как указанные преобразования были совершены,первую строку и первый столбец мысленно вычёркивают и продолжают пока неостанется матрица нулевого размера. Если на какой-то из итераций средиэлементов первого столбца не нашёлся ненулевой, то переходят к следующемустолбцу и проделывают аналогичную операцию.
2) На втором этапеосуществляется так называемый обратный ход, суть которого заключается в том,чтобы выразить все получившиеся базисные переменные через небазисные и построитьфундаментальную систему решений либо, если все переменные являются базисными,то выразить в численном виде единственное решение системы линейных уравнений.Эта процедура начинается с последнего уравнения, из которого выражаютсоответствующую базисную переменную (а она там всего одна) и подставляют впредыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждойстрочке соответствует ровно одна базисная переменная, поэтому на каждом шаге,кроме последнего (самого верхнего), ситуация в точности повторяет случай последнейстроки.
/>В простейшем случае алгоритм выглядиттак:
/>
· Прямой ход:
/>
3) Обратныйход. Из последнего ненулевого уравнения выражаем базисную переменную черезнебазисные и подставляем в предыдущие уравнения. Повторяя эту процедуру длявсех базисных переменных, получаем фундаментальное решение.
/>Помимо аналитического решения СЛАУ,метод Гаусса также применяется для:
1) нахождения матрицы,обратной к данной (к матрице справа приписывается единичная такого же размера,что и исходная: />, после чего />приводитсяк виду единичной матрицы методом Гаусса—Жордана; в результате на местеизначальной единичной матрицы справа оказывается обратная к исходной матрица: />);
2) определения рангаматрицы (согласно следствию из теоремы Кронекера—Капелли ранг матрицы равенчислу её главных переменных);
3) численного решенияСЛАУ в вычислительной технике (ввиду погрешности вычислений используется МетодГаусса с выделением главного элемента, суть которого заключена в том, чтобы накаждом шаге в качестве главной переменной выбирать ту, при которой средиоставшихся после вычёркивания очередных строк и столбцов стоит максимальный помодулю коэффициент).
В отличие от матричногометода и метода Крамера, метод Гаусса может быть применен к системам линейныхуравнений с произвольным числом уравнений и неизвестных. Суть методазаключается в последовательном исключении неизвестных.
Система т линейных уравненийс п неизвестными имеет вид:
/>
x1, x2, …, xn – неизвестные.
aij — коэффициенты при неизвестных.
bi — свободные члены (или правые части)
Система линейныхуравнений называется совместной, если она имеет решение, и несовместной,если она не имеет решения.
Совместная системаназывается определенной, если она имеет единственное решение и неопределенной,если она имеет бесчисленное множество решений.
Две совместные системыназываются равносильными, если они имеют одно и то же множество решений.
К элементарнымпреобразованиям системы отнесем следующее:
1) перемена местами двухлюбых уравнений;
2) умножение обеих частейлюбого из уравнений на произвольное число, отличное от нуля;
3) прибавление к обеимчастям одного из уравнений системы соответствующих частей другого уравнения,умноженных на любое действительное число.
Элементарныепреобразования переводят систему уравнений в равносильную ей.
Элементарныепреобразования системы используются в методе Гаусса.
Для простоты рассмотримметод Гаусса для системы трех линейных уравнений с тремя неизвестными в случае,когда существует единственное решение:
Дана система:
/> ( 1 )
1-ый шаг метода Гаусса.
На первом шаге исключимнеизвестное х1 из всех уравнений системы (1), кроме первого.Пусть коэффициент />. Назовем еговедущим элементом. Разделим первое уравнение системы (1) на а11. Получимуравнение:
/> ( 2 )
где />
Исключим х1из второго и третьего уравнений системы (1). Для этого вычтем из них уравнение (2),умноженное на коэффициент при х1 (соответственно а21и а31).
Система примет вид:
/> ( 3 )
Верхний индекс (1) указывает, чторечь идет о коэффициентах первой преобразованной системы.
2-ой шаг метода Гаусса.
На втором шаге исключимнеизвестное х2из третьего уравнения системы (3). Пустькоэффициент />. Выберем его за ведущийэлемент и разделим на него второе уравнение системы (3), получим уравнение:
/> ( 4 )
где />
Из третьего уравнениясистемы (3) вычтем уравнение (4), умноженное на />Получимуравнение: />
Предполагая, что />находим />
В результатепреобразований система приняла вид:
/> (5)
Система вида (5)называется треугольной.
Процесс приведениясистемы (1) к треугольному виду (5) (шаги 1 и 2) называют прямым ходом методаГаусса.
Нахождение неизвестных изтреугольной системы называют обратным ходом метода Гаусса.
Для этого найденноезначение х3 подставляют во второе уравнение системы (5) и находят х2.Затем х2 и х3 подставляют в первое уравнение и находят х1.
В общем случае длясистемы т линейных уравнений с п неизвестными проводятся аналогичныепреобразования. На каждом шаге исключается одно из неизвестных из всехуравнений, расположенных ниже ведущего уравнения.
Отсюда другое называниеметода Гаусса – метод последовательного исключения неизвестных.
Если в ходе преобразованийсистемы получается противоречивое уравнение вида 0 = b, где b ¹ 0, то это означает, что системанесовместна и решений не имеет.
В случае совместнойсистемы после преобразований по методу Гаусса, составляющих прямой ход метода,система т линейных уравнений с п неизвестными будет приведена или к треугольномуили к ступенчатому виду.
Треугольная система имеетвид:
/>
Такая система имеетединственное решение, которое находится в результате проведения обратного ходаметода гаусса.
Ступенчатая система имеетвид:
/>
Такая система имеет бесчисленноемножество решений. Чтобы найти эти решения, во всех уравнениях системы члены снеизвестными хk+1, …, xk переносят в правую часть. Этинеизвестные называются свободными и придают им произвольные значения. Изполученной треугольной системы находим х1, …, xk,которые будут выражаться через свободные неизвестные. Подробнее об этом можноузнать в рекомендуемой литературе.
Рассмотренный метод Гаусса легкопрограммируется на ЭВМ и является более экономичным (по числу действий), чемдругие методы.
3 Решение уравненияметодами Ньютона, Хорд
Метод хорд (способ пропорциональныхчастей) — численный метод уточнения корня трансцендентного уравнения.
Точный корень/>уравнения/>находится на отрезке />. Производная />наэтом промежутке непрерывна и сохраняет постоянный знак. Приближенный корень />,при котором />, можно найти используя метод хорд. Для этого нужновзять начальное приближение корня />и применить к немуитерационную формулу:
линейный уравнение хорда гаусс ньютон
/>, />, если />
/>, />, если />
Погрешностьвычислений:
/>, />, />
В отличие от метода дихотомии,обращающего внимание лишь на знаки значений функции, но не на сами значения,метод хорд использует пропорциональное деление интервала (рисунок 1).
/>Рис. 1. Метод хорд Рис.2. Метод касательных
Здесь вычисляютсязначения функции на концах отрезка и строится “хорда”, соединяющая точки (a,f(a)) и (b, f(b)). Точка пересечения ее с осью абсцисс
/>
принимается за очередноеприближение к корню. Анализируя знак f(z) в сопоставлении со знаком f(x) наконцах отрезка, сужаем интервал до [a,z] или [z,b] и продолжаем процесспостроения хорд до тех пор, пока разница между очередными приближениями неокажется достаточно малой (в пределах допустимой погрешности) |Zn-Zn-1|.
Можно доказать, чтоистинная погрешность найденного приближения:
/>,где X* — корень уравнения, Zn и Zn+1 — очередные приближения, mи M – наименьшее.
Метод Ньютона
Пусть корень уравнения /> отделенна отрезке [a, b], причем /> и /> непрерывны и сохраняютопределенные знаки при />. Если на некотором произвольном шаге n найдено приближенное значение корня />, то можноуточнить это значение по методу Ньютона. Положим
/> (1)
где /> считаем малойвеличиной. Применяя формулу Тейлора, получим:
/>
Следовательно,
/>
Внеся эту поправку вформулу (1), найдем следующее (по порядку) приближение корня
/> (2)
Геометрически методНьютона эквивалентен замене дуги кривой /> касательной, проведенной внекоторой точке кривой. В самом деле, положим для определенности, что /> при /> и /> (см.рис.).
Выберем, например, />, для которого />. Проведемкасательную к кривой /> в точке B0с координатами/>.
/>
В качестве первогоприближения /> корнявозьмем абсциссу точки пересечения касательной с осью Ox. Через точку /> снова проведем касательную,абсцисса точки пересечения которой даст второе приближение /> корня и т.д.
Формулу для уточнениякорня можно получить из прямоугольного треугольника />, образованного касательной,проведенной в точке />, осью абсцисс и перпендикуляром,восстановленным из точки />.
Имеем />
Так как угол образованкасательной и осью абсцисс, его тангенс численно равен величине производной,вычисленной в точке, соответствующей абсциссе точки касания, т.е. />
/>Тогда />
или для любого шага n
/>.
В качестве начальнойточки /> можнопринять либо один из концов отрезка [a, b], либо точку внутри этого интервала.В первом случае рекомендуется выбирать ту границу, где выполняется условие
/>
т.е. функция и ее втораяпроизводная в точке /> должны быть одного знака.
В качестве простейшихусловий окончания процедуры уточнения корня рекомендуется выполнение условия
/>
Как следует из последнегонеравенства, требуется при расчете запоминать три значения аргумента />. Впрактических инженерных расчетах часто применяют сравнение аргументов натекущей и предыдущей итерациях:
/>
При составлении программырешения уравнения методом Ньютона следует организовать многократный расчетприближений /> длякорня. Если удается получить аналитическое выражение для производной, то еевычисление, а также вычисление /> можно оформить в виде функций.
4 Разработка блоксхемы решения системы уравнения методом Гаусса
/>
/>
5 Разработка блоксхемы решения уравнения методом Ньютона
/>
6 Разработка блоксхемы решения уравнения методом Хорд
/>
7 Языкпрограммирования Turbo Pascal
Turbo Pascal являетсяреализацией Pascal'я. Самая первая версия Pascal быля разработана на кафедреинформатики Стэндфордского университета швейцарским ученым Николаусом Виртом в1968 году.
С момента появленияPascal на рынке продуктов прошло много времени прежде чем он получил всеобщеепризнание. В середине 80-х годов американской фирмой Borland International, Incбыла создана реализация языка Pascal, известная и по сей день под именем TurboPascal. Эта фирма объединила очень быстрый компилятор с редактором текста и добавилак стандартному Паскалю мощное расширение, что способствовало успеху первойверсии этого языка.
В 1985 году на рынке ПЭВМпоявился язык программирования Турбо Паскаль (версия 3.0) с компиляторомстандартного Паскаля. С тех пор Паскаль стал применяться в общеобразовательных,профессионально-технических школах и в сфере высшего образования в качестве«первого» языка программирования. Благодаря простоте использования язык ТурбоПаскаль получил широкое распространение и в любительских кругах. Повышениюпопулярности Турбо Паскаля способствовал набор небольших сопутствующих программ(Toos), позволяющих получать чрезвычайно компактную, быструю и легко читаемуюпрограмму. Эти качества Турбо Паскаля были высоко оценены и в средепрофессиональных программистов. Встроенный редактор текста использует достаточношироко распространенную систему команд, берущую начало от пакета WordStar ихорошо знакомую каждому, кто интенсивно использует ПЭВМ.
В появившемся со временемпакете Турбо Паскаль 4.0 было устранено большинство подвергавшихся критикеограничений компилятора и была повышена производительность системы. Кроме того,новый компилятор версии 4.0 имел существенные отличия от предыдущей версии.Наиболее важным нововведением была ИNIТ-концепция, заимствованная из языкаМодула-2. Это дало возможность реализовать в рамках ТП разработку крупныхпрограммных продуктов.
С выходом в свет версии5.0 ТП получил еще большие шансы на благосклонную реакцию со стороныпрофессиональных пользователей благодаря встроенному в среду программированияинтегрированному отладчику, который позволил повысить производительность труда.
Существенно улучшилатехнические характеристики ТП реализация аппарата перекрытий (overlays),позволяющего строить мощные программные комплексы, рассчитанные на эксплуатациюв малых по объему областях памяти. Суть механизма перекрытий сводится к делениюпрограммы на части, поочередно загружаемые по мере необходимости с дискеты илижесткого диска в одну и ту же область памяти, заменяя при этом находившуюся тамчасть программы.
Кроме того, в ТП 5.0 былирасширены возможности отладки программ и обеспечена возможность поддержкирасширенной памяти в стандарте Lotus-Intel-Microsoft (SLIMS/EMS 4.0).Сокращение EMS обозначает Expanded Memory Specification (спецификациярасширенной памяти). Нельзя путать этот вид дополнительной памяти с другим — ExtendedMemory. EMS имеется на обычных ПЭВМ класса XT, в то время как Extended Memory —только на машинах АТ-класса (с процессором 286, 386 и выше) при объеме памятисвыше 1 Мбайта.
В этой версии были такжеисправлены и улучшены библиотеки графических процедур, поставляемые вместе спакетом ТП и обеспечивающие полную совместимость с графическими адаптерамикласса VGA (Video Graphics Array).
В рамках версии ТП 5.5были осуществлены дальнейшие преобразования в направлении улучшения техническиххарактеристик пакета. Наряду с внутренними улучшениями и новыми возможностямивстроенной справочной системы Help, а также большим набором учебных примеров,важным нововведением явилась реализация в языке концепцииобъектно-ориентированного программирования (ООП).
Через некоторое время нарынке появился ТП 6.0, в котором теоретическая концепцияобъектно-ориентированного программирования была реализована практически сполным набором объектов, которые могли использоваться для решения прикладныхзадач. Кроме того, реализация системы меню приведена в соответствие состандартом SAA (Turbo Vision). В качестве практического примера использованияновых возможностей был реализован текстовый редактор, встроенный в IDE ~Integrated Development Environment — интегрированную инструментальную оболочку.При этом сторонники программирования на ТП 6.0 получили возможность не толькоработать со встроенным многооконным текстовым редактором, но и использоватьмышь, которая значительно облегчает работу пользователя.
В 1992 году фирма BorlandInternational представила пользователям очередную версию языка Паскаль — ТурбоПаскаль 7.0. Наряду со всеми преимуществами, которые унаследованы от предыдущейверсии (многооконный режим работы, возможность использования мыши, возможностьиспользования языка программирования низкого уровня Ассемблер, возможность создаватьобъектно-ориентированные программы), в ТП 7.0 были произведены изменения иулучшения. Во-первых: появилась возможность выделять определенным цветомразличные элементы исходного текста (зарезервированные слова, идентификаторы,числа и т. д.), позволяющая даже неопытным пользователям устранять ошибки наэтапе ввода исходного текста. Во-вторых: язык программирования ТП 7.0 былрасширен (появилась возможность использовать типизированный адресный оператор,открытые массивы и строки и т. д.), что предоставило пользователюдополнительные возможности при решении повседневных задач. В-третьих: былулучшен компилятор, вследствие чего «коды программ» стали более эффективными.В-четвертых: был улучшен интерфейс пользователя. Кроме того, в ТП 7.0 расширенывозможности объектно-ориентированного программирования (в частности, расширеныи улучшены возможности Turbo Vision).
8 Разработка программырешения системы уравнения методом Гаусса при помощи TurboPascal
program Gauss;
const
N=3;
A:array[1..N,1..N]of real = ((9.1, 5.6, 7.8),
(3.8, 5.1,2.8),
(4.1, 5.7,1.2));
B:array[1..N]of real = (9.8,
6.7,
5.8);
type
matrtype=array[1..N,1..N+1]of real;
var
i,j:byte;
matr:matrtype;
procedureGausse(var matr:matrtype; N:byte);
vari,j,k:byte;
begin
for i:=1 toN-1 do
for j:=i+1 toN do
for k:=N+1downto i do
matr[j,k]:=matr[j,k]-matr[i,k]/matr[i,i]*matr[j,i];
for i:=N downto1 do
begin
for j:=i+1 toN do
Matr[i,N+1]:=Matr[i,N+1]-Matr[i,j]*Matr[j,N+1];
Matr[i,N+1]:=Matr[i,N+1]/Matr[i,i];
end;
end;
begin
clrscr;
writeln('resheniesistemi iz ',N,' linear yravnenii');
for i:=1 to Ndo
begin
writeln('vvodimyravnenie',i,':');
for j:=1 to Ndo
begin
write('A[',i
,',',j,']=');
read(A[i,j]);
end;
write('B[',i,']=');
readln(B[i]);
end;
writeln('Sistemalinear yravnenii');
for i:=1 to Ndo
begin
for j:=1 to Ndo
write(A[i,j]:5:2);
writeln(B[i]:5:2);
end;
for i:=1 to Ndo
begin
for j:=1 to Ndo
matr[i,j]:=A[i,j];
matr[i,N+1]:=B[i];
end;
Gausse(matr,N);
writeln('resheniesistemi yravnenii:');
for i:=1 to Ndo
writeln('X',i,'=',matr[i,N+1]:5:2);
readkey;
end.
9 Разработка программырешения уравнения методом Ньютона при помощи TurboPascal
uses crt;
var
a,b,Exp,s:real;
i: integer;
functionFunc(x: real): real;
begin
Func:=2*x*x*x-3*x*x-12*x+10;
end;
functionPFunc(x: real): real;
begin
PFunc:=6*x*x-6*x-12;
end;
Begin
clrscr;
Writeln('Vvediteverhnij predel:');
readln(b);
Writeln('Vvediteto4nost'':');
readln(Exp);
i:=0;
repeat
a:=b-Func(b)/PFunc(b);
s:=b;
b:=a;
i:=i+1;
Writeln('Shag',s:5:2,' X-',a:5:2,' f(x)=',Func(b));
until(abs(a-s)>Exp);
Writeln('Otvet:',b:5:2);
readln;
end.
10 Разработкапрограммы решения уравнения методом Хорд при помощи TurboPascal
program hord;
varx,a,b,eps,s:real;
functionf(x:real):real;
begin
f:=2*x*x*x-3*x*x-12*x+10;
end;
begin
write('vveditelevuiu granicu');
readln(a);
write('vveditepravuiu granicu');
readln(b);
write('vvediteepsilon');
readln(eps);
whilef(b)-f(a)>=eps do
begin
s:=b-f(b)/(f(b)-f(a))/(b-a);
a:=b; b:=s;
end;
writeln(s:5:2);
readln;
end.
Заключение
В соответствии с заданиемкурсовой работы была осуществлена программная реализация задачи. В ходевыполнения работы были получены навыки программирования системы уравнений.
Список используемыхисточников
1)Блашкин И.И., Буров А.А. Новые возможности Turbo-Pascal 7.1. — Спб.: Изд-во“Макет”, 2005.
2)Бородич Ю.С. и др. Паскаль для персональных компьютеров: Справ. Пособие/ Ю.С. Бородич,А.Н. Вальвачев, А.И.Кузьмич. — Мн.: Выш. Шк.: БФ ГИТМП “НИКА”, 2001.
3)ВасильевП.П. Турбо Паскаль — мой друг: М.: Компьютер, ЮНИТИ, 2006.
4)Джордейн Р. Справочник программиста персональных компьютеров типа IBM PC, XT,AT: Пер. с англ./ Предисл. Н.В. Гайского. — М.:Финансы и статистика, 2001.
5)Зуев Е.А. Язык программирования Turbo Pascal 7.1. — М.: Унитех, 2005.