Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > матричное уравнение


Автор: mrgloom 24.7.2012, 14:18
есть матричное уравнение, все матрицы 3х3, надо найти M, А и B известны. 
Цитата

A*M=M*B

пните в нужную сторону 

Автор: Pavia 24.7.2012, 18:17
A*M-M*B=0
Далее решаем систему уравнений

C*D=0
D=(m00,m01,m02,m10,m11,m12,m20,m21,m22);

Автор: mrgloom 25.7.2012, 08:50
а С чему равно?

Автор: W4FhLF 5.8.2012, 20:13
Pavia, далеко не всё так просто. Вообще по виду уравнение не имеет решений в общем случае, кроме тривиального М = 0. 

Может это поможет: http://en.wikipedia.org/wiki/Sylvester_equation

Хотя форма другая всё-таки. 

Автор: entrix 6.8.2012, 02:35
Смотрите GNU Octave, там есть соответствующая функция syl:

Solve the Sylvester equation

          A X + X B + C = 0
using standard lapack subroutines. For example:

          syl ([1, 2; 3, 4], [5, 6; 7, 8], [9, 10; 11, 12])
               ⇒ [ -0.50000, -0.66667; -0.66667, -0.50000 ]

http://www.gnu.org/software/octave/doc/interpreter/Functions-of-a-Matrix.html#index-syl-2110

Автор: mrgloom 6.8.2012, 11:15
похоже, то что нужно.
попробую в Mathematica.

Автор: mrgloom 6.8.2012, 12:12
попробовал в Mathematica выдало все нули, ну т.е. тривиальное решение.

может что то сделал не правильно?

мне всё таки надо наверно сперва доказать, что существует решение отличное от тривиального.

Автор: maxim1000 6.8.2012, 12:21
это обычное однородное линейное уравнение, как и сказал Pavia

так что можно просто построить матрицу (9*9) и посмотреть на её определитель

Автор: mrgloom 6.8.2012, 12:51
вы походу перепутали 
A*X=B*X
и 
A*X=X*B

тут Х так просто не выразить

Автор: W4FhLF 6.8.2012, 13:34
maxim1000, умножение матриц операция не коммутативная.

Автор: mrgloom 6.8.2012, 15:31
http://math.stackexchange.com/questions/179413/existence-of-non-trivial-solution-of-sylvester-equation


проверяю на существование не тривиального решения
через первый критерий
Цитата
NullSpace[KroneckerProduct[IdentityMatrix[3],A]-KronekerProduct[B,IdentityMatrix[3]]]

выдает {}
матрицы задавал как 
Цитата
A={{a11,a12,a13},{a21,a22,a23},{a31,a32,a33}}
B={{b11,b12,b13},{b21,b22,b23},{b31,b32,b33}}

так же пробовал
Цитата
A={{a11,a12,a13},{a21,a22,a23},{0,0,1}}
B={{b11,b12,b13},{b21,b22,b23},{b31,b32,1}}


хотелось бы узнать как по матрице A
Цитата
A={{a11,a12,a13},{a21,a22,a23},{0,0,1}}

можно найти хотя бы 1 матрицу B  которая будет удовлетворять вышеописанному условию?
 
так же пробовал через другое эквивалентное условие.
Цитата
Resultant[Det[A-x IdentityMatrix[3]],Det[-B-x IdentityMatrix[3]],x] =0

хотя возможно оно выглядит так 
Цитата
Resultant[Det[A-x IdentityMatrix[3]],Det[B-x IdentityMatrix[3]],x]=0

вопрос опять же остается, 
хотелось бы узнать как по матрице A
Цитата
A={{a11,a12,a13},{a21,a22,a23},{0,0,1}}

можно найти хотя бы 1 матрицу B которая будет удовлетворять вышеописанному условию?

Автор: maxim1000 6.8.2012, 18:18
Цитата(W4FhLF @  6.8.2012,  13:34 Найти цитируемый пост)
maxim1000, умножение матриц операция не коммутативная. 

а этого и не нужно
просто записать каждый коеэффициент левого произведения и каждый коэффициент правого произведения, ну и приравнять

