Перегляд вихідного коду сторінки Метод Гаусса — Йордана

'''Метод Гаусса&nbsp;— Йордана''' використовується для розв'язання [[система лінійних алгебраїчних рівнянь|систем лінійних алгебраїчних рівнянь]], знаходження [[обернена матриця|оберненої матриці]], знаходження координат [[Вектор (математика)|вектора]] у заданому базисі, відшукання [[Ранг (лінійна алгебра)|рангу матриці]]. Метод є модифікацією [[метод Гауса|методу Гаусса]]. Названий на честь [[Карл Фрідріх Гаусс|Карла Фрідріха Гаусса]] та німецького математика та геодезиста [[Вільгельм Йордан|Вільгельма Йордана]].

== Алгоритм ==
# Обирається перша зліва колонка, що містить хоч одне ненульове значення.
# Якщо верхнє число у цій колонці&nbsp;— нуль, то обмінюється увесь перший рядок [[Матриця (математика)|матриці]] з іншим рядком матриці, де у цій колонці нема нуля.
# Усі елементи першого рядка діляться на верхній елемент обраної колонки.
# Від рядків, що залишились, віднімається перший рядок, помножений на перший елемент відповідного рядка, з метою отримання нуля в першому елементі кожного рядка (крім першого).
# Далі, повторюємо ці операції із матрицею, отриманою з початкової матриці після викреслювання першого рядка та першого стовпчика.
# Після повторення операцій ''n'' − 1 разів отримаємо верхню трикутну матрицю.
# Віднімаємо від передостаннього рядка останній рядок, помножений на відповідний коефіцієнт, щоб у передостанньому рядку залишилась лише 1 на головній діагоналі.
# Повторюємо попередній крок для наступних рядків. У результаті отримуємо одиничну матрицю і рішення на місці [[вільний вектор|вільного вектора]] (над ним необхідно виконувати ті самі перетворення).

== Розгорнутий алгоритм для знаходження оберненої матриці ==
Нехай дано:

: <math>
  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}
</math>

=== Прямий хід (алгоритм утворення нулів під головною діагоналлю) ===
* Поділимо перший рядок матриці А на <math>a_{11}</math> отримаємо: <math>a_{1j}^1 = \frac{a_{1j} }{a_{11} }</math>, ''j''&nbsp;— стовпець матриці ''А''.

* Повторюємо дії для матриці I, за формулою: <math>b_{1s}^1 = \frac{b_{1s} }{a_{11} }</math>, ''s''&nbsp;— стовпець матриці ''I''.

Отримаємо:

: <math>
  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}
</math>
* Будемо утворювати 0 у першому стовпці: <math>a_{2j}^1=a_{2j}-a_{1j}^1 a_{21} \; \dots \; a_{nj}^1=a_{nj}-a_{1j}^1 a_{n1}</math>.
* Повторюємо дії для матриці І, за формулами : <math>b_{2s}^1=b_{2s}-b_{1s}^1 a_{21} \; \dots \; b_{ns}^1=b_{ns}-b_{1s}^1 a_{n1}</math>
Отримаємо:

: <math>
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}^1 \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}
</math>
* Продовжуємо виконувати аналогічні операції використовуючи формули : <math>a_{ij}^k=\frac{a_{ij}^k}{a_{ii} } \qquad a_{ij}^k=a_{ij}^{k-1}-a_{kj}^k a_{ik}^{k-1}</math>
за умови, що <math>k = 1 \to n,i = k + 1 \to n,j = 1 \to n</math>

* Повторюємо дії для матриці І, за формулами : <math>b_{ik}^k=\frac{b_{ik}^k}{a_{ii} } \qquad b_{is}^k=b_{is}^{k-1}-b_{ks}^k a_{ik}^{k-1}</math>
за умови, що <math>k=1 \to n,\; i=k+1 \to n,\; s=1 \to n</math>.

Отримаємо:

: <math>
  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}
</math>

