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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод Гауса — Йордана використовується для розв'язання систем лінійних алгебраїчних рівнянь, знаходження оберненої матриці, знаходження координат вектора у заданому базисі, відшукання рангу матриці. Метод є модифікацією методу Гауса. Названий на честь Гауса та німецького математика та геодезиста Вільгельма Йордана.

Алгоритм[ред.ред. код]

  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 & 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=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_{ik}^{k-1}

при умові, що k = 1 \to n,i = k + 1 \to n,j = 1 \to 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 & | & 0 \\
    4 & 2 & 1 & | & 1 \\
    9 & 3 & 1 & | & 3
  \end{pmatrix}

Виконаємо такі дії:

  • До рядка 2 додамо: -4 * рядок 1.
  • До рядка 3 додамо: -9 * рядок 1.

Отримаємо:


  \begin{pmatrix}
    1 &\  1 &\  1 & | & 0 \\
    0 & -2 & -3 & | & 1 \\
    0 & -6 & -8 & | & 3
  \end{pmatrix}
  • До рядка 3 додамо: -3 * рядок 2.
  • Рядок 2 ділимо на -2

  \begin{pmatrix}
    1 &  1 &  1 & | &\ 0 \\
    0 & 1 & {3 \over 2} & | & -{1 \over 2} \\
    0 & 0 & 1 & | &\ 0
  \end{pmatrix}
  • До рядка 1 додамо: -1 * рядок 3.
  • До рядка 2 додамо: -3/2 * рядок 3.

  \begin{pmatrix}
    1 & 1 & 0 & | &\ 0 \\
    0 & 1 & 0 & | & -{1 \over 2} \\
    0 & 0 & 1 & | &\ 0
  \end{pmatrix}
  • До рядка 1 додамо: -1 * рядок 2.

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

У правому стовпчику отримаємо рішення:

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


Джерела[ред.ред. код]

Посилання[ред.ред. код]