SHPORA.net :: PDA

[ Back ]

В общем случае линейное уравнение имеет вид:

a1x1+a2x2+...+anxn=b

Уравнение имеет решение: если хотя бы один из коэффициентов a1 = a2 = ... = an при неизвестных x1, x2,....xn отличен от нуля. В этом случае любой n-мерный вектор Х = (x1, x2,....xn) называется решением уравнения, если при подстановке его координат уравнение обращается в тождество.

ОБЩАЯ ХАРАКТЕРИСТИКА РАЗРЕШЕННОЙ СИСТЕМЫ УРАВНЕНИЙ

Пример 20.1

Дать характеристику системе уравнений.



Решение:

1. Входит ли в состав системы линейных уравнений противоречивое уравнение? (Если коэффициенты a1 = a2 = ... = an =0, а b ? 0, в этом случае уравнение имеет вид: 0*x1+0*x2+...+0*xn= b и называется противоречивым.)

• Если система содержит противоречивое, то такая система несовместна и не имеет решения

2. Найти все разрешенные переменные. (Неизвестная Xn называется разрешенной для системы уравнений, если она входит в одно из уравнений системы с коэффициентом +1, а в остальные уравнения не входит (т.е. входит с коэффициентом, равным нулю).

• В нашем примере неизвестная X1 входит в первое уравнение с коэффициентом единица, во второе уравнение не входит, то есть X1 является первой разрешенной.

• Аналогично X2 - содержится только во втором уравнении а X5 только в первом.

3. Является ли система уравнений разрешенной? (Система уравнений называется разрешенной, если каждое уравнение системы содержит разрешенную неизвестную, среди которых нет совпадающих)

• Наша система является разрешенной т.к. каждое уравнение содержит в себе разрешенные неизвестные X1 , x2, x3 )

Разрешенные неизвестные, взятые по одному из каждого уравнения системы, образуют полный набор разрешенных неизвестных системы. (в нашем примере это x1 x2 x5)

Разрешенные неизвестные, входящие в полный набор, называют также базисными (x1 x2 x5), а не входящие в набор - свободными (x3 x4).



В общем случае разрешенная система уравнений имеет вид:



!На данном этапе главное понять что такое разрешенная неизвестная (входящая в базис и свободная).

ОБЩЕЕ ЧАСТНОЕ БАЗИСНОЕ РЕШЕНИЯ

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



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

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

• Базисное решение (вектор) называется вырожденным, если число его координат, отличных от нуля, меньше числа разрешенных неизвестных.

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

Теорема (1)

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

Пример 1. Найти общее, базисное и какое-либо частное решение системы уравнений:



Решение:

1. Проверяем является ли система разрешенной?

• Система является разрешенной (т.к. каждое из уравнений содержит в себе разрешенную неизвестную)

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

• В нашем случае мы можем включить в набор разрешенных неизвестных из первого уравнения - x1 и x5, а из второго уравнения только x2. То есть набор может состоять из (x1 x2) или (x5 x2).

3. Записываем общее решение в зависимости от того какие разрешенные неизвестные мы включили в набор.

• допустим мы включили в набор неизвестные x1 и x2, тогда общее решение будет выглядеть так:



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

• Пусть Х3=0, Х4=1, Х5=2, тогда из общего решения находим:



Ответ: частное решение (один из вариантов) Хч=(9,24,0,1,2)

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

• Х3=Х4=Х5=0, то из общего решения получаем Х1=10, Х2=20 и базисное решение: Хб=(10,20,0,0,0)

ЭЛЕМЕНТАРНЫЕ ПРЕОБРАЗОВАНИЯ ЛИНЕЙНЫХ УРАВНЕНИЙ

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

Теорема (2)

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

Теорема (3)

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

Следствие из Теорем (2 и 3)

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

ФОРМУЛЫ ПЕРЕСЧЕТА КОЭФФИЦИЕНТОВ СИСТЕМЫ

Если у нас есть система уравнений и мы хотим преобразовать ее в разрешенную систему уравнений в этом нам поможет метод Жордана-Гаусса.

