Ошибка с плавающей запятой в вычислении матрицы Ruby

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

Например, следующая матрица имеет собственный вектор, связанный с собственным значением 1:

> m = Matrix[[0r, 1/2r, 1/2r, 1/3r],
             [0r,  0r,  1/4r, 1/3r],
             [0r, 1/4r,  0r,  1/3r],
             [1r, 1/4r, 1/4r,  0r]]

Ruby находит собственные значения достаточно хорошо, но собственный вектор взрывается:

> m.eigen.eigenvalues[2]
=> 1.0000000000000009

m.eigen.eigenvectors[2]
=> Vector[5.957702309312754e+15, 5.957702309312748e+15, 5.957702309312743e+15, 5.957702309312753e+15]

Фактический собственный вектор должен быть (7, 4, 4, 9).

Разве это не тревожит? Если Ruby не справится с крошечными матрицами, то как мы можем доверять ему вообще? Или я делаю что-то неправильно?

Ответ 1

Нет, это не беспокоит. Эта матрица, вероятно, просто не работает с этой конкретной реализацией алгоритма собственного вектора. Эффективное и стабильное вычисление общего собственного вектора, в конце концов, нетривиально.

Библиотека Matrix адаптирована из Java-пакета JAMA, в котором говорится, что она выполняет числовые вычисления, а не символьные вычисления:

Не распространяется. JAMA ни в коем случае не является полной средой линейной алгебры... она сосредоточена на принципе математической функциональности, необходимой для выполнения числовой линейной алгебры

Алгоритм QR: численные расчеты

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

На k-м шаге (начиная с k = 0) мы вычисляем QR-разложение A _k= Q _k R _k... При определенных условиях ^[4] матрицы A _k сходятся к треугольной матрице, форме Шура A. Собственные значения треугольной матрицы перечислены на диагонали, и задача на собственные значения решена.

В "псевдо" Ruby это концептуально означает:

working_matrix = orig_matrix.dup
all_q_matrices = []
loop do
  q, r = working_matrix.qr_decomposition
  all_q_matrices << q
  next_matrix = r * q
  break if difference_between(working_matrix, next_matrix) < accuracy_threshold
end
eigenvalues = working_matrix.diagonal_values

Для собственных векторов это продолжается:

при сходимости AQ = QΛ, где Λ - диагональная матрица собственных значений, к которым сходится A, и где Q - это совокупность всех ортогональных преобразований подобия, требуемых для ее получения. Таким образом, столбцы Q являются собственными векторами.

В "псевдо" Ruby, продолжение:

eigenvectors = all_q_matrices.inject(:*).columns

Ошибка с плавающей точкой в численных расчетах

Мы можем видеть, что итерация численных вычислений выполняется для вычисления приближенных собственных значений, и в качестве побочного эффекта собирается группа приближенных Q матриц. Затем эти аппроксимированные Q матрицы составляются вместе для формирования собственных векторов.

Сложность аппроксимаций - это то, что, вероятно, вызвало крайне неточные результаты. Пример катастрофической отмены в Math StackExchange показывает простое квадратичное вычисление с относительной ошибкой 400%. Вы могли бы представить, как алгоритм итеративной матрицы с повторяющимися арифметическими операциями может работать намного хуже.

Зерно соли

Опять же, у меня нет глубокого понимания математики алгоритма и его реализации, поэтому я не знаю точно, какие части вычисления вызвали вашу конкретную ошибку 85110032990182200%, но я надеюсь, что теперь вы можете понять, как это может иметь получилось.

Ответ 2

Потому что Ruby использует IEEE-754 в качестве стандарта точности с плавающей точкой.

Как известно, у него есть проблема точности с плавающей точкой.

Поэтому попробуйте использовать десятичное число в ruby, это решит проблему с плавающей точкой.