9 уравнений
9 неизвестных
все уравнения линейные

тот факт, что произведение некоммутативно, приведёт разве что к тому, что формулы будут разные и разные наборы неизвестных будут слева и справа, но для СЛАУ это не так важно

Автор: mrgloom 7.8.2012, 09:34
дело в том, что эти 9 уравнений не решить как обычную СЛАУ.
т.к.  хотя бы для примера
AX-XB
первая строчка зависит от x11,x12,x13,x21,x31
AX
первая строчка зависит от x11,x21,x31


возможно 
AX-XB=0
как то и переписывается в виде типа  
P*X=C
но как построить матрицы P,C ?

Автор: maxim1000 7.8.2012, 10:01
Цитата(mrgloom @  7.8.2012,  09:34 Найти цитируемый пост)
дело в том, что эти 9 уравнений не решить как обычную СЛАУ.
т.к.  хотя бы для примера
AX-XB
первая строчка зависит от x11,x12,x13,x21,x31
AX
первая строчка зависит от x11,x21,x31

да почему???
даже если в каждом уравнении будут участвовать все 9 неизвестных, менее линейной система не станет

на всякий случай уточню, систему будет представлена уже матрицей 9*9 (т.к. 9 неищвестных и 9 уравнений)

Автор: mrgloom 7.8.2012, 10:53
да, я кажется понял.

вместо системы 3х3*3х3 получаем 9х9*1х9
A*X-X*B=new_A*new_Xr=0
я это вручную сделал, а вот как записать формулу для матрицы 9х9 в общем виде?
потом загнал  в LeastSquares и получил опять тривиальное решение =0.

Автор: maxim1000 7.8.2012, 15:50
Цитата(mrgloom @  7.8.2012,  10:53 Найти цитируемый пост)
я это вручную сделал, а вот как записать формулу для матрицы 9х9 в общем виде?

так вручную в коде и записать, 9 уравнений - не так уж и много
ну и в процессе можно обнаружить какую-нибудь закономерность, может, код сократится


Цитата(mrgloom @  7.8.2012,  10:53 Найти цитируемый пост)
потом загнал  в LeastSquares и получил опять тривиальное решение =0. 

зачастую под решением СЛАУ подразумевается нахождение конкретного вектора
здесь задача решить однородную систему, если есть какие-то нетривиальные решения, то их есть целое линейное подпространство, надо какие-нибудь специализированные методы смотреть

Автор: mrgloom 8.8.2012, 09:00
Цитата

ну и в процессе можно обнаружить какую-нибудь закономерность

складывается впечатление, что закономерность какая то непростая.

там проблема в том, что не тривиальное решение существует только когда, выполняется условие, которое зависит от матриц А,В.
Матрицу А я могу варьировать(но там есть некоторые ограничения), а матрица В неким образом всё таки зависит от матрицы А.
и матрица В определена с погрешностью.

так вот непонятно можно ли подобрать матрицу А таким образом, чтобы у уравнения АХ=ХВ существовало отличное от тривиальное решение? 

Автор: maxim1000 8.8.2012, 10:48
для существования нетривиального решения матрицы 9*9 должна быть вырождена
так что можно определитель приравнять нулю

хотя, конечно, аналитически с формулой определителя 9*9 работать неудобно, но можно попробовать как-то численно...

Автор: mrgloom 8.8.2012, 14:10
и что получится полином 9 степени от 18 параметров?  и как его решать?

Автор: maxim1000 8.8.2012, 15:50
Цитата(mrgloom @  8.8.2012,  14:10 Найти цитируемый пост)
и что получится полином 9 степени от 18 параметров?

насколько я понимаю, B предполагается известной, нужно найти A
тогда будет полином от 9 параметров (элементы B будут просто числами)
честно говоря, на вскидку, алгоритм нахождения нулей этого полинома я не предложу, но, возможно, что-то и есть...

кроме того, наверное, на A есть какие-то ограничения, иначе можно просто взять A=B, тогда единичная матрица в качестве X вполне себе подходит на роль нетривиального решения

