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

СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 2.1. Формы записи СЛАУ Систему линейных алгебраических уравнений (СЛАУ) размерности m можно записать в скалярном: a11  x1  a12  x 2  ...  a1m  x m  f1  a 21  x1  a 22  x 2  ...  a2 m  x m  f 2  (2.1) ...  a m1  x1  a m 2  x 2  ...  amm  x m  f m векторном:  a11   a12   a1m   f1          a a a  21   22   2m   f2  x  x  ... x   ...  1  ...  2  ...  m  ...  (2.1)         a  a  a  f   m1   m2   mm   m или матричном виде: Ax  f  a11   a21 A Здесь    am1 a12 a22 am 2  x1      x2  x   ...  частей,  xm 1   x   m   x , (2.1) ... a1m   f1     f 2  ... a2 m   – матрица системы, f   ...  – вектор правых  f m 1    f    m  ... amm  – вектор неизвестных. Система имеет единственное решение, если A  0. По определению решения,  подставив вектор x в СЛАУ, получим m тождественных уравнений. Назовем расширенной матрицей системы A матрицу, полученную в результате добавления к исходной матрице системы вектора правых частей:  a11 ... a1m   a21 ... a2 m A      am1 ... amm f1   f2  . ...   fm  2.2. Методы решения СЛАУ Методы решения СЛАУ можно разбить на два класса: прямые (точные) и итерационные (приближенные). Прямые методы позволяют получить решение за конечное число арифметических операций. Если операции реализуются точно, то и решение будет точным (поэтому класс прямых методов еще называют точными методами). В итерационных методах решением является предел некоторой бесконечной последовательности единообразных действий. 2.3. Прямые методы решения СЛАУ с невырожденной матрицей Метод Крамера. Компоненты вектора решения определяются по формуле xi   Ai , i = 1, 2, …, m, A (2.2) где матрицы Ai получены из основной матрицы A заменой i-го столбца на вектор правых частей. Метод обратной матрицы. Вектор решения получим, умножив обратную матрицу на вектор правых частей: (2.3) x  A1 f . Метод Гаусса-Жордано. Исходная система с помощью эквивалентных преобразований (перестановка строк; умножение строк на ненулевую константу; сложение строк) расширенной матрицы сводится к системе с диагональной (единичной) матрицей. Этот метод можно использовать для нахождения обратной матрицы, для чего в расширенную матрицу надо включить единичную матрицу.  x1  x 2  x 3  2   2 x1  x 2  x 3  3 Пример 2.1. Решить СЛАУ   x x x  6  1 2 3 методом Крамера, Гаусса – Жордано и обратной матрицы. Решение. Создаем основную и три вспомогательных матрицы, находим их определители и решение по формулам (2.2.):  1 1 1  2 1 1     A   2 1 1  , A1   3 1 1  ,      1 1 1 6 1 1   1 2 1  1 1 2     A 2   2 3 1  , A3   2 1 3  ,     1 6 1 1 1 6     A1 6 A 2 18 A3 12 x1    1, x2    3, x3    2. A 6 A 6 A 6 Выполним проверку решения, подставив полученный вектор в исходную систему, записанную в скалярной форме:  1 3  2  2  2 1  3  2  3   1 3  2  6 или в матричной форме:  1 1 1  1   11  1 3  (1)  2   2          Ax   2 1 1    3    (2) 1  1 3  1 2    3          1 1 1 2 1  1  1  3  1  2       6 Для того, чтобы найти обратную матрицу и решение СЛАУ по метод ГауссаЖордано, включим единичную матрицу I в расширенную и выполним эквивалентные преобразования, приводящие исходную матрицу СЛАУ к единичной. Эти же преобразования переведут единичную матрицу в обратную матрицу, а вектор правых частей – в решение СЛАУ. A I f 1 1 –1 1 2 –2 1 1 1 3 1 1 1 1 6 Прибавляем ко второй строке первую, умноженную на 2, а из третьей вычитаем первую: 1 1 –1 1 2 3 –1 2 1 7 2 –1 1 4 Делим вторую строку на 3 и вычитаем ее из первой: 1 1 1 1 3 3 3 1 1 3 2 2 3 –1 1 3 1 1 7 3 3 4 Делим последнюю строку на 2 и прибавляем ее с коэффициентом строке и с коэффициентом  1 3 – ко второй: 1 1 1 1 1 1 1 2 2 3 3 1 1 1 1 3 к первой 3 1 6 3 2 2 A 1 x I В дальнейшем для обозначения эквивалентных преобразований будем использовать символ . Вектор решения совпадает с тем, что получен методом Крамера. Проверим, что обратная матрица найдена правильно: 1 1   0 3 3  1 1 1       1 1 1 A × A 1   2 1 1     2 3 6      1 1 1  1 1   2  2  1 1 1 1 1  1  1 1  0  1  2  (1)    2  1   3   1 3  1 0 1 3  1 6  1 2         1 1 1 1 1 1 1  2  0  1  1    2      1  1 0 2   1  1   2 3 3 6 2   2  3   1 1 1 1   1  1 0  1 1  1   1  1     1 1 0 1  1  1     2 3 3 6 2   2  3  1 0 0    0 1 0   0 0 1 Умножив обратную матрицу на вектор правых частей, получим решение методом обратной матрицы (2.3):   1 1  1 1  02    3  6     3 3  1 3 3   2             1 1 1 1 1 1   x  A 1  f    3   2   3   6   3    2 3 6 2 3 6         6    2    1 1 1 1         2  0  3   6   2 2 2     2  2.4. Исследование СЛАУ Методы Крамера и обратной матрицы решения СЛАУ можно использовать, если система имеет единственное решение, т.е. матрица квадратная и ее определитель не равен нулю. Метод Гаусса-Жордано можно использовать для решения или исследования СЛАУ с прямоугольной или вырожденной матрицей. 1 x1  0  x2  1 x3  2 1 x  1 x  0  x  3  1 2 3  Пример 2.2. Решить СЛАУ 1  x1  1  x2  1  x3  2 . 2  x1  1 x2  1 x3  1 Число неизвестных в системе – три, а число уравнений –четыре. Если все уравнения независимы, то СЛАУ переопределена и решения не имеет. Попробуем решить систему с помощью метода Гаусса-Жордано.  1 0 1 2   1 0 1 2   1 0 1 2   1 0 0        3  0 1 1 5  0 1 1 5  0 1 0 1 1 0  ~ ~ ~ 1  1 1 2  1 2 4 3 9       0 0 1         2 1 1 1  0 1 1 5   0 0 0 0   0 0 0 1  2  3  0 На третьем шаге все элементы последней строки расширенной матрицы занулились. Это означает, что последнее уравнение СЛАУ является следствием трех остальных уравнений, и может быть отброшено. Итоговую систему запишем в векторном виде: 1 0  0  1         x1   0   x2   1   x3   0    2  ,         0 0 1  3 или 1  0  0       x1  e1  x2  e2  x3  e3  f , e1   0  , e2   1  , e3   0  .       0  0 1 Здесь e1 , e2 , e3 - базисные вектора в трехмерном векторном пространстве, f - вектор правой части СЛАУ. 2  x1  0  x2  1 x3  1 x4  1 3  x  1 x  1 x  0  x  2  2 3 4 Пример 2.3. Решить СЛАУ  1 . 5  x1  1 x2  2  x3  1 x4  3 1 x1  1 x2  0  x3  1 x4  1 Решение. Легко проверить, что определитель матрицы равен нулю. В этом случае СЛАУ либо несовместна, либо имеет бесконечно много решений. Запишем расширенную матрицу и выполним преобразования Гаусса – Жордано: 2  3  5  1 1 1 1  1   1 1 0 2   2 ~ 1 2 1 3   3   1 0 1 1  5 0 1 1  1 1 0 1 1  1 1     0 1 1 1  0 2 1 3 1  0 2 ~   ~ 1 1 0 2   0 2 1 3 1  0 0     1 2 1 3   0 4 2 6 2   0 0 1 0 1 1  1 3 1  0 0 0  0 0 0 На первом шаге мы поменяли местами первую и четвертую строки, на втором – преобразовали первый столбец, на третьем – преобразовали третий столбец. В итоге две последние строки занулились, и СЛАУ можно записать в виде 1 1 0  1   1 x1     x2     x3     x4       0  2 1  3   1           Неизвестные x1 и x3, которые в этой записи умножаются на базисные вектора, назовем базисными, а две остальные неизвестные – свободными. Получим общее уравнение СЛАУ, выразив базисные неизвестные через свободные: x1  1  x2  x4 x3  1  2  x2  3  x4 . Частное решение получим, подставив вместо свободных переменных произвольные значения, например x2  x4  0 x1  1  x2  x4  1 . x3  1  2  x2  3  x4  1 Выполним проверку частного решения, подставив его в исходную систему: 2  3  5  1 1 1  1  1      1 1 0   0   2       . 1 2 1  1  3       1 0 1  0   1 2  x1  0  x2  1 x3  1 x4  1 3  x  1 x  1 x  0  x  2  2 3 4 Пример 2.4. Решить СЛАУ  1 . 5  x1  1 x2  2  x3  1 x4  5 1 x1  1 x2  0  x3  1 x4  7 Решение. Матрица СЛАУ такая же, как и в предыдущем примере. Выполняя аналогичные преобразования, получим: 2  3  5  1 1 1 1  1   1 1 0 2   3 ~ 1 2 1 5   5   1 0 1 7   2 0 1 7   1 1 0 1 7  1     1 1 0 2   0 2 1 3 19   0 ~ ~ 1 2 1 5   0 4 2 6 30   0     0 1 1 1  0 2 1 3 13   0 1 1 0 1 7  2 1 3 19  . 0 0 0 8  0 0 0 6 Все элементы двух последних строк, кроме последнего столбца, занулились. Запишем два последних уравнения в скалярном виде: 0  x1  0  x2  0  x3  0  x4  8 0  x1  0  x2  0  x3  0  x4  6 . Эти уравнения не могут быть выполнены ни при каких значениях x1, x2, x3 и x4, следовательно, решения СЛАУ не существует. 2.5. Метод прогонки Для решения систем с ленточными (трехдиагональными) матрицами предназначен метод прогонки. Рассмотрим систему с трехдиагональной матрицей: c0 x0  b0 x1  f 0 (2.4) (2.5) ai xi1  ci xi  bi xi1  fi , i = 1, 2, …, m – 1 (2.6) am xm1  cm xm  fm В матричном виде эта система имеет вид:  c0 a  1 0  0    0  0 b0 c1 b1 0 a2 c2 b2   x0 0   x1 0     x2 ...    ...    ...    xm 1 bm 1    xm  cm   0 a3 c3 b3 am 1 cm 1 am                      f0 f1 f3 f m 1 fm            В методе прогонки решение ищем в виде xi   i 1xi 1   i 1 , i =0, 1,…m-1, (2.7) где  i , i - прогоночные коэффициенты. Метод имеет два этапа. На первом этапе определяются прогоночные коэффициенты, на втором – решение. Первый этап. Запишем уравнение (2.4) в виде (2.7): x0  b0 f x1  0 , c0 c0 получим формулы для определения α1, β1: b f 1  0 , 1   0 . c0 (2.8) c0 Уменьшим в (2.7) индекс на единицу: xi 1  i xi  i и подставим полученное выражение в (2.5): aii xi  ai i  ci xi  bi xi 1  fi , откуда xi  bi a   fi xi 1  i i ci  ai i ci  ai i . Данное равенство совпадает с (2.7), если i = 0, 1, …, m – 1 выполняются рекуррентные соотношения при всех  i 1  bi ci  ai i ,  i 1  ai  i  f i ci  ai i , (2.9) по которым вычисляются все остальные коэффициенты αi, βi. Второй этап. При i = m – 1 из (2.7) получим: xm 1   m xm   m . Подставляя это выражение в (2.6) и разрешая полученное выражение относительно xm, записываем: a   fm xm  m m , (2.11) cm  am m где αm и βm известны. Далее по формулам (2.7) последовательно находятся xm–1, xm–2, …, x0. Метод прогонки позволяет быстро и точно решать большие СЛАУ. Для успешного применения метода прогонки нужно, чтобы в процессе вычислений не возникало ситуаций с делением на нуль, а при больших размерностях систем не должно быть быстрого роста погрешностей округления. Это обеспечивает выполнение условия диагонального преобладания ci  bi  ai , i = 0, 1, 2, …, m. (2.12) Пример 2.5. Решить методом прогонки СЛАУ A  x  f , где 4 1   1 4  A  0 3  0 0 0 0  2 5 1 0 1    0 0 2    1 0  , f   3 .    4 2  4 5 0 5    Решение. Составим вектора a, b и c, содержащие элементы главной и дополнительных диагоналей: 0 1  4        1  2  4       a   3  , b   1  , c   5  .       1  2  4 0 0  5        Нумерация элементов массива начинается с нуля, поэтому m=4. Заметим также, что дополнительные диагонали a и b короче главной, поэтому a0 = b4 = 0, а вектор c содержит элементы главной диагонали с противоположным знаком. Вычисляем по (2.8) первые прогоночные коэффициенты: b f 1 1 1  0   0.25 , 1   0    0.25 . c0 4 c0 4 Вычисляем по (2.9) остальные прогоночные коэффициенты: 2  b1 a  f 2 1  0.25  1   0.471;  2  1 1 1   0.412; c1  a11 4  1  0.25 c1  a11 4  1  0.25 3  b2 a   f2 1 1  0.25  1   0.156; 3  2 2   0.661; c2  a2 2 5  3  0.471 c2  a2 2 5  3  0.471 4  b3 a   f3 2 1  0.661  4   0.481;  4  3 3   0.804. c3  a3 3 4  1  0.156 4  1  0.156 4  1  0.25 Вычисляем по (2.11) x4  a4  4  f 4 0  (0.804)  5   1. c4  a4 4 5  0  0.481 Вычисляем по (2.7) все остальные компоненты решения: x3   4  x4   4  0.481 1  (0.804)  0.323; x2   3  x3  3  0.156  (0.323)  0.661  0.711; x1   2  x2   2  0.471  0.711  (0.412)  0.077; x0  1  x1  1  0.25  (0.077)  0.25  0.269. Проверяем полученное решение: 0   0   A  x  f   0 .   0 0   2.6. Решение СЛАУ в пакете MathCAD Описанные выше алгоритмы решения СЛАУ реализованы в MathCAD в виде функции lsolve, основанной на прямом методе Гаусса, и в виде вычислительного блока Given/Find, в основе которого лежит итерационный алгоритм. Для применения функции lsolve система должна быть записана в матричном виде (2.1). Пример использования функции lsolve показан на рис. 2.1. Использование блока Given/Find может быть связано как со скалярной, так и с матричной формой записи СЛАУ. Как уже было отмечено, данный метод основан на итерационной схеме решения, поэтому всем неизвестным сначала должны быть присвоены начальные значения. В случае если СЛАУ имеет единственное решение, выбор начального приближения не влияет на решение. После этого необходимо привести ключевое слово Given (Дано) и записать СЛАУ в виде логического выражения, т.е. с использованием знака логического равенства <=>, который можно найти на панели инструментов Boolean (Логическая). Затем вызвать встроенную функцию Find, аргументами которой являются искомые величины. На рис. 2.2 показано решение СЛАУ, записанной в матричной форме, с помощью вычислительного блока Given/Find. Рис. 2.1. Решение СЛАУ с помощью функции lsolve Рис. 2.2. Решение СЛАУ с помощью блока Given/Find Используя матричные функции, описанные выше, СЛАУ небольшой размерности можно решать с помощью метода обратной матрицы и метода Крамера. Соответствующие примеры показаны на рис. 2.3 и 2.4. Обращаем внимание, что для вычисления определителей используется кнопка «определитель» с панели инструментов «Матрицы» (см. рис. 1.1), и ее не следует путать с кнопкой «модуль», находящейся на панели инструментов «Калькулятор». Рис. 2.3. Решение СЛАУ методом обратной матрицы Рис. 2.4. Решение СЛАУ методом Крамера Стандартная функция rref(A), где A – расширенная матрица СЛАУ, выполняет преобразования Гаусса-Жордано. На рис. 2.5 приведено решение примеров 2.1-2.4 с помощью этой функции. Пример 2.1 2 1 0 0  1 1 1      f   3  I  identity( 3)  0 1 0 A  2 1 1       6 0 0 1 1 1 1 1 0 0 0   1 rref ( aug men t( A I f ) )   0 1 0  2  1 0 0 1  2  Пример 2.2  1 1 A   1 2  Пример 2.3, 2.4  1 rref ( au gmen t( A f1 ) )   0 0   1 1 3 3 1 1 3 6 1    2 2  1  2   1  3 1 0  f    rref ( aug men t( A f ) )     2 0 1 1  1  0 1 1     0 1   2 3 A   5 1   1 1 0  A  0 f1  1 2 1   1 0 1  0 1 1  3 0 0 1  1 0 2 0 1 3  0 0 0  1   2  f2  3 1    1  2 5 7    1  1 0.5 1.5 0.5  rref ( aug men t( A f2 ) )   0 0 0 0   0 0 0 0   0 0.5 0.5 0.5  0 0.5 0.5 0   1 0.5 1.5 0  1 0  Рис. 2.5. Решение СЛАУ с помощью стандартной функции rref В некоторых случаях для решения СЛАУ можно использовать пользовательские процедуры-функции, реализующие прямые или итерационные методы решения СЛАУ. Ниже показан фрагмент рабочего листа MathCAD, на котором приведен пример 2.5 решения СЛАУ с трехдиагональной матрицей методом прогонки (рис. 2.6). Процедура-функция progonka содержит два цикла для нахождения прогоночных коэффициентов и вектора решения. pro gonka( a b c f )  n  las t( f ) b alf  1 c f bet  1 4 1  A   0 0  0 c b i 1  i c  alf  a i i i a  bet  f bet i 1  i i a  bet  f n n n c  a  alf n i c  alf  a i x  1 0  2 1      3 5 1 0  a   3  b   1  2 1 0 1 4 2       0 0 0 5 0 0 4 2 0 0 1  4  2 4     c   5  f   3  4 4     5  5  for i  1  n  1 alf 1 0 0 0 n i i n n for i  n n  1  1 x i 1  x  alf  bet i i i x  0.269   0.077    pro gon ka( a b c f )   0.711   0.322     1  Рис. 2.6. Решение СЛАУ методом прогонки