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

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

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

Алгоритм[править | править код]

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

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

Пусть дано:

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

  • Разделим первую строку матрицы А на получим: , j — столбец матрицы А.
  • Повторяем действия для матрицы I, по формуле: , s — столбец матрицы I
Получим:
  • Будем образовывать 0 в первом столбце :
  • Повторяем действия для матрицы І, по формулам :
Получим:
  • продолжаем выполнять аналогичные операции, используя формулы :
при условии, что
  • Повторяем действия для матрицы І, по формулам :
при условии, что
Получим :

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

Используем формулу: , при условии, что

Повторяем действия для матрицы І, по формуле : , при условии, что

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

Пример[править | править код]

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

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

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

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

Получим:

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

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

.

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

 1 namespace Gauss_Jordan_Method
 2 {
 3     class Maths
 4     {
 5         /// <summary>
 6         /// Метод Гаусса-Жордана (Обратная матрица)
 7         /// </summary>
 8         /// <param name="Matrix">Начальная матрица</param>
 9         /// <returns></returns>
10         public static double[,] GaussJordan(double[,] Matrix)
11         {
12             int n = Matrix.GetLength(0); //Размерность начальной матрицы
13  
14             double[,] xirtaM = new double[n, n]; //Единичная матрица (искомая обратная матрица)
15             for (int i = 0; i < n; i++)
16                 xirtaM[i, i] = 1;
17  
18             double[,] Matrix_Big = new double[n, 2*n]; //Общая матрица, получаемая скреплением Начальной матрицы и единичной
19             for (int i = 0; i < n; i++)
20                 for (int j = 0; j < n; j++)
21                 {
22                     Matrix_Big[i, j] = Matrix[i, j];
23                     Matrix_Big[i, j + n] = xirtaM[i, j];
24                 }
25  
26             //Прямой ход (Зануление нижнего левого угла)
27             for (int k = 0; k < n; k++) //k-номер строки
28             {
29                 for (int i = 0; i < 2*n; i++) //i-номер столбца
30                     Matrix_Big[k, i] = Matrix_Big[k, i] / Matrix[k, k]; //Деление k-строки на первый член !=0 для преобразования его в единицу
31                 for (int i = k + 1; i < n; i++) //i-номер следующей строки после k
32                 {
33                     double K = Matrix_Big[i, k] / Matrix_Big[k, k]; //Коэффициент
34                     for (int j = 0; j < 2*n; j++) //j-номер столбца следующей строки после k
35                         Matrix_Big[i, j] = Matrix_Big[i, j] - Matrix_Big[k, j] * K; //Зануление элементов матрицы ниже первого члена, преобразованного в единицу
36                 }
37                 for (int i = 0; i < n; i++) //Обновление, внесение изменений в начальную матрицу
38                     for (int j = 0; j < n; j++)
39                         Matrix[i, j] = Matrix_Big[i, j];
40             }
41             
42             //Обратный ход (Зануление верхнего правого угла)
43             for (int k = n - 1; k > -1; k--) //k-номер строки
44             {
45                 for (int i = 2*n - 1; i > -1; i--) //i-номер столбца
46                     Matrix_Big[k, i] = Matrix_Big[k, i] / Matrix[k, k];
47                 for (int i = k - 1; i > -1; i--) //i-номер следующей строки после k
48                 {
49                     double K = Matrix_Big[i, k] / Matrix_Big[k, k];
50                     for (int j = 2*n - 1; j > -1; j--) //j-номер столбца следующей строки после k
51                         Matrix_Big[i, j] = Matrix_Big[i, j] - Matrix_Big[k, j] * K;
52                 }
53             }
54  
55             //Отделяем от общей матрицы
56             for (int i = 0; i < n; i++)
57                 for (int j = 0; j < n; j++)
58                     xirtaM[i, j] = Matrix_Big[i, j + n];
59  
60             return xirtaM;        
61         }
62     }
63 }

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

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

Литература[править | править код]

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

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

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