Как решить линейную систему квадратной матрицы в C ++, когда матрица не имеет LU-разложения?

Question

Я пытался разработать программу для решения системы Ax = b для квадратной матрицы A с использованием LU-декомпозиции.Однако я понял, что такая декомпозиция не всегда существует (можно сказать, что если операция обмена строк не требуется, то она существует).Однако из многих источников я вижу, что это отличный метод для вычисления решений Ax = b.

Мой вопрос: как часто встречается матрица, не имеющая LU-разложения??Если кто-то сталкивается с такой матрицей, как он должен справиться с этим?Должен ли он создать отдельный метод, такой как метод исключения Гаусса на всякий случай?

Пожалуйста, дайте мне некоторое представление об этом.Заранее спасибо.

Примечание: я пытаюсь использовать эту информацию для решения A ^ TAx = A ^ Tb, т.е. найти математическую модель с использованием метода наименьших квадратов.

Answer 1

Взято из википедии в самой краткой форме

Любая квадратная матрица $ A $ допускает факторизацию LUP.Если $ A $ обратимо, то оно допускает факторизацию LU (или LDU) тогда и только тогда, когда все его главные старшие миноры ненулевые.Если $ A $ - особая матрица ранга $ k $, то она допускает факторизацию LU, если первые $ k $ старших главных миноров не равны нулю, хотя обратное неверно.

У меня нет полностью написанной реализации, но это выглядит сложным.Я думаю, что в зависимости от вашей матрицы существуют более простые числовые схемы, которые сокращают ваше решение.

Как часто вы сталкиваетесь с таким?Ну, никто не имеет ни малейшего представления о том, что вы делаете, так что это невозможно ответить.Если вы столкнулись с таким, переключитесь на другую схему.

Одна из тех, которые я часто использовал на практике, - это Гаусс-Зайдель.На самом деле Википедия имеет полностью написанную схему.

Answer 2

LU-разложения существуют тогда и только тогда, когда все ведущие главные миноры матрицы ненулевые.

Исходя из вашего фактического вопроса, вы решаете:

A^TAx=A^T

A^TA - квадратная симметричная матрица.Мы можем по диагонали матрицы: A = R^-1 D R, и вы всегда можете переставить ее, чтобы найти x.Вам нужно ненулевые собственные значения, чтобы это работало.

(квадратная) матрица обратима тогда и только тогда, когда она не имеет нулевого собственного значения.

Я думаю, что инверсия с помощью исключения Гаусса может быть лучшим решением.