Операции над матрицами

Описание метода

 

Пусть исходная система выглядит следующим образом

 

Матрица A называется основной матрицей системы, b — столбцом свободных членов.

Тогда согласно свойству элементарных преобразований над строками основную матрицу этой системы можно привести к ступенчатому виду(эти же преобразования нужно применять к столбцу свободных членов):

 

При этом будем  считать, что базисный минор (ненулевой  минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных [3].

Тогда переменные  называются главными переменными. Все  остальные называются свободными.

Если хотя бы одно число , где i > r, то рассматриваемая  система несовместна.

Пусть  для любых i > r.

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений  системы на свой коэффициент при  самом левом  (, где  — номер  строки):

,

где

Если свободным  переменным системы (2) придавать все  возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.

 

Следствия:

1: Если в  совместной системе все переменные  главные, то такая система является  определённой.

2: Если количество  переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной.

Условие совместности

Упомянутое  выше условие   для всех   может быть сформулировано в качестве необходимого и достаточного условия совместности:

Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

Теорема Кронекера-Капелли. 
Система совместна тогда и только тогда, когда ранг её основной матрицы равен рангу её расширенной матрицы.

Следствия:

• Количество главных переменных равно рангу системы и не зависит от её решения.
• Если ранг совместной системы равен числу переменных данной системы, то она определена.

Алгоритм

Описание

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

• На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.
• На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.

Метод Гаусса требует  порядка O(n³) действий.

Этот метод  опирается на:

Теорема (о приведении матриц к ступенчатому виду). 
Любую матрицу путём элементарных преобразований только над строками можно привести к ступенчатому виду.

Простейший случай

В простейшем случае алгоритм выглядит так: 

• Прямой ход:

• Обратный ход. Из последнего ненулевого уравнения выражаем базисную переменную через небазисные и подставляем в предыдущие уравнения. Повторяя эту процедуру для всех базисных переменных, получаем фундаментальное решение.

Пример

Покажем, как  методом Гаусса можно решить следующую  систему:

Обнулим коэффициенты при   во второй и третьей строчках. Для этого вычтем из них первую строчку, умноженную на   и  , соответственно:

Теперь обнулим  коэффициент при   в третьей строке, вычтя из неё вторую строку, умноженную на  :

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

На втором этапе  разрешим полученные уравнения в  обратном порядке. Имеем:

 из третьего;

 из второго, подставив полученное 

 из первого, подставив  полученные   и  .

Таким образом  исходная система решена.

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

Применение и модификации

Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:

• нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная:  , после чего  приводится к виду единичной матрицы методом Гаусса—Жордана; в результате на месте изначальной единичной матрицы справа оказываетсяобратная к исходной матрица:  );
• определения ранга матрицы (согласно следствию из теоремы Кронекера—Капелли ранг матрицы равен числу её главных переменных);
• численного решения СЛАУ в вычислительной технике (ввиду погрешности вычислений используется Метод Гаусса с выделением главного элемента, суть которого заключена в том, чтобы на каждом шаге в качестве главной переменной выбирать ту, при которой среди оставшихся после вычёркивания очередных строк и столбцов стоит максимальный по модулю коэффициент).

Достоинства метода

• Менее трудоёмкий по сравнению с другими методами.
• Позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение.
• Позволяет найти максимальное число линейно независимых уравнений — ранг матрицы системы^[4].

 

Метод Крамера

Метод Крамера (правило Крамера) — способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно). Назван по имени Габриэля Крамера (1704–1752), придумавшего метод.

Описание метода

Для системы n линейных уравнений с n неизвестными (над произвольным полем)

с определителем  матрицы системы Δ, отличным от нуля, решение записывается в виде

(i-ый столбец  матрицы системы заменяется столбцом свободных членов). 
В другой форме правило Крамера формулируется так: для любых коэффициентов c₁, c₂, …, c_n справедливо равенство:

В этой форме  формула Крамера справедлива  без предположения, что Δ отлично от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборыb₁,b₂,...,b_n и x₁,x₂,...,x_n, либо набор c₁,c₂,...,c_n состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Пример

Система линейных уравнений:

Определители:

 

Решение:

Пример:

Определители:

 

Вычислительная сложность

Метод Крамера  требует вычисления n + 1 определителей размерности  . При использовании метода Гаусса для вычисления определителей, метод имеет временную сложность порядка O(n⁴), что хуже, чем если бы метод Гаусса напрямую использовался для решения системы уравнений. Поэтому метод считался непрактичным. Однако в 2010 году было показано, что метод Крамера может быть реализован со сложностью O(n³), сравнимой со сложностью метода Гаусса.

 

Матричный метод

Ма́тричный  метод решения (метод решения через обратную матрицу) систем линейных алгебраических уравнений с ненулевым определителем состоит в следующем.

