Решение системы уравнений со множеством неизвестных

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

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

Введение

Во многих сферах деятельности человека возникают ситуации, когда требуется решить систему уравнений со множеством неизвестных. Примером может послужить транспортная задача: имеется т складов с продукцией; п магазинов, куда нужно эту продукцию доставить на реализацию. Известны все расстояния от каждого k-того склада до каждого l-того магазина. Требуется составить маршруты таким образом, чтобы затраты на перевозку были минимальны. Задача может быть решена численным методом с помощью системы линейных уравнений.

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

«Пусть дана система линейных уравнений

(1)

Коэффициенты при неизвестных составляют прямоугольную таблицу

,

называемую матрицей системы. Коэффициенты b1, b2, …, bm называются свободными членами уравнений системы. Если свободные члены равны нулю, система называется однородной, в противном случае - неоднородной. Матрицу



называют расширенной матрицей системы (1).

Решение системы (1) - это упорядоченный набор (х1, х2, …, хп) из п чисел, при подстановке которых в уравнения системы вместо соответствующих неизвестных каждое уравнение превращается в тождество. Система, не имеющая ни одного решения, называется несовместной. Система, имеющая хотя бы одно решение, называется совместной.

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

Элементарными называются следующие преобразования:

Умножение обеих частей какого-либо уравнения на число, отличное от нуля.

Прибавление (вычитание) к одному уравнению другого, умноженного на некоторое число.

Перестановка уравнений.

Вычеркивание уравнений вида 0 х1 + 0 х2 + … + 0 хп = 0, т. е. тождеств 0 = 0.

Перестановка неизвестных в системе уравнений». [11, стр. 9, 10]

Если т = п, т. е. количество неизвестных совпадает с количеством линейно независимых уравнений системы, то СЛУ имеет единственное решение. Такую систему называют определенной. Если же n > m, т. е. количество неизвестных больше, чем количество линейно независимых уравнений СЛУ, то система имеет бесконечное множество решений и называется неопределенной. В таком случае т неизвестных принимают за главные, а оставшиеся п - т - за свободные неизвестные. «Члены, содержащие свободные неизвестные, переносят в правую часть уравнений системы и решают ее относительно главных неизвестных». [11, стр. 57]

«Матрица F, состоящая из столбцов высоты п, называется фундаментальной матрицей для однородной системы с матрицей А размеров т х п, если:

а) AF = 0;

б) столбцы F линейно независимы;

в) ранг F максимален среди рангов матриц, удовлетворяющих условию а).

…Столбцы фундаментальной матрицы называются фундаментальной системой решений». [2, стр. 195]

«Каждое решение однородной системы представляет собой п-мерный вектор-столбец. Линейное пространство решений однородной системы является (n - r)-мерным пространством (n - число неизвестных системы, r - ранг ее матрицы, n - r - число свободных неизвестных в системе). Любой его базис называют фундаментальной системой решений (ФСР) однородной системы уравнений». [11, стр. 59]

Последнее утверждение требует введения понятия ранга матрицы. «Пусть в матрице А существует линейно независимая система из r строк и нет линейно независимой системы из большего числа строк. Тогда мы будем говорить, что строчный ранг матрицы А равен r». [2, стр. 183]

«Выделим в (т х п)-матрице А k строк и k столбцов. Элементы, стоящие на пересечениях этих стрк и столбцов, составляют матрицу порядка k. Определитель этой матрицы называют минором k-го порядка матрицы А». [11, стр. 22]

«Ранг матрицы совпадает с наивысшим порядком отличных от нуля миноров этой матрицы. Такие миноры называют базисными». [11, стр. 46]

Из сказанного выше вытекает, что для определенной СЛУ, где n = r, фундаментальной системы решений не существует, так как n - r = 0. Задачей данной работы является нахождение ФСР неопределенной СЛУ.

линейный уравнение матрица ранг

Постановка задачи

Дана неопределенная система линейных уравнений

,

где т п.

«Сопоставим системе линейных уравнений (1) однородную систему с той же матрицей коэффициентов… По отношению к системе (1) она называется она называется приведенной…

Пусть хо - решение системы (1). Столбец х также будет ее решением тогда и только тогда, когда найдется такое решение у приведенной системы, что х = х0 + у… Это предложение сводит задачу описания множества решений совместной системы линейных уравнений к описанию множества решений ее приведенной системы». [2, стр. 194]

Таким образом, поиск ФСР неоднородной СЛУ сводится к нахождению ФСР приведенной (однородной) СЛУ.

Исходя из сказанного выше, составим план нахождения ФСР:

В случае неоднородной СЛУ взять приведенную СЛУ.

Привести матрицу системы к трапециедальному виду (например, методом Гаусса).

Определить ранг матрицы.

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

Решение задачи

