Алгоритм векторного умножения

Question

Пусть A, B - матрицы пространства R ^ n, а b принадлежат R ^ n. Опишите быстрый алгоритм для вычисления A ^ -2 * B * A ^ -3 * б. Сколько вычислений сделает алгоритм?

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

Мы еще не говорили о нотациях Big O, поэтому вопрос требует строго действия алгоритма. Как бы вы ответили на этот вопрос?

Answer 1

Я бы просто обработал задачу справа налево, используя линейный решатель при работе с инверсией A, и умножив матрицу при работе с B:

x1 = linsolve(A, b)
x2 = linsolve(A, x1)
x3 = linsolve(A, x2)
y = B*x3
z1 = linsolve(A,y)
result = linsolve(A,z1)

Вы можете уменьшить на постоянный множительколичество операций, сохраняя LU-разложение A в памяти, но если вам не дано больше структуры для A и B, квадратическая сложность кажется наилучшей, к которой вы можете стремиться.