Как я могу получить собственные значения и собственные векторы быстро и точно?
Мне нужно вычислить собственные значения и собственные векторы большой матрицы (около 1000 * 1000 или даже больше). Matlab работает очень быстро, но не гарантирует точности. Мне нужно, чтобы это было довольно точно (ошибка 1e-06 в порядке) и в течение разумного времени (час или два в порядке).
Моя матрица симметрична и довольно редка. Точные значения: по диагонали, по диагонали под главной диагональю и по диагонали над ней. Пример:
Пример матрицы http://img692.imageshack.us/img692/2269/zb2u.png
Как я могу это сделать? С ++ для меня самый удобный.
Решение
Ваша система трехдиагональная и (симметричный) Матрица Теплица. Я предполагаю, что Эйген и Матлаб eig есть особые случаи для обработки таких матриц. Eсть решение в замкнутой форме для собственных значений в этом случае (ссылка (PDF)). В Matlab для вашей матрицы это просто:
n = size(A,1);
k = (1:n).';
v = 1-2*cos(pi*k./(n+1));
Это может быть дополнительно оптимизировано, если заметить, что собственные значения сосредоточены вокруг 1 и, следовательно, нужно вычислить только половину из них:
n = size(A,1);
if mod(n,2) == 0
k = (1:n/2).';
u = 2*cos(pi*k./(n+1));
v = 1+[u;-u];
else
k = (1:(n-1)/2).';
u = 2*cos(pi*k./(n+1));
v = 1+[u;0;-u];
end
Я не уверен, как вы собираетесь получить более быстрый и точный результат (кроме выполнения этапа уточнения с использованием собственных векторов и оптимизации) с помощью простого кода. Вышесказанное должно быть очень легко переведено на C ++ (или использовать Matlab’s codgen генерировать код C / C ++, который использует это или eig). Тем не менее, ваша матрица все еще плохо подготовлена. Просто помните, что оценки точности являются худшим случаем.
Другие решения
Если вы не против использования сторонней библиотеки, я имел большой успех при использовании броненосец библиотеки линейной алгебры.
Для примера ниже arma это пространство имен, которое они любят использовать, vec это вектор, mat это матрица
arma::vec getEigenValues(arma::mat M) {
return arma::eig_sym(M);
}
Вы также можете сериализовать данные непосредственно в MATLAB и наоборот.
MATLAB не гарантирует точность
Я считаю это требование необоснованным. На каком основании вы говорите, что вы можете найти (значительно) более точную реализацию, чем высокоразвитые вычислительные алгоритмы MATLAB?
И … используя MATLAB eig, следующее вычисляется менее чем за полсекунды:
%// Generate the input matrix
X = ones(1000);
A = triu(X, -1) + tril(X, 1) - X;
%// Compute eigenvalues
v = eig(A);
Это быстро хорошо!
Мне нужно, чтобы это было довольно точно (ошибка 1e-06 в порядке)
Помните, что точное определение собственных значений связано с нахождением корней характеристического полинома. Эта конкретная матрица 1000×1000 очень неупитанный:
>> cond(A)
ans =
1.6551e+003
Общее правило это для условия номер 10К, Вы можете потерять до К цифры точности (вдобавок к тому, что будет потеряно в численном методе из-за потери точности в арифметическом методе).
Так что в вашем случае, я ожидаю, что результаты будут точными до приблизительной ошибки 10-3.