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

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

Алгоритм

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

Расширенный алгоритм для нахождения обратной матрицы

Пусть дано:

$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right)a_{11}\ne 0I=\left(\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)$

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

• Разделим первую строку матрицы А на $a_{11}$ получим: $a_{1j}^1=\frac{a_{1j}}{a_{11}}$, j — столбец матрицы А.
• Повторяем действия для матрицы I, по формуле: $b_{1s}^1=\frac{b_{1s}}{a_{11}}$, s — столбец матрицы I

Получим:

$A=\left(\begin{array}{cccc}1& a_{12}^1& \cdots & a_{1n}^1\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right)I=\left(\begin{array}{cccc}{b}_{11}^1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)$

• Будем образовывать 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=\left(\begin{array}{cccc}1& a_{12}^1& \cdots & a_{1n}^1\\ 0& a_{22}^1& \cdots & a_{2n}^1\\ ⋮& ⋮& \ddots & ⋮\\ 0& a_{n2}^1& \cdots & a_{nn}^1\end{array}\right)I=\left(\begin{array}{cccc}{b}_{11}^1& 0& \cdots & 0\\ b_{21}^1& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ b_{n1}^1& 0& \cdots & 1\end{array}\right)$

• продолжаем выполнять аналогичные операции, используя формулы : $a_{ij}^k=\frac{a_{ij}^k}{a_{ii}}{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}}{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=\left(\begin{array}{cccc}1& a_{12}^1& \cdots & a_{1n}^1\\ 0& 1& \cdots & a_{2n}^2\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)I=\left(\begin{array}{cccc}{b}_{11}^1& 0& \cdots & 0\\ b_{21}^2& b_{22}^2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ b_{n1}^n& b_{n2}^n& \cdots & b_{nn}^n\end{array}\right)$

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

Используем формулу: $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=\left(\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)I=A^{-1}$

Пример

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

$\{\begin{array}{ccccccc}a& +& b& +& c& =& 0\\ 4a& +& 2b& +& c& =& 1\\ 9a& +& 3b& +& c& =& 3\end{array}$

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

$\left(\begin{array}{ccccc}1& 1& 1& |& 0\\ 4& 2& 1& |& 1\\ 9& 3& 1& |& 3\end{array}\right)$

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

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

Получим:

$\left(\begin{array}{ccccc}1& 1& 1& |& 0\\ 0& -2& -3& |& 1\\ 0& -6& -8& |& 3\end{array}\right)$

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

$\left(\begin{array}{ccccc}1& 1& 1& |& 0\\ 0& 1& \frac{3}{2}& |& -\frac{1}{2}\\ 0& 0& 1& |& 0\end{array}\right)$

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

$\left(\begin{array}{ccccc}1& 1& 0& |& 0\\ 0& 1& 0& |& -\frac{1}{2}\\ 0& 0& 1& |& 0\end{array}\right)$

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

$\left(\begin{array}{ccccc}1& 0& 0& |& \frac{1}{2}\\ 0& 1& 0& |& -\frac{1}{2}\\ 0& 0& 1& |& 0\end{array}\right)$

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

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

Реализация алгоритма на языке программирования C#

namespace Gauss_Jordan_Method
{
    class Maths
    {
        /// <summary>
        /// Метод Гаусса-Жордана (Обратная матрица)
        /// </summary>
        /// <param name="Matrix">Начальная матрица</param>
        /// <returns></returns>
        public static double[,] GaussJordan(double[,] Matrix)
        {
            int n = Matrix.GetLength(0); //Размерность начальной матрицы

            double[,] xirtaM = new double[n, n]; //Единичная матрица (искомая обратная матрица)
            for (int i = 0; i < n; i++)
                xirtaM[i, i] = 1;

            double[,] Matrix_Big = new double[n, 2*n]; //Общая матрица, получаемая скреплением Начальной матрицы и единичной
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                {
                    Matrix_Big[i, j] = Matrix[i, j];
                    Matrix_Big[i, j + n] = xirtaM[i, j];
                }

            //Прямой ход (Зануление нижнего левого угла)
            for (int k = 0; k < n; k++) //k-номер строки
            {
                for (int i = 0; i < 2*n; i++) //i-номер столбца
                    Matrix_Big[k, i] = Matrix_Big[k, i] / Matrix[k, k]; //Деление k-строки на первый член !=0 для преобразования его в единицу
                for (int i = k + 1; i < n; i++) //i-номер следующей строки после k
                {
                    double K = Matrix_Big[i, k] / Matrix_Big[k, k]; //Коэффициент
                    for (int j = 0; j < 2*n; j++) //j-номер столбца следующей строки после k
                        Matrix_Big[i, j] = Matrix_Big[i, j] - Matrix_Big[k, j] * K; //Зануление элементов матрицы ниже первого члена, преобразованного в единицу
                }
                for (int i = 0; i < n; i++) //Обновление, внесение изменений в начальную матрицу
                    for (int j = 0; j < n; j++)
                        Matrix[i, j] = Matrix_Big[i, j];
            }

            //Обратный ход (Зануление верхнего правого угла)
            for (int k = n - 1; k > -1; k--) //k-номер строки
            {
                for (int i = 2*n - 1; i > -1; i--) //i-номер столбца
                    Matrix_Big[k, i] = Matrix_Big[k, i] / Matrix[k, k];
                for (int i = k - 1; i > -1; i--) //i-номер следующей строки после k
                {
                    double K = Matrix_Big[i, k] / Matrix_Big[k, k];
                    for (int j = 2*n - 1; j > -1; j--) //j-номер столбца следующей строки после k
                        Matrix_Big[i, j] = Matrix_Big[i, j] - Matrix_Big[k, j] * K;
                }
            }

            //Отделяем от общей матрицы
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    xirtaM[i, j] = Matrix_Big[i, j + n];

            return xirtaM;        
        }
    }
}

Литература

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation

Ссылки

• Algorithm for Gauss-Jordan elimination in PythonШаблон:Ref-en
• Шаблон:Cite web