Обращение матрицы методом Гаусса

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

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

Министерство науки и высшего образования РФ

КАФЕДРА ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

КУРСОВАЯ РАБОТА

«Обращение матрицы методом Гаусса»

по дисциплине Программирование

2022 г.

Аннотация

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

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

Для ее решения используется метод Гаусса, основанный на преобразовании расширенной матрицы системы.

Содержание

Введение

1. Задача расчета количества заготовок из листового металла

1.1 Содержательная постановка задачи

1.2 Математическая постановка задачи

2. Выбор и обоснование численного метода решения задачи

2.1 Методы решения систем линейных алгебраических уравнений

2.2Алгоритм решения систем линейных алгебраических уравнений методом Гаусса. Обращение матрицы методом Гаусса

3. Разработка алгоритма

3.1 Структура данных

3.2 Структура алгоритма

3.3 Схема алгоритма

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

4.1 Описание переменных и структур данных

4.2 Описание функций

4.3 Текст программы на языке программирования Borland Pascal 7.0

5. Тестовая задача

5.1 Аналитическое решение тестовой задачи

5.2 Решение, полученное с использованием разработанного программного обеспечения

5.3 Выводы

6. Инструкция пользователю

Заключение

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

Введение

В современном обществе электронно-вычислительные машины (ЭВМ) проникли во все сферы деятельности человека, начиная с начального образования и заканчивая изучением новейших технологий.

Благодаря разнообразию программного и аппаратного обеспечения сегодня возможно использование всех потенциальных возможностей компьютерных технологий. Это позволяет запоминать большие массивы информации производить длинные и сложные последовательности вычислений без вмешательства человека, быстро эту информацию обрабатывать, выдавать точные результаты и держать их в защищенном виде, при этом занимать минимальное место.

Каждую секунду в мире производятся миллиарды измерительных операций, результаты которых используются для обеспечения надлежащего качества и технического уровня выпускаемой продукции, обеспечения безопасной и безаварийной работы транспорта, для медицинских и экологических диагнозов и других важнейших целей.

Большую роль компьютерные технологии играют в медицине. Создаются различные виртуальные модели развития заболеваний, создаются огромные базы информации, на основании которых изобретаются новые препараты для лечения.

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

С появлением ЭВМ в развитии рынка труда автоматизация обработки информации позволяет мгновенно информировать руководителей о состоянии предприятий и рабочих мест. Увеличивается экономический потенциал в области страховых и финансовых услуг. С помощью ЭВМ стало возможным решить проблему занятости, в том числе для людей с ограниченными физическими возможностями.

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

В современном мире ЭВМ широко применяются в решении научных, технических и экономических задач, для которых мощным математическим средством являются численные методы.

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

Для решения наиболее точных и сложных моделей в достижении хорошего количественного и качественного результата на помощь приходят численные методы, которые начали развивать еще Ньютон, Эйлер, Лобачевский, Гаусс, Чебышев, Крылов. В результате потребностей вычислительной математики в большом количестве вычислений для получения численного решения с большой точностью и надежностью выходом из создавшейся ситуации стало создание ЭВМ. В виду этого скорость выполнения арифметических операций менее чем за пятьдесят лет возросла от 0,1 операции в секунду при ручном счете до 10¹² операций на современных ЭВМ [2].

Необходимость численного решения задач возникает во всех сферах деятельности человека. Математический аппарат широко используется в современных экономических приложениях. Специалисты в области экономики сталкиваются со сложными теоретическими и прикладными задачами, решение которых невозможно без математического моделирования. Использование математических методов в экономике восходит к работам Ф. Кенэ («Экономическая таблица»), А. Смита (классическая макроэкономическая модель), Д. Риккардо (модель международной торговли).

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

Для реализации численных методов на ЭВМ существует множество разнообразных программ и программных комплексов. Использование компьютерной техники позволяет перейти от простейших расчетов и оценок различных конструкций или процессов к новой стадии работы детальному математическому моделированию (вычислительному эксперименту). Данный процесс может не только сократить потребность в реальных экспериментах, но и заменить их в ряде случаев.

Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов - языков программирования. Языки программирования (третьего поколения) общего назначения, например, Бейсик, Кобол, Си и Паскаль используются для написания компьютерных программ любого типа, которые в решении прикладных задач представляют собой набор правил, позволяющих компьютеру выполнить тот или иной вычислительный процесс, организовать управление различными объектами, и т.п.

Подводя итог выше сказанному целью данной курсовой работы является изучение и реализация в программном продукте решения систем линейных алгебраических уравнений методом Гаусса,основанным на преобразовании расширенной матрицы. В работе мною применены навыки, полученные в курсах «Информатика», «Программирование», «Вычислительная математика» и выполнены поставленные задачи:

