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

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

Видео:Решение системы уравнений методом ГауссаСкачать

Метод исключения Гаусса

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

Треугольные системы

Рассмотрим следующую треугольную ( 2times 2 )-систему: $$ begin l_ & 0 \ l_ & l_ end begin x_1\ x_2 end = begin b_1\ b_2 end $$

Если ( l_, l_ ne 0 ), то неизвестные могут быть определены последовательно: $$ begin x_1 &= b_1/l_,\ x_2 &= (b_2 — l_x_1)/l_ end $$

Это ( 2times 2 )-версия алгоритма, известного как прямая подстановка. Общую процедуру получаем, разрешая ( i )-е уравнение системы ( Lx = b ) относительно ( x_i ): $$ x_i = left( b_i — sum_^ l_ x_j right)/l_. $$

Если вычисления выполнить для ( i ) от ( 1 ) до ( n ), то будут получены все компоненты вектора ( x ). Заметим, что на ( i )-м шаге необходимо скалярное произведение векторов ( L(i,1:i-1) ) и ( x(1:i-1) ). Так как ( b_i ) содержится только в формуле для ( x_i ), мы можем записать ( x_i ) на месте ( b_i ).

Прямая подстановка

Предположим, что ( L in mathbb^ ) — нижняя треугольная матрица и ( b in mathbb^n ). Следующий код Python заменяет ( b ) на решение системы ( Lx = b ). Матрица ( L ) должна быть невырождена.

Аналогичный алгоритм для верхней треугольной системы ( Ux = b ) называется обратная подстановка. Вот формула для ( x_i ): $$ x_i = left( b_i — sum_^ u_ x_j right)/u_. $$ и снова ( x_i ) можно записать на месте ( b_i ).

Обратная подстановка

Если матрица ( U in mathbb^ ) верхняя треугольная и ( b in mathbb^n ), то следующий код Python заменяет ( b ) на решение системы ( Ux = b ). Матрица ( U ) должна быть невырождена.

Отметим, что при реализации формул прямой и обратной подстановки мы использовали срезы массивов (см. раздел ref). В первом алгоритме L[i,:i] означает, что берется из строки двумерного массива с индексом i все элементы с нулевого до i-1 -го включительно, а b[:i] — элементы массива b с индексами от 0 до i-1 включительно. Во втором алгоритме используются срезы U[i,i+1:] , содержащий от i+1 -го до последнего (включительно) элементы i -той строки, и b[i+1:] с элементами от i+1 -го до последнего (включительно). Кроме того использовалась функция dot модуля numpy , которая вычисляет скалярное произведение двух векторов. Таким образом, мы здесь использовали векторизованные вычисления.

( LU )-разложение

Как мы только что видели, треугольные системы решаются «легко». Идея метода Гаусса — это преобразование системы (1) в эквивалентную треугольную систему. Преобразование достигается соответствующих линейных комбинаций уравнений. Например, в системе $$ begin 3x_1 + 5x_2 &= 9,\ 6x_1 + 7x_2 &= 4, end $$ умножая ее первую строку на 2 и вычитая ее из второй части, мы получим $$ begin 3x_1 + 5x_2 &= 9,\ -3x_2 &= -14. end $$

Это и есть метод исключений Гаусса при ( n=2 ). Дадим полное описание этой важной процедуры, причем опишем ее выполнение на языке матричных разложений. Данный пример показывает, что алгоритм вычисляет нижнюю треугольную матрицу ( L ) и верхнюю треугольную матрицу ( U ) так, что ( A = LU ), т.е. $$ begin 3 & 5 \ 6 & 7 end = begin 1 & 0 \ 2 & 1 end begin 3 & 5 \ 0 & -3 end $$ Решение исходной задачи ( Ax = b ) находится посредством последовательного решения двух треугольных систем: $$ Ly = b, quad Ux = y quad Rightarrow Ax = LUx = Ly = b $$

Матрица преобразования Гаусса.

Чтобы получить разложение, описывающее исключение Гаусса, нам нужно иметь некоторое матричное описание процесса обнуления матрицы. Пусть ( n=2 ), тогда как ( x_1 ne 0 ) и ( tau = x_2/x_1 ), то $$ begin 1 & 0 \ -tau & 1 end begin x_1\ x_2 end = begin x_1\ 0 end $$ В общем случае предположим, что ( x in mathbb^n ) и ( x_k ne 0 ). Если $$ tau^ = [ underbrace_k, tau_, ldots, tau_n ], quad tau_i = frac quad i = k+1, k+2, ldots, n $$ и мы обозначим $$ begin tag M_k = I — tau^ e_k^T, end $$ где $$ begin e_k^T &= [underbrace_, 1, underbrace_],\ I &= [e_1, e_2 ldots, e_n] end $$ то $$ M_k x = begin 1 & dots & 0 & 0 & dots & 0 \ vdots & ddots & vdots & vdots & ddots & vdots \ 0 & dots & 1 & 0 & dots & 0 \ 0 & dots & -tau_ & 1 & dots & 0 \ vdots & ddots & vdots & vdots & ddots & vdots \ 0 & dots & -tau_n & 0 & dots & 1 end begin x_1\ vdots \ x_k \ x_ \ vdots \ x_n end = begin x_1\ vdots \ x_k \ 0\ vdots \ 0 end $$

