MAXimal | |
добавлено: 5 Jul 2008 21:03 Содержание [скрыть] Нахождение ранга матрицыРанг матрицы - это наибольшее число линейно независимых строк/столбцов матрицы. Ранг определён не только для квадратных матриц; пусть матрица прямоугольна и имеет размер NxM. Также ранг матрицы можно определить как наибольший из порядков миноров матрицы, отличных от нуля. Заметим, что если матрица квадратная и её определитель отличен от нуля, то ранг равен N(=M), иначе он будет меньше. В общем случае, ранг матрицы не превосходит min(N,M). АлгоритмИскать ранг можно с помощью модифицированного метода Гаусса. Будем выполнять абсолютно те же самые операции, что и при решении системы или нахождении её определителя, но если на каком-либо шаге в i-ом столбце среди невыбранных до этого строк нет ненулевых, то мы этот шаг пропускаем, а ранг уменьшаем на единицу (изначально ранг полагаем равным max(N,M)). Иначе, если мы нашли на i-ом шаге строку с ненулевым элементом в i-ом столбце, то помечаем эту строку как выбранную, и выполняем обычные операции отнимания этой строки от остальных. Реализацияconst double EPS = 1E-9; int rank = max(n,m); vector<char> line_used (n); for (int i=0; i<m; ++i) { int j; for (j=0; j<n; ++j) if (!line_used[j] && abs(a[j][i]) > EPS) break; if (j == n) --rank; else { line_used[j] = true; for (int p=i+1; p<m; ++p) a[j][p] /= a[j][i]; for (int k=0; k<n; ++k) if (k != j && abs (a[k][i]) > EPS) for (int p=i+1; p<m; ++p) a[k][p] -= a[j][p] * a[k][i]; } }
|