Эффективное решение линейной системы Ax = b при изменении только одного постоянного члена
Как эффективно решить большую систему линейных уравнений, когда изменяется только несколько постоянных членов? Например:
У меня сейчас система Ax = b. Я вычисляю инверсию A один раз, сохраняю ее в матрице и каждый раз, когда любые обновления записи в b выполняют умножение матрицы на вектор A ^ -1 (b), чтобы пересчитать x.
Это неэффективно, так как только пара записей будет иметь обновление в b. Существуют ли более эффективные способы решения этой системы, когда A-1 остается постоянным, но конкретные известные значения изменяются в b?
Я использую uBlas и Eigen, но не знаю решений, которые бы решали эту проблему выборочного пересчета. Спасибо за любое руководство.
Решение
вычисление A^-1, Если b_i это i-й компонент bзатем изучите d/db_i A^-1 b (производная от A ^ -1 по i-му компоненту b) — равно столбцу A^-1 (в частности, i-й столбец). А производные линейных функций постоянны по своей области. Так что если у вас есть b а также b'и они отличаются только i-м компонентом, то A^-1 b - A^-1 b' = [d/db_i A^-1] * (b-b')_i, Для нескольких компонентов просто сложите их (как A^-1 является линейным).
Или, короче говоря, вы можете рассчитать A^-1 (b'-b) с некоторыми оптимизациями для входных компонентов, которые равны нулю (которые, если изменятся только некоторые компоненты, составят большинство компонентов). A^-1 b' = A^-1 (b'-b) + A^-1 (b), И если вы знаете, что изменятся только некоторые компоненты, вы можете взять копию соответствующего столбца A^-1, затем умножьте это на изменение в этом компоненте b.
Другие решения
Вы можете воспользоваться линейностью задачи:
x0 = A_(-1)*b0
x = A_(-1)*b = x0 + A_(-1)*db
где db — матрица разностей между b а также b0 и он должен быть заполнен нулями: вы можете сжать его до разреженной матрицы.
Эйген Либ имеет много интересных функций для разреженных матриц (умножение, обратное, …).
Во-первых, не вычисляйте обратную матрицу, используйте декомпозицию LU или декомпозицию QR (медленнее, чем LU, но стабильнее). Такие разложения масштабируются лучше, чем инверсия производительности с размером матрицы, и, как правило, стабильнее (особенно QR).
Существуют способы обновить QR-декомпозицию, если A немного изменяется (например, с помощью матрицы ранга 1), но если B изменяется, вы должны решить снова с новым b — вы не можете избежать этого, и это O (n ^ 2).
Однако, если правая часть B изменяется только на фиксированный элемент, т.е. B ‘= B + дБ с заранее известным дБ, вы можете решить A dx = дБ раз и навсегда, и теперь решение x’ of Ax ‘= B’ равно x + dX.
Если дБ неизвестно заранее, но всегда представляет собой линейную комбинацию нескольких векторов dB_i, вы можете решить для A dx_i = dB_i, но если у вас много таких dB_i, вы получите процесс ^ 2 (на самом деле это составляет вычисление обратного) …
Во-первых, не выполняйте инверсию матрицы, используйте вместо этого библиотеку решателей. Во-вторых, передать ваш начальный x в библиотеку как первое предположение.
Библиотека выполнит некую декомпозицию, такую как LU, и использует ее для вычисления x, Если вы выбираете итеративный решатель, то он уже делает в значительной степени то, что вы описываете, чтобы сосредоточиться на решении; оно начнется с худшего предположения и сгенерирует лучшее, а любая хорошая процедура потребует первоначального предположения, чтобы ускорить процесс. Во многих случаях у вас есть хорошее представление о результате, так что имеет смысл использовать это.
Если новый b рядом со старым bтогда новый x должно быть рядом со старым xи это послужит хорошей первоначальной догадкой.