Матрица ( M_k ) — это матрица преобразования Гаусса. Она является нижней унитреугольной. Компоненты ( tau_, tau_, ldots, tau_n ) — это множители Гаусса. Вектор ( tau^ ) называется вектором Гаусса.

Для реализации данных идей имеется функция, которая вычисляет вектор множителей. Если x — массив из n элементов и x[0] ненулевой, функция gauss возвращает вектор длины ( n-1 ), такой, что если M — матрица преобразования Гаусса, причем M[1:,1] = -gauss(x) и y = dot(M,x) , то y[1:] = 0 :

Применение матриц преобразовния Гаусса.

Умножение на матрицу преобразования Гаусса выполняется достаточно просто. Если матрица ( C in mathbb^ ) и ( M_k = I — tau^ e_k^T ), тогда преобразование вида $$ M_k C = (I — tau^ e_k^T)C = C — tau^ (e_k^T C) $$ осуществляет одноранговую модификацию. Кроме того, поскольку элементы вектора ( tau^ ) равны нулю от первого до ( k )-го равны нулю, то в каждой ( k )-ой строке матрицы ( C ) задействованы лишь элементы, начиная с ( k+1 )-го. Следовательно, если «C« — двумерный массив, задающий матрицу ( C ), и «M« задает ( n times n )-преобразование Гаусса ( M_1 ), причем «M[1:,1] = -t«, «t« — множитель Гаусса, соответствующий ( tau^ ), тогда следующая функция заменяет ( C ) на ( M_1C ):

Отметим, что если матрица M[k+1:,k] = -t , тогда обращение вида C[k. ] = gauss_app(C[k. ], t) заменяет ( C ) на ( M_kC )

Матрицы преобразовния Гаусса ( M_1, M_2, ldots, M_ ), как правило, можно подобрать так, что матрица ( M_M_ldots M_1A = U ) является верхней треугольной. Легко убедиться, что если ( M_k = I — tau^e_k^T ), тогда обратная к ней задается следующим выражением ( M_k^ = I + tau^ e_k^T ) и поэтому $$ begin tag A = LU, end $$ где $$ L = M_1^ M_2^ ldots M_^. $$

Очевидно, что ( L ) — это нижняя унитреугольная матрица. Разложение (3) называется ( LU )-разложением матрицы ( A ). Необходимо проверять ведущие элементы матрицы ( A ) (( a_ )) на нуль, чтобы избежать деления на нуль в функции gauss . Это говорит о том, что ( LU )-разложение может не существовать. Известно, что ( LU )-разложение матрицы ( A ) существует, если главные миноры матрицы ( A ) не равны нулю при этом оно единственно и ( det = u_ u_ cdots u_ ).

Рассмотрим пример при ( n=3 ):

Функция numpy.dot

Обратите внимание, что в приведенном примере мы использовали функцию dot модуля numpy , которая выполняет умножение матриц в «правильном смысле», в то время как выражение M1*A производит поэлементное умножение.

Обобщение этого примера позволяет представить ( k )-й шаг следующим образом:

• Мы имеем дело с матрицей ( A^ = M_cdots M_1A ), которая с ( 1 )-го по ( (k-1) )-й столбец является верхней треугольной.
• Поскольку мы уже получили нули в столбцах с ( 1 )-го по ( (k-1) )-й, то преобразование Гаусса можно применять только к столбцам с ( k )-го до ( n )-го. На самом деле нет необходимости применять преобразование Гаусса также и ( k )-му столбцу, так как мы знаем результат.
• Множители Гаусса, задающие матрицу ( M_k ) получаются по матрице ( A(k:n,k) ) и могут храниться в позициях, в которых получены нули.

С учетом сказанного выше мы можем написать следующую функцию:

Эта функция возвращает ( LU )-разложение матрицы ( A ). Где же храниться матрица ( L )? Дело в том, что если ( L = M_1^M_2^ ldots M_^ ), то элементы с ( (k+1) )-го до ( n )-го в ( k )-том столбце матрицы ( L ) равны множителям Гаусса ( tau_, tau_, ldots, tau_ ) соответственно. Этот факт очевиден, если посмотреть на произведение, задающее матрицу ( L ): $$ L = (I + tau^e_1^T cdots (I + tau^e_^T)) = I + sum_^ tau^e_k^T. $$ Поэтому элементы ( l_ = lu_ ) для всех ( i > k ). Здесь ( lu_ ) — элементы матрицы возвращаемой функцией lu .

