Гауссова эллимация - матрицы линейных уравнений, алгоритм

Question

Давайте предположим, что у нас есть простая матрица 3rows x 7cols. В матрицу входят только нули (0) и (1), например:

1 0 1 1 1 0 0
0 0 1 1 0 0 0
0 0 1 0 1 1 0

Senario: Если мы знаем сумму ненулей в каждой строке,

(в первом ряду 4, во втором ряду 2, в третьем ряду 3.) (синяя линия)

дополнительно, если мы знаем сумму каждого столбца (1, 0, 3, 2, 2, 1, 0) (зеленая линия)

также, если мы знаем сумму каждой диагонали сверху-слева-внизу-справа (1,0,1,2,3,0,1,1,0) (красные линии) против часовой стрелки

и, наконец, мы знаем сумму каждой диагонали от нижнего левого до верхнего правого (0,0,2,1,3,2,1,0,0) (желтые линии)

Мой вопрос: С этими значениями в качестве входных данных (и длиной матрицы 3x7),

4, 2, 3
1, 0, 3, 2, 2, 1, 0
1, 0, 1, 2, 3, 0, 1, 1, 0
0, 0, 2, 1, 3, 2, 1, 0, 0

Как мы можем нарисовать первую матрицу? После долгих размышлений я пришел к выводу, что это система линейных уравнений с неизвестными значениями 3х7 и некоторыми уравнениями. Правильно?

Как я могу сделать алгоритм в C или что-то еще, чтобы решить эти уравнения? Должен ли я использовать такой метод, как уравнение Гаусса?

Любая помощь будет принята с благодарностью!

Answer 1

Вы можете использовать разложение по сингулярным значениям для вычисления ненулевого решения методом наименьших квадратов для системы линейных однородных (и неоднородных) уравнений в матричной форме.

Краткий обзор см .:

http://campar.in.tum.de/twiki/pub/Chair/TeachingWs05ComputerVision/3DCV_svd_000.pdf

Сначала вы должны записать свои системы в виде матричного уравнения в форме Ax = b, где x - 21 неизвестный в виде вектора столбца, а A - матрица 28 x 21, которая образуетлинейная система при умножении.По сути, вам необходимо вычислить матрицу A линейных уравнений, вычислить разложение сингулярного значения A и вставить результаты в уравнение, как показано в уравнении 9.17

Существует множество библиотек, которые будут вычислять SVD для вас.в C, так что вам нужно только сформулировать матрицу и выполнить вычисления в 9.17.Самая сложная часть, вероятно, заключается в понимании того, как все это работает, поскольку для библиотечной SVD-функции требуется относительно мало кода.

Чтобы начать работу по формированию уравнения линейных систем, рассмотрим простое 3 x 3case.

Предположим, что наша система представляет собой матрицу вида

1 0 1
0 1 0
1 0 1

У нас будут следующие входные данные для линейной системы:

2 1 2             (sum of rows                 - row)
2 1 2             (sum of colums               - col)
1 0 3 0 1         (sum of first diagonal sets  - t2b)
1 0 3 0 1         (sum of second diagonal sets - b2t)

, поэтому теперь мысоздать матрицу для линейной системы

 A            a1 a2 a3 b1 b2 b3 c1 c2 c3     unknowns (x)    =   result (b)