Автор: mrgloom 9.8.2012, 16:19
Цитата

Solve[(m31 x1 + m32 y1 + 1) u1 == (m11 x1 + m12 y1 + m13) &&
  (m31 x1 + m32 y1 + 1) v1 == (m21 x1 + m22 y1 + m23) &&
  (m31 x2 + m32 y2 + 1) u2 == (m11 x2 + m12 y2 + m13) &&
  (m31 x2 + m32 y2 + 1) v2 == (m21 x2 + m22 y2 + m23) &&
  (m31 x3 + m32 y3 + 1) u3 == (m11 x3 + m12 y3 + m13) &&
  (m31 x3 + m32 y3 + 1) v3 == (m21 x3 + m22 y3 + m23) &&
  (m31 x4 + m32 y4 + 1) u4 == (m11 x4 + m12 y4 + m13) &&
  (m31 x4 + m32 y4 + 1) v4 == (m21 x4 + m22 y4 + m23) &&
  (m31 x5 + m32 y5 + 1) u5 == (m11 x5 + m12 y5 + m13) &&
  (m31 x5 + m32 y5 + 1) v5 == (m21 x5 + m22 y5 + m23) &&
  (m31 x6 + m32 y6 + 1) u6 == (m11 x6 + m12 y6 + m13) &&
  (m31 x6 + m32 y6 + 1) v6 == (m21 x6 + m22 y6 + m23) &&
  (m31 x7 + m32 y7 + 1) u7 == (m11 x7 + m12 y7 + m13) &&
  (m31 x7 + m32 y7 + 1) v7 == (m21 x7 + m22 y7 + m23) &&
  (m31 x8 + m32 y8 + 1) u8 == (m11 x8 + m12 y8 + m13) &&
  (m31 x8 + m32 y8 + 1) v8 == (m21 x8 + m22 y8 + m23) &&
  (m31 x9 + m32 y9 + 1) u9 == (m11 x9 + m12 y9 + m13) &&
  (m31 x9 + m32 y9 + 1) v9 == (m21 x9 + m22 y9 + m23) &&
  (m31 x10 + m32 y10 + 1) u10 == (m11 x10 + m12 y10 + m13) &&
  (m31 x10 + m32 y10 + 1) v10 == (m21 x10 + m22 y10 + m23) &&
  dx == x2 - x1 &&
  dy == y2 - y1 &&
  dx == x4 - x3 &&
  dy == y4 - y3 &&
  dx == x6 - x5 &&
  dy == y6 - y5 &&
  dx == x8 - x7 &&
  dy == y8 - y7 &&
  dx == x10 - x9 &&
  dy == y10 - y9
 , {dx, dy, m11, m12, m13, m21, m22, m23, m31, m32,
   x1, x2, x3, x4, x5, x6, x7, x8, x9, x10,
   y1, y2, y3, y4, y5, y6, y7, y8, y9, y10}]


а такую систему можно как AX=B представить?

Автор: mrgloom 10.8.2012, 10:24
что если поставить задачу так.
я знаю координаты точек u,v после преобразования, а до преобразования x,y не знаю, но знаю что расстояние между точками сохраняется.

пример имею 5 одних и тех же четырехугольников до и после
user posted image
user posted image

возможно ли имея такую информацию найти неизвестное преобразование?

Автор: maxim1000 10.8.2012, 10:39
Судя по картинкам, у меня складывается впечатление, что это не афинное преобразование.
Больше похоже на http://en.wikipedia.org/wiki/Texture_mapping#Perspective_correctness.

Подозреваю, что там нужны несколько другие методы...

Автор: mrgloom 10.8.2012, 11:21
ну да перспективное, но ни задаются одной формулой
у афинного просто последняя строка 0 0 1 

Автор: baldina 10.8.2012, 14:04
Цитата(maxim1000 @  10.8.2012,  10:39 Найти цитируемый пост)
Судя по картинкам, у меня складывается впечатление, что это не афинное преобразование.
...
Подозреваю, что там нужны несколько другие методы... 