1.Обзорно рассмотреть существующие методы по решению систем линейных алгебраических уравнений. Изучить метод Гаусса, основанный на преобразовании расширенной матрицы системы, на конкретной инженерной задаче;

2.Разработать на базе этого метода вычислительную структуру данных и схему алгоритма;

3. Разработать интерфейс программы для решения системы линейных алгебраических уравнений методом Гаусса на языке программирования BorlandPascal 7.0.

Курсовая работа состоит из шести разделов, введения и заключения. Первый и второй разделы - теоретические и содержат общие сведения о решении системы линейных алгебраических уравнений методом Гаусса, основанным на преобразовании расширенной матрицы. Третий -описывает этапы разработки алгоритма, реализующего численный метод. Четвертый - содержит текст программы с комментариями, а также полное описание структур данных и функций. Пятый - программная реализация. В нем описывается тестируемая программа и анализ получившихся результатов. Шестой - содержит инструкцию пользователю. В заключении представлен вывод о проделанной работе.

1. Задача расчета количества заготовок из листового металла

1.1 Содержательная постановка задачи

Задача расчета системы линейных алгебраических уравнений в области промышленности, к примеру, производства металлоконструкций, позволяет упрощать производственный процесс изготовления сборочных деталей разного типа из стального проката, анализировать нормативную потребность листового материала при технологических операциях [6].

Затраты на материал остаются самыми большими расходами для производств, и лучшее использование материалов напрямую влияет на чистую прибыль компании. Используя правильные технологии и внедряя передовые методы для наилучшего использования материалов и оптимизации рабочего процесса, можно получить максимальную отдачу от раскроя.

Предприятие, только начавшее изучать методы раскроя листового металла, может начать с прямоугольного раскроя - распространенной стратегии в программном обеспечении начального уровня, которая позволяет разместить одну деталь в прямоугольной или квадратной области на листе или пластине. Это самый простой тип раскроя, он прост и дешев в реализации, но при этом остается много пустого пространства. По этой причине большинство операторов-раскройщиков используют точный раскрой по форме деталей, при котором детали ориентируются как кусочки головоломки, оставляя минимальное пространство между ними.

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

Последовательность выполнения заданий может иметь большое значение. Скажем, у изготовителя есть задания, требующие серии крупных деталей, и еще одно задание с множеством мелких деталей. Вместо того чтобы выполнять резку всех мелких деталей сразу, можно распределить их и позволить им "заполнить пробелы" в нескольких листах крупных деталей, что поможет получить максимальную отдачу от каждого листа.

Программное обеспечение для раскроя позволяет сэкономить материал, снизить трудозатраты и повысить производительность - тройная выгода.

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

Существованием единственного решения задачи будет условие равенства линейных уравнений в системе с количеством неизвестных. Если, например, количество строк (количество уравнений в системе) будет меньше, чем количество столбцов (количество неизвестных), то система будет неопределенной, т. е. нельзя будет однозначно определить все неизвестные (решить систему).

Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение тогда и только тогда, когда главный определитель матрицы не равен нулю, т.е..

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

1. и каждый из дополнительных определителей . Это имеет место только тогда, когда коэффициенты при неизвестных пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число . При этом система имеет бесчисленное множество решений.

2. и хотя бы один дополнительный определитель . Это имеет место только тогда, когда коэффициенты при всех неизвестных , пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений.

1.2 Математическая постановка задачи

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

Задача. Предприятию из листового материала необходимо выкроить 360 заготовок типа А, 300 заготовок типа Б и 675 заготовок типа В. При этом для безотходного производства применяется три способа раскроя. При первом способе раскроя получается 3 заготовки типа А, 1 заготовка типа Б и 4 заготовки типа В, при втором способе раскроя получается 2 заготовки типа А, 6 заготовок типа Б и 1 заготовка типа В, при третьем способе раскроя получается 1 заготовка типа А, 2 заготовки типа Б и 5 заготовок типа В. Найти расход материала при каждом из указанных способов раскроя.

Условие задачи запишем в виде таблицы.

Тип заготовки	Количество заготовок по способам раскроя, шт.	Необходимое количество заготовок, шт.
	I способ	II способ	III способ
А	3	2	1	360
Б	1	6	2	300
В	4	1	5	675

В качестве исходных данных принимается количество заготовок трех типов (А, Б, В) по трем способам раскроя (I, II, III). Неизвестным параметром является количество листов материала, из которого будут получены заготовки, для трех способов раскроя.

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