После разложения матрицы ( A ) с помощью функции lu в возвращаемом массивы будут храниться матрицы ( L ) и ( U ). Поэтому мы можем решить систему ( Ax = b ), используя прямую и обратную подстановки описанные в разделе Треугольные системы:

Замечание

Отметим, что во всех представленных функциях мы выполняли явное преобразование входных параметров в массивы NumPy с элементами типа float . Это позволит правильно работать функциям в случае, если мы по ошибке создадим входные параметры не как массивы, а как списки.

Как известно метод Гаусса является прямым, т.е. дает точное решение системы линейных уравнений. Для проверки реализации решения системы линейных уравнений методом Гаусса мы можем написать следующую функцию:

Замечание

Здесь мы задали матрицу A системы и точное решение expected , на основе которых получили вектор правой части b = np.dot(A,x) . Для сравнения численного решения с точным используется функция np.linalg.norm . В случае вызова с одним аргументом вычисляется ( l_2 )-норма: ( | v |_2 = sqrt<sum_^n v_i^2> ).

Выбор ведущего элемента

Как уже упоминалось, ( LU )-разложение может не существовать. В методе Гаусса с выбором ведущего элемента на очередном шаге исключается неизвестное, при котором коэффициент по модулю является наибольшим. В этом случае метод Гаусса применим для любых невырожденных матриц (( det A ne 0 )).

Такая стратегия предполагает переупорядочивание данных в виде перестановки двух матричных строк. Для этого используются понятие перестановочной матрицы. Перестановочная матрица (или матрица перестановок) — это матрица, отличающаяся от единичной лишь перестановкой строк, например $$ P = begin 0 & 0 & 0 & 1\ 1 & 0 & 0 & 0\ 0 & 0 & 1 & 0\ 0 & 1 & 0 & 0 end. $$

Перестановочную матрицу нет необходимости хранить полностью. Гораздо более эффективно перестановочную матрицу можно представить в виде целочисленного вектора ( p ) длины ( n ). Один из возможных способов такого представления — это держать в ( p_k ) индекс столбца в ( k )-й строке, содержащий единственный элемент равный ( 1 ). Так вектор ( p = [4, 1, 3, 2] ) соответствует кодировке приведенной выше матрицы ( P ). Также возможно закодировать ( P ) указанием индекса строки в ( k )-ом столбце, содержащего ( 1 ), например, ( p = [2, 4, 3, 1] ).

Если ( P ) — это матрица перестановок, а ( A ) — некоторая матрица, тогда матрица ( AP ) является вариантом матрицы ( A ) с переставленными столбцами, а ( PA ) — вариантом матрицы ( A ) с переставленными строками.

Перестановочные матрицы ортогональны, и поэтому если ( P ) — перестановочная матрица, то ( P^ = P^T ).

В этом разделе особый интерес представляют взаимные перестановки. Такие перестановки осуществляют матрицы, получаемые простой переменой мест двух строк единичной матрицы, например $$ E = begin 0 & 0 & 0 & 1\ 0 & 1 & 0 & 0\ 0 & 0 & 1 & 0\ 1 & 0 & 0 & 0 end. $$

Взаимные перестановки могут использоваться для описания перестановок строк и столбцов матрицы. В приведенном примере порядка ( 4 times 4 ) матрица ( EA ) отличается от матрицы ( A ) перестановкой ( 1 )-й и ( 4 )-й строк. Аналогично матрица ( AE ) отличается от матрицы ( A ) перестановкой ( 1 )-го и ( 4 )-го столбцов.

Если ( P = E_n E_ cdots E_1 ) и каждая матрица ( E_k ) является единичной с переставленными ( k )-й и ( p_k )-й строками, то вектор ( p = [p_1, p_2, ldots, p_n] ) содержит всю необходимую информацию о матрице ( P ). Действительно, вектор ( x ) может быть замещен на вектор ( Px ) следующим образом: $$ begin mathbf & k = 1:n\ & x_k leftrightarrow x_

end $$ Здесь символ ( leftrightarrow ) обозначает «выполнение перестановки»: $$ x_k leftrightarrow x_

Leftrightarrow r = x_k, x_k = x_

, x_

= r. $$

Поскольку каждая матрица ( E_k ) является симметричной и ( P^T = E_1 E_2 cdots E_n ), то также можно выполнить замещение вектора ( x ) на вектор ( P^Tx ): $$ begin mathbf & k = n:1:-1\ & x_k leftrightarrow x_

end $$