=== Зворотний хід (алгоритм утворення нулів над головною діагоналлю) ===
Використаємо формулу: <math>a_{ij}^{k-1}=a_{ij}^{k-1}-a_{ij}^k a_{ik}^i</math>, при умові, що <math>k=n \to 1,\; i=1 \to k-1,\; j=1 \to n</math>.

Повторюємо дії для матриці І, за формулою <math>b_{is}^{k-1}=b_{is}^{k-1}-b_{is}^k a_{ik}^i</math>, за умови, що <math>k=n \to 1,\; i=1 \to k-1,\; s=1 \to n</math>.

Остаточно отримуємо:

: <math>
  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}
</math>

== Приклад ==

Розв'яжемо систему рівнянь:
: <math>\left\{\begin{array}{ccccccl}
a &+& b &+& c &=& 0\\
4a &+& 2b &+& c &=& 1\\
9a &+& 3b &+& c &=& 3 \end{array}\right.
</math>

Запишемо її у вигляді матриці 3&times;4, де останній стовпчик є вільним членом:
: <math>
  \begin{pmatrix}
    1 & 1 & 1 & | & 0 \\
    4 & 2 & 1 & | & 1 \\
    9 & 3 & 1 & | & 3
  \end{pmatrix}
</math>

Виконаємо такі дії:
* До рядка 2 додамо: -4 * рядок 1.
* До рядка 3 додамо: -9 * рядок 1.

Отримаємо:
: <math>
  \begin{pmatrix}
    1 &\  1 &\  1 & | & 0 \\
    0 & -2 & -3 & | & 1 \\
    0 & -6 & -8 & | & 3
  \end{pmatrix}
</math>

* До рядка 3 додамо: -3 * рядок 2.
* Рядок 2 ділимо на -2

: <math>
  \begin{pmatrix}
    1 &  1 &  1 & | &\ 0 \\
    0 & 1 & {3 \over 2} & | & -{1 \over 2} \\
    0 & 0 & 1 & | &\ 0
  \end{pmatrix}
</math>

* До рядка 1 додамо: -1 * рядок 3.
* До рядка 2 додамо: -3/2 * рядок 3.

: <math>
  \begin{pmatrix}
    1 & 1 & 0 & | &\ 0 \\
    0 & 1 & 0 & | & -{1 \over 2} \\
    0 & 0 & 1 & | &\ 0
  \end{pmatrix}
</math>

* До рядка 1 додамо: -1 * рядок 2.

: <math>
  \begin{pmatrix}
    1 & 0 & 0 & | &\ {1 \over 2} \\
    0 & 1 & 0 & | & -{1 \over 2} \\
    0 & 0 & 1 & | &\ 0
  \end{pmatrix}
</math>

У правому стовпчику отримаємо рішення:
: <math>a = \frac{1}{2} \; ; \ b = -\frac{1}{2} \; ; \ c = 0</math> .

== Джерела ==
* {{Гантмахер.Теорія матриць}}
* {{Гельфанд.Линейная алгебра}}
* {{Мальцев.Основы линейной алгебры}}
* Рокіцький І.&nbsp;О.&nbsp;Застосування лінійної алгебри // І.&nbsp;О.&nbsp;Рокіцький, О.&nbsp;Б.&nbsp;Панасенко.&nbsp;— Вінниця: Вид. Главацька Р. В., 2012.&nbsp;— С. 144

== Посилання ==
* Lipschutz, Seymour, and Lipson, Mark. «Schaum's Outlines: Linear Algebra». Tata McGraw-hill edition. Delhi 2001. pp. 69-80.
* [https://web.archive.org/web/20070402231833/http://users.powernet.co.uk/kienzle/octave/matcompat/scripts/linear-algebra/rref.m Algorithm for Gauss-Jordan elimination in Matlab]
* [http://elonen.iki.fi/code/misc-notes/python-gaussj/index.html Algorithm for Gauss-Jordan elimination in Python]

[[Категорія:Методи розв'язку СЛАР|Г]]