, (1.2.1)

что будет предопределять существование единственного решения поставленной задачи.

В данной задаче система имеет единственное решение: 90 листов для заготовки А, 15 листов для заготовки Б, 60 листов для заготовки С.

Аналитическое решение тестовой задачи приведено в п. 5.1.

2. Выбор и обоснование численного метода решения задачи

2.1 Методы решения систем линейных алгебраических уравнений

Современная вычислительная математика располагает большим арсеналом методов, а математическое обеспечение ЭВМ - многими пакетами прикладных программ, позволяющих решать различные возникающие на практике линейные системы. Чтобы ориентироваться среди методов и программ и в нужный момент сделать оптимальный выбор, нужно разбираться в основах построений методов и алгоритмов, учитывающих специфику постановок задач, знать их сильные стороны и недостатки, а также границы применимости.

Методы решения систем линейных алгебраических уравнений делятся на две группы - прямые и итерационные. В рамках поставленной задачи в курсовой работе будем рассматривать только прямые методы.

Прямые методы используют конечные соотношения (формулы) для вычисления неизвестных. Они дают решение после выполнения заранее известного числа операций. Эти методы сравнительно просты и наиболее универсальны, т.е. пригодны для решения широкого класса линейных систем.

Вместе с тем прямые методы имеют и ряд недостатков. Как правило, они требуют хранения в оперативной памяти ЭВМ сразу всей матрицы, и при больших значениях неизвестных расходуется много места в памяти. Далее, прямые методы обычно не учитывают структуру матрицы - при большом числе нулевых элементов в разреженных матрицах эти элементы занимают место в памяти машины, и над ними проводятся арифметические действия. Существенным недостатком прямых методов является также накапливание погрешностей в процессе решения, поскольку вычисления на любом этапе используют результаты предыдущих операций. Поэтому прямые методы используются обычно для сравнительно небольших систем с плотно заполненной матрицей и не близким к нулю определителем[4].

Отметим еще, что прямые методы решения линейных систем иногда называют точными, поскольку решение выражается в виде точных формул через коэффициенты системы. Однако точное решение может быть получено лишь при выполнении вычислений с бесконечным числом разрядов. На практике при использовании ЭВМ вычисления проводятся с ограниченным числом знаков, определяемым разрядностью машины. Поэтому неизбежны погрешности в окончательных результатах.

Выбор метода решения системы зависит от структуры и размерности матрицы исходной системы. Линейную алгебраическую систему уравнений удобно записывать в матричной форме:

, (2.1.1)

, , , (2.1.2)

где - вещественная -матрица коэффициентов системы;

- матрица-столбец неизвестных с вещественными координатами;

- вектор-столбец свободных членов.

Для решения линейных алгебраических систем наиболее часто используют пять прямых методов: Кремера, Гаусса, квадратного корня (метод Холецкого), трех диагональной прогонки и матричный метод [7].

Метод Кремера и матричный метод лучше использовать для решения систем 2-го и 3-го порядка. С увеличением порядка системы они становятся не устойчивыми методами относительно ошибок округления, что приводит к быстрому росту погрешностей. В этих методах используется определитель системы, который стоит в знаменателе формул решений. Если модуль определителя намного меньше единицы , то формулы будут давать большие погрешности.

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

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

матрица гаусс линейный алгебраический

, (2.1.3)

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

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

Данный метод имеет более универсальное применение и используется для систем с произвольным числом линейных уравнений и неизвестных. Он менее трудоемкий по сравнению с матричным методом и методом Кремера. Метод Гаусса будет подробно рассмотрен в дальнейшем.

Методом квадратного корня лучше решать линейные системы вида (2.1.1) с симметричной положительно определенной матрицей (когда ). Метод основан на разложении матрицы в произведение:

, (2.1.4)

где - верхняя треугольная матрица с положительными элементами на главной диагонали;

- транспонированная матрица к матрице ;

- диагональная матрица, на диагонали которой находятся числа .

Преимуществом данного метода является использование приблизительно вдвое меньше арифметических операций и объема памяти, чем метод Гаусса.Такие системы возникают, например, при решении дифференциальных уравнений методом конечных элементов.

Метод прогонки является частным случаем метода Гаусса и применяется для решения систем линейных уравнений с трехдиагональной матрицей , где во всех остальных элементах, кроме главной диагонали и двух соседних с ней, стоят нули [8].

Система в матричном виде:

, (2.1.5)

, , , (2.1.6)

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

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

Кроме решения систем линейных алгебраических уравнений простыми численными методами существуют другие задачи линейной алгебры - вычисление определителя, собственных значений и собственных векторов матрицы, а также обращение матриц.