Существуют разные стратегии выбора ведущего элемента. Мы остановимся на стратегии частичного выбора. Пусть матрица $$ A = begin 3 & 17 & 10 \ 2 & 4 & -2 \ 6 & 18 & -12 end. $$ Чтобы добиться наименьших множителей в первой матрице разложения по Гауссу с помощью взаимных перестановок строк, надо сделать элемент ( a_ ) наибольшим в первом столбце. Если ( E_1 ) — матрица взаимных перестановок, тогда $$ E_1 = begin 0 & 0 & 1 \ 0 & 1 & 0 \ 1 & 0 & 0 end. $$

Поэтому $$ E_1A = begin 6 & 18 & -12 \ 2 & 4 & -2 \ 3 & 17 & 10 end $$ и $$ M_1 = begin 1 & 0 & 0 \ -1/3 & 1 & 0 \ -1/2 & 0 & 1 end Rightarrow M_1E_1A = begin 6 & 18 & -12 \ 0 & -2 & 2 \ 0 & 8 & 16 end. $$

Теперь, чтобы получить наименьший множитель в матрице ( M_2 ), необходимо переставить ( 2 )-ю и ( 3 )-ю строки и т.д.

Пример иллюстрирует общую идею, основанную на перестановке строк. Обобщая эту идею, получим следующий алгоритм:

( LU )-разложение с частичным выбором

Если матрица ( E in mathbb^ ), то данный алгоритм вычисляет матрицы преобразования Гаусса ( M_1, M_2 ldots, M_ ) и матрицы взаимных перестановок ( E_1, E_2, ldots, E_ ), такие что матрица ( M_E_ cdots M_1E_1A = U ) является верхней треугольной. При этом нет множителей, превосходящих ( 1 ) по абсолютной величине. Подматрица ( [a_]_^k ) замещается на матрицу ( [u_]_^k ), ( k = 1, 2, ldots, n ). Подматрица ( [a_]_^n ) замещается на матрицу ( [m_]_^ ), ( k = 1, 2, ldots , n-1 ). Целочисленный вектор ( piv ) размера ( n-1 ) задает взаимные перестановки. В частности, матрица ( E_k ) переставляет строки ( k ) и ( piv_k ), ( k = 1, 2, ldots, n-1 ).

for ( k = 1:n )

1. Зададим ( mu ), такое что ( k leq mu leq n ) и ( |a_| = max_|a_| )
2. ( a_ leftrightarrow a_ ); ( piv_k = mu )

if ( a_ ne 0 )

Чтобы решить линейную систему ( Ax = b ) после вызова последнего алгоритма, мы должны

1. Вычислить вектор ( y = M_E_ cdots M_1E_1 b ). 2. Решить верхнюю треугольную систему ( Ux = y ).

Видео:Матричный метод решения систем уравненийСкачать

Приведение матрицы к треугольному виду

Приведение матрицы к треугольному виду методом Гаусса и методом Барейса.

Ниже два калькулятора для приведения матриц к треугольному, или ступенчатому, виду. Первый использует для этого метод Гаусса, второй — метод Барейса. Описание методов и немного теории — под калькуляторами.

Приведение матрицы к треугольному виду (метод Гаусса)

Приведение матрицы к треугольному виду (метод Барейса)

Итак, для начала определимся с понятием треугольной, или ступенчатой матрицы:
Матрица имеет ступенчатый вид, если:

1. Все нулевые строки матрицы стоят последними
2. Первый ненулевой элемент строки всегда находится строго правее первого ненулевого элемента предыдущей строки
3. Все элементы столбца под первым ненулевым элементом строки равны нулю (это впрочем следует из первых двух пунктов)

Пример ступенчатой матрицы:
1 0 2 5
0 3 0 0
0 0 0 4

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

Пример треугольной (верхнетреугольной) матрицы:
1 0 2 5
0 3 1 3
0 0 4 2
0 0 0 3
Кстати, определитель треугольной матрицы вычисляется простым перемножением ее диагональных элементов.

Чем же так интересны ступенчатые (и треугольные) матрицы, что к ним надо приводить все остальные? — спросите вы.
У них есть замечательной свойство, а именно, любую прямоугольную матрицу можно с помощью элементарных преобразований привести к ступенчатой форме.

Что же такое элементарные преобразования? — спросите вы.
Элементарными преобразованиями матрицы называют следующие операции:

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

И что? — спросите вы.
А то, что элементарные преобразования матрицы сохраняют эквивалентность матриц. А если вспомнить, что системы линейных алгебраический уравнений (СЛАУ) записывают как раз в матричной форме, то это означает, что элементарные преобразования матрицы не изменяют множество решений системы линейных алгебраических уравнений, которую представляет эта матрица.

Приведя матрицу системы линейных уравнений AX=B к треугольной форме A’X = B’, то есть, с соответствующими преобразованиями столбца B, можно найти решение этой системы так называемым «обратным ходом».

Чтобы было понятно, используем треугольную матрицу выше и перепишем систему уравнений в более привычной форме (столбец B я придумал сам):

Понятно, что сначала мы найдем , потом, подставив его в предыдущее уравнение, найдем и так далее — двигаясь от последнего уравнения к первому. Это и есть обратный ход.

