11.Системы линейных алгебраических уравнений

Общий вид и свойства системы уравнений

Система т линейных уравнений с п неизвестными (переменными) х1

х2, ..., хn имеет вид

{a11x1+a12x2+...+a1nxn=b1

{a21x1+a22x2+...+a2nxn=b2

{….......................................

{am1x1+am2x2+...+amnxn=bm

Здесь аij и bi, — заданные числа (i = 1, 2,..., m; j = 1, 2,..., n), которые называются, соответственно, коэффициентами при неизвестных и свободными членами уравнений (1.35). Первый индекс у коэффициентов

при неизвестных означает номер уравнения, второй индекс соответствует номеру неизвестного xt.

Решением системы уравнений (1.35) называется набор п чисел хх = оц,

х2 = а2,..., хn = аn при подстановке которых в эту систему каждое уравнение данной системы превращается в тождество.

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

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

Элементарные преобразования исходной системы приводят к эквивалентной системе.

• вычеркивание уравнения 0x1+0x20...+0xn= 0 — нулевой строки;

• перестановка уравнений или слагаемых aijXj в уравнениях;

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

• удаление уравнений, являющихся линейными комбинациями других уравнений системы.

Матричная форма системы уравнений

Сведем коэффициенты при неизвестных в системе уравнений (1.35)

в матрицу

A=(a11 a12 … a1n)

(a21 a22 … a2n)

(…....................)

(am1 am2 … amn)

Эта матрица состоит из т строк и п столбцов и называется матрицей системы. Введем в рассмотрение две матрицы-столбца: матрицу неизвестных А' и матрицу свободных членов В (векторы-столбцы)

X=(x1), B=(b1)

(x2) (b2)

(....) (…)

(xn) (bm)

Тогда систему линейных уравнений (1.37) можно записать в матричной форме, поскольку размер матрицы А равен тхп, а размер X — n х 1, и значит, произведение этих матриц имеет смысл:

АХ = В.

(1.38)

Произведение матриц АХ является, как и В, матрицей-столбцом размера m x 1. Все уравнения системы (1.35) вытекают из уравнения (1.38) в силу определения равенства двух матриц (см. 1.2.1).

Введем в рассмотрение еще одну матрицу: дополним матрицу системы А столбцом свободных членов и получим новую матрицу размера

тех (п+ 1):

о.,,

An=(a11 a12 … a1n b1)

(a21 a22 … a2n b2)

(…..........................)

(am1 am2 … amn bm)

Матрица Ав называется расширенной матрицей системы. Эта матрица играет важную роль в вопросе о разрешимости системы уравнений.

12. Критерий совместимости слау (теорема Кронекера-Капелли)

Теорема 1.5 (Кронекера— Капелли: критерий совместности системы).

Система линейных уравнений совместна тогда и только тогда, когда

ранг матрицы системы равен рангу расширенной матрицы системы.

Определение 21. Рангом совместной системы линейных алгебраиче-

ских уравнений называется ранг ее матрицы.

Доказательство (условия совместности системы)

Необходимость

Пусть система совместна. Тогда существуют числа такие, что. Следовательно, столбецявляется линейной комбинацией столбцовматрицы. Из того, что ранг матрицы не изменится, если из системы его строк (столбцов) вычеркнуть или приписать строку (столбец), которая является линейной комбинацией других строк (столбцов) следует, что.

Достаточность

Пусть . Возьмем в матрицекакой-нибудь базисный минор. Так как, то он же и будет базисным минором и матрицы. Тогда, согласно теореме о базисномминоре, последний столбец матрицы будет линейной комбинацией базисных столбцов, то есть столбцов матрицы. Следовательно, столбец свободных членов системы является линейной комбинацией столбцов матрицы.

13. Методы решения систем линейных алгебраических

уравнений

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

В этом разделе мы рассмотрим частный случай системы (1.35), когда число уравнений равно числу неизвестных, т. е. m=n. Система уравнений имеет вид

{a11x1+a12x2+...+a1nxn=b1

{a21x1+a22x2+...+a2nxn=b2

{…........................................

{am1x1+am2x2+...+amnxn=bm

Квадратная матрица А порядка n этой системы получается из матрицы (1.36) при m= n.

В матричной форме система уравнений (1.40) имеет вид (1.38). Пусть матрица системы А является невырожденной, т. е. существует обратная матрица А '. Умножив обе части этого уравнения слева на А ', получаем решение системы (1.40) в матричной форме:

(1.41)

Х = А^В.

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

1

-1

и A достаточно велик, нахождение обратной матрицы может быть довольно трудоемким процессом.

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

Другой метод решения системы уравнений (1.40) основан на теореме

Крамера. Составим определитель матрицы системы А:

Δ=|a11 a12 … a1n|

|a21 a22 … a2n|

|.........................|

|am1 am2 … amn|

который называется также определителем системы.

Теорема 1.6 (правило Крамера). Пусть А — определитель матрицы системы А, а А, — определитель, полученный из определителя А заменой j-vo столбца столбцом свободных членов В. Тогда, если Д * 0, то

система линейных уравнений (1.40) имеет единственное решение, определяемое по формулам

x1=Δj/Δ, j=1, 2, …, n.

(1.43)

Формулы вычисления неизвестных (1.43) носят название формул Крамера.

Метод Гаусса

Рассмотрим систему уравнений общего вида (1.35). Пусть для определенности a11≠0 (если а11 = 0, то можно переставить на первое место ненулевое слагаемое или начать с другого уравнения). Умножим первое уравнение системы (1.35) на число a21/a11 и вычтем его из второго уравнения этой системы. Затем умножим обе части первого уравнения на число а31/а11 и вычтем его из третьего уравнения и т. д. — т. е. процесс заключается в последовательном вычитании

первого уравнения, умножаемого на числа а11/а11, из i-го уравнения

(i= 1, 2, 3, ..., п). Таким образом, в результате элементарных преобразований мы получаем эквивалентную систему в которой, начиная со второго уравнения, отсутствуют слагаемые, содержащие неизвестное Хij.

{a11x1+a12x2+...+a1nxn=b,

{a22x2+a23x3+...+a2nxn=b1

{…........................................

{am2x2+am3x3+...+amnxm.

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

мы переходим от расширенной матрицы (1.39) исходной системы к расширенной матрице

AB=(a11 a12 a13 … a1n | b1)

(0 a22 a23 … a2n | b2)

(…............................|.....)

(0 am2 am3 ...amn| bm)

Второй шаг заключается в том, что теперь 2-я строка матрицы (1.45)

используется для аналогичных элементарных преобразований строк с 3-й по т-ю: эта строка последовательно умножается на число a12/a22 и вычитается из i-й строки (i = 3, 4,..., m). В результате этих (m - 2) элементарных преобразований получаем новую расширенную матрицу, соответствующую новой эквивалентной системе уравнений. Эта

матрица имеет вид

AB=(a11 a12 a13 … a1n | b1)

(0 a22 a23 … a2n | b2)

(0 0 a33 … a3n | b3 )

(…............................|.....)

(0 0 am3 ...amn| bm)

где верхний индекс означает новые коэффициенты. В случае, если элемент а22 = 0, то второе уравнение можно поменять местами с другим уравнением, у которого элемент a12≠ 0.

Продолжим этот процесс аналогичным образом (т. е. на третьем шаге

преобразуются строки с 4-й по т-ю, на четвертом шаге — строки с 5-й по m-ю и т. д.) до тех нор, пока не дойдем до последней m-строки.

После ( г - 1)-го шага процесса последовательного исключения неизвестных мы получим следующую расширенную матрицу:

AB=(a11 a12 … a1r a1r+1 … a1n| b1)

(0 a22 … a2r a2r+1 … a2n| b2)

(…........................................| …..)

(0 0 … arr arr+1 … arn| br)

(0 0 … 0 0 … 0 | br+1)

(…........................................|.......)

(0 0 … 0 0 … 0 | bm)

Последние (m — г) строк этой матрицы соответствуют уравнениям эквивалентной системы уравнений

0x1+0x2+...+0xn=b1; i=r+1, r+2,...,m.

(1.48)

Эти уравнения могут появиться, если соответствующие уравнения исходной системы (1.35) представляют собой линейные комбинации других уравнений этой системы, о чем говорилось в предыдущем разделе. Здесь мы не исследовали заранее систему (1.35) на совместность; поэтому, если эта система несовместна, то хотя бы одно из чисел br=1, br=2, …, bm не равно нулю. Таким образом, метод Гаусса позволяет на определенном шаге установить возможную несовместность исходной системы линейных уравнений или выявить и удалить уравнения, являющиеся линейными комбинациями других уравнений системы (1.35), если она совместна.

Пусть система (1.35) совместна, тогда все правые части уравнений (1.48)

равны нулю, и после удаления нулевых уравнений в эквивалентной системе и нулевых строк в расширенной матрице получаем матрицу специфического ступенчатого вида, ранг которой равен r. Все элементы этой

матрицы, стоящие слева или ниже элементов аm равны нулю:

AB=(a11 a12 a13 … a1r … a1n| b1)

(0 a22 a23 … a2r … a2n| b2)

(0 0 a33 … a3r … a3n| b3)

(…........................................| …..)

(0 0 0 … arr … arn| br)

Эта расширенная матрица соответствует системе уравнений ранга г, которая имеет вид

{a11x1+ a12x2+ a13x3+ … +a1nxn= b1

{a22x2+a23x3+ … +a2nxn= b2

{a33x3+ … +a3nxn= b3

{…........................................…..

{arrxr+...+arn= br

(1.50)

Система уравнений (1.50) уже полностью подготовлена к нахождению решения, которое осуществляется снизу вверх, т. е. от последнегоуравнения к первому. Переход от системы (1.35) к эквивалентной ее системе (1.50) называется прямым ходом, а нахождение неизвестных из системы (1.50) — обратным ходом метода Гаусса. Укажем дальней-

шую последовательность действий.

1. Если ранг системы (1.35) г=n, то система (1.50) имеет вид

{a11x1+a12x2+...+a1rxr=b1

{a22x2+...+a2rxr=b2

{…..............................

{arrxr=br

(1.51)

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

— из последнего r-уравнения неизвестное хг = br/ar

— из ( r - 1)-го уравнения неизвестное хr-х путем подстановки в это уравнение уже найденного неизвестного х^n

— из i-го уравнения неизвестное х, при подстановке в него найденных величин хп хг+1, ..., xi + 1,

— и так далее до первого уравнения, из которого при подстановке в него уже найденных величин хr, хг+1,, ..., хr+2 находим х1.

2. Ранг системы уравнений (1.50) г < п. В этом случае объявляем неизвестные хг+ь хг+2у •> хп свободными и формируем правые части уравнений (1.50), оставляя в левых частях слагаемые, содержащие базисные переменные х1, х2, ..., хr;.

{a11x1+a12x2+...+a1rxr=b1-a1r+1xr+1 - … -a1nxn,

{a22x2+...+a2rxr=b2-a2r+1xr+1 - … -a2nxn

{….................................................

{arxr=brr+1xr+1 - … - arnxn.

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

14.

Решение СЛАУ прямоугольного вида(mxn). Общее решение, частное решение, базисное решение, опорное решение:

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

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

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

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

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