Пусть дана система  линейных уравнений с n неизвестными (над произвольным полем):

Тогда её можно  переписать в матричной форме:

AX = B, где A — основная матрица системы, B и X — столбцы свободных членов и решений системы соответственно:

Умножим это  матричное уравнение слева на A ^{− 1} — матрицу, обратную к матрице A: 

Так как A ^{− 1}A = E, получаем X = A ^{− 1}B. Правая часть этого уравнения даст столбец решений исходной системы. Условием применимости данного метода (как и вообще существования решения неоднородной системы линейных уравнений с числом уравнений, равным числу неизвестных) является невырожденность матрицы A. Необходимым и достаточным условием этого является неравенство нулю определителя матрицы A:

.

Для однородной системы линейных уравнений, то есть когда вектор B = 0, действительно обратное правило: система AX = 0 имеет нетривиальное (то есть ненулевое) решение только если det A = 0. Такая связь между решениями однородных и неоднородных систем линейных уравнений носит название альтернативы Фредгольма.

Пример решения неоднородной СЛАУ

Сначала убедимся в том, что определитель матрицы из коэффициентов при неизвестных СЛАУ не равен нулю.

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

 

 

Далее найдём союзную матрицу, транспонируем её и подставим в формулу для нахождения обратной матрицы.

 

 

Подставляя переменные в формулу, получаем:

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

Итак, x=2; y=1; z=4.

 

 

 

Глава I. Векторы  на плоскости и в пространстве

§ 2.  Векторы

Любой отрезок прямой имеет две концевые   точки. Если одна из них принята за начало отрезка, а другая — за конец, то такой отрезок называется направленным. Направленные   отрезки обычно обозначаются двумя буквами со стрелкой, например,AB^>, BA^>, OA^>, OB^> и  т. д., где первая буква   обозначает начало  отрезка,  а  вторая  буква —  конец отрезка.

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

Например, на рис. 4, где ABCD — параллелограмм, направленные отрезки AB^> иDC^> равны, так как |АВ| = |DC|, (AB) || (DC) и отрезки AB^> и DC^> направлены в одну сторону.

Направленные отрезки AB^> и AD^> не являются равными, так как они не параллельны. Направленные отрезки AB^> и CD^> тоже не являются равными, так как они имеют противоположные направления, хотя они параллельны и имеют равные длины.

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

Согласно определению  все равные между собой направленные отрезки изображают один и тот же вектор. Например, если вектор, изображенный на рис. 4 направленным отрезком AB^>, обозначить а, то а = AB^> = CD^>.

Длина вектора а = AB^>, обозначаемая | а | или | AB^>| — это длина отрезка АВ.

Направление вектора  а = AB^> — это направление, определяемое лучом АВ.

Вектор, длина которого равна нулю, называется нулевым вектором и обозначается 0. Очевидно, что у нулевого   вектора   начало   совпадает   с   концом: 0 = AА^> = BВ^>.

Таким образом, каждый вектор а =/= 0 вполне определяется длиной и направлением. Нулевой вектор направления не имеет.

§ 3. Сумма векторов

Пусть даны два вектора а = OA^> и b = OB^> (рис. 5).

От точки А отложим  отрезок АС такой, что AС^> = b. Тогда,  вектор с =OС^> называется суммой векторов   а и b   и  обозначается а + b.

Таким образом, OA^> + AС^> = OС^>. Это равенство называют правилом треугольникасложения двух векторов.

Oчевидно, что это  правило справедливо и в том  случае, когда точки О, А и В лежат на одной прямой (рис. 6, 7). В частности, а + 0 = а.

 

 

Сложение    векторов    обладает   следующими    свойствами:

1.  Свойство   коммутативности   (перестановочности): для любых векторов а и b

а + b = b + а.                              (1)

2.  Свойство ассоциативности  (сочетательности): для любых векторов а, b и с

(а + b) + с = а + (b + с).                    (2) 

 

1. Пусть a = OA^>, b = OB^>. Рассмотрим случай, когда точки О, А и В не лежат на одной прямой. На отрезках    ОА    и    ОВ   построим   параллелограмм ОАСВ (рис. 8).

Тогда   |ОА| = |ВС|,   (ОА) || (ВС)  и   |ОВ|  = |АС|,   (ОВ) || (АС),  как  противоположные стороны параллелограмма.    Следовательно,

а = OA^>= BC^>,    b  = OB^> = AC^>,

и поэтому

а + b = OA^>+ AC^> = OC^>,     b + а = OB^> + BC^> = OC^> ,

что и доказывает равенство (1).

Для случая, когда точки  О, А, В лежат на одной прямой, доказательство равенства (1) проведите самостоятельно.

2. От некоторой точки  О отложим вектор OA^> = а, от точки А отложим вектор AB^> =b и, наконец, от точки В отложим вектор BC^> = с (рис. 9, 10).