상수 항이 몇 개만 변할 때 큰 선형 방정식 시스템을 어떻게 효율적으로 풀 수 있습니까? 예 :선형 시스템의 효율적인 솔루션 Ax = b 상수 항이 하나만 변할 때
현재 Ax = b 시스템이 있습니다. A의 역함수를 한 번 계산하여 행렬에 저장하고 b에있는 모든 항목 업데이트가 x를 다시 계산하기 위해 행렬 - 벡터 곱셈 A^-1 (b)를 수행 할 때마다.
두 개의 엔트리 만 b에서 업데이트되므로 비효율적입니다. A-1이 일정하지만 특정 값이 b에서 변할 때이 시스템을보다 효율적으로 해결할 수 있습니까?
필자는 uBlas 및 Eigen을 사용하지만 선택적 재 계산 문제를 해결할 솔루션에 대해서는 알지 못합니다. 어떤 지침을 주셔서 감사합니다.
계산 A^-1. b_i이 b의 i 번째 구성 요소 인 경우 의 i 번째 구성 요소와 관련하여 A^-1의 미분 경로 인 을 조사하십시오. 이는 A^-1의 열 (특히 i 번째 열)과 같습니다. 선형 함수의 파생물은 해당 도메인에서 일정합니다. 따라서 b과 b'이 있고 i 번째 구성 요소 만 다른 경우는 A^-1 b - A^-1 b' = [d/db_i A^-1] * (b-b')_i입니다. 여러 구성 요소의 경우 추가하십시오 (A^-1은 선형 임).
간단히 말해 입력 구성 요소가 0 인 일부 입력을 최적화하여 A^-1 (b'-b)을 계산할 수 있습니다 (일부 구성 요소 만 변경하면 대부분의 구성 요소가됩니다). A^-1 b' = A^-1 (b'-b) + A^-1 (b). 일부 구성 요소 만 변경된다는 것을 알고있는 경우 적절한 열 A^-1의 사본을 가져 와서 b의 해당 구성 요소가 변경된 값을 곱하면됩니다.
먼저 역행렬을 계산하지 말고, 대신 LU 분해 또는 QR 분해 (LU보다 느리지 만 안정적)를 사용하십시오. 이러한 분해는 행렬 크기에 따라 성능에 반비례하며 일반적으로 안정적입니다 (특히 QR).
A가 약간 변경되면 (예 : 순위 1 행렬) QR 분해를 업데이트하는 방법이 있지만 B가 변경된 경우 새 b로 다시 풀어야합니다.이 것을 벗어날 수는 없습니다. O (n^2)입니다.
그러나 오른쪽면 B가 고정 요소 (예 : B '= B + dB를 미리 알고 있다면, A dx = dB를 한번 풀면 Ax'= B '의 해 x'는 x + dX가됩니다.
dB가 미리 알려지지 않았지만 항상 몇 dB_i 벡터의 선형 결합 인 경우 A dx_i = dB_i를 풀 수 있지만 dB_i가 많으면^2 프로세스로 끝납니다 실제로 문제점의 선형성을 이용할 수
... 역)을 계산 금액 :
DB가b 및
b0하고 0으로 채워 져야 간의 차이 행렬이다
x0 = A_(-1)*b0
x = A_(-1)*b = x0 + A_(-1)*db
: 그것을 희박한 행렬로 압축 할 수 있습니다.
Eigen lib에는 희소 행렬 (곱셈, 역함 ...)을위한 멋진 기능이 많이 있습니다.
먼저 행렬 역변환을 수행하지 말고 솔버 라이브러리를 대신 사용하십시오. 둘째로, 은 처음으로으로 라이브러리에 x을 전달합니다.
라이브러리는 LU와 같은 분해 작업을 수행하고이를 사용하여 x을 계산합니다. 반복적 인 솔버를 선택하면, 솔직히 솔루션에 대해 집에서 설명하는 것을 이미 수행하고 있습니다. 그것은 더 나쁜 추측으로 시작하여 더 좋은 추측을 생성 할 것이고, 좋은 루틴은 프로세스의 속도를 높이기 위해 초기 추측을 취할 것입니다. 많은 상황에서 어쨌든 결과에 대한 좋은 아이디어가 있으므로이를 개발하는 것이 좋습니다. 새로운 b 이전 b 근처에 있으면
는, 새로운 x 이전 x 가까이해야하고, 그것은 좋은 초기 추측이 될 것입니다.
트릭을 수행합니다. 간결한 설명 주셔서 감사합니다. – Atlas