Введение:
Во многих сферах деятельности человека возникают ситуации, когда требуется решить систему уравнений со множеством неизвестных. Примером может послужить транспортная задача: имеется т складов с продукцией; п магазинов, куда нужно эту продукцию доставить на реализацию. Известны все расстояния от каждого k-того склада до каждого l-того магазина. Требуется составить маршруты таким образом, чтобы затраты на перевозку были минимальны. Задача может быть решена численным методом с помощью системы линейных уравнений.
Это лишь один из примеров, где применяются системы линейных уравнений.
«Пусть дана система линейных уравнений
(1)
Коэффициенты при неизвестных составляют прямоугольную таблицу
,
называемую матрицей системы. Коэффициенты b1, b2, …, bm называются свободными членами уравнений системы. Если свободные члены равны нулю, система называется однородной, в противном случае – неоднородной. Матрицу
называют расширенной матрицей системы (1).
Решение системы (1) – это упорядоченный набор (х1, х2, …, хп) из п чисел, при подстановке которых в уравнения системы вместо соответствующих неизвестных каждое уравнение превращается в тождество. Система, не имеющая ни одного решения, называется несовместной. Система, имеющая хотя бы одно решение, называется совместной.
Две системы с одними и теми же неизвестными эквивалентны (равносильны), если каждое решение одной из них является решением другой или обе системы несовместны. Общий способ отыскания решений обычно основывается на последовательном переходе с помощью элементарных преобразований от данной системы к такой эквивалентной системе, для которой решение находится достаточно просто.
Элементарными называются следующие преобразования:
1. Умножение обеих частей какого-либо уравнения на число, отличное от нуля.
2. Прибавление (вычитание) к одному уравнению другого, умноженного на некоторое число.
3. Перестановка уравнений.
4. Вычеркивание уравнений вида 0 Ч х1 + 0 Ч х2 + … + 0 Ч хп = 0, т. е. тождеств 0 = 0.
5. Перестановка неизвестных в системе уравнений». [11, стр. 9, 10]
Если т = п, т. е. количество неизвестных совпадает с количеством линейно независимых уравнений системы, то СЛУ имеет единственное решение. Такую систему называют определенной. Если же n > m, т. е. количество неизвестных больше, чем количество линейно независимых уравнений СЛУ, то система имеет бесконечное множество решений и называется неопределенной. В таком случае т неизвестных принимают за главные, а оставшиеся п – т – за свободные неизвестные. «Члены, содержащие свободные неизвестные, переносят в правую часть уравнений системы и решают ее относительно главных неизвестных». [11, стр. 57]
.........
Основная часть:
Рассмотрим нахождение фундаментальной системы решений для приведенной (однородной) системы линейных уравнений.
Приведение матрицы к трапециедальному виду.
Чтобы привести матрицу к трапециедальному виду, воспользуемся методом Гаусса. «Алгоритм этого метода заключается в следующем. …Умножим первое уравнение на а21/а11 и вычтем из второго уравнения, затем – на а31/а11 и вычтем из третьего уравнеия и т. д. …Элемент а11 называют ведущим элементом этого шага. Следующие шаги прямого хода метода Гаусса осуществляются аналогично». [11, стр. 10,11]
Таким образом, система превращается в эквивалентную систему вида
,
где п – количество неизвестных; r – количество уравнений, оставшихся после преобразования (при преобразовании может получиться уравнение, представляющее собой тождество 0 = 0, это уравнение отбрасывается).
Понятие фундаментальной системы решений имеет смысл только для системы уравнений, где r < n. Если r = n, то система имеет треугольный вид и легко решается обратным ходом метода Гаусса. Мы же будем рассматривать только случай, когда r < n.
Приведение системы уравнений к трапециедальному виду можно производить в матричном виде. Блок-схема преобразования матрицы системы методом Гаусса представлена в приложении на рис.1, где z – двумерный массив, представляющий собой матрицу системы уравнений; п, т – размерность массива (т – число уравнений в системе, п – число неизвестных).
Процедура zero(f, m, k, z) предназначена для удаления нулевых строк из матрицы z, если таковые образуются в результате преобразований. В итоге мы получаем преобразованную матрицу и ее ранг, равный числу строк.
Получение ФСР.
«Для определения ФСР находят общее решение данной однородной системы. Берут любой, отличный от нуля, определитель порядка n – r, т.е. порядка, равного числу свободных неизвестных системы. Элементы i-й строки (столбца) этого определителя принимают за значения свободных неизвестных и находят из общего решения значения остальных (главных) неизвестных. Так поступают для всех строк (столбцов) выбранного определителя. Полученные так n – r решений и дадут фундаментальную систему решений». [1, стр.59, 60]
ФСР будет представлять собой таблицу, в которой приведены значения свободных неизвестных и соответствующих им значения главных элементов:
...........
Заключение:
Задача данной работы заключалась в нахождении фундаментальной системы решений системы линейных уравнений. В ходе работы было выполнено следующее:
1. Описан способ приведения матрицы системы к трапециедальному виду методом Гаусса.
2. Разработан алгоритм поиска фундаментальной системы решений однородной неопределенной системы линейных уравнений.
3. Написана и отлажена программа на алгоритмическом языке Turbo Pascal, предназначенная для
- приведения матрицы системы к трапециедальному виду;
- нахождения фундаментальной системы решений неопределенной однородной системы решений.
Задачу данной работы можно считать выполненной.