Преобразование Жордана с разрешающим элементом Alk?0 позволяет получить для системы уравнений разрешенную неизвестную Хк в уравнении с номером l. (пример 2).

Преобразование Жордана состоит из элементарных преобразований двух типов:

1. Уравнение с разрешающим элементом Aik делится на этот элемент (умножается на -1/Alk )

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

Допустим мы хотим сделать неизвестную xk в нижнем уравнении разрешенной неизвестной. Для этого мы должны разделить aik на -Alk, так чтобы сумма (-aik /alk + aik =0).

Пример 2 Пересчитаем коэффициенты системы



При делении уравнения с номером l на Alk, его коэффициенты пересчитываются по формулам:



Чтобы исключить Хк из уравнения с номером i, нужно уравнение с номером l умножить на и прибавить к этому уравнению.

Теорема (4) О сокращении числа уравнений системы.

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

Теорема (5) О несовместимости системы уравнений.

Если система уравнений содержит противоречивое уравнение, то она несовместна.

АЛГОРИТМ МЕТОДА ЖОРДАНА-ГАУССА

Алгоритм решения систем уравнений методом Жордана-Гаусса состоит из ряда однотипных шагов, на каждом из которых производятся действия в следующем порядке:

1. Проверяется, не является ли система несовместной. Если система содержит противоречивое уравнение, то она несовместна.

2. Проверяется возможность сокращения числа уравнений. Если в системе содержится тривиальное уравнение, его вычеркивают.

3. Если система уравнений является разрешенной, то записывают общее решение системы и если необходимо - частные решения.

4. Если система не является разрешенной, то в уравнении, не содержащем разрешенной неизвестной, выбирают разрешающий элемент и производят преобразование Жордана с этим элементом.

5. Далее заново переходят к пункту 1

Пример 3 Решить систему уравнений методом Жордана-Гаусса.

Найти: два общих и два соответствующих базисных решения



Решение:

Вычисления приведены в нижеследующей таблице:

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



В первых трех строках таблицы помещены коэффициенты при неизвестных и правые части исходной системы. Результаты первого преобразования Жордана с разрешающим элементом равным единице приведены в строках 4, 5, 6. Результаты второго преобразования Жордана с разрешающим элементом равным (-1) приведены в строках 7, 8, 9. Так как третье уравнение является тривиальным, то его можно не учитывать.

Равносильная система с разрешенными неизвестными Х1 и Х2 имеет вид:



Теперь можем записать Общее решение:



Приравниваем свободные переменные Х3 и Х4 нулю и получаем: Х1 = -3+0+0 = -3, Х2 = 4-2*0-3*0 = 4.

Базисное решение: Хб1 = (-3,4,0,0)

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



В нашем случае выбран разрешающий элемент (-1) в первом уравнении при x3 (строка 7). Далее производим преобразование Жордана. Получаем новую разрешенную систему (строки 10,11) c новыми разрешенными неизвестными Х2 и Х3:



Записываем второе общее решение:



И соответствующее ему базисное решение: Хб2= (0, -2, 3, 0)

Ответы:

Общее решение:



Базисное решение: Хб1 = (-3,4,0,0)

Общее решение:



Базисное решение: Хб2= (0, -2, 3, 0)



Описывается метод полного исключения Жордана-Гаусса

Чтобы сделать cимплекс-метод пригодным для реализации на ЭВМ был разработан табличный вариант симплекс-метода. В его основе лежит метод полного исключения Жордана-Гаусса.

Пусть задана система линейных алгебраических уравнений



j=1, 2, ., m.

В матричной форме данная система имеет следующий вид:

Ax=A0.

Матрица Ap=[A, A0] называется расширенной матрицей.

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

1) одну из строк расширенной матрицы умножают на множитель, отличный от нуля;

2) из каждой строки расширенной матрицы вычитают одну строку, умноженную на некоторое число.

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

Первая итерация метода полного исключения.

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

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

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

Если после k-й итерации главная часть матрицы Ap(k) не содержит ни одного элемента или содержит только нули, то процесс заканчивается.