Рассмотрим нахождение фундаментальной системы решений для приведенной (однородной) системы линейных уравнений.

Приведение матрицы к трапециедальному виду

Чтобы привести матрицу к трапециедальному виду, воспользуемся методом Гаусса. «Алгоритм этого метода заключается в следующем. …Умножим первое уравнение на а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]

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

e	х1	х2	…	хr	хr+1	хr+2	…	хn
e1	11	12	…	1r	11	12	…	1п
e2	21	22	…	2r	21	22	…	2п
…	…	…	…	…	…	…	…	…
en-r	n-r,1	n-r,2	…	n-r,r	n-r,1	n-r,2	…	n-r,n

Алгебраические векторы еi = (i1, i2, …, ir, i1, i2, …, in) называют векторами решений ФСР.

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



Для получения общего решения системы, воспользуемся методом, подобным обратному ходу метода Гаусса. Обратный ход метода Гаусса заключается в следующем: «из последнего уравнения этой системы найдем значение неизвестного хп. Подставив его в предпоследнее уравнение, найдем значение хп-1. Продолжая так далее, однозначно определим все неизвестные х1, х2, …, хп». [11, стр. 12] Однако этот метод дает однозначное решение лишь для определенной системы, т. е. системы, ранг которой равен количеству неизвестных. В неопределенной системе «свободные неизвестные могут принимать любые фиксированные значения». [11, стр. 12]

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

(2)

ФСР будет представлять собой следующую таблицу:

e	х1	х2	…	хr	хr+1	хr+2	…	хn
e1	11	12	…	1r	1	0	…	0
e2	21	22	…	2r	0	1	…	0
…	…	…	…	…	…	…	…	…
en-r	n-r,1	n-r,2	…	n-r,r	0	0	0	1

Для получения ФСР предлагают сначала найти общее решение системы. Что это за решение? Рассмотрим на примере. Пусть дана система уравнений

Приведем матрицу системы к трапециедальному виду:

Ранг матрицы равен 2, значит, ФСР имеет n - r = 2 вектора решений. Запишем первое уравнение:

-3,5х2 + 5,5х3 - 10,5х4 = 0

-3,5х2 = -5,5х3 + 10,5х4

Это «значение» подставляется в первое уравнение (уравнение, расположенное на строку выше):

2х1 + х2 - 3х3 + 5х4 = 0

2х1 = -х2 + 3х3 - 5х4

2х1 = -(1,6х3 - 3х4) + 3х3 - 5х4 = 1,4х3 - 2х4

Таким образом, мы получили общее решение Х = (1,4х3 - 2х4; 1,6х3 - 3х4; х3; х4).

Далее свободным неизвестным (х3, х4) будем присваивать значения элементов столбца (строки) ненулевого определителя, например, и, подставляя их в общее решение, найдем значения (х1, х2).

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

Пример 1

Пусть дана система уравнений:

Преобразуем матрицу системы к трапециедальному виду:

Ранг матрицы равен 2, следовательно, ФСР будет иметь n - r = 2 вектора решений. х3 и х4 будем считать свободными, х1 и х2 - главными неизвестными. Поменяем знак коэффициентов при свободных неизвестных (как при переносе в правую часть уравнений):

На первом шаге х2 принимает следующие значения:

Так мы получаем столбец значений в ФСР:

е	х1	х2	х3	х4
е1		6	1	0
е2		-9	0	1

На втором шаге мы используем эти значения, подставляя их в следующее уравнение:

,

и мы получаем следующий столбец значений:

е	х1	х2	х3	х4
е1	-11	6	1	0
е2	14	-9	0	1

Пример 2.

Пусть дана система уравнений:



Преобразуем матрицу системы к трапециедальному виду:

Ранг матрицы равен 2, следовательно, ФСР будет иметь n - r = 3 вектора решений. х2, х3 и х4 будем считать свободными, х1 и х2 - главными неизвестными. Поменяем знак коэффициентов при свободных неизвестных:

На первом шаге х2 принимает следующие значения:

Так мы получаем столбец значений в ФСР:

е	х1	х2	х3	х4	х5
е1		1,8	1	0	0
е2		0,4	0	1	0
е3		-1	0	0	1

На втором шаге мы используем эти значения, подставляя их в следующее уравнение:

и мы получаем следующий столбец значений:

е	х1	х2	х3	x4	х5
е1	-0,6	1,8	1	0	0
е2	-1,8	0,4	0	1	0
e3	0	-1	0	0	1

Пример 3.

Пусть дана система уравнений:

Преобразуем матрицу системы к трапециедальному виду:

Ранг матрицы равен 3, следовательно, ФСР будет иметь n - r = 1 вектор решений. х4 будем считать свободным, х1, х2 и х3 - главными неизвестными. Поменяем знак коэффициентов при свободном неизвестном:

На первом шаге х3 принимает следующее значение:

