Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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>>``
```c++
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`-разложению может быть вычислен так:
```c++
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;
}
```
Начало
Рабочее место участника
Учебные задачи: АиСД. Полиномы, матрицы