Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
4 –1 0 0 1 –4 I : 4 x 5 0 0 1 0 4 3 8 II : 4 x 4 0 0 0 1 0 0 1 Элементы первой и второй строк разделим на 4. В каждой строке матрицы выбран ведущий элемент. Базисными неизвестными (табл. 1.9) являются x 2 , x 4 , x 5 Свободные неизвестные — x 1 , x 3 Таблица 1.9 Базис x 1 x 2 x 3 x 4 x 5 B A x 2 –2 1 –1/4 0 0 1/4 –1 x 5 0 0 1/4 0 1 3/4 2 x 4 0 0 0 1 0 0 1 Второе базисное решение исходной системы уравнений X 2 = (0, 1/4, 0, 0, 3/4). 1.6. Обращение матриц методом Гаусса — Жордана Пусть матрица A = (a ij ), i, 1, j n = невырожденная, т. е. ее определитель не ра- вен нулю. Матрица A обратима тогда и только тогда, когда для каждого j соот- ветствующая система уравнений AX = E j ( 1, ) j n = имеет единственное решение, где E j — j-й столбец единичной матрицы E, X = (x 1 , x 2 , …, x n ) T . Если матрица A обратима, то j-й столбец матрицы A –1 совпадает с единственным решением системы уравнений AX = E j ( 1, ) j n = (X = A –1 E j ). Для определения A –1 необходимо решить n систем линейных уравнений с n неизвестными. Так как эти системы отличаются только набором свободных членов, то их можно решать параллельно в одной таблице. То есть для матри- цы A построим матрицу (A | E). Используя элементарные преобразования над строками матрицы (A | E), приведем ее к виду (E | B), что всегда возможно, если A обратима. Тогда B = A –1 . Таким образом, мы осуществляем переход: ( ) 1 (A |E) E| A . − → 26 Решение матричных уравнений методом Гаусса — Жордана Рассмотрим матричное уравнение AX = B. Пусть матрица A = (a ij ), i, 1, j n = невырожденная. Для решения матричного уравнения запишем матрицу (A | B), приписывая к A справа матрицу B. Далее с помощью преобразований Гаусса — Жордана матрицу (A | B) приводим к виду (E | X), где X = A –1 B: ( ) 1 (A |B) E| A B . − → 1.7. Нахождение базиса системы векторов A 1 , A 2 , …, A m (A j ∈ R n ) Начнем изложение этого параграфа с примера. Пример 1.3. Выяснить, являются ли следующие системы векторов линейно зависимыми или линейно независимыми: 1) a 1 = (5, 2, 3, 1), a 2 = (0, 4, 7, −2), a 3 = (0, 0, 3, 2), a 4 = (0, 0, 0, 9); 2) a 1 = (1, −1, 2), a 2 = (2, 2, −2), a 3 = (4, 0, 2). 1. Составим векторное равенство α 1 A 1 + α 2 A 2 + α 3 A 3 + α 4 A 4 = θ. Запишем его в векторно-матричном виде, представив векторы как векто- ры-столбцы: 1 2 3 4 5 0 0 0 0 2 4 0 0 0 3 7 3 0 0 1 2 2 9 0 α + α + α + α = − (1.9) Равенство (1.9) является однородной системой уравнений с четырьмя неизвестными: 1 1 2 1 2 3 1 2 3 4 5 0, 2 4 0, 3 7 3 0, 2 2 9 0. α = α + α = α + α + α = α − α + α + α = Нетрудно видеть, что все α 1 = … = α 4 = 0, а это означает, что система векто- ров линейно независима. 2. Составим векторное равенство α 1 A 1 + α 2 A 2 + α 3 A 3 = θ. 27 Запишем его в векторно-матричном виде: 1 2 3 1 2 4 0 1 2 0 0 . 2 2 2 0 α − + α + α = − (1.10) Равенство (1.9) является однородной системой уравнений с тремя пере- менными: 1 2 3 1 2 1 2 3 2 4 0, 2 0, 2 2 2 0. α + α + α = −α + α = α − α + α = Составим матрицу из коэффициентов и определим ее ранг: ( ) 1 2 4 1 2 4 1 2 4 1 2 0 II I 0 4 4 : 4 0 1 1 2 2 2 III 2 I 0 6 6 : 6 0 1 1 − + → → → − − ⋅ − − − ( ) 1 2 4 1 0 2 I 2 II 0 1 1 0 1 1 + − ⋅ → → Очевидно, ранг матрицы равен 2. Система (1.10) имеет, кроме нулевого решения α 1 = α 2 = α 3 = 0, бесконечное множество решений. Базисными пере- менными являются α 1 , α 2 . Свободная переменная α 3 . Общее решение системы: R 1 3 2 3 3 2 , , α = − α α = −α α ∈ Полагая α 3 = 1, найдем решение однородной системы линейных уравнений: 1 2 3 2, 1, 1. α = − α = − α = То есть значения коэффициентов α 1 = −2, α 2 = −1, α 3 = 1 реализуют линейную зависимость векторов a 1 , a 2 , a 3 : 1 2 3 2 − − + = a a a q 28 Таким образом, вопросо линейной зависимости системы n-мерных векто- ров A 1 , A 2 , …, A m (A j ∈ R n ) сводится к исследованию существования ненулевого решения однородной системы линейных уравнений: 1 1 2 2 m m A A A α + α + …+ α = q Если система имеет только нулевое решение, то система векторов A 1 , A 2 , …, A m линейно независима. В частности, при m = n система A 1 , A 2 , …, A m линейно не- зависима тогда и только тогда, когда определитель системы | A | ≠ 0. Для отыскания базиса системы векторов A 1 , A 2 , …, A m находят общее ре- шение однородной системы линейных уравнений: 1 1 2 2 m m A A A α + α + …+ α = q (1.11) С помощью преобразований Гаусса — Жордана матрица из коэффициентов при неизвестных α j приводится к виду: 1 1 1, 1 1, , 1 , 1 0 0 1 r r m r m r r r m A A A A q q q q + + + ′ ′ ′ ′ (1.12) Векторы A 1 , …, A r преобразовались в единичные 1 , , , r A A ′ ′ поэтому они линейно независимы и составляют базис системы векторов A 1 , A 2 , …, A m На практике номер базисной переменной и номер уравнения не обязательно совпадают. Векторы — коэффициенты уравнения (1.11) при неизвестных — ба- зисных переменных образуют базис системы векторов A 1 , A 2 , …, A m Так как разложение каждого из векторов A j по векторам найденного базиса A 1 , …, A r совпадает с разложением вектора j A′ по полученному единичному базису 1 , , , r A A ′ ′ то из (1.12) вытекает: 1 1 1 1 1 1 1 , r ,r r,r r m ,m r,m r A q A q A A q A q A + + + = + + = + + или кратко: ( ) 1 1, r j r i,r j i i A q A j m r + + = = = − ∑ То есть элементы каждого из столбцов 1 , , r m A A + ′ ′ матрицы (1.12) явля- ются, соответственно, коэффициентами разложения вектора A j по векторам найденного базиса A 1 , …, A r 29 Пример 1.4. Найти базис и ранг системы векторов: A 1 = (9, 8, −3, 9), A 2 = (4, 1, −2, 3), A 3 = (1, 1, −1, −2), A 4 = (3, 4, −1, 2), A 5 = (1, 2, 1, 6). Решение. Заметим, что так как пространство четырехмерное, а векторов пять, то система линейно зависима (см. следствие из теоремы Штейница, с. 8). Составим векторное равенство 1 1 2 2 3 3 4 4 5 5 A A A A A α + α + α + α + α = q Запишем его в матричном виде, представив векторы как векторы-столбцы: 1 2 3 4 5 9 4 1 3 1 0 8 1 1 4 2 0 3 2 1 1 1 0 9 3 2 2 6 0 α + α + α + α + α = − − − − − Составим матрицу из коэффициентов и воспользуемся элементарными пре- образованиями со строками матрицы по методу Гаусса — Жордана (табл. 1.10). Таблица 1.10 Базис A 1 A 2 A 3 ↓ A 4 A 5 B 9 4 1 3 1 0 8 1 1 4 2 0 –3 –2 –1 –1 1 0 9 3 –2 2 6 0 Здесь в верхней строке указаны векторы-столбцы коэффициентов при неиз- вестных, в левом столбце — векторы, входящие в базис системы векторов A 1 , A 2 , A 3 , A 4 , A 5 . В следующих таблицах (табл. 1.11–1.16) вектор B не указываем, так как он состоит из нулей. В качестве разрешающего выбираем элемент в первой строке и в столбце A 3 табл. 1.10. С помощью элементарных преобразований получаем табл. 1.11. Таблица 1.11 Базис A 1 A 2 A 3 A 4 ↓ A 5 A 3 9 4 1 3 1 –1 –3 0 1 1 6 2 0 2 2 27 11 0 8 8 30 Далее выбираем разрешающий элемент в столбце A 4 и во второй строке, получаем табл. 1.12. Таблица 1.12 Базис A 1 A 2 A 3 A 4 A 5 A 3 12 13 1 0 –2 A 4 –1 –3 0 1 1 8 8 0 0 0 35 35 0 0 0 Третья и четвертая строки пропорциональны. Одну из них удаляем. Третью строку разделим на 8, получим табл. 1.13. Таблица 1.13 Базис A 1 A 2 ↓ A 3 A 4 A 5 A 3 12 13 1 0 –2 A 4 –1 –3 0 1 1 1 1 0 0 0 В качестве разрешающего элемента выбираем число 1 (отмечено рамкой (табл. 1.13)). Таблица 1.14 Базис A 1 A 2 A 3 A 4 A 5 A 3 –1 0 1 0 –2 A 4 2 0 0 1 1 A 2 1 1 0 0 0 Наконец, поменяем в табл. 1.14 местами строки (обратим внимание, что это мы можем сделать 3! = 6 раз), получим табл. 1.15. Таблица 1.15 Базис A 1 A 2 A 3 A 4 A 5 A 2 1 1 0 0 0 A 3 –1 0 1 0 –2 A 4 2 0 0 1 1 Итак, α 2 , α 3 , α 4 — базисные переменные, векторы A 2 , A 3 , A 4 образуют базис системы A 1 , A 2 , A 3 , A 4 , A 5 31 Запишем разложения оставшихся векторов в базисе {A 2 , A 3 , A 4 }: 1 2 3 4 2 3 4 5 2 3 4 3 4 1 1 2 2 ; 0 2 1 2 A A A A A A A A A A A A A = ⋅ − ⋅ + ⋅ = − + = ⋅ − ⋅ + ⋅ = − + В нашем примере базис образуют три вектора: A 2 , A 3 , A 4 . Но если выбрать другие базисные неизвестные, то, соответственно, изменится и базис. Количе- ство способов выбора базиса не превышает величины 3 5 5! 10. 2!3! C = = Кроме того, для каждого набора трех векторов можно выбрать 3! упорядоченных совокупностей. Общее количество способов выбора трех линейно независимых векторов не превзойдет 10 × 6 = 60. Для того чтобы найти другой базис, необходимо выбрать какой-либо другой разрешающий элемент. В нашем примере в табл. 1.15 можно выбрать в качестве разрешающего элемента, например, число 1 в первой строке и в столбце A 1 , получим табл. 1.16. Таблица 1.16 Базис A 1 A 2 A 3 A 4 A 5 A 1 1 1 0 0 0 A 3 0 1 1 0 –2 A 4 0 –2 0 1 1 В базис введен вектор A 1 и выведен A 2 . Базисными переменными являются α 1 , α 3 , α 4 . Векторы A 1 , A 3 , A 4 образуют базис системы A 1 , A 2 , A 3 , A 4 , A 5 Запишем разложения оставшихся векторов (табл. 1.16) в базисе {A 1 , A 3 , A 4 }: 2 1 3 4 5 3 4 2 , 2 A A A A A A A = + − = − + Аналогичным образом можно перебрать все наборы базисных переменных и соответствующих наборов линейно независимых систем. 1.8. Нахождение неотрицательного базисного решения Применение математических методов в экономике приводит к необхо- димости отыскания неотрицательных базисных решений системы линейных уравнений. Напомним вид базисного решения: 1 , , , 0, , 0 . r n r X d d − = 32 Следовательно, чтобы базисное решение было неотрицательным, необхо- димо так изменить метод Гаусса — Жордана, чтобы все d j ≥ 0 ( ). 1, j r = Пусть в исходной системе AX = B все свободные члены b i ≥ 0 (иначе умно- жим соответствующие отрицательным свободным членам уравнения на (−1)). За разрешающий элемент выберем a kl > 0. Тогда после первой итерации i kl k il i kl b a b a b a − ′ = Потребуем, чтобы для любого i было справедливо 0. i b′ ≥ Так как a kl > 0, то необходимо требовать, чтобы b i a kll − l b k a il ≥ 0, то есть i kl k il b a b a ≥ (1.13) Если a il ≤ 0, то неравенство (1.13) выполняется без других дополнительных условий. Если a il > 0, то необходимо, чтобы для каждого i выполнялось нера- венство i k il kl b b a a ≥ То есть разрешающие элементы для преобразований Гаусса — Жордана необходимо выбирать из условия : 0 min il i k i a il kl b b a a ∀ > = После очередного шага (преобразование однократного замещения) мы вновь получим матрицу с неотрицательными свободными членами. Если разрешаю- щий элемент выбирать так для каждого шага, то после последнего шага все d j ≥ 0 ( 1, ). j r = Следовательно, базисное решение будет неотрицательным либо будет установлено, что неотрицательного базисного решения не существует. Приведем а л г о р и т м нахождения неотрицательного базисного решения: 1) выбираем любой l-й столбец, в котором есть хотя бы один положи- тельный элемент a il , если такого столбца нет, то неотрицательного базисного решения не существует; 2) для каждого a il > 0 выбранного столбца находим отношение i i il b a θ = и вы- бираем среди них наименьшее: 0 min , l i i θ = θ выбранная k-я строка называется разрешающей, элемент на пересечении раз- решающей строки и l-го столбца a kl также называется разрешающим; 3) пересчитываем таблицу (A | B) методом Гаусса — Жордана с выбранным разрешающим элементом a kl и переходим к первому пункту. |