Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
Замечание.На практике в учебных задачах вместо формул (1.5) рассмат- ривают формулы , ( ). ij ij kl kj il i i kl k il a a a a a b b a b a i k ′ ′ = − = − ≠ Числа в правых частях последних равенств находятся в вершинах некоторого прямоугольника (рис. 1.1), причем попарно перемножаются числа, расположенные в противоположных вершинах этого прямоугольника: заменяемый элемент a ij умножается на разрешающий a kl (соответственно, элемент b i умножается на раз- решающий a kl ), и затем вычитается произведение элементов второй диагонали прямоугольников. В таком случае сохраняется «целочисленность» всех коэффи- циентов. Если при решении системы линейных уравнений использовать формулы (1.5), то придется иметь дело с дробными числами. Шаг 2. Описанную операцию повторяют, выби- рая разрешающий элемент в другой строке. Теорема 1.4 (Штейница). Максимальное число переходов не зависит от выбора ведущих элементов и равно рангу матрицы A (r(A) = r). Метод исключения неизвестных заканчивается при получении матрицы вида ( ) A В 1, 1 1 1 , 1 1 1 ... 0 0 ... 1 | , 0 ... 0 0 ... 0 0 ... 0 0 ... 0 r n r r rn r r r r m q q d q q d d d + + + = где r(A) = r. a ij a il a kj a kl b i a il b k a kl Рис. 1.1. «Правило прямоугольника» 18 Если хотя бы одно из чисел d r+1 , …, d m ≠ 0, то система линейных уравнений несовместна (получаем противоречивое уравнение 0 · x 1 + 0 · x 2 + … + 0 · x n = d (d ≠ 0)). Если же все d r+1 = … = d m = 0, то система линейных уравнений совместна, причем она преобразуется в эквивалентную ей систему вида 1 1, 1 1 1 1 , 1 1 , r r n n r r r r rn n r x q x q x d x q x q x d + + + + + + + = + + + = (1.6) Система (1.6) является разрешенной относительно базисных неизвестных x 1 , …, x r (на практике номер уравнения и номер базисных переменных могут не совпадать). Переменные x r+1 , …, x n называются свободными. Полагая 1 1 1 , , , , , , r n n r n r x C x C C C + − − = = ∈ R (1.7) получим значения базисных переменных, т. е. найдем общее решение системы линейных уравнений (1.6) и, следовательно, системы (1.2). В частности, если свободные неизвестные равны нулю (C 1 = … = C n–r = 0), то получаем так называемое базисное решение системы линейных уравнений: 1 2 , , , , 0, ,0 . r n r X d d d − = При этом базисное решение называется невырожден- ным, если число его ненулевых координат равно числу базисных неизвестных в выбранном наборе. Если ненулевых координат в базисном решении меньше числа разрешенных, то такое базисное решение называется вырожденным. Частным решением системы уравнений называется решение, получающееся из общего при конкретных значениях свободных неизвестных (1.7). Сформулируем у с л о в и я с о в м е с т н о с т и системы линейных алге- браических уравнений. Теорема 1.5 (Кронекера * — Капелли ** ). Система линейных уравнений (1.2) совместна тогда и только тогда, когда ранг основной матрицы системы равен рангу расширенной матрицы: r(A) r(A |B). = Следствие 1. Если система уравнений (1.6) совместна и ранг матрицы сис- темы равен числу переменных (r = n), то система имеет единственное решение. * Леопольд Кронекер (1823–1891) — немецкий математик. Иностранный член-корреспон- дент Петербургской академии наук (1872), член Берлинской АН (1861), профессор университета в Берлине. Основные труды по алгебре и теории чисел. ** Альфредо Капелли (1855–1910) — итальянский математик, член Национальной академии деи Линчеи. Известен прежде всего как человек, который открыл тождество Капелли. 19 Следствие 2. Если система (1.6) совместна и ранг матрицы системы меньше числа переменных (r < n), то система имеет бесконечное множество решений. При этом число свободных неизвестных равно n − r. Так как 1 2 , , , , 0, , 0 r n r X d d d − = — решение системы уравнений, то ис- пользуя векторную форму записи системы линейных уравнений (1.4), получаем: 1 1 B, r r A d A d + + = (1.8) где d j — компонента базисного решения; A j — соответствующий столбецма- трицы системы; B — вектор-столбец свободных членов. То есть вектор-столбец свободных членов является линейной комбинацией векторов базиса {A 1 , …, A r } с коэффициентами d 1 , …, d r . В этом заключается векторный смысл базисного решения. Пример 1.1. Решить систему линейных уравнений 1 2 3 1 2 3 1 2 3 4 7 8 23, 2 4 5 13, 3 11 2 15 x x x x x x x x x − + = − − + = − − + + = методом Гаусса — Жордана. Решение. Запишем расширенную матрицу данной системы: 4 7 8 23 2 4 5 13 . 3 11 2 15 − − − − − Шаг 1. Обратимся к первому столбцу расширенной матрицы. Наша цель: выбрать какой-либо ненулевой разрешающий элемент. В первом столбце три ненулевых элемента: 4, 2, −3. Мы можем выбрать любой из них. Предпочти- тельно выбрать тот элемент, модуль которого ближе всего к единице. В нашем случае таким элементом является 2. Наша цель: обнулить все элементы в первом столбце, кроме разрешающего элемента. То есть обнулению подлежат числа 4 и (−3). 4 7 8 23 2 4 5 13 . 3 11 2 15 − − − − − 20 Элементы разрешающей второй строки перепишем. Заполним свободные места (кроме элемента в рамочке) в первомразрешающемстолбце нулями; остальные элементы матрицы пересчитаем по «правилу прямоугольника»: ( ) 12 13 4 7 4 8 7 2 4 4 2, 8 2 4 5 4; 2 4 2 5 a a − ′ ′ = = − ⋅ − ⋅ − = = = ⋅ − ⋅ = − − ( ) ( ) ( ) ( ) 1 32 4 23 2 4 23 2 4 13 6, 11 2 4 3 10; 2 13 3 11 b a − − ′ ′ = = − ⋅ − ⋅ − = = = ⋅ − − ⋅ − = − − ( ) ( ) ( ) 33 3 2 5 2 13 2 2 5 3 19, 15 2 3 13 9. 3 2 3 15 a b − ′ ′ = = ⋅ − ⋅ − = = = ⋅ − − ⋅ − = − − − В результате первого шага получим матрицу 0 2 4 6 2 4 5 13 . 0 10 19 9 − − − − Замечание. В основе метода прямоугольника лежат два элементарных пре- образования. Так, например, элементы 32 33 3 , , , a a b ′ ′ ′ вычисленные по «правилу прямоугольника», можно было бы получить с помощью двух элементарных преобразований: 4 7 8 23 I ( 2)II 0 1 2 3 2 4 5 13 II 3 2 4 5 13 , 3 11 2 15 III 2 3 II 0 10 19 9 − − + − − − − ⋅ → − − − ⋅ + ⋅ − то есть сначала третью строку умножили на 2, а потом к полученной строке прибавили вторую строку, умноженную на 3. Элементы первой строки получены прибавлением к ней второй строки, умноженной на (−2). Шаг 2. Разделим элементы первой строки на 2: 0 1 2 3 2 4 5 13 . 0 10 19 9 − − − − В качестве разрешающего элемента выберем 12 1 0. a′ = ≠ С помощью этого элемента обнулим два остальных элемента второго столбца. Это можно сделать по «правилу прямоугольника». Так как разрешающий элемент равен 1, то лег- че получить нули с помощью элементарных преобразований над строками: 21 II + 4 · I и III + (−10) · I.Запись II + 4 · I означает, что к элементам второй строки прибавляются соответствующие элементы первой строки, умноженные на 4. Запись III + (−10) · I говорит о том, что к элементам третьей строки прибавля- ются соответствующие элементы первой строки, умноженные на (−10). ( ) 0 1 2 3 0 1 2 3 2 4 5 13 II 4 I 2 0 3 1 . 0 10 19 9 III 10 I 0 0 39 39 − − − − + ⋅ → − − − + − ⋅ − Шаг 3. Перейдем к обнулению элементов третьего столбца. Разделим эле- менты третьей строки на 39, разрешающим элементом может быть только число 1: 0 1 2 3 I 2 III 0 1 0 1 2 0 3 1 II 3 III 2 0 0 4 . 0 0 1 1 0 0 1 1 − + ⋅ − − + ⋅ → − − − Разделим элементы второй строки на 2 и поменяем местами первую и вто- рую строки: 1 0 0 2 0 1 0 1 . 0 0 1 1 − − Итак, x 1 = −2, x 2 = 1, x 3 = −1. Векторный смысл базисного решения: 4 7 8 23 2 2 1 4 1 5 13 3 11 2 15 − − − ⋅ + ⋅ − − ⋅ = − − Пример 1.2. Решить систему линейных уравнений 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 2 3 2, 6 3 2 4 5 3, 6 3 4 8 13 9, 4 2 2 1 x x x x x x x x x x x x x x x x x x x x − + + + = − + + + = − + + + = − + + + = методом Гаусса — Жордана. Если система является неопределенной, указать любые два базисных решения. 22 Решение. Приведенные выше вычисления (пример 1.1)удобно располагать в так называемых таблицах Гаусса — Жордана. В первой строке табл. 1.1 указаны: x j — неизвестные; B — вектор-столбец свободных членов. Для предотвращения случайных ошибок в расчетах полезно ввести специальный контрольный стол- бец A Его элементы представляют собой суммы соответствующих элементов по строкам таблицы: 1 n i ij i j a a b = = + ∑ С другой стороны, строки преобразуются по тем же формулам, что и остальные элементы таблицы. Поэтому, выполняя их расчет указанными двумя способами и сравнивая результаты, можно вы- явить вкравшуюся ошибку. При проведении преобразований каждого шага разрешающие элементы выделяются. В первом столбце будут указываться базисные неизвестные (начиная с табл. 1.2). Таблица 1.1 Базис x 1 x 2 x 3 ↓ x 4 x 5 B A Примечания 2 –1 1 2 3 2 9 6 –3 2 4 5 3 17 II + (–2) · I 6 –3 4 8 13 9 37 III + (–4) · I 4 –2 1 1 2 1 7 IV + (–1) · I Выбираем ведущий элемент a 13 = 1 ≠ 0 и получим нули в третьем столбце. В столбце «Примечания» описаны выполняемые действия. В результате шага 1 получим табл. 1.2. Таблица 1.2 Базис x 1 x 2 x 3 x 4 x 5 B A x 3 2 –1 1 2 3 2 9 2 –1 0 0 –1 –1 –1 –2 1 0 0 1 1 1 2 –1 0 –1 –1 –1 –2 Вторая и третья строки пропорциональны, одну из них, например вторую, удалим, получим табл. 1.3. Таблица 1.3 Базис x 1 x 2 ↓ x 3 x 4 x 5 B A Примечания x 3 2 –1 1 2 3 2 9 I + II –2 1 0 0 1 1 1 2 –1 0 –1 –1 –1 –2 III + II 23 В качестве разрешающего элемента выберем элемент второй строки a 22 = 1 ≠ 0. Обнулим элементы столбца x 2 , получим табл. 1.4. Таблица 1.4 Базис x 1 x 2 x 3 x 4 ↓ x 5 B A Примечания x 3 0 0 1 2 4 3 10 I + 2 · III x 2 –2 1 0 0 1 1 1 0 0 0 –1 0 0 –1 Итак, разрешающий элемент выбран в первой и во второй строке, осталось выбрать в третьей строке. Единственный элемент этой строки a 14 = −1. Обнуле- нию подлежит лишь один элемент столбца x 4 (табл. 1.5). Таблица 1.5 Базис x 1 x 2 x 3 x 4 x 5 B A x 3 0 0 1 0 4 3 8 x 2 –2 1 0 0 1 1 1 x 4 0 0 0 –1 0 0 –1 Умножим третью строку на (−1) и поменяем местами первую и вторую строки, получим табл. 1.6. Таблица 1.6 Базис x 1 x 2 x 3 x 4 x 5 B A x 2 –2 1 0 0 1 1 1 x 3 0 0 1 0 4 3 8 x 4 0 0 0 1 0 0 1 В каждой строке таблицы выбран разрешающий элемент. Базисные не- известные x 2 , x 3 , x 4 . Количество неизвестных n = 5, поэтому нужно выбрать n − r = 2 свободных. Так как r < n, то согласно следствию 2 из теоремы Кронеке- ра — Капелли данная система является неопределенной (т. е. имеет бесконечное множество решений). В результате исходная система линейных уравнений приводится к эквивалентной системе: 1 2 5 3 5 4 2 1, 4 3, 0 x x x x x x − + + = + = = 24 Выбрав переменные x 2 , x 3 , x 4 в качестве базисных, а x 1 , x 5 — в качестве сво- бодных, найдем общее решение системы линейных уравнений: 5 R, R 2 1 5 3 5 4 1 1 2 , 3 4 , 0, x x x x x x x x = + − = − = ∈ ∈ В частности, при x 1 = x 5 = 0 получим базисное решение: X 1 = (0, 1, 3, 0, 0). Заметим, что базисные неизвестные находятся в левом столбце, а их значе- ния, соответственно — в столбце свободных членов табл. 1.5, поэтому можно сразу по таблице записать базисное решение системы. Отметим также, что число ненулевых координат в базисном решении примера меньше числа разрешенных (базисных), поэтому полученное базисное решение является вырожденным. Замечание. Если разрешенная система уравнений, равносильная исходной системе, содержит n неизвестных и r уравнений, то число общих и соответст- вующих базисных решений исходной системы не превосходит числа сочетаний r n C Количество сочетаний можно вычислить по формуле ! !( )! r n n C r n r = − Для того чтобы найти второе общее и соответствующее ему базисное реше- ние, в полученной разрешенной системе в каком-либо уравнении необходимо выбрать какой-либо другой разрешающий элемент. Таблица 1.7 Базис x 1 x 2 x 3 x 4 x 5 ↓ B A x 2 –2 1 0 0 1 1 1 ← x 3 0 0 1 0 4 3 8 x 4 0 0 0 1 0 0 1 В нашем примере (табл. 1.7) можно выбрать в качестве разрешающего элемента одно из чисел: (−2), 1 или 4. Выберем, например, число 4 и обнулим элементы столбца x 5 . Таким образом, из базиса будет выведен третий вектор- столбец и введен пятый. Обнулению подлежит число 1. Элементы разрешающей второй строки перепишем. На месте элемента 1 запишем 0, остальные элементы матрицы пересчитаем по «правилу прямоугольника»: 11 12 2 1 1 1 2 4 0 1 8, 1 4 0 1 4; 0 4 0 4 a a − ′ ′ = = − ⋅ − ⋅ = − = = ⋅ − ⋅ = |