Рассмотрим подход решения линейных систем через обращение матрицы в рамках метода Гаусса.

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

, (2.1.7)

где - единичная матрица.

Так для матрицы третьего порядка, умножив:

, (2.1.8)

получим три системы уравнений относительно девяти неизвестных .

В общем случае имеют место соотношения:

, (2.1.9)

где

(2.1.10)

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

Умножая обе части в векторном выражении (2.1.1) слева на обратную матрицу , получаем:

, (2.1.11)

Однако, если не использовать экономичных схем для вычисления обратной матрицы, этот способ неприемлем для практического решения линейных систем при больших значениях из-за большого объема вычислений.

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

2.2 Алгоритм решения систем линейных алгебраических уравнений методом Гаусса. Обращение матрицы методом Гаусса

Одним из самых распространенных среди прямых методов решения систем линейных уравнений является метод Гаусса и его модификации.

Гаусс Карл Фридрих (1777-1855) - немецкий математик. Гаусс учился в Геттингенском университете и первое выдающееся открытие опубликовал в студенческие годы. Всемирную славу Гауссу принесла работа по определению орбиты планеты по малому числу наблюдений, изложенная в знаменитой монографии «Теория движения небесных тел». С именем Гаусса связаны фундаментальные исследования почти во всех основных областях математики: в алгебре, теории чисел, дифференциальной геометрии, математическом анализе, теории функций комплексного переменного, теории вероятностей, а также аналитической и небесной механике, астрономии, физике и геодезии.

Вычисления с помощью метода Гаусса заключаются в последовательном исключении неизвестных из системы для преобразования ее к эквивалентной системе с верхней треугольной матрицей. Вычисления значений неизвестных производят на этапе обратного хода [3].

Прямой ход состоит из шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного из уравнений с номерами . Предположим, что коэффициент . Будем называть его главным элементом 1-го шага.

Найдем величины:

, (2.2.1)

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

, (2.2.2)

в которой и вычисляются по формулам:

, . (2.2.3)

2-й шаг. Целью этого шага является исключение неизвестного из уравнений с номерами . Пусть , где - коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага:

, (2.2.4)

и вычтем последовательно из третьего, четвертого, …, го уравнения системы второе уравнение, умноженное соответственно на , , …, .

В результате получим систему:

, (2.2.5)

в которой коэффициенты и вычисляются по формулам:

, . (2.2.6)

Аналогично проводятся остальные шаги. Опишем очередной й шаг.

й шаг. В предположении, что главный (ведущий) элемент го шагаотличен от нуля, вычислим множители го шага:

, (2.2.7)

и вычтем последовательно из го, …, го уравнений полученной на предыдущем шаге системы e уравнение, умноженное соответственно на , , …, .

После го шага исключения получим систему уравнений, матрица которой является верхней треугольной.

. (2.2.8)

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

, , (2.2.9)

где верхний индекс (номер этапа) должен изменяться от до , нижние индексы и (в любой очередности) - от до .

На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим . Подставляя найденное значение в предпоследнее уравнение, получим . Осуществляя обратную подстановку, далее последовательно находим , , …, . Вычисления неизвестных здесь проводятся по формулам, начиная с последнего:

,

(2.2.10)

.

Очевидно, обратный ход метода Гаусса определяется одной формулой:

, (2.2.11)

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

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

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

. (2.2.12)

Представляя искомую матрицу как набор векторов-столбцов:

, , …, , (2.2.13)

а единичную матрицу как набор единичных векторов:

, , …, , (2.2.14)

матричное уравнение (2.2.12) в соответствии с правилами умножения матриц подменим эквивалентной системой не связанных между собой векторно-матричных уравнений:

, , …, . (2.2.15)

Каждое из последних уравнений имеет вид (2.1.1) и может быть решено методом Гауссапо схеме единственного решения.

При этом особенностью является то обстоятельство, что все системы линейных алгебраических уравнений (2.2.15) имеют одну и ту же матрицу коэффициентов, а это означает, что наиболее трудоемкая часть метода Гаусса - приведение матрицы системы к треугольному виду - общая для всех этих систем.

Так что в решении систем уравнений методом Гаусса через обращение матриц, целесообразно не просто применить его последовательно раз к системам (2.2.15), а подкорректировать таким образом, чтобы в роли вектора оказались все единичные векторы , , …, . Тогда в результате будут получаться столбец за столбцом элементы обратной матрицы .

Решение линейных систем через обращение матрицы в рамках метода Гауссаосновано на преобразовании расширенной матрицы системы.

Расширенной матрицей называется матрица вида:

