Матричная сумма мощности

Question

Каков наилучший способ вычисления суммы матриц, таких как A^i + A^(i + 1) + A^i + 2 ........ A^n для очень больших n ?

Я думал два возможных способов:

1) С помощью логарифмической матрицы (LME возведение в степень) для^I, а затем рассчитать последующие матрицы путем умножения А.

Проблема: На самом деле не использует алгоритм LME, поскольку я использую его только для самой низкой мощности!

2) Используйте LME для нахождения A^n и запомните промежуточные вычисления.

Задача: Слишком много места для больших n.

Есть ли третий способ?

Answer 1

Обратите внимание, что:

A + A^2 = A(I + A) 
A + A^2 + A^3 = A(I + A) + A^3 
A + A^2 + A^3 + A^4 = (A + A^2)(I + A^2) 
        = A(I + A)(I + A^2) 

Пусть

B(n) = A + ... + A^n 

Мы имеем:

B(1) = A 
B(n) = B(n/2) * (I + A^(n/2)) if n is even 
B(n) = B(n/2) * (I + A^(n/2)) + A^n if n is odd 

Таким образом, вы будете делать логарифмический ряд шагов, и нет необходимости вычислять инверсий ,

В то время как прямая реализация приведет к (log n)^2 фактору, вы можете сохранить его на log n путем вычисления силы A как вы вычислить B.

Answer 2

Почему бы не просто диагонализировать матрицу, чтобы сделать умножение дешевым.

редактировать:

Пока матрица не вырождена, вы должны быть в состоянии найти диагональное представление D матрицы А, что А = ПРП^-1, где P состоит из собственных векторов А, и D имеет собственные значения A по диагонали. Получение D^m = D * D^(m-1) является дешевым, поскольку оно вы только умножаете по диагонали (т.е. такое же количество умножений, как размер матрицы)

Получение S (m) = S (m-1) + D^m также дешево, поскольку вы добавляете только диагональные элементы.

Тогда у Вас есть

A^I + A^(г + 1) + A^I + 2 ........ А^п = Р (О^I + D^(I +1) + D^i + 2 ........ D^n) P^-1 = P (S (n) - S (i)) P^-1

Единственная трудная вещь является нахождение P и P^-1

Answer 3

вы можете использовать тот факт, что сумма к n геометрической серии матриц равна:

S_n = (I-A)^(-1) (I-A^n) 

и, так как вы не начнете сюда м 0, вы можете просто вычислить:

result = S_n - S_i 

где i это ваш начальный индекс.