Экспонирование матрицы само по себе N раз? - PullRequest
Новая
       56

Экспонирование матрицы само по себе N раз?

0 голосов
/ 25 сентября 2018

Я выполняю экспонирование матрицы с использованием FOR: 

import numpy as np
fl=2
cl=2
fl2=fl
cl2=cl
M = random.random((fl,cl))
M2 = M
Result = np.zeros((fl,cl))
Temp = np.zeros((fl,cl))
itera = 2
print('Matriz A:\n',M)
print('Matriz AxA:\n',M2)

for i in range (0,itera):
    for a in range(0,fl):
        for b in range (0,cl):  
            Result[a,b]+=M[a,b]*M[a,b]
            temp[a,b]=Result[a,b]
            Res[a,k]=M[a,b]
print('Potencia:\n',temp)
print('Matriz:\n', Result)

Ошибка в том, что она не очень хорошо выполняет умножение в Result[a,b]+=M[a,b]*M[a,b], и когда я сохраняю ее во временной матрице, умножаю ее наисходная матрица не выполняет следующий переход в for i in range (0,itera):

Я знаю, что могу выполнить функцию np.matmul, но я пытаюсь сделать это с помощью цикла FOR

Пример

Ответы [ 2 ]

0 голосов
/ 25 сентября 2018

Здесь есть некоторые проблемы:

  1. вы делаете не сбрасывает матрицу result после умножения, следовательно, вы продолжаете добавлять больше значений;и
  2. вы никогда не назначаете result обратно на m для выполнения умножения следующее .

Наивное мощностьреализация

Я думаю, что также лучше "инкапсулировать" умножение матриц в отдельную функцию, например: 

def matmul(a1, a2):
    m, ka = a1.shape
    kb, n = a2.shape
    if ka != kb:
        raise ValueError()
    res = np.zeros((m, n))
    for i in range(m):
        for j in range(n):
            d = 0.0
            for k in range(ka):
                d += a1[i,k] * a2[k,j]
            res[i, j] = d
    return res

Тогда мы можем вычислить мощность этой матрицы с помощью: 

m2 = m
for i in range(topow-1):
    m = matmul(m, m2)

Обратите внимание, что мы можем не использовать m здесь в качестве единственной матрицы.Так как если мы напишем m = matmul(m, m), то m будет m2.Но это означает, что если мы выполним умножение во второй раз, мы получим m4 вместо m3.

Это тогдадает ожидаемые результаты: 

>>> cross = np.array([[1,0,1],[0,1,0], [1,0,1]])
>>> matmul(cross, cross)
array([[2., 0., 2.],
       [0., 1., 0.],
       [2., 0., 2.]])
>>> matmul(cross, matmul(cross, cross))
array([[4., 0., 4.],
       [0., 1., 0.],
       [4., 0., 4.]])
>>> matmul(cross, matmul(cross, matmul(cross, cross)))
array([[8., 0., 8.],
       [0., 1., 0.],
       [8., 0., 8.]])

Логарифмический умножение мощности

Выше можно рассчитать M n in O (n) (линейное время), но мы можем добиться большего, мы можем вычислить эту матрицу за логарифмическое время: мы делаем это, посмотрев, равна ли мощность 1, если онато есть мы просто возвращаем матрицу, если это не так, мы проверяем, является ли мощность четной, если она четной, мы умножаем матрицу на себя и вычисляем мощность этой матрицы, но с мощностью, деленной на два, так M 2 n = (M × M) n .Если мощность нечетная , мы делаем более или менее то же самое, за исключением того, что мы умножаем его на исходное значение для M : M 2 n + 1 *1 073 * = М × (M × M) N .Например: 

def matpow(m, p):
    if p <= 0:
        raise ValueError()
    if p == 1:
        return m
    elif p % 2 == 0:  # even
        return matpow(matmul(m, m), p // 2)
    else:             # odd
        return matmul(m, matpow(matmul(m, m), p // 2))

Выше можно написать более изящно, но я оставляю это как упражнение:).

Обратите внимание, однако, что использование массивов с пустяками для скалярных вычислений обычно меньше эффективнее, чем использование умножения матриц (и других функций).Они оптимизированы и интерпретируются , а не , и обычно значительно превосходят эквиваленты Python.Поэтому я бы очень посоветовал вам использовать их.Также проверяются функции numpy, что снижает вероятность ошибок в них.

0 голосов
/ 25 сентября 2018

Вы ищете np.linalg.matrix_power.

Если вы используете numpy, не используйте цикл for, используйте векторизованную операцию. 

arr = np.arange(16).reshape((4,4))

np.linalg.matrix_power(arr, 3)


array([[ 1680,  1940,  2200,  2460],
       [ 4880,  5620,  6360,  7100],
       [ 8080,  9300, 10520, 11740],
       [11280, 12980, 14680, 16380]])

То же самоев качестве явного умножения: 

arr @ arr @ arr

>>> np.array_equal(arr @ arr @ arr, np.linalg.matrix_power(arr, 3))
True

Так как вы спросили

Если вы действительно хотите наивныйРешение с помощью петель, мы можем собрать куски довольно легко.Во-первых, нам нужен способ фактически умножить матрицы.Есть варианты, которые бьют n ^ 3 сложности, этот ответ не собирается делать это.Вот базовая функция умножения матриц: 

def matmultiply(a, b):
  res = np.zeros(a.shape)
  size = a.shape[0]

  for i in range(size):
    for j in range(size):
      for k in range(size):
        res[i][j] += a[i][k] * b[k][j]

  return res

Теперь вам нужна экспоненциальная функция.Эта функция принимает матрицу и степень и увеличивает матрицу до этой степени.

def loopy_matrix_power(a, n):
  res = np.identity(a.shape[0])
  while n > 0:
    if n % 2 == 0:
      a = matmultiply(a, a)
      n /= 2
    else:
      res = matmultiply(res, a)
      n -= 1

  return res

В действии: 

loopy_matrix_power(arr, 3)


array([[ 1680.,  1940.,  2200.,  2460.],
       [ 4880.,  5620.,  6360.,  7100.],
       [ 8080.,  9300., 10520., 11740.],
       [11280., 12980., 14680., 16380.]])
...