sum of row 1 [ 1  1  1  0  0  0  0  0  0 ]      [a1]                [2]       
sum of row 2 [ 0  0  0  1  1  1  0  0  0 ]      [a2]                [1]
sum of row 3 [ 0  0  0  0  0  0  1  1  1 ]      [a3]                [2]
sum of col 1 [ 1  0  0  1  0  0  1  0  0 ]      [b1]                [2]
sum of col 2 [ 0  1  0  0  1  0  0  1  0 ]      [b2]                [1]
sum of col 3 [ 0  0  1  0  0  1  0  0  1 ]      [b3]                [2]
sum of t2b 1 [ 1  0  0  0  0  0  0  0  0 ]      [c1]                [1]
sum of t2b 2 [ 0  1  0  1  0  0  0  0  0 ]      [c2]                [0]
sum or t2b 3 [ 0  0  1  0  1  0  1  0  0 ]      [c3]                [3]
sum of t2b 4 [ 0  0  0  0  0  1  0  1  0 ]                          [0]
sum of t2b 5 [ 0  0  0  0  0  0  0  0  1 ]                          [1]
sum of b2t 1 [ 0  0  0  0  0  0  1  0  0 ]                          [1]
sum of b2t 2 [ 0  0  0  1  0  0  0  1  0 ]                          [0]
sum of b2t 3 [ 1  0  0  0  1  0  0  0  1 ]                          [3]
sum of b2t 4 [ 0  1  0  0  0  1  0  0  0 ]                          [0]
sum of b2t 5 [ 0  0  1  0  0  0  0  0  0 ]                          [1]

Когда вы умножаете Ax, вы видите, что вы получаете линейную систему уравнений.Например, если вы умножите первую строку на неизвестный столбец, вы получите

a1 + a2 + a3 = 2

Все, что вам нужно сделать, это поставить 1 в любом из столбцов, которые появляются в уравнении, и 0 в другом месте.

Теперь все, что вам нужно сделать, это вычислить SVD для A и вставить результат в уравнение 9.17 для вычисления неизвестных.

Я рекомендую SVD, потому что он может быть эффективно вычислен.Если вы предпочитаете, вы можете дополнить матрицу A вектором результата b (A | b) и поместить A в уменьшенную форму ряда строк, чтобы получить результат.

Answer 2

Начните с первого столбца. Вы знаете верхнее и нижнее значения (из первых значений красного и желтого списков). Вычтите сумму этих двух из первых в зеленом списке, и теперь у вас также есть среднее значение.

Теперь просто работайте направо.

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

и так далее

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

Это также легко обобщается. Вам просто нужно использовать (#rows) -1 столбец-призрак.

Наслаждайтесь.

Answer 3

Для массива 10х15 единиц и нулей вы пытаетесь найти 150 неизвестных и иметь 10 + 15 + 2 * (10 + 15-1) = 73 уравнения, если игнорируете, что значения ограничены тем, что они либо или ноль. Очевидно, что вы не можете создать линейную систему на этой основе, которая имеет уникальное решение.

Так достаточно ли этого ограничения, чтобы дать уникальное решение?

Для матрицы 4x4 со следующими суммами есть два решения:

- 1 1 1 1
| 1 1 1 1
\ 0 1 1 0 1 1 0
/ 0 1 1 0 1 1 0

0   0   1   0 
1   0   0   0 
0   0   0   1 
0   1   0   0 

0   1   0   0 
0   0   0   1 
1   0   0   0 
0   0   1   0 

Так что я не ожидал бы, что будет найдено уникальное решение для больших матриц - такая же симметрия существует во многих местах:

- 1 1 0 0 1 1
| 1 1 0 0 1 1
\ 0 1 0 0 1 0 1 0 0 1 0
/ 0 1 0 0 1 0 1 0 0 1 0

0   0   0   0   1   0 
1   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   1 
0   1   0   0   0   0 

0   1   0   0   0   0 
0   0   0   0   0   1 
0   0   0   0   0   0 
0   0   0   0   0   0 
1   0   0   0   0   0 
0   0   0   0   1   0 

Answer 4

Как насчет другого варианта

Count the amount of unknown squares each sum passes through   
While there are unsolved cells
   Solve all the cells which are passed through by a sum with only one unknown square
       Cells are solved by simply subtracting off all the known cells from the sum
   Update the amount of unknown squares each sum passes through

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

Редактировать: Также обнулять любые пути с нулевой суммой, которые должны решать любые, которые разрешимы (я думаю)