03/04/2025 11:52:09

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2763. LU-разложение

Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Написать функции, выполняющие $LU$ -разложение матрицы и решение системы уравнений через $LU$ -разложение.

Верхнетреугольная матрица $U$ представляет собой результат исключения, а нижнетреугольную матрицу $L$ образована единицами на главной диагонали и множителями, вычисляемыми в процессе исключения Гаусса для обнуления соответствующих коэффициентов в строках матрицы. Эти матрицы можно хранить одновременно в исходной матрице $A$ , так как диагональные элементы $L$ равные 1 можно не сохранять.

LU-разложение без перестановок строк матрицы существует, только если все ведущие (угловые) главные миноры матрицы невырождены. Поэтому для предотвращения случая, когда a_{ii}=0 и для уменьшения ошибки вычислений рекомендуется выбирать строку с наибольшим абсолютным значением коэффициента в $i$ -ом столбце для обмена с $i$ -ой строкой, а затем использовать ее в качестве опорной на $i$ -ой итерации.

Вектор $P$ должен содержать информацию о перестановках строк в процессе исключения Гаусса, чтобы применить ее к столбцу свободных членов $b$ (метод исключения Гаусса выполняет действия над матрицей $n xx (n+1)$ , включающей свободные члены $b$ , а при LU-разложении столбец $b$ указывается позже).

Матрицы представлены как vector<vector<double>>

void LUdecomp(vector<vector<double>>&A, vector<int>& P);
vector<double> LUsolve(const vector<vector<double>&LU, vector<int>& P, const vector<double>& b);

Если кроме вектора $P$ подсчитать количество выполненных перестановок (inv=1, если количество перестановок нечетно), то определитель матрицы по $LU$ -разложению может быть вычислен так:

double LUdeterm(const vector<vector<double>>&LU, bool inv) {
    double det =inv?-1:1;
    for (int i = 0; i < LU.size(); i++)
        det *= LU[i][i];
    return det;
}