Как быстро и точно получить собственные значения и собственные векторы?

Ваша система трехдиагональная и (симметричная) Теплицевая матрица. Я предполагаю, что у eigen и Matlab eig есть особые случаи для обработки таких матриц. В этом случае существует решение для собственных значений (ссылка (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++ (или использовать codgen для создания кода C/C++, использующего this или eig). Однако ваша матрица все еще плохо обусловлена. Просто помните, что оценки точности являются наихудшим случаем.

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 x 1000 очень плохо обусловлена:

>> cond(A)

ans =
    1.6551e+003

Общее практическое правило заключается в том, что для числа условия 10^{k< /i>}, вы можете потерять до k цифр точности (помимо того, что было бы потеряно для численного метода из-за потери точности арифметического метода).