Алгоритм приведения матрицы к ступенчатой форме с помощью элементарных преобразований называют методом Гаусса. Метод Гаусса — классический метод решения систем линейных алгебраических уравнений. Также его еще называют Гауссовым исключением, так как это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к эквивалентной системе ступенчатого (или треугольного) вида, из которого последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.

Теперь про сам метод.
Собственно, как можно занулить переменную во втором уравнении? Вычтя из него первое, домноженное на коэффициент
Поясним на примере:

Зануляем во втором уравнении:

Во втором уравнении больше не содержится

Обобщенно алгоритм метода Гаусса можно представить следующим образом:

где N — число строк,
— i-тая строка,
— элемент, находящийся в i-той строке, j-том столбце

И все бы ничего, да и метод отличный, но. Дело все в делении на , присутствующем в формуле. Во-первых, если диагональный элемент будет равен нулю, то метод работать не будет. Во-вторых, в процессе вычисления будет накапливаться погрешность, и чем дальше, тем больше. Результат будет отличаться от точного.

Для уменьшения погрешности используют модификации метода Гаусса, которые основаны на том, что погрешность тем меньше, чем больше знаменатель дроби. Эти модификации — метод Гаусса с выбором максимума в столбце и метод Гаусса с выбором максимума по всей матрице. Как следует из названия, перед каждым шагом исключения переменной по столбцу (всей матрице) ищется элемент с максимальным значением и проводится перестановка строк (строк и столбцов), таким образом, чтобы он оказался на месте .

Но есть еще более радикальная модификация метода Гаусса, которая называется методом Барейса (Bareiss).
Как можно избавиться от деления? Например, умножив перед вычитанием строку на . Тогда вычитать надо будет строку , домноженную только на , без всякого деления.
.
Уже хорошо, но возникает проблема с ростом значений элементов матрицы в ходе вычисления.

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

Кстати, то, что в случае целочисленных элементов исходной матрицы алгоритм Барейса приводит к треугольной матрице с целочисленными элементами, то есть без накопления погрешности вычислений — довольно важное свойство с точки зрения машинной арифметики.

Алгоритм Барейса можно представить следующим образом:

Алгоритм, аналогично методу Гаусса, также можно улучшить поиском максимума по столбцу(всей матрице) и перестановкой соответствующих строк (строк и столбцов).

Видео:Математика без Ху!ни. Метод Гаусса.Скачать

Решение систем линейных уравнений методом Гаусса

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

Видео:Решение системы уравнений методом обратной матрицы.Скачать

Понятие метода Гаусса

Чтобы сразу же понять суть метода Гаусса, остановите ненадолго взгляд на анимации ниже. Почему одни буквы постепенно исчезают, другие окрашиваются в зелёный цвет, то есть становятся известными, а числа сменяются другими числами? Подсказка: из последнего уравнения совершенно точно известно, чему равна переменная z .

Догадались? В такой системе, называемой трапециевидной, последнее уравнение содержит только одну переменную и её значение можно однозначно найти. Затем значение этой переменной подставляют в предыдущее уравнение (обратный ход метода Гаусса, далее — просто обратный ход), из которого находят предыдущую переменную, и так далее.

Метод Гаусса, называемый также методом последовательного исключения неизвестных, состоит в следующем. При помощи элементарных преобразований систему линейных уравнений приводят к такому виду, чтобы её матрица из коэффициентов оказалась трапециевидной (то же самое, что треугольной или ступенчатой) или близкой к трапециевидной (прямой ход метода Гаусса, далее — просто прямой ход). Пример такой системы и её решения как раз и был приведён на анимации в начале урока.

В трапециевидной (треугольной) системе, как видим, третье уравнение уже не содержит переменных y и x , а второе уравнение — переменной x .

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

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

Преимущества метода:

1. при решении систем линейных уравнений с числом уравнений и неизвестных более трёх метод Гаусса не такой громоздкий, как метод Крамера, поскольку при решении методом Гаусса необходимо меньше вычислений;
2. методом Гаусса можно решать неопределённые системы линейных уравнений, то есть, имеющие общее решение (и мы разберём их на этом уроке), а, используя метод Крамера, можно лишь констатировать, что система неопределённа;
3. можно решать системы линейных уравнений, в которых число неизвестных не равно числу уравнений (также разберём их на этом уроке);
4. метод основан на элементарных (школьных) методах — методе подстановки неизвестных и методе сложения уравнений, которых мы коснулись в соответствующей статье.

Кроме того, метод Гаусса является основой одного из методов нахождения обратной матрицы.

Чтобы все прониклись простотой, с которой решаются трапециевидные (треугольные, ступенчатые) системы линейных уравнений, приведём решение такой системы с применением обратного хода. Быстрое решение этой системы было показано на картинке в начале урока.

