Почему поиск собственных значений матрицы 4 * 4 с помощью z3py занимает так много времени и не дает никаких решений? - PullRequest
0 голосов
/ 11 июля 2020

Я пытаюсь вычислить собственные значения матрицы 4 * 4 с именем A в моем коде (я знаю, что собственные значения являются действительными значениями). Все элементы A являются выражениями z3 и должны быть вычислены на основе предыдущих ограничений. Приведенный ниже код является последней частью длинного кода, который пытается вычислить матрицу A, а затем ее собственные значения. Код написан как единое целое, но я разделил его на две отдельные части, чтобы отладить его: часть 1, в которой код пытается найти матрицу A, и часть 2, которая вычисляет собственные значения. В части 1 код работает очень быстро и вычисляет A менее чем за SE c, но когда я добавляю в код часть 2, он не дает мне никаких решений после.

Мне было интересно Что может быть причиной? Это из-за порядка полинома (который равен 4) или что? Я был бы признателен, если бы кто-нибудь помог мне найти альтернативный способ вычисления собственных значений или дал мне несколько советов о том, как переписать код, чтобы он мог решить проблему.

(Обратите внимание, что A2 в коде actusl является матрица со всеми ее элементами в виде выражений z3, определенных предыдущими ограничениями в коде. Но здесь я определил элементы как реальные значения, чтобы сделать код исполняемым. Таким образом, код дает решение так быстро, но в в реальной ситуации это занимает так много времени, как дни. Например, один из элементов A выглядит примерно так:

0 +
 1*Vq0__1 +
 2 * -Vd0__1 +
 0 +
 ((5.5 * Iq0__1 - 0)/64/5) * 
 (0 +
  0 * (Vq0__1 - 0) +
  -521702838063439/62500000000000 * (-Vd0__1 - 0)) +
 ((.10 * Id0__1 - Etr_q0__1)/64/5) * 
 (0 +
  521702838063439/62500000000000 * (Vq0__1 - 0) +
  0.001 * (-Vd0__1 - 0)) +
 0 +
 0 + 0 +
 0 +
 ((100 * Iq0__1 - 0)/64/5) * 0 +
 ((20 * Id0__1 - Etr_q0__1)/64/5) * 0 +
 0 +
 -5/64

Все переменные в этом примере являются переменными z3.)

from z3 import *
import numpy as np


def sub(*arg):
    counter = 0
    for matrix in arg:
        if counter == 0: 
            counter += 1
            Sub = [] 
            for i in range(len(matrix)):
                Sub1 = []
                for j in range(len(matrix[0])):
                    Sub1 += [matrix[i][j]]
                Sub += [Sub1]
        else:
            row = len(matrix)
            colmn = len(matrix[0])
            for i in range(row):
                for j in range(colmn):
                    Sub[i][j] = Sub[i][j] - matrix[i][j]  
    return Sub

Landa = RealVector('Landa', 2) # Eigenvalues considered as real values
LandaI0 = np.diag(  [ Landa[0] for i in range(4)]  ).tolist()

ALandaz3 = RealVector('ALandaz3', 4 * 4 )

############# Building ( A - \lambda * I ) to find the eigenvalues ############

A2 = [[1,2,3,4],
      [5,6,7,8],
      [3,7,4,1],
      [4,9,7,1]]

s = Solver()

for i in range(4):
    for j in range(4):
        s.add( ALandaz3[ 4 * i + j ] == sub(A2, LandaI0)[i][j] )
ALanda = [[ALandaz3[0], ALandaz3[1], ALandaz3[2], ALandaz3[3] ],
          [ALandaz3[4], ALandaz3[5], ALandaz3[6], ALandaz3[7] ],
          [ALandaz3[8], ALandaz3[9], ALandaz3[10], ALandaz3[11]],
          [ALandaz3[12], ALandaz3[13], ALandaz3[14], ALandaz3[15] ]]
Determinant = (
 ALandaz3[0] * ALandaz3[5] * (ALandaz3[10] * ALandaz3[15] - ALandaz3[14] * ALandaz3[11]) -
 ALandaz3[1] * ALandaz3[4] * (ALandaz3[10] * ALandaz3[15] - ALandaz3[14] * ALandaz3[11]) +
 ALandaz3[2] * ALandaz3[4] * (ALandaz3[9]  * ALandaz3[15] - ALandaz3[13] * ALandaz3[11]) -
 ALandaz3[3] * ALandaz3[4] * (ALandaz3[9]  * ALandaz3[14] - ALandaz3[13] * ALandaz3[10]) )

tol = 0.001 

s.add( And( Determinant >= -tol, Determinant <= tol ) )   # giving some flexibility instead of equalling to zero

print(s.check())
print(s.model())

1 Ответ

0 голосов
/ 12 июля 2020

Обратите внимание, что вы, кажется, используете Z3 для типа уравнений, для которых он абсолютно не предназначен. Z - решатель sat / smt . Такой решатель внутренне работает с огромным количеством булевых уравнений. Целые числа и дроби можно преобразовать в логические выражения, но с обычными числами с плавающей запятой Z3 быстро достигает своих пределов. См. здесь и здесь для множества типичных примеров и обратите внимание на то, как избегаются числа с плавающей запятой.

Z3 может ограниченно работать с числами с плавающей запятой, преобразовывая их в дроби , но не работает с приближениями и точностью, которые требуются в численных алгоритмах. Поэтому результаты обычно не те, на которые вы надеетесь.

Нахождение собственных значений - типичная числовая задача, где вопросы точности очень сложны. Python имеет библиотеки, такие как numpy и scipy , чтобы эффективно с ними справляться. См., Например, numpy.linalg.eig.

Если, однако, ваша матрица A2 содержит некоторые символьные c выражения (и использует дроби вместо чисел с плавающей запятой), sympy ' s матричные функции могут быть интересной альтернативой.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...