(2.2.16)

Так как реальные машинные вычисления производятся не с точными, а с усеченными числами, т.е. неизбежны ошибки округления, то анализируя формулы (2.2.10), можно сделать вывод о том, что выполнение алгоритма может прекратиться, или привести к неверным результатам, если знаменатели дробей на каком-то этапе окажутся равными нулю или очень маленькими числами. Чтобы уменьшить влияние ошибок округлений и исключить деление на нуль, на каждом этапе прямого хода уравнения системы обычно переставляют так, чтобы деление производилось на наибольший по модулю в данном столбце элемент. Числа, на которые производится деление в методе Гаусса, называются ведущими или главными элементами, а модификация метода Гаусса - методом с постолбцовым выбором главного элемента.

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

3. Разработка алгоритма

3.1 Структура данных

Программа, расчета количества заготовок из листового металла, использует следующие структуры данных: четыре двумерных динамических массива, предназначенные для хранения исходной матрицы, единичной матрицы, обобщенной матрицы и матрицы, записанной из файла. Все массивы, кроме последнего, являются действительными, так как с числами, записанными в них, производятся различные вычисления. Последний массив является целочисленным, так как предназначен только для переноса исходной матрицы из файла в программу. Два одномерных динамических массива, предназначенные для хранения матрицы свободных коэффициентов и матрицы искомых коэффициентов. Данные массивы являются действительными, так как значения, записанные в них, могут изменяться в зависимости от вычислений. Глобальной переменной, используемой в программе, является: размер матрицы, данная переменная является целочисленного типа.

В подпрограмме ObrMatr используются следующие структуры данных: переменные i, j, kцелочисленного типа предназначены для определения номера элемента массива. Это облегчает поиск нужного элемента для дальнейших вычислений. Также в подпрограмме используется переменная dтипа extended. Она предназначена для определения коэффициента, используемого в решении.

В подпрограмме CalkRez используются следующие структуры данных: переменные i, jцелочисленного типа, предназначенные для определения номера элемента массива для удобного поиска необходимого элемента.

3.2 Структура алгоритма

Функция ObrMatr, предназначенная для обращения матрицы, имеет следующую структуру алгоритма: при прямом ходе проверяется наличие нулевых элементов в исходной матрице, если их нет, вычисления продолжаются. С помощью цикла определяется значение коэффициента и заполняется обратная матрица путем вычислений через единичную матрицу. При обратном ходе значения, полученные при прямом ходе, подставляются в объединенную матрицу и вычисляется результат.

Функция CalkRez, предназначенная для вычисления коэффициента матрицы, имеет следующую структуру алгоритма: обнуляем значение коэффициента, затем присваиваем новое значение и переходим к следующему элементу. Далее выводим полученные значения.

3.3 Схема алгоритма

На рисунке 1 представлена схема алгоритма обращения матрицы.

Рисунок 1 - Схема алгоритма обращения матрицы методом Гаусса

Ниже представлена схема алгоритма вычисления коэффициентов матрицы.



Рисунок 2 - Схема алгоритма вычисления коэффициентов матрицы

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

4.1 Описание переменных и структур данных

В программе используются двумерные динамические массивы: ArrayAE,ArrayA,ArrayE,ArrayB,ArrayX; переменные: FRead, FWrite, N, содержащие имена файлов и размер матрицы.

Массив ArrayAE - предназначен для хранения исходной матрицы и дополнительной единичной матрицы, предназначенной для вычисления прямого хода обращения.

Массив ArrayA - предназначен для хранения исходной матрицы и выполнения различных преобразований с ней.

Массив ArrayE- предназначен для хранения единичной матрицы и выполнения различных преобразований с ней.

Массив ArrayB - предназначен для хранения матрицы свободных членов и выполнения различных преобразований с ними.

Массив ArrayX- предназначен для хранения матрицы искомых коэффициентов.

4.2 Описание функций

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

Function ObrMatr(): extended - функция, предназначенная для обращения матрицы. Данная функция разделена на три части: прямой ход, обратный ход и вывод полученных значений. При прохождении первой части проверяется наличие нулевых значений среди введенных. Если такие есть, то программа выведет сообщение о том, что будет происходить деление на ноль и дальнейшие операции не будут выполнены. Потребуется исправить введенные данные и снова запустить вычисления. Если нулевые значения не обнаружены будут произведены вычисления, соответствующие прямому ходу при обращении матрицы. При прохождении второй части будут выполнены вычисления, соответствующие обратному ходу при вычислении обратной матрицы. Если первая и вторая части выполнены успешно, функция заполнит двумерный массив получившимися значениями и выведет их в таблицу, соответствующую обратной матрице на форме, а также вернет заполненный массив.

