3. Решение систем линейных уравнений методом Жордана-Гаусса. Рассмотрим систему m линейных уравнений с n неизвестными
a
11
x
1
+ a
12
x
2
+ ... + a
1n
x
n
= b
1
,
a
21
x
1
+ a
22
x
2
+ ... + a
2n
x
n
= b
2
,
a
m1
x
1
+ a
m2
x
2
+ ... + a
m1n
x
n
= b
m
(1) Решением системы линейных уравнений называется совокупность n чисел α
1
,
α
2
,…,α
n
, таких, что при подстановке их вместо неизвестных каждое уравнение обращается в тождество. Система линейных уравнений называется совместной, если существует хотя бы одно ее решение. Система, не имеющая ни одного решения, называется несовместной. Совместные системы подразделяются на определенные, имеющие единственное решение, и неопределенные, имеющие бесконечное множество решений. Каждой системе линейных уравнений поставим в соответствие матрицу А из коэффициентов и расширенную матрицу
, полученную присоединением к матрице А столбца свободных членов
20
A
A
A
A
n
a
11
A =
a
21
a
12
a
22
a
1n
a
2n
a
11
a
21
a
12
a
22
a
1n
a
2n
b
1
b
2
... ; A =
.
a
a
... a
a
a
... a b
m1
m2
mn
m1
m2
mn
m
Вопрос о совместности системы линейных уравнений решается теоремой
Кронекера-Капелли: система линейных уравнений совместна тогда и только тогда, когда ранг расширенной матрицы
равен рангу матрицы А, те. когда r(
) = А.
A
A На основании теоремы Кронекера-Капелли имеем
1. Если r(
) ≠ А, то система несовместна.
2. Если r(
) = А, то система совместна. В этом случае r уравнений системы линейно независимы, остальные m-r уравнений являются их линейной комбинацией. Поэтому в системе оставляем лишь r уравнений, коэффициенты при неизвестных которых составляют базисный минор. В результате получим r линейных уравнений с r неизвестными. Если r = n, то система имеет единственное решение. Если r < n, то система имеет бесконечное множество решений, те. является неопределенной. Число свободных переменных равно n - r. Метод Жордана-Гаусса применяется для решения системы m линейных уравнений с n неизвестными вида
a
ij
x
j
= b
i
,i = 1,..., m.
j =1 Над строками расширенной матрицы преобразования
• перестановка любых двух уравнений
осуществляем следующие
• умножение обеих частей одного из уравнений на любое отличное от нуля число
• прибавление к обеим частям одного уравнения соответствующих частей другого, умноженных на любое число, отличное от нуля
• вычеркивание нулевой строки (уравнения с нулевыми коэффициентами и свободным членом, равным 0). Можно показать, что элементарные преобразования переводят данную систему уравнений в эквивалентную систему. Две системы линейных уравнений называются эквивалентными, или равносильными, если каждое решение первой системы (если они существуют) является решением второй, и наоборот. Соответствующие расширенные матрицы также называются эквивалентными. При практическом решении системы линейных уравнений методом Жордана- Гаусса последовательно над строками матрицы А выполняют элементарные преобразования, так что некоторое неизвестное исключается из всех уравнений, кроме одного, те. в составе расширенной матрицы формируется единичная матрица. В процессе решения могут встретиться следующие случаи.
1. Будет получена матрица
, эквивалентная матрице А, в левой части некоторой строки ее стоят нули, а в правой - число, отличное от нуля, что соответствует уравнению
0 * X
1
+ 0 * X
2
+ … + 0 * X
n
= b i
(b i
≠ 0).
21 r 0 n 0 Это признак несовместности системы (1), те. система не имеет решений. 2. В результате преобразований получилась матрица вида 1 0 0 1 0 b1 0 b A = 0 2 . 1 b В этом случае система (1) - совместная, определенная и имеет единственное решение Х = b 1 , Х = b 2 , Х = b n 3. На некотором этапе получилась расширенная матрица вида 0 1 ... 0 ... 0 a1 r +1 a a1 n a b1 b A = 2 r +1 2 n 2 . ... 1 ar r+1 ... ar n br Система совместна и имеет бесчисленное множество решений. Общее решение системы можно записать в виде x1 = b1 − a1 r +1 xr +1 − ... − a1 n xn x2 = b2 − a2 r +1 xr +1 − ... − a2 n xn xr = br − ar r+1 xr +1 − ... − ar n xn Придавая каждой из стоящих в правых частях равенств переменных Х, Х,
..., X
n произвольные значения, будем получать частные решения системы. Неизвестные Х, Х, ..., Х называются базисными, или основными, они соответствуют линейно-независимым векторам A
1
, ...,А
r
Таким образом, любые r переменных называются базисными основными, если определитель матрицы коэффициентов при них отличен от нуля, а остальные
(n-r) переменных называются свободными, или неосновными. Базисным решением системы уравнений называется частное решение, в котором неосновные переменные имеют нулевые значения. Каждому разбиению на основные и неосновные переменные соответствует одно базисное решение, а количество способов разбиения не превышает величины С
n!
m!(n − m)! Если все компоненты базисного решения неотрицательны, то такое решение называется опорным. Пример 9. Решить методом Жордана-Гаусса систему линейных уравнений
X
1
+ X
2
+ 2X
3
= -1,
2X
1
- X
2
+ 2X
3
= -4,
4X
1
+ X
2
+ 4X
3
= -2. Решение. Составим расширенную матрицу
0 1 0
22
A
11 0
22 22 0
A
0
A
2
0
0
(0)
1
= 2
1 2 −1
−1 2 − 4.
1 4 − 2
1 Итерация. В качестве направляющего элемента выбираем элемент
a
(0)
= 1
. Преобразуем первый столбец в единичный. Для этого ко второй и третьей строкам прибавляем первую строку, соответственно умноженную на - 2 и - 4. Получим матрицу
1 1
(1)
2 −1
A =
0 − 3 − 2 − 2.
− 3 − 4 2
2 Итерация. Выбираем направляющий элемент
a
(1)
= −3
. Так как
a
(1)
1
, то делим вторую строку на -3. Затем умножаем вторую строку на 1 и 3 и складываем соответственно с первой и третьей строками. Получим матрицу
(2)
1 0
4 3 − 5 3
A
= 0 1 2 3 2 3
− 2 4
3 Итерация. Выбираем направляющий элемент
a
(2)
= −2
. Так как
a
(2)
1
, то делим третью
33 33 строку на -2. Преобразуем третий столбец в единичный. Для этого умножаем третью строку на - 4/3 и -2/3 и складываем соответственно с первой и второй строками. Получим матрицу
(3)
1 0
= 0 1 0 1
0 2
1 − 2
откуда X
1
= 1, X
2
= 2, X
3
= -2. Пример 10. Решить методом Жордана-Гаусса систему линейных уравнений
X
1
- X
2
+ X
3
- X
4
= 4,
X
1
+ X
2
+ 2X
3
+ 3X
4
= 8,
2X
1
+ 4X
2
+ 5X
3
+ 10X
4
= 20,
2X
1
- 4X
2
+ X
3
- 6X
4
= 4. Решение. Расширенная матрица имеет вид
1
(0)
=
1
Применяя элементарные преобразования, получим
4 2
−1 1 −1 4
1 2
3 8
4 5 10 20
,
− 4 1 − 6 4
23
A
0 0
A
1 6
11
A
(1)
1 −1 1
0 2 1
−1 4
4 4
A =
6 3
12 12
,
(2)
− 2
1
=
0
−1 − 4 − 4 Исходная система эквивалентна следующей системе уравнений
X
1
- 3X
2
X
4
= 0,
2X
2
+ X
3
+ 4X
4
= 4. Общее решение имеет вид
X
1
= 3X
2
+ 5X
4
,
X
3
= 4 – 2X
2
– Найдем базисные решения. Для этого полагаем Х = 0, Х = 0, тогда X
1
= 0, Х 4. Базисное решение имеет вид (0, 0, 4, 0). Получим другое базисное решение. Для этого в качестве свободных неизвестных примем Хи Х. Выразим неизвестные Хи Х через неизвестные Хи Х
X
1
= 6 – 1.5X
2
– X
4
X
2
= 2 – 0.5X
3
– Тогда базисное решение примет вид (6, 2, 0, 0). Пример 11. Решить методом Жордана-Гаусса систему линейных уравнений
X
1
+ 2X
2
+ 2X
3
+ 22X
4
– 4X
5
= 11,
X
1
+ 2X
2
+ X
3
+ 16X
4
– 4X
5
= 9,
X
1
+ X
2
+ X
3
+ 12X
4
– 2X
5
= 6. Решение. Составим расширенную матрицу
1 Итерация.
(0)
1 2
=
1 2
1 2 22 1 16 1 12
− 4 11
− 4 9
− 2
В качестве направляющего элемента выбираем элемент
a
(0)
= 1
. Преобразуем первый столбец в единичный. Для этого ко второй и третьей строкам прибавляем первую строку, умноженную на -1. Получим матрицу
(1)
1
=
0
2 2
0
−1
−1 −1 22
− 6
−10
− 4 11
0
− 2
2
− 5
0 0
0
− 3 2
0 1
− 5 4
0
4
0 0
0 0
0 0
0 0
24 32 A 0 22 22 A 0 3 5 2 Итерация. Выбираем направляющий элемент
a
(1)
= −1
. Умножаем третью строку на -1. Преобразуем второй столбец в единичный. Для этого к первой строке прибавляем третью строку, умноженную на -2. Получим матрицу
(2)
1
=
0
3 Итерация. Выбираем направляющий элемент
a
(2)
= −1
. Так как
a
(2)
1
, то умножаем вторую строку на -1. Преобразуем третий столбец в единичный. Для этого вторую строку складываем с третьей. Получим матрицу
(3)
1 0 0 2
=
0 0 1 6
1 0 4 0
1
0 2
− 2
Исходная система эквивалентна следующей системе уравнений
X
1
+ 2X
4
= 1,
X
3
+ 6X
4
= 2,
X
2
+ 4X
4
- 2X
5
= 3. Общее решение имеет вид
X
1
= 1 – 2X
4
,
X
2
= 3 – 4X
4
+ 2X
5
,
X
1
= 2 – Переменные Х, Х, X
3
, являются основными или базисными. Любое частное решение получается из общего путем придания конкретных значений свободным переменным. Если свободные переменные Хи Х положить равными нулю, то получим первое базисное решение Х = 1, X
2
= 3,X
3
= 2, X
4
= 0, X
5
= 0. чем Первое базисное решение имеет вид (1, 3, 2, 0, 0). Общее число групп основных переменных, те. базисных решений, не более
C
3
=
n!
=
m!(n − m)!
5!
3!(5 − 3)!
= 1* 2 * 3* 4 * 5 = 10 1* 2 * 3*1* 2 Решение примера 11 в EXCEL В среде EXCEL общее число групп можно определить с помощью функции
ЧИСЛКОМБ.
ЧИСЛКОМБ - возвращает количество комбинаций для заданного числа объектов. Функция ЧИСЛКОМБ используется для определения числа всех возможных сочетаний объектов в группы. Синтаксис
ЧИСЛКОМБ (число число_выбранных)
0 0
2 0
1 0
−1 − 6 0 − 2 1 −1 −10 2 5
25 Число - это число объектов.
Число_выбранных - это число объектов в каждой комбинации.
• Числовые аргументы усекаются до целых.
• Если любой из аргументов не число, то ЧИСЛКОМБ возвращает значение ошибки ИМЯ.
• Если число < 0 или число_выбранных < 0, или число < число_выбранных, то функция ЧИСЛКОМБ возвращает значение ошибки ЧИСЛО.
• Комбинацией считается любое множество или подмножество объектов, безотносительно к их порядку. Комбинации отличаются от перестановок, для которых порядок существенен.
• Число комбинаций определяется следующим образом, где число равно n и число_выбранных равно k:
n
=
k
P
k ,n
k! =
n!
k!(n − k)! где
P
k ,n
= n!
(n − k)! На рисунке 15 показано, как использовать функцию ЧИСЛКОМБ. Рисунок 15 - Число сочетаний из 5 по 3 равно 10. В нашем примере число базисных решений равно 7, так как три группы переменных третья, седьмая и девятая - не могут быть базисными, потому что определитель матрицы коэффициентов при них равен нулю (см. таблицу 1). Рассмотрим по шагам получение всех базисных решений с помощью EXCEL, начиная с первого Х, Х, X
3 1. Матрица коэффициентов при Х, Х, X
3
,
26 1
1 0
1
1 2 2
1 2 1
находится в ячейках B7:D9, выделен диапазон для размещения обратной матрицы
B11:D13, введена формула для вычислений (рисунок 16). Рисунок 16 - Выделен диапазон для размещения обратной матрицы в ячейках
B11:D13, введена формула для вычислений.
2. Затем следует нажать клавиши CTRL+SHIFT+ENTER. В диапазоне B11:D13 размещена обратная матрица (рисунок 17):
− 1
0
0 2
1 1
− 1 Рисунок 17 - В диапазоне B11:D13 размещена обратная матрица.
1
27 3. Для получения решения системы уравнений необходимо умножить
11 полученную обратную матрицу на вектор-столбец свободных членов
9
. На
6
рисунке 18 показан выделенный диапазон для результата умножения и введена функция. Затем следует нажать клавиши CTRL+SHIFT+ENTER. Рисунок 18 - Умножение обратной матрицы на вектор-столбец свободных членов. В диапазоне F11:F13 получено первое базисное решение системы уравнений Х = 1, Х = 2, X
3
= 2, Х = 0, Х = 0 (рисунок 19). Рисунок - В диапазоне F11:F13 получено решение. Для получения второго базисного решения для переменных Х, Х, выполняем указанную последовательность действий (рисунок 20).
28 Второе базисное решение имеет вид (0.333; 1.667; 0; 0.333; 0). Рисунок 20 - Получено второе базисное решение. Для третьей группы переменных Х, Х, X
5
нельзя найти базисное решение, потому что определитель равен нулю (рисунок 21). Рисунок 21 - В ячейке В результат выполнения функции МОПРЕД - определитель равен нулю. В таблице 1 содержатся результаты вычислений по всем 10 группам переменных, те. результат решения примера 11. Шестой столбец таблицы содержит базисные решения. Таблица 1 - Результаты вычислений по 10 группам переменных
1 2
3 4
5 6
X1
X2
X3
X4
X5 1
2 2
22
-4 11 1
2 1
16
-4 9
1 1
1 12
-2 6
1)
X1
X2
X3 1
2 2
1 2
1 1
1 1
-1 0
2 1
0 1
-1 3
1
-1 0
2
29 Продолжение таблицы 1 1
2 3
4 5
6 2)
X1
X2
X4 1
2 22 1
2 16 1
1 12
-1.33333 0.333333 2
0.3333
-0.66667 1.666667
-1 1.6667 0.166667
-0.16667 0
0.3333 3)
X1
X2
X5 1
2
-4 1
2
-4 1
1
-2 ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО определитель 4)
X1
X3
X4 1
2 22 1
1 16 1
1 12
-1
-0.5 2.5
-0.5 1
-2.5 1.5
-2.5 0
0.25
-0.25 0.75 5)
X1
X4
X5 1
22
-4 1
16
-4 1
12
-2
-1.33333 0.333333 2
0.333333 0.166667
-0.16667 0
0.333333 0.333333
-0.83333 0.5
-0.8333 6)
X2
X3
X4 2
2 22 2
1 16 1
1 12 2
1
-5 1
4
-1
-6
-1
-0.5 0
1 0.5
30 Продолжение таблицы 1 1 2 3 4 5 6 7) X2 X3 X5 2 2 -4 2 1 -4 1 1 -2 ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО определитель 8) X3 X4 X5 2 22 -4 1 16 -4 1 12 -2 4 -1 -6 -1 -0.5 0 1 0.5 -1 -0.5 2.5 -0.5 9) X2 X4 X5 2 22 -4 2 16 -4 1 12 -2 ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО ЧИСЛО определитель 10) X1 X3 X5 1 2 -4 1 1 -4 1 1 -2 -1 0 2 1 1 -1 0 2 0 -0.5 0.5 -1.5 |
Скачать 1.22 Mb.