Я использовал разные методы для вычисления как ранга матрицы, так и решения матричной системы уравнений. Я наткнулся на функцию linalg.svd. Сравнивая это с моими собственными усилиями по решению системы с устранением по Гауссу, она кажется более быстрой и точной. Я пытаюсь понять, как это возможно.
Насколько я знаю, функция linalg.svd использует алгоритм QR для вычисления собственных значений моей матрицы. Я знаю, как это работает математически, но я не знаю, как Numpy удается сделать это так быстро и без потери точности.
Итак, мой вопрос: как работает функция numpy.svd, а точнее, как ей удается делать это быстро и точно (по сравнению с устранением по Гауссу)?
linear-algebra
python
lapack
RobVerheyen
источник
источник
dgesddЛапака для настоящих SVD. Итак, ваш реальный вопрос, вероятно, «как работает Lapack dgesdd?», И это довольно неуместно для stackoverflow.Ответы:
В вашем вопросе есть ряд вопросов.
Не используйте метод исключения Гаусса (LU-факторизация) для вычисления числового ранга матрицы. Факторизация LU для этой цели ненадежна в арифметике с плавающей точкой. Вместо этого используйте раскрывающую ранг QR-декомпозицию (например,
xGEQPXилиxGEPQYв LAPACK, где x - это C, D, S или Z, хотя эти подпрограммы трудно отследить; см . Ответ JedBrown на связанный вопрос ), или используйте SVD (разложение по единственному значению, такое какxGESDDилиxGESVD, где x снова является C, D, S или Z). SVD - более точный и надежный алгоритм определения числового ранга, но он требует больше операций с плавающей запятой.Однако для решения линейной системы факторизация LU (с частичным поворотом, которая является стандартной реализацией в LAPACK) чрезвычайно надежна на практике. Существуют некоторые патологические случаи, когда LU-факторизация с частичным поворотом неустойчива (см. Лекцию 22 в Числовой линейной алгебреТрефетен и Бау для деталей). QR-факторизация - это более стабильный численный алгоритм для решения линейных систем, поэтому, вероятно, он дает вам такие точные результаты. Однако для квадратных матриц требуется больше операций с плавающей запятой, чем для факторизации LU в 2 раза (я полагаю, Джекпулсон может меня поправить). Для прямоугольных систем QR-факторизация является лучшим выбором, поскольку она даст решения методом наименьших квадратов для переопределенных линейных систем. SVD также можно использовать для решения линейных систем, но это будет дороже, чем QR-факторизация.
Яннеб прав, что numpy.linalg.svd - это обертка
xGESDDв LAPACK. Разложение по сингулярным значениям происходит в два этапа. Во-первых, матрица, подлежащая разложению, приводится к двухдиагональной форме. Алгоритм, используемый для преобразования в двуугольную форму в LAPACK, вероятно, является алгоритмом Лоусона-Хансона-Чана, и он действительно использует QR-факторизацию в одной точке. Лекция 31 в Числовой линейной алгебре Трефетена и Бау дает обзор этого процесса. ЗатемxGESDDиспользуется алгоритм «разделяй и властвуй» для вычисления сингулярных значений, а также левого и правого сингулярных векторов из двухдиагональной матрицы. Чтобы получить представление об этом шаге, вам нужно обратиться к Матричным вычислениям Голуба и Ван Лоана или Прикладной числовой линейной алгебре Джима Деммеля.Наконец, не следует путать единичные значения с собственными значениями . Эти два набора величин не одинаковы. SVD вычисляет сингулярные значения матрицы. Числовые вычисления Клива Молера с MATLAB дают хороший обзор различий между единичными значениями и собственными значениями . В общем, не существует очевидной связи между сингулярными значениями данной матрицы и ее собственными значениями, за исключением случая нормальных матриц, где особые значения являются абсолютным значением собственных значений.
источник
rankфункции). При использовании любого из подходов также требуется немного осмотрительности; в подходе SVD числовой ранг - это число сингулярных значений выше определенного (обычно очень малого) предела. (Подход QR аналогичен, но заменяет сингулярные значения диагональными элементами матрицы R.)Из-за формулировки вашего вопроса, я предполагаю, что ваша матрица квадратная. Подпрограммы LAPACK SVD, такие как zgesvd , по существу, выполняются в три этапа для квадратных матриц:
источник
numpy.linalg.svd - это оболочка вокруг {Z, D} GESDD из LAPACK. LAPACK, в свою очередь, очень тщательно написан ведущими экспертами в области численной линейной алгебры. В самом деле, было бы очень удивительно, если бы кто-то, не очень хорошо знакомый с полем, смог победить LAPACK (ни по скорости, ни по точности).
Что касается того, почему QR лучше, чем устранение по Гауссу, это, вероятно, больше подходит для /scicomp//
источник