перейдите к размерности на 1 больше, получите аффинное.

Цитата(mrgloom @  10.8.2012,  10:24 Найти цитируемый пост)
расстояние между точками сохраняется

судя по рисунку, это не так. может, имеется в виду соотношение расстояний? (и это естественно, т.к. в данном случае имеем только поворот в 3D)

Добавлено через 6 минут и 43 секунды
Цитата(mrgloom @  10.8.2012,  10:24 Найти цитируемый пост)
я знаю координаты точек u,v после преобразования, а до преобразования x,y не знаю

что еще известно?

Автор: mrgloom 10.8.2012, 14:57
Цитата(baldina @  10.8.2012,  14:04 Найти цитируемый пост)
судя по рисунку, это не так. может, имеется в виду соотношение расстояний? (и это естественно, т.к. в данном случае имеем только поворот в 3D)

вы наверно не поняли,  я знаю что расстояния между точками до преобразования были одинаковые, а после они конечно разные ибо искажение.
пример было 2  одинаковых по длине отрезка но с разными координатами х1,у1,х2,у2 и х3,у3,х4,у4  (этих координат я не знаю) , но знаю что длины отрезков одинаковые, а так же знаю какие координаты точек после преобразования соответствуют точкам отрезков. 

Автор: mrgloom 10.8.2012, 17:07

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

Цитата

Clear[x1]; Clear[x2]; Clear[x3]; Clear[x4]; Clear[x5]; Clear[x6]; \
Clear[x7]; Clear[x8]; Clear[x9]; Clear[x10]
Clear[y1]; Clear[y2]; Clear[y3]; Clear[y4]; Clear[y5]; Clear[y6]; \
Clear[y7]; Clear[y8]; Clear[y9]; Clear[y10];
u1 = 60.5 ; u2 = 71; u3 = 172; u4 = 178; u5 = 21.5; u6 = 35.9; u7 = \
130; u8 = 139; u9 = 148; u10 = 157;
v1 = 102; v2 = 62.9; v3 = 80.4; v4 = 37.1; v5 = 250; v6 = 197; v7 = \
186; v8 = 133; v9 = 243; v10 = 183;
NSolve[u1 == (m13 + m11 x1 + m12 y1)/(1 + m31 x1 + m32 y1) &&
  v1 == (m23 + m21 x1 + m22 y1)/(1 + m31 x1 + m32 y1) &&
  u2 == (m13 + m11 x2 + m12 y2)/(1 + m31 x2 + m32 y2) &&
  v2 == (m23 + m21 x2 + m22 y2)/(1 + m31 x2 + m32 y2) &&
  u3 == (m13 + m11 x3 + m12 y3)/(1 + m31 x3 + m32 y3) &&
  v3 == (m23 + m21 x3 + m22 y3)/(1 + m31 x3 + m32 y3) &&
  u4 == (m13 + m11 x4 + m12 y4)/(1 + m31 x4 + m32 y4) &&
  v4 == (m23 + m21 x4 + m22 y4)/(1 + m31 x4 + m32 y4) &&
  u5 == (m13 + m11 x5 + m12 y5)/(1 + m31 x5 + m32 y5) &&
  v5 == (m23 + m21 x5 + m22 y5)/(1 + m31 x5 + m32 y5) &&
  u6 == (m13 + m11 x6 + m12 y6)/(1 + m31 x6 + m32 y6) &&
  v6 == (m23 + m21 x6 + m22 y6)/(1 + m31 x6 + m32 y6) &&
  u7 == (m13 + m11 x7 + m12 y7)/(1 + m31 x7 + m32 y7) &&
  v7 == (m23 + m21 x7 + m22 y7)/(1 + m31 x7 + m32 y7) &&
  u8 == (m13 + m11 x8 + m12 y8)/(1 + m31 x8 + m32 y8) &&
  v8 == (m23 + m21 x8 + m22 y8)/(1 + m31 x8 + m32 y8) &&
  u9 == (m13 + m11 x9 + m12 y9)/(1 + m31 x9 + m32 y9) &&
  v9 == (m23 + m21 x9 + m22 y9)/(1 + m31 x9 + m32 y9) &&
  u10 == (m13 + m11 x10 + m12 y10)/(1 + m31 x10 + m32 y10) &&
  v10 == (m23 + m21 x10 + m22 y10)/(1 + m31 x10 + m32 y10) &&
  dx == x2 - x1 && dx == x4 - x3 && dx == x6 - x5 && dx == x8 - x7 &&
  dx == x10 - x9 && dy == y2 - y1 && dy == y4 - y3 && dy == y6 - y5 &&
  dy == y8 - y7 && dy == y10 - y9
 , {dx, dy, m11, m12, m13, m21, m22, m23, m31, m32,
  x1, x2, x3, x4, x5, x6, x7, x8, x9, x10,
  y1, y2, y3, y4, y5, y6, y7, y8, y9, y10}]



