Решение СЛАУ методом LU разложения

[holloloh]

При каких условиях возможно LU разложение матрицы A?
Я прочитал некоторое количество книжек/ресурсов и получил, что
1)Главные миноры не должны быть равны нулю
2)элементы на главной диагонали матрицы А не равны нулю
3)Матрица должна быть невырожденной
Каким условием пользоваться?
Проще всего пользоваться вторым, но я не уверен, что это правда...

[Белый кролик]

Теорема.Если все главные миноры квадратной матрицы А отличны от нуля, то существуют такие нижняя L и верхняя U треугольные матрицы,что А=LU.Если элементы диагонали одной из матриц L или U фиксированы(ненулевые), то такое разложение единственно.
Из книжки В.М. Вержбицкий "Численные методы. Линейная алгебра и нелинейные уравнения",  Москва,"Издательский дом "ОНИКС 21 век", 2005 год.
Скачать книжки по численным методам www.poiskknig.ru

[holloloh]

Вержбицкий конечно прекрасная книга, но давайте прикинем время работы алгоритма.
Для того, чтобы найти определитель минора, мы раскладываем его по строке пока миноры не станут второго (в крайнем случае третьего или четвертого) порядка.
Пусть O(n) время работы алгоритма, n - длина строки, по которой раскладываем
О(2) = 1 - просто возвращаем результат
Тогда
O(n) = n*O(n - 1) = n*(n - 1)O(n-2) = ... =  n!/2*O(2) = n!/2
Это очень грубая оценка, но тенденция видна.
Вы мне предлагаете проверить, что все главные миноры не равны нулю.
У меня проверка на то, что алгоритм работает будет дольше, чем работа самого алгоритма
+он рекурсивен, и боюсь стек провалится очень быстро.
Что делать?

[holloloh]

Основную мысль Вержбицкого я понял так:
"На миноры не смотрим, просто проверяем, что Uii != 0", что по мне не очень хорошо, особенно если Unn = 0, а матрица размера 100x100

[Белый кролик]

Может вы сформулируете задачу целиком?

[Белый кролик]

что Uii != 0", Unn = 0

Это что такое вы написали?
Я так понял,вам нужен очень простой и очень быстрый способ определения возможности разложения ну очень большой матрицы?

[BcegoqpeHu]

Ну проверять главные миноры на равенство нулю мне тоже кажется не слишком быстрое решение. Проверять элементы главной диагонали не пойдёт.
Пример.
0 2 3
4 0 6
7 8 0
Меняем 1 и 2 строки и матрица:
4 0 6
0 2 3
7 8 0
уже имеет LU разложение.
То, что матрица должна быть невырождена это само собой разумеется, но этого недостаточно.

ИМХО. Первое, что приходит в голову:
проверить элемент (0,0) на равенство нулю и побаловаться с перестановкой строк. А затем в процессе разложения на матрицы L и U проверять делитель на ноль. Если он равен нулю, то разложения не существует. Но есть большой риск, что с некоторыми матрицами это всё не получится.