Метод Гаусса — Жордана

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод Гаусса — Жордана (метод полного исключения неизвестных) — метод, который используется для решения квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе или отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь К. Ф. Гаусса и немецкого геодезиста и математика Вильгельма Йордана[1].

Алгоритм[править | править исходный текст]

  1. Выбирают первый слева столбец матрицы, в котором есть хоть одно отличное от нуля значение.
  2. Если самое верхнее число в этом столбце ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.
  3. Все элементы первой строки делят на верхний элемент выбранного столбца.
  4. Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.
  5. Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца.
  6. После повторения этой процедуры n-1 раз получают верхнюю треугольную матрицу
  7. Вычитают из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.
  8. Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).


Расширенный алгоритм для нахождения обратной матрицы[править | править исходный текст]

Пусть дано:

A=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} \quad a_{ii} \ne 0 \quad I=\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}

Прямой ход (алгоритм образования нулей под главной диагональю)[править | править исходный текст]

  • Разделим первую строку матрицы А на a_{11} получим: a_{1j}^1 = \frac{a_{1j} }{a_{11} }, j — столбец матрицы А.
  • Повторяем действия для матрицы I, по формуле: b_{1s}^1 = \frac{b_{1s} }{a_{11} }, s — столбец матрицы I
Получим:
A=\begin{pmatrix} 1 & a_{12}^1 & \cdots & a_{1n}^1 \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} \qquad I=\begin{pmatrix} b_{11}^1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}
  • Будем образовывать 0 в первом столбце : a_{2j}^1=a_{2j}-a_{1j}^1 a_{21} \; \dots \; a_{nj}^1=a_{nj}-a_{1j}^1 a_{n1}
  • Повторяем действия для матрицы І, по формулам : b_{2s}^1=b_{2s}-b_{1s}^1 a_{21} \; \dots \; b_{ns}^1=b_{ns}-b_{1s}^1 a_{n1}
Получим:
A=\begin{pmatrix} 1 & a_{12}^1 & \cdots & a_{1n}^1 \\ 0 & a_{22}^1 & \cdots & a_{2n}^1 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & a_{2n}^1 & \cdots & a_{nn}^2 \end{pmatrix} \qquad I=\begin{pmatrix} b_{11}^1 & 0 & \cdots & 0 \\ b_{21}^1 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1}^1 & 0 & \cdots & 1 \end{pmatrix}
  • продолжаем выполнять аналогичные операции, используя формулы : a_{ij}^k=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_{ik}^{k-1}
при условии, что k = 1 \rightarrow n,i = k + 1 \rightarrow n,j = 1 \rightarrow n
  • Повторяем действия для матрицы І, по формулам : b_{ik}^k=\frac{b_{ik}^k}{a_{ii} } \qquad b_{is}^k=b_{is}^{k-1}-b_{ks}^k a_{ik}^{k-1}
при условии, что k=1 \to n,\; i=k+1 \to n,\; s=1 \to n
Получим :
A=\begin{pmatrix} 1 & a_{12}^1 & \cdots & a_{1n}^1 \\ 0 & 1 & \cdots & a_{2n}^2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix} \qquad I=\begin{pmatrix} b_{11}^1 & 0 & \cdots & 0 \\ b_{21}^2 & b_{22}^2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1}^n & b_{n2}^n & \cdots & b_{nn}^n \end{pmatrix}

Обратный ход (алгоритм образования нулей над главной диагональю)[править | править исходный текст]

Используем формулу: a_{ij}^{k-1}=a_{ij}^{k-1}-a_{ij}^k a_{ik}^i, при условии, что k=n \to 1,\; i=1 \to k-1,\; j=1 \to n

Повторяем действия для матрицы І, по формуле : b_{is}^{k-1}=b_{is}^{k-1}-b_{is}^k a_{ik}^i, при условии, что k=n \to 1,\; i=1 \to k-1,\; s=1 \to n

Окончательно получаем :

A=\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix} \qquad I=A^{-1}

Пример[править | править исходный текст]

Для решения следующей системы уравнений:

\left\{\begin{array}{ccccccl}
a &+& b &+& c &=& 0\\
4a &+& 2b &+& c &=& 1\\
9a &+& 3b &+& c &=& 3 \end{array}\right.

Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:


  \begin{pmatrix}
    1 & 1 & 1 \!& \vline &\! 0 \\
    4 & 2 & 1 \!& \vline &\! 1 \\
    9 & 3 & 1 \!& \vline &\! 3
  \end{pmatrix}

Проведём следующие действия:

  • К строке 2 добавим: −4 × Строку 1.
  • К строке 3 добавим: −9 × Строку 1.

Получим:


  \begin{pmatrix}
    1 &\  1 &\  1 \!& \vline &\! 0 \\
    0 & -2 & -3 \!& \vline &\! 1 \\
    0 & -6 & -8 \!& \vline &\! 3
  \end{pmatrix}
  • К строке 3 добавим: −3 × Строку 2.
  • Строку 2 делим на −2

  \begin{pmatrix}
    1 &  1 &  1 \!& \vline &\!\ 0 \\
    0 & 1 & {3 \over 2} \!& \vline &\! -{1 \over 2} \\
    0 & 0 & 1 \!& \vline &\!\ 0
  \end{pmatrix}
  • К строке 1 добавим: −1 × Строку 3.
  • К строке 2 добавим: −3/2 × Строку 3.

  \begin{pmatrix}
    1 & 1 & 0 \!& \vline &\!\ 0 \\
    0 & 1 & 0 \!& \vline &\! -{1 \over 2} \\
    0 & 0 & 1 \!& \vline &\!\ 0
  \end{pmatrix}
  • К строке 1 добавим: −1 × Строку 2.

  \begin{pmatrix}
    1 & 0 & 0 \!& \vline &\!\ {1 \over 2} \\
    0 & 1 & 0 \!& \vline &\! -{1 \over 2} \\
    0 & 0 & 1 \!& \vline &\!\ 0
  \end{pmatrix}

В правом столбце получаем решение:

a = \frac{1}{2} \; ; \ b = -\frac{1}{2} \; ; \ c = 0 .

Примечания[править | править исходный текст]

  1. Транскрипция фамилии Йордан как «Жордан» является ошибочной, но она общепринята и встречается в большинстве русскоязычных источников.

Литература[править | править исходный текст]

  • Lipschutz, Seymour, and Lipson, Mark. «Schaum’s Outlines: Linear Algebra». Tata McGraw-hill edition. Delhi 2001. pp. 69-80.

Ссылки[править | править исходный текст]

Примеры реализации алгоритма: