У меня есть n числовых переменных (не знаю, пофиг), назовем их X[n]. У меня также есть отношения m >> n между ними, назовем их R[m], вида:
X[i] = alpha*X[j], alpha — ненулевое положительное действительное число, i и j различны, но пара (i, j) не обязательно уникальна (т. е. могут быть две связи между одними и теми же переменными с разным альфа-фактором)
Что я пытаюсь сделать, так это найти набор alpha параметров, которые решают переопределенную систему в некотором смысле наименьших квадратов. Идеальным решением было бы минимизировать квадрат суммы различий между каждым параметром уравнения и его выбранным значением, но меня устраивает следующее приближение:
Если я превращу m уравнений в переопределенную систему из n неизвестных, любой численный решатель на основе псевдообратных чисел даст мне очевидное решение (все нули). Итак, что я сейчас делаю, так это добавляю в смесь еще одно уравнение, x[0] = 1 (на самом деле подойдет любая константа) и решаю сгенерированную систему в смысле наименьших квадратов, используя псевдоинверсию Мура-Пенроуза. Хотя это пытается минимизировать сумму (x[0] - 1)^2 и сумму квадратов x[i] - alpha*x[j], я нахожу это хорошим и численно стабильным приближением к моей проблеме. Вот пример:
a = 1
a = 2*b
b = 3*c
a = 5*c
в Октаве:
A = [
1 0 0;
1 -2 0;
0 1 -3;
1 0 -5;
]
B = [1; 0; 0; 0]
C = pinv(A) * B or better yet:
C = pinv(A)(:,1)
Что дает значения для a, b, c: [0.99383; 0.51235; 0.19136] Что дает мне следующие (разумные) отношения:
a = 1.9398*b
b = 2.6774*c
a = 5.1935*c
Так что прямо сейчас мне нужно реализовать это на C/C++/Java, и у меня есть следующие вопросы:
Есть ли более быстрый способ решить мою проблему, или я на правильном пути с созданием переопределенной системы и вычислением псевдообратной?
Мое текущее решение требует разложения по сингулярным числам и трех матричных умножений, что немного много, учитывая, что m может быть 5000 или даже 10000. Существуют ли более быстрые способы вычисления псевдообратного (на самом деле, мне нужен только первый столбец, а не вся матрица при условии, что B равно нулю, кроме первой строки) учитывая разреженность матрицы (каждая строка содержит ровно два ненулевых значения, одно из которых всегда равно единице, а другое всегда отрицательно)
Какие математические библиотеки вы бы предложили использовать для этого? Лапак в порядке?
Я также открыт для любых других предложений, при условии, что они численно стабильны и асимптотически быстры (скажем, k*n^2, где k может быть большим).
