Запутался в разложении Eigen QR

Я запутался в QR-разложении Эйгена. Насколько я понимаю, матрица Q хранится неявно как последовательность преобразований Хаусхолдера, а матрица R хранится как верхняя треугольная матрица, и что диагональ R содержит собственные значения A (по крайней мере, до фазы, которая равна все, что меня волнует).

Однако я написал следующую программу, которая вычисляет собственные значения матрицы A двумя разными методами: один использует Eigen::EigenSolver, а другой — QR. Я знаю, что мой метод QR возвращает неправильные результаты, а метод EigenSolver возвращает правильные результаты.

Что я здесь неправильно понимаю?

#include <iostream>
#include <algorithm>
#include <Eigen/Dense>

int main()
{
    using Real = long double;
    long n = 2;
    Eigen::Matrix<Real, Eigen::Dynamic, Eigen::Dynamic> A(n,n);

    for(long i = 0; i < n; ++i) {
        for (long j = 0; j < n; ++j) {
            A(i,j) = Real(1)/Real(i+j+1);
        }
    }

    auto QR = A.householderQr();

    auto Rdiag = QR.matrixQR().diagonal().cwiseAbs();
    auto [min, max] = std::minmax_element(Rdiag.begin(), Rdiag.end());
    std::cout << "\u03BA\u2082(A) = " << (*max)/(*min) << "\n";

    std::cout << "\u2016A\u2016\u2082 via QR = " << (*max) << "\n";
    std::cout << "Diagonal of R =\n" << Rdiag << "\n";


    // dblcheck:

    Eigen::SelfAdjointEigenSolver<decltype(A)> eigensolver(A);
    if (eigensolver.info() != Eigen::Success) {
        std::cout << "Something went wrong.\n";
        return 1;
    }
    auto absolute_eigs = eigensolver.eigenvalues().cwiseAbs();
    auto [min1, max1] = std::minmax_element(absolute_eigs.begin(), absolute_eigs.end());
    std::cout << "\u03BA\u2082(A) via eigensolver = " << (*max1)/(*min1) << "\n";
    std::cout << "\u2016A\u2016\u2082 via eigensolver = " << (*max1) << "\n";
    std::cout << "The absolute eigenvalues of A via eigensolver are:\n" << absolute_eigs << "\n";
}

Выход:

κ₂(A) = 15
‖A‖₂ via QR = 1.11803
Diagonal of R =
  1.11803
0.0745356
κ₂(A) via eigensolver = 19.2815
‖A‖₂ via eigensolver = 1.26759
The absolute eigenvalues of A via eigensolver are:
0.0657415
  1.26759

Другая информация:

  • Клонированный эйген из головы:
$ hg log | more
changeset:   11993:20cbc6576426
tag:         tip
date:        Tue May 07 16:44:55 2019 -0700
summary:     Fix AVX512 & GCC 6.3 compilation
  • Возникает при компиляции с помощью g++-8, g++-9 и Apple Clang с -ffast-math и без него. Я получаю тот же неправильный результат с Eigen::FullPivHouseholderQR.

  • Я также заглянул в источник HouseholderQR.h, и они вычисляют определитель через m_qr.diagonal().prod(), что придает мне уверенности в том, что я правильно использую API. Взятие произведения собственных значений из EigenSolver возвращает те же значения, что и QR.absDeterminant().

  • Следующий фрагмент кода не возвращает исходную матрицу A:

Eigen::Matrix<Real, Eigen::Dynamic, Eigen::Dynamic> R = QR.matrixQR();
Eigen::Matrix<Real, Eigen::Dynamic, Eigen::Dynamic> Q = QR.householderQ();
std::cout << "Q*R = \n" << Q*R << "\n";
  • Я проверил, что Q обладает всеми необходимыми свойствами: Q^-1 = Q^T, Q^TQ = I и |det(Q)| = 1.

  • Я также проверил, что QR.householderQ().transpose()*QR.matrixQR() не равно A; хотя один столбец правильный, а другой неправильный.

Я не знаю Эйгена. Но QR-разложение не дает вам собственных значений. Требуется дальнейшая обработка, чтобы получить собственные значения из QR-разложения. Просто произведение диагоналей является определителем (потому что R треугольное, а Q имеет определитель плюс/минус один).

geza 08.05.2019 23:07

@geza: ты прав. Вероятно, следует удалить этот вопрос.

user14717 08.05.2019 23:17
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
4
2
2 085
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Как указал @geza, матрица R QR-разложения (в общем случае) не будет содержать собственные значения исходной матрицы, жизнь была бы слишком легкой, если бы это было так :)

К другой вашей проблеме, если вы хотите восстановить A из Q и R, вам нужно только посмотреть на верхнюю треугольную часть QR.matrixQR()

Eigen::Matrix<Real, Eigen::Dynamic, Eigen::Dynamic>
              R = QR.matrixQR().triangularView<Eigen::Upper>();

Кроме того, я бы посоветовал быть осторожным с использованием auto в сочетании с шаблонами выражений (в вашем случае нет ничего серьезного, за исключением того, что Rdiag оценивается как минимум дважды).

Кроме того, использование long double едва ли является хорошей идеей на современных процессорах. Сначала убедитесь, что используемые вами алгоритмы численно стабильны, и если точность действительно является проблемой, рассмотрите возможность использования чисел с плавающей запятой произвольной точности (например, MPFR).

Другие вопросы по теме