Исключение Гаусса - матрицы линейных уравнений, алгоритм

Для массива 10x15 единиц и нулей вы попытаетесь найти 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 

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

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

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

и так далее

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

Это также легко обобщается. Вам просто нужно использовать (#rows)-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 3.

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

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 в сокращенную ступенчатую форму строк, чтобы получить результат.

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

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

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

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