Function CalkRez(): extended - функция, предназначенная для вычисления коэффициентов матрицы. В данной функции проводятся вычисления, соответствующие перемножению полученной в предыдущей функции обратной матрицы на коэффициент свободных членов. Результатом выполнения данной функции будут искомые коэффициенты, которые будут выведены в соответствующую таблицу на форме.

4.3 Текст программы на языке программирования Borland Pascal 7.0

unit CourseWork;

{$mode objfpc}{$H+}

interface

uses

Classes, SysUtils, Forms, Controls, Graphics, Dialogs, ExtCtrls, StdCtrls, Buttons, Grids;

type

TFormCW = class(TForm)

ButtonCl: TButton;

ButtonRez: TButton;

ButtonRF: TButton;

ButtonWF: TButton;

EditInpN: TEdit;

Label1: TLabel;

LabelRez: TLabel;

LabelObr: TLabel;

LabelA: TLabel;

LabelInpN: TLabel;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

StringGridRez: TStringGrid;

StringGridB: TStringGrid;

StringGridA: TStringGrid;

StringGridObr: TStringGrid;

procedure ButtonClClick(Sender: TObject);

procedure ButtonRezClick(Sender: TObject);

procedure ButtonRFClick(Sender: TObject);

procedure ButtonWFClick(Sender: TObject);