Пример 1. Решить систему линейных уравнений, применяя обратный ход:

Решение. В данной трапециевидной системе переменная z однозначно находится из третьего уравнения. Подставляем её значение во второе уравнение и получаем значение переменой y:

Теперь нам известны значения уже двух переменных — z и y. Подставляем их в первое уравнение и получаем значение переменной x:

Из предыдущих шагов выписываем решение системы уравнений:

Чтобы получить такую трапециевидную систему линейных уравнений, которую мы решили очень просто, требуется применять прямой ход, связанный с элементарными преобразованиями системы линейных уравнений. Это также не очень сложно.

Видео:Математика без Ху!ни. Метод Гаусса. Совместность системы. Ранг матрицы.Скачать

Элементарные преобразования системы линейных уравнений

Повторяя школьный метод алгебраического сложения уравнений системы, мы выяснили, что к одному из уравнений системы можно прибавлять другое уравнение системы, причём каждое из уравнений может быть умножено на некоторые числа. В результате получаем систему линейных уравнений, эквивалентную данной. В ней уже одно уравнение содержало только одну переменную, подставляя значение которой в другие уравнений, мы приходим к решению. Такое сложение — один из видов элементарного преобразования системы. При использовании метода Гаусса можем пользоваться несколькими видами преобразований.

На анимации выше показано, как система уравнений постепенно превращается в трапециевидную. То есть такую, которую вы видели на самой первой анимации и сами убедились в том, что из неё просто найти значения всех неизвестных. О том, как выполнить такое превращение и, конечно, примеры, пойдёт речь далее.

При решении систем линейных уравнений с любым числом уравнений и неизвестных в системе уравнений и в расширенной матрице системы можно:

1. переставлять местами строки (это и было упомянуто в самом начале этой статьи);
2. если в результате других преобразований появились равные или пропорциональные строки, их можно удалить, кроме одной;
3. удалять «нулевые» строки, где все коэффициенты равны нулю;
4. любую строку умножать или делить на некоторое число;
5. к любой строке прибавлять другую строку, умноженное на некоторое число.

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

Видео:Решение системы уравнений методом обратной матрицы - bezbotvyСкачать

Алгоритм и примеры решения методом Гаусса системы линейных уравнений с квадратной матрицей системы

Рассмотрим сначала решение систем линейных уравений, в которых число неизвестных равно числу уравнений. Матрица такой системы — квадратная, то есть в ней число строк равно числу столбцов.

Пример 2. Решить методом Гаусса систему линейных уравнений

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

Для упрощения внешнего вида решения составим расширенную матрицу системы:

В этой матрице слева до вертикальной черты расположены коэффициенты при неизвестных, а справа после вертикальной черты — свободные члены.

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

С помощью нового первого уравнения исключим переменную x из второго и всех последующих уравнений. Для этого ко второй строке матрицы прибавим первую строку, умноженную на (в нашем случае на ), к третьей строке – первую строку, умноженную на (в нашем случае на ).

Это возможно, так как

Если бы в нашей системе уравнений было больше трёх, то следовало бы прибавлять и ко всем последующим уравнениям первую строку, умноженную на отношение соответствующих коэффициентов, взятых со знаком минус.

В результате получим матрицу эквивалентную данной системе новой системы уравнений, в которой все уравнения, начиная со второго не содержат переменнную x:

Для упрощения второй строки полученной системы умножим её на и получим вновь матрицу системы уравнений, эквивалентной данной системе:

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

Если бы в нашей системе уравнений было больше трёх, то следовало бы прибавлять и ко всем последующим уравнениям вторую строку, умноженную на отношение соответствующих коэффициентов, взятых со знаком минус.

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

Мы получили эквивалентную данной трапециевидную систему линейных уравнений:

Если число уравнений и переменных больше, чем в нашем примере, то процесс последовательного исключения переменных продолжается до тех пор, пока матрица системы не станет трапециевидной, как в нашем демо-примере.

Решение найдём «с конца» — обратный ход. Для этого из последнего уравнения определим z:
.
Подставив это значение в предшествующее уравнение, найдём y:

Из первого уравнения найдём x:

Ответ: решение данной системы уравнений — .

Проверить решение системы можно и на калькуляторе, решающем методом Крамера: в этом случае будет выдан тот же ответ, если система имеет однозначное решение. Если же система имеет бесконечное множество решений, то таков будет и ответ, и это уже предмет пятой части этого урока.

Решить систему линейных уравнений методом Гаусса самостоятельно, а затем посмотреть решение

Пример 3. Решить систему линейных уравнений:

Перед нами вновь пример совместной и определённой системы линейных уравнений, в которой число уравнений равно числу неизвестных. Отличие от нашего демо-примера из алгоритма — здесь уже четыре уравнения и четыре неизвестных.

Пример 4. Решить систему линейных уравнений методом Гаусса:

