ошибка с плавающей запятой при вычислении матрицы 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 не может обрабатывать крошечные матрицы, то как мы вообще можем ему доверять? Или я что-то не так делаю?


ruby eigenvector
person Théophile    schedule 12.12.2017    source источник
comment
Результат мне тоже кажется неправильным (в этом мы также можем убедиться, выполнив m*m.eigen.eigenvectors[2]). Было бы полезно, если бы вы могли отправить отчет об ошибке, используя свой пример. Может быть, вы найдете даже небольшую матрицу, которая дает неверный результат?   -  person user1934428    schedule 13.12.2017
comment
Может ли это иметь какое-то отношение к комплексным собственным значениям, а не к действительным? Ваша матрица не является симметричной, поэтому, конечно, не гарантируется наличие реальных собственных значений. Выполняя собственное разложение с помощью numpy.linalg.eig () в Python, обнаруживается, что два собственных значения являются комплексными. Если метод собственных значений R ориентирован на симметричные матрицы, то неудивительно, что он изо всех сил пытается правильно правильно найти любой из собственных векторов.   -  person rwp    schedule 10.02.2018
comment
Возможно, собственные векторы не нормализованы, как это сделано в Numpy. Для записи я попробовал ваш пример с Ruby stdlib и Python Numpy. Собственные значения совпадают (хотя и разная точность), но векторы даже не нормализованы (я только что проверил 3-е из упомянутых вами).   -  person Eric Platon    schedule 03.06.2018
comment
@rwp Я должен был упомянуть, что я конструировал матрицы специально для того, чтобы иметь собственное значение $ 1 $, соответствующее собственному вектору, элементы которого действительны и положительны. Это гарантируется теоремой Перрона-Фробениуса. Верно, что другие собственные значения сложны, но собственное значение $ 1 $ кажется более важным, поскольку оно имеет наибольшее абсолютное значение.   -  person Théophile    schedule 03.06.2018
comment
@EricPlaton Но вектор выше кратен $ [1,1,1,1] $, а не $ [7,4,4,9] $, так что это не просто проблема нормализации.   -  person Théophile    schedule 03.06.2018
comment
да. Мой комментарий запутан. Нормализация обращается к «взрыву». Проблема в несовпадении с Numpy.   -  person Eric Platon    schedule 03.06.2018
comment
@EricPlaton А, понятно. Я помню, как несколько месяцев назад попробовал это на другом компьютере и дал правильный результат. В то время я думал, что проблема исправлена ​​(например, из-за использования более новой версии Ruby), но я попытался установить 2.5.1 только сейчас, и у меня возникла та же проблема. Хм.   -  person Théophile    schedule 03.06.2018
comment
Мои тесты были на Ruby 2.3.1.   -  person Eric Platon    schedule 03.06.2018

Ответы (1)


arrow_upward
2
arrow_downward

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

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

Не охвачено. 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 являются собственными векторами.

В «псевдо» Руби продолжение:

eigenvectors = all_q_matrices.inject(:*).columns

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

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

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

Крупинка соли

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

person Kache    schedule 19.04.2019
comment
Я все еще обеспокоен, но спасибо за подробное объяснение. :) - person Théophile; 05.03.2021