Приведение матрицы к треугольному виду. Метод Гаусса

   Дана матрица n x m.
   Необходимо с помощью следующих операций:

Поменять местами две строки

Прибавить к одной строке другую строку, умноженную на некоторое число

получить матрицу, у которой левая нижняя часть относительно главной диагонали нулевая.

   Поставим на место первой строки такую строку матрицы, у которой первый элемент не равен нулю. Вычтем из всех остальных строк матрицы первую строку так, чтобы их первые элементы занулились. Решим эту же задачу для подматрицы [2..n][2..m], потом для подматрицы [3..n][3..m] и так далее. В результате получим искомую матрицу.
   Асимптотика O(N³).
   Реализацию класса matrix смотрите здесь.

Листинг C++

// приведение матрицы к треугольному виду, метод Гаусса с главным элементом
matrix gauss (matrix & a)
{
   int i, j, k;
   int countSwaps = 1;
   matrix c = a;
   for (i = 0; i < a.N (); ++ i)
   {
      // находим строку с максимальным первым элементом
      int iMax = i;
      for (j = i + 1; j < a.N (); ++ j)
         if (abs (c[j][i]) > abs (c[iMax][i]))
            iMax = j;
      if (abs (c[iMax][i]) < eps)
         continue;
      for (k = 0; k < a.M (); ++ k)
         swap (c[i][k], c[iMax][k]);
      countSwaps = - countSwaps * (i != iMax ? 1 : - 1);

      //  вычитаем текущую строку из всех остальных
      for (j = i + 1; j < a.N (); ++ j)
      {
         double q = - c[j][i] / c[i][i];
         for (k = a.M () - 1; k >= i; -- k)
            c[j][k] += q * c[i][k];
      }
   }
   // умножаем матрицу на -1, если мы сделали нечётное количество перестановок строк
   // в итоге определитель результирующей матрицы будет равен определителю начальной матрицы
   return mul (c, countSwaps);
}

Создана 16:19 04.01.2011
Изменена 16:19 04.01.2011

По всем вопросам обращаться: rumterg@gmail.com