попробовал переписать без деления, тоже самое.
Цитата

Clear[x1]; Clear[x2]; Clear[x3]; Clear[x4]; Clear[x5]; Clear[x6]; \
Clear[x7]; Clear[x8]; Clear[x9]; Clear[x10]
Clear[y1]; Clear[y2]; Clear[y3]; Clear[y4]; Clear[y5]; Clear[y6]; \
Clear[y7]; Clear[y8]; Clear[y9]; Clear[y10];
u1 = 60.5 ; u2 = 71; u3 = 172; u4 = 178; u5 = 21.5; u6 = 35.9; u7 = \
130; u8 = 139; u9 = 148; u10 = 157;
v1 = 102; v2 = 62.9; v3 = 80.4; v4 = 37.1; v5 = 250; v6 = 197; v7 = \
186; v8 = 133; v9 = 243; v10 = 183;
NSolve[u1 (1 + m31 x1 + m32 y1) == (m13 + m11 x1 + m12 y1) &&
  v1 (1 + m31 x1 + m32 y1) == (m23 + m21 x1 + m22 y1) &&
  u2 (1 + m31 x2 + m32 y2) == (m13 + m11 x2 + m12 y2) &&
  v2 (1 + m31 x2 + m32 y2) == (m23 + m21 x2 + m22 y2) &&
  u3 (1 + m31 x3 + m32 y3) == (m13 + m11 x3 + m12 y3) &&
  v3 (1 + m31 x3 + m32 y3) == (m23 + m21 x3 + m22 y3) &&
  u4 (1 + m31 x4 + m32 y4) == (m13 + m11 x4 + m12 y4) &&
  v4 (1 + m31 x4 + m32 y4) == (m23 + m21 x4 + m22 y4) &&
  u5 (1 + m31 x5 + m32 y5) == (m13 + m11 x5 + m12 y5) &&
  v5 (1 + m31 x5 + m32 y5) == (m23 + m21 x5 + m22 y5) &&
  u6 (1 + m31 x6 + m32 y6) == (m13 + m11 x6 + m12 y6) &&
  v6 (1 + m31 x6 + m32 y6) == (m23 + m21 x6 + m22 y6) &&
  u7 (1 + m31 x7 + m32 y7) == (m13 + m11 x7 + m12 y7) &&
  v7 (1 + m31 x7 + m32 y7) == (m23 + m21 x7 + m22 y7) &&
  u8 (1 + m31 x8 + m32 y8) == (m13 + m11 x8 + m12 y8) &&
  v8 (1 + m31 x8 + m32 y8) == (m23 + m21 x8 + m22 y8) &&
  u9 (1 + m31 x9 + m32 y9) == (m13 + m11 x9 + m12 y9) &&
  v9 (1 + m31 x9 + m32 y9) == (m23 + m21 x9 + m22 y9) &&
  u10 (1 + m31 x10 + m32 y10) == (m13 + m11 x10 + m12 y10) &&
  v10 (1 + m31 x10 + m32 y10) == (m23 + m21 x10 + m22 y10) &&
  dx == x2 - x1 && dx == x4 - x3 && dx == x6 - x5 && dx == x8 - x7 &&
  dx == x10 - x9 && dy == y2 - y1 && dy == y4 - y3 && dy == y6 - y5 &&
  dy == y8 - y7 && dy == y10 - y9
 , {dx, dy, m11, m12, m13, m21, m22, m23, m31, m32,
  x1, x2, x3, x4, x5, x6, x7, x8, x9, x10,
  y1, y2, y3, y4, y5, y6, y7, y8, y9, y10}]