Решение. Составляем расширенную матрицу системы. С помощью первого уравнения исключаем из последующих уравнений переменную . Для этого ко второй строке прибавляем первую, умноженную на , к третьей строке — первую, умноженную на , к четвёртой — первую, умноженную на .

Теперь нужно с помощью второго уравнения исключить переменную из последующих уравнений. Проведём подготовительные работы. Чтобы было удобнее с отношением коэффициентов, нужно получить единицу в во втором столбце второй строки. Для этого из второй строки вычтем третью, а полученную в результате вторую строку умножим на -1.

Проведём теперь собственно исключение переменной из третьего и четвёртого уравнений. Для этого к третьей строке прибавим вторую, умноженную на , а к четвёртой — вторую, умноженную на .

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

Получили систему уравнений, которой эквивалентна заданная система:

Следовательно, полученная и данная системы являются совместными и определёнными. Окончательное решение находим «с конца». Из четвёртого уравнения непосредственно можем выразить значение переменной «икс четвёртое»:

.

Это значение подставляем в третье уравнение системы и получаем

,

откуда находим «икс третье»:

.

Далее, подставляем значения и во второе уравнение системы:

,

.

Наконец, подстановка значений

в первое уравнение даёт

,

откуда находим «икс первое»:

.

Ответ: данная система уравнений имеет единственное решение .

Проверить решение системы можно и на калькуляторе, решающем методом Крамера: в этом случае будет выдан тот же ответ, если система имеет однозначное решение.

Видео:Как привести матрицу к ступенчатому виду - bezbotvyСкачать

Решение методом Гаусса прикладных задач на примере задачи на сплавы

Системы линейных уравнений применяются для моделирования реальных объектов физического мира. Решим одну из таких задач — на сплавы. Аналогичные задачи — задачи на смеси, стоимость или удельный вес отдельных товаров в группе товаров и тому подобные.

Пример 5. Три куска сплава имеют общую массу 150 кг. Первый сплав содержит 60% меди, второй — 30%, третий — 10%. При этом во втором и третьем сплавах вместе взятых меди на 28,4 кг меньше, чем в первом сплаве, а в третьем сплаве меди на 6,2 кг меньше, чем во втором. Найти массу каждого куска сплава.

Решение. Составляем систему линейных уравнений:

Умножаем второе и третье уравнения на 10, получаем эквивалентную систему линейных уравнений:

Составляем расширенную матрицу системы:

Внимание, прямой ход. Путём сложения (в нашем случае — вычитания) одной строки, умноженной на число (применяем два раза) с расширенной матрицей системы происходят следующие преобразования:

Прямой ход завершился. Получили расширенную матрицу трапециевидной формы.

Применяем обратный ход. Находим решение с конца. Видим, что .

Из второго уравнения находим

,

Из третьего уравнения —

.

Проверить решение системы можно и на калькуляторе, решающем методом Крамера: в этом случае будет выдан то же ответ, если система имеет однозначное решение.

О простоте метода Гаусса говорит хотя бы тот факт, что немецкому математику Карлу Фридриху Гауссу на его изобретение потребовалось лишь 15 минут. Кроме метода его имени из творчества Гаусса известно изречение «Не следует смешивать то, что нам кажется невероятным и неестественным, с абсолютно невозможным» — своего рода краткая инструкция по совершению открытий.

Во многих прикладных задачах может и не быть третьего ограничения, то есть, третьего уравнения, тогда приходится решать методом Гаусса систему двух уравнений с тремя неизвестными, или же, наоборот — неизвестных меньше, чем уравнений. К решению таких систем уравнений мы сейчас и приступим.

С помощью метода Гаусса можно установить, совместна или несовместна любая система n линейных уравнений с n переменными.

Видео:Метод Крамера за 3 минуты. Решение системы линейных уравнений - bezbotvyСкачать

Метод Гаусса и системы линейных уравнений, имеющие бесконечное множество решений

Следующий пример — совместная, но неопределённая система линейных уравнений, то есть имеющая бесконечное множество решений.

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

,

соответствующие уравнению вида

Если во всех уравнениях имеющих вид

свободные члены равны нулю, то это означает, что система неопределённа, то есть имеет бесконечное множество решений, а уравнения этого вида – «лишние» и их исключаем из системы.

Пример 6. Решить методом Гаусса систему линейных уравнений:

Решение. Составим расширенную матрицу системы. Затем с помощью первого уравнения исключим переменную из последующих уравнений. Для этого ко второй, третьей и четвёртой строкам прибавим первую, умноженную соответственно на :

Теперь вторую строку прибавим к третьей и четвёртой.

В результате приходим к системе

Последние два уравнения превратились в уравнения вида . Эти уравнения удовлетворяются при любых значениях неизвестных и их можно отбросить.