procedure EditInpNEditingDone(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

public

end;

type

ArrayAE = array of array of extended; //двумерной массив AE

ArrayA = array of array of extended; //двумерный массив А

ArrayE = array of array of extended; //двумерный массив E

ArrayR = array of array of integer; //двумерный массив R

ArrayB = array of extended; //одномерный массив B

ArrayX = array of extended; //одномерный массив X

var

FormCW: TFormCW;

AE: ArrayAE; //матрицакоэффициентовиединичнаяматрица

A: ArrayA; //матрица коэффициентов

E: ArrayE; //единичная матрица

B: ArrayB; //матрица свободных членов

X: ArrayX; //матрица найденных коэффициентов

R: ArrayR; //матрица из файла

N: integer; //размер матрицы

//обращение матрицы матодом Гаусса

functionObrMatr: extended;

//вычисление коэффициентов матрицы

functionCalkRez: extended;

implementation

{$R *.lfm}

procedure TFormCW.FormCreate(Sender: TObject);

begin

N:= 3;

EditInpN.Text:= IntToStr(N);

StringGridA.ColCount:= N;

StringGridA.RowCount:= N;

StringGridObr.RowCount:= N;

StringGridObr.ColCount:= N;

StringGridB.RowCount:= N;

StringGridRez.RowCount:= N;

end;

//ввод и проверка введенных данных

procedure TFormCW.EditInpNEditingDone(Sender: TObject);

begin

try

N:= StrToInt(EditInpN.Text);

except

raise Exception.Create('Пустой ввод');

end;

if (N < 2) then

raise EConvertError.Create(

'Неверно введена размерность массива');

StringGridA.ColCount:= N;

StringGridA.RowCount:= N;

StringGridObr.RowCount:= N;

StringGridObr.ColCount:= N;

StringGridB.RowCount:= N;

StringGridRez.RowCount:= N;

end;

//очистка полей

procedure TFormCW.ButtonClClick(Sender: TObject);

begin

StringGridA.Clean;

StringGridObr.Clean;

StringGridB.Clean;

StringGridRez.Clean;

end;

//вычисление результата

procedure TFormCW.ButtonRezClick(Sender: TObject);

var

i, j: integer;

begin

//матрица коэффициентов

SetLength(A, N, N); //выделение памяти

try

for i:= 0 to N - 1 do

for j:= 0 to N - 1 do

begin

if StrToInt(FormCW.StringGridA.Cells[i, j]) <= 0 then

begin

ShowMessage('Ячейка заполнена не верно. Число должно быть натуральным.');

exit;

end

else

A[i, j]:= StrToInt(FormCW.StringGridA.Cells[i, j]);

end;

except

raise Exception.Create('Введена буква');

end;

//единичная матрица

SetLength(E, N, N);

for i:= 0 to N - 1 do

E[i, i]:= 1;

//общая матрицы

SetLength(AE, N, 2 * N);

for i:= 0 to N - 1 do

for j:= 0 to N - 1 do

begin

AE[i, j]:= A[i, j];

AE[i, j + N]:= E[i, j];

end;

ObrMatr;

//матрица свободных членов

SetLength(B, N);

for j:= 0 to N - 1 do

B[j]:= StrToInt(FormCW.StringGridB.Cells[0, j]);

//результат

SetLength(X, N);

for j:= 0 to N - 1 do

X[j]:= 0;

CalkRez;

A:= Nil;

E:= Nil;

AE:= Nil;

B:= Nil;

X:= Nil;

end;

//обращение матрицы методом Гаусса

function ObrMatr: extended;

var

i, j, k: integer;

d: extended;

begin

//прямой ход

for k:= 0 to N - 1 do //k - номер строки

begin

for i:= 0 to 2 * N - 1 do //i - номер столбца

begin

if A[k, k] = 0 then

begin

ShowMessage('Деление на ноль.');

exit;

end

else

AE[k, i]:= AE[k, i] / A[k, k];

end;

for i:= k + 1 to N - 1 do

begin

d:= AE[i, k] / AE[k, k]; //коэффициент

for j:= 0 to 2 * N - 1 do

AE[i, j]:= AE[i, j] - AE[k, j] * d;

end;

for i:= 0 to N - 1 do

for j:= 0 to N - 1 do

A[i, j]:= AE[i, j];

end;

//обратный ход

for k:= N - 1 downto 0 do //k - номер строки

begin

for i:= 2 * N downto 0 do //i - номер столбца

AE[k, i]:= AE[k, i] / A[k, k];

for i:= k - 1 downto 0 do

begin

d:= AE[i, k] / AE[k, k];

for j:= 2 * N downto 0 do

AE[i, j]:= AE[i, j] - AE[k, j] * d;

end;

end;

//отделение матрицы коэффициентов от общей матрицы

for i:= 0 to N - 1 do

for j:= 0 to N - 1 do

A[i, j]:= AE[i, j + n];

//вывод матрицы в Memo

for i:= 0 to N - 1 do

for j:= 0 to N - 1 do

FormCW.StringGridObr.Cells[i, j]:= FloatToStrF(A[i, j], ffFixed, 0, 4);

Result:= A[i, j];

end;

//вычисление коэффициентов матрицы

function CalkRez: extended;

var

i, j: integer;

begin

//умножение обратной матрицы на столбец

for j:= 0 to N - 1 do

begin

X[j]:= 0;

for i:= 0 to N - 1 do

X[j]:= X[j] + A[i, j] * B[i];

end;

for j:= 0 to N - 1 do

FormCW.StringGridRez.Cells[0, j]:= FloatToStrF(X[j], ffFixed, 0, 0);

end;

//открыть из файла

procedure TFormCW.ButtonRFClick(Sender: TObject);

var

i, j: integer;

FileRead: TextFile;

FRead: string;

begin

if OpenDialog1.Execute then

begin

FRead:= OpenDialog1.FileName;

AssignFile(FileRead, FRead);

Reset(FileRead); //чтение файла

end;

SetLength(R, N, N + 1);

for i:= 0 to N - 1 do

for j:= 0 to N do

begin

Read(FileRead, R[i, j]);

end;

for i:= 0 to N - 1 do

for j:= 0 to N do

begin

if j = N then

StringGridB.Cells[0, i]:= IntToStr(R[i, j])

else

StringGridA.Cells[j, i]:= IntToStr(R[i, j]);

end;

CloseFile(FileRead);

R:= Nil;

end;

//сохранить в файл

procedure TFormCW.ButtonWFClick(Sender: TObject);

var

i: integer;

FileWrite: TextFile;

FWrite: string;

begin

if SaveDialog1.Execute then

begin

FWrite:= SaveDialog1.FileName;

AssignFile(FileWrite, FWrite);

Rewrite(FileWrite);

end;

for i:= 0 to N - 1 do

begin

Writeln(FileWrite, StrToInt(StringGridRez.Cells[0, i]));

end;

CloseFile(FileWrite);

end;

end.

5. Тестовая задача

5.1 Аналитическое решение тестовой задачи

Условие тестовой задачи приводилось ранее в п. 1.2 курсовой работы.

Систему уравнений (1.2.1) удобно записать в матричной форме вида (2.1.2):

, , ,

где - количество заготовок трех типов (А, Б, В) по трем способам раскроя (I, II, III), шт.;

-расход материала (количество листов материала) для заготовок при каждом из указанных способов раскроя, шт.;

- необходимое общее количество заготовок трех типов, шт.

Решение данной системы через обращение матрицы методом Гаусса будет основано на преобразовании расширенной матрицы системы вида (2.2.16):

.

Для удобства, вычисления элементов обратной матрицы производятся по схеме единственного деления [5], которая составляется следующим образом (см. таблицу 5.1.1).

В разделе I схемы записываются коэффициенты матрицы и единичные векторы , , матрицы . Последняя строка раздела I, состоящая из единиц и элементов , , получается делением первой строки раздела на ведущий коэффициент . Элементы I, II, III разделов схемы, определяемые по формулам (2.2.1) - (2.2.8), составляют прямой ход.

Обратный ход начинается с вычисления последних неизвестных системы линейных уравнений , где по формуле (2.2.10) и заканчивается вычислением первого неизвестного. При обратном ходе используются строки прямого хода, содержащие единицы и соответствующие элементы .

Таблица 5.1.1

						Разделы схемы	Способ решения
			1	0	0	I	Прямой ход
			0	1	0
			0	0	1
						II
						III
		1				IV	Обратный ход
	1
1

Решение тестовой задачи по схеме записано в таблице 5.1.2.

Таблица 5.1.2

						Разделы схемы	Способ решения
	2	1	1	0	0	I	Прямой ход
1	6	2	0	1	0
4	1	5	0	0	1
1				0	0
				1	0	II
				0	1
	1				0
					1	III
		1
		1				IV	Обратный ход
	1
1

Следовательно, получили матрицу, обратную к матрице :

.

Осталось определить значения матрицы-столбца по формуле (2.1.11).

,

где шт., шт., шт.

Данная задача имеет единственное решение. Расход материала при каждом из указанных способов раскроя составляет: 90 листов для заготовки А, 15 листов для заготовки Б, 60 листов для заготовки С.

Ответ найден.

5.2 Решение, полученное с использованием разработанного программного обеспечения

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

Рисунок 3 - Решение, полученное с использованием разработанного программного обеспечения

5.3 Выводы

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

По результатам работы было найдено аналитическое решение системы линейных алгебраических уравнений и составлена вычислительная схема алгоритма, а также разработан интерфейс программы на языке программирования BorlandPascal 7.0.

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

6. Инструкция пользователю

После запуска программы пользователю потребуется ввести размер матрицы, при этом число должно быть целым больше единицы. После этого потребуется заполнить массив коэффициентов и массив свободных членов. Вводимые числа также должны быть целыми больше нуля. После заполнения таблицы, при нажатии кнопки «Рассчитать» произойдут необходимые вычисления и в таблице ниже будет выведен результат работы программы. Перед повторным вычислением потребуется очистить поля, нажав кнопку «Очистить». При чтении, записи из файла, также потребуется нажать на соответствующую кнопку.

Заполнить массив коэффициентов и массив свободных членов можно из файла формата *.txt.

Заключение

В ходе курсовой работы рассмотрено решение систем линейных уравнений методом Гаусса, основанным на преобразовании расширенной матрицы системы, на конкретной инженерной задаче. Для достижения цели выполнена систематизация знаний и умений по теме «Системы линейных уравнений». В качестве языка программирования был выбран язык BorlandPascal 7.0 ввиду его наглядности и облегченного понимания для начинающих программистов, а также возможности в дальнейшем использовать для решения более трудных задач. С помощью единожды созданной программы можно решать системы линейных уравнений, вводя минимум значений. Также эта программа может быть использована не только разработчиком, но и простыми пользователями.

В ходе выполнения курсовой работы были решены следующие задачи:

1) изучены теоретические основы основных методов решения систем линейных алгебраических уравнений: матричного, Крамера и Гаусса;

2) рассмотрены примеры решения систем линейных уравнений изученными методами;

3) рассмотрены практические задачи экономического содержания, сводящиеся к составлению и решению систем линейных уравнений;

4) определена эффективность использования изученных методов решения систем линейных уравнений в экономических задачах.

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

1. Буйначев С.К., Применение численных методов в математическом моделировании: учебное пособие - Екатеринбург, 2014, - 70с.

2. Бахвалов Н.С., Жидков Н.П. Кобельков Г.М. Численные методы. -М.: Лаборатория Базовых Знаний, 2000, - 624с.

3. Вержбицкий В.М.Основы численных методов: Учебник для вузов - М.: Высшая школа, 2002. - 840с.

4. Турчак Л.И. Основы численных методов: Учеб. пособие. - М.: Наука., 1987. - 320с.

5. Численные методы. Учебник для техникумов под ред. Н.И. Данилина, Н.С. Дубровская, О.П. Кваша. М., 1976, - 368с.

6. https://www.stankoff.ru/blog/post/683

7. Беликова Г.И., Бровкина Е.А., Вагер Б.Г., Витковская Л.В., Матвеев Ю.Л. Численные методы. Учебное пособие. - СПб.: РГГМУ, 2019. -174с.

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