попробовал для афинных преобразований m31=m32=0
(убрал 2 переменные и убрал 2 уравнения)
получил почему, то что не решений
Цитата

Clear[x1]; Clear[x2]; Clear[x3]; Clear[x4]; Clear[x5]; Clear[x6]; \
Clear[x7]; Clear[x8]; Clear[x9]; Clear[x10]
Clear[y1]; Clear[y2]; Clear[y3]; Clear[y4]; Clear[y5]; Clear[y6]; \
Clear[y7]; Clear[y8]; Clear[y9]; Clear[y10];
u1 = 60.5 ; u2 = 71; u3 = 172; u4 = 178; u5 = 21.5; u6 = 35.9; u7 = \
130; u8 = 139; u9 = 148; u10 = 157;
v1 = 102; v2 = 62.9; v3 = 80.4; v4 = 37.1; v5 = 250; v6 = 197; v7 = \
186; v8 = 133; v9 = 243; v10 = 183;
m32 = 0; m31 = 0;
NSolve[u1 (1 + m31 x1 + m32 y1) == (m13 + m11 x1 + m12 y1) &&
  v1 (1 + m31 x1 + m32 y1) == (m23 + m21 x1 + m22 y1) &&
  u2 (1 + m31 x2 + m32 y2) == (m13 + m11 x2 + m12 y2) &&
  v2 (1 + m31 x2 + m32 y2) == (m23 + m21 x2 + m22 y2) &&
  u3 (1 + m31 x3 + m32 y3) == (m13 + m11 x3 + m12 y3) &&
  v3 (1 + m31 x3 + m32 y3) == (m23 + m21 x3 + m22 y3) &&
  u4 (1 + m31 x4 + m32 y4) == (m13 + m11 x4 + m12 y4) &&
  v4 (1 + m31 x4 + m32 y4) == (m23 + m21 x4 + m22 y4) &&
  u5 (1 + m31 x5 + m32 y5) == (m13 + m11 x5 + m12 y5) &&
  v5 (1 + m31 x5 + m32 y5) == (m23 + m21 x5 + m22 y5) &&
  u6 (1 + m31 x6 + m32 y6) == (m13 + m11 x6 + m12 y6) &&
  v6 (1 + m31 x6 + m32 y6) == (m23 + m21 x6 + m22 y6) &&
  u7 (1 + m31 x7 + m32 y7) == (m13 + m11 x7 + m12 y7) &&
  v7 (1 + m31 x7 + m32 y7) == (m23 + m21 x7 + m22 y7) &&
  u8 (1 + m31 x8 + m32 y8) == (m13 + m11 x8 + m12 y8) &&
  v8 (1 + m31 x8 + m32 y8) == (m23 + m21 x8 + m22 y8) &&
  u9 (1 + m31 x9 + m32 y9) == (m13 + m11 x9 + m12 y9) &&
  v9 (1 + m31 x9 + m32 y9) == (m23 + m21 x9 + m22 y9) &&
  u10 (1 + m31 x10 + m32 y10) == (m13 + m11 x10 + m12 y10) &&
  v10 (1 + m31 x10 + m32 y10) == (m23 + m21 x10 + m22 y10) &&
  dx == x2 - x1 && dx == x4 - x3 && dx == x6 - x5 && dx == x8 - x7 &&
  dx == x10 - x9 && dy == y2 - y1 && dy == y4 - y3 && dy == y6 - y5
 , {dx, dy, m11, m12, m13, m21, m22, m23,
  x1, x2, x3, x4, x5, x6, x7, x8, x9, x10,
  y1, y2, y3, y4, y5, y6, y7, y8, y9, y10}]

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)