Чтобы удовлетворить второму уравнению, мы можем для и выбрать произвольные значения , тогда значение для определится уже однозначно: . Из первого уравнения значение для также находится однозначно: .

Как заданная, так и последняя системы совместны, но неопределённы, и формулы

при произвольных и дают нам все решения заданной системы.

Видео:Решение системы линейных уравнений методом ГауссаСкачать

Метод Гаусса и системы линейных уравнений, не имеющие решений

Следующий пример — несовместная система линейных уравнений, то есть не имеющая решений. Ответ на такие задачи так и формулируется: система не имеет решений.

Как уже говорилось в связи с первым примером, после выполнения преобразований в расширенной матрице системы могли появиться строки вида

,

соответствующие уравнению вида

Если среди них есть хотя бы одно уравнение с отличным от нуля свободным членом (т.е. ), то данная система уравнений является несовместной, то есть не имеет решений и на этом её решение закончено.

Пример 7. Решить методом Гаусса систему линейных уравнений:

Решение. Составляем расширенную матрицу системы. С помощью первого уравнения исключаем из последующих уравнений переменную . Для этого ко второй строке прибавляем первую, умноженную на , к третьей строке — первую, умноженную на , к четвёртой — первую, умноженную на .

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

Для исключения из третьего и четвёртого уравнения к третьей строке прибавим вторую, умноженную на , а к четвёртой — вторую, умноженную на .

Теперь с помощью третьего уравнения исключим переменную из четвёртого уравнения. Для этого к четвёртой строке прибавим третью, умноженную на .

Заданная система эквивалентна, таким образом, следующей:

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

Решить систему линейных уравнений методом Гаусса самостоятельно, а затем посмотреть решение

Пример 8. Решить систему линейных уравнений:

Видео:Решение системы уравнений методом Крамера.Скачать

Метод Гаусса и системы, в которых число неизвестных меньше числа уравнений

Следующий пример — система линейных уравнений, в которой число неизвестных меньше числа уравнений.

Пример 9. Решить методом Гаусса систему линейных уравнений:

Решение. Составляем расширенную матрицу системы. С помощью первого уравнения исключаем из последующих уравнений переменную . Для этого ко второй строке прибавляем первую, умноженную на , к третьей строке — первую, умноженную на , к четвёртой — первую, умноженную на . Далее новые вторую, третью и четвёртую строки умножаем на .

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

Проведём теперь исключение переменной из третьего и четвёртого уравнений. Для этого к третьей строке прибавим вторую, умноженную на , а к четвёртой — вторую, умноженную на .

Четвёртая и третья строки — одинаковые, поэтому четвёртую исключаем из матрицы. А третью умножаем на .

Получили следующую систему уравнений, которой эквивалентна заданная система:

и известны, а находим из первого уравнения:

.

Ответ: данная система уравнений имеет единственное решение (1; 1; 1).

Видео:Решение системы уравнений методом Гаусса 4x4Скачать

Метод Гаусса и системы, в которых число неизвестных больше числа уравнений

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

Если при выполнении преобразований в расширенной матрице системы встретилось хотя бы одно уравнение вида

(*)

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

Неизвестным, которые удовлетворяли уравнению вида 0 = 0, например, третьему и четвёртому (*, отброшенным уравнениям), придадим произвольные значения (пример 2). Они чаще всего записываются так: . Подставляя эти значения в остальные уравнения, не имеющие вида (*), например, первое и второе, получаем формулы, дающие нам значения остальных неизвестных. В них можно подставлять любые численные значения и . Следовательно, существует бесконечное множество выбора значений этих неизвестных, поэтому полученная система уравнений является неопределённой. В этом случае неопределённой является и исходная система.

Пример 10. Решить методом Гаусса систему линейных уравнений:

Решение. Составляем расширенную матрицу системы. Далее ко второй строке прибавляем первую, умноженную на .

Заданная система эквивалентна, таким образом, следующей:

В ней отсутствуют уравнения, дающие однозначные значения для и . Это равносильно появлению уравнений вида , которые можно отбросить. Мы можем для и выбрать произвольные значения . Из первого уравнения значение для находится однозначно: .

Как заданная, так и последняя системы совместны, но неопределённы, и формулы

при произвольных и дают нам все решения заданной системы.

🎥 Видео

Метод Гаусса. Прямой ход методом Гаусса. Обратный ход. Ступенчатая и треугольная расширенная матрицаСкачать

Решение системы трех уравнений по формулам КрамераСкачать

Решение матричных уравненийСкачать

Решение системы уравнений методом Крамера 2x2Скачать

Метод Гаусса решения систем линейных уравненийСкачать

метод Гаусса СИСТЕМА ЛИНЕЙНЫХ УРАВНЕНИЙ решение СЛАУСкачать

Решение систем линейных уравнений с помощью матрицСкачать

Система линейных уравнений. Общее решение. Метод ГауссаСкачать