Так мы получаем столбец значений в ФСР:

е	х1	х2	х3	х4
е1			0,3	1

На втором шаге мы используем это значение, подставляя его в следующее уравнение:

и мы получаем следующий столбец значений:

е	х1	х2	х3	х4
е1		-1,5	0,3	1

На третьем шаге мы используем значение второй переменной, подставляя его в следующее уравнение:

и мы получаем последний столбец значений:

е	х1	х2	х3	х4
е1	1,1	-1,5	0,3	1

Таким образом, общая формула нахождения значений ФСР имеет вид:

Блок-схема нахождения ФСР представлена в приложении на рисунке 2.

Заключение

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

Описан способ приведения матрицы системы к трапециедальному виду методом Гаусса.

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

Написана и отлажена программа на алгоритмическом языке Turbo Pascal, предназначенная для приведения матрицы системы к трапециедальному виду;

нахождения фундаментальной системы решений неопределенной однородной системы решений.

Задачу данной работы можно считать выполненной.

Список литературы

Александров П. С. Курс аналитической геометрии и линейной алгебры. М.: Наука, 1979.

Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры: Учеб. для вузов. - 8-е изд., перераб. - М.: Физико-математическая литература, 2000. - 376 с.

Бортаковский А.С. Линейная алгебра в примерах и задачах: Учеб. пособие / А.С. Бортаковский, А. В. Пантелеев. - М.: Высш. школа, 2005. - 591 с.

Воеводин В.В. Линейная алгебра. М.: Наука, 1980.

Гельфанд И.М. Лекции по линейной алгебре. М.: Наука, 1971.

Глухов М. М. Алгебра и аналитическая геометрия: Учебное пособие. - М.: ГелиосАРВ, 2005. - 392 с.

Ильин В.А., Позняк Э.Г. Линейная алгебра. - М.: Наука, 1974.

Малугин В.А. Математика для экономистов: линейная алгебра. Курс лекций. - М.: Эксмо, 2006. - 224с.

Меженный О. А. Turbo Pascal: учитесь программировать. - М.: Издательский дом «Вильямс», 2002. - 448 с.

Фаддеев Д.К. Лекции по линейной алгебре. М.: Наука, 1984.

Шевцов Г.С. Линейная алгебра: Учебное пособие. - 2-е изд. исп. и доп. - М.: Гардарики, 1999. - 360 с.

Приложения

Приложение 1

Приложение 2

Приложение 3

Текст программы на Turbo Pascal'е, предназначенной для поиска ФСР СЛУ.

program FSR_SLU;

type matr=array[1..20, 1..20] of real;

var z,e:matr;

n,l,rang: integer;

procedure vivod (k,r:integer; var m:matr);

var i,j: integer;

begin

writeln(' ');

for i:=1 to r do begin

for j:=1 to k-1 do

write(' ',m[j,i]:4:1);

writeln(' ',m[k,i]:4:1);

end;

readln;

end;

procedure form (k,r:integer; var m:matr);

var i,j:integer;

begin

for i:=1 to r do

for j:=1 to k do

read(m[j,i]);

end;

procedure gauss(k,r: integer; var m:matr);

var i,j,f,d: integer;

x:real;

b:boolean;

begin

i:=1;

while i<r do begin

f:=i+1;

while f<=r do begin

x:=m[i,f]/m[i,i];

for j:=1 to k do

m[j,f]:= m[j,f] - m[j,i]*x;

b:=true; j:=1;

repeat

b:=(m[j,f]<>0);

j:=j+1;

until ((b) or (j>k));

if not b then begin

for d:=f to r do

for j:=1 to k do

m[j,d] :=m[j,d+1];

f:=f-1;

r:=r-1;

end;

f:=f+1;

end;

i:=i+1;

end;

writeln('rang=',r);

rang:=r;

end;

procedure fse(k,r:integer; m:matr; var f:matr);

var i,j,d:integer;

x:array[1..20] of real;

begin

for j:=1 to k-rang do

f[rang,j]:=-m[rang+j,rang]/m[rang,rang];

for i:=rang-1 downto 1 do

for j:=1 to k-rang do begin

x[j]:=0;

for d:=1 to i do

x[j]:=x[j]+m[rang-d+1,i]*f[rang-d+1,j];

f[i,j]:= (-m[rang+j,i] - x[j])/m[i,i];

end;

for i:=1 to k-rang do

f[rang+i,i]:=1;

end;

begin

writeln('vvedite razmer matrizy systemy n, m');

readln(n,l);

writeln('vvedite matrizu');

form (n,l,z);

vivod(n,l,z);

gauss(n,l,z);

vivod(n,rang,z);

if rang<n then begin

fse(n,l,z,e);

vivod(n,n-rang,e);

end

else writeln ('systema opredelena');

end.

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

...