어느 것이 더 빠르거나 안정적인 지 : 여러 오른쪽으로 매트릭스를 반전 시키거나 3 개의 선형 방정식 시스템을 해결합니까?

Question

각각의 재귀 라운드에서 해결하고있는 두 가지 방정식이 있습니다.

x = a -inv (b) * y * inv (b), x = x + a ' * inv (b) * a,

이런 식으로 문제를 해결합니다.

c = inv (b)y <=> bc = y, 해결 C. D = Cinv (b) <=> db = c <=> b'd '= c', d '를 해결합니다.

e = inv (b)*a <=> be = a, 해결.

모든 행렬은 시간이 지남에 따라 변경되므로 모든 재귀를 다시 수행해야합니다. n은 보통 약 1-10 정도이며 아마도 더 많지만 일반적으로 그런 것입니다. B는 긍정적 인 명확성이므로 요인 화에 Cholesky를 사용할 수 있으며 여러 오른쪽의 방정식을 해결할 수 있습니다.

B를 반전시킨 다음 매트릭스 곱셈을 수행하는 것보다 훨씬 느리거나 빠르나요? 하나의 반전 대 3 개의 선형 방정식 시스템 (다른 방정식도)과 일부 전환. 나는 그것이 반전보다 적어도 수치 적으로 더 안정적이라고 생각합니까?

감사.

Answer 1

우선, 모든 매트릭스가 순서 nx n이라고 가정 해 봅시다. 그런 다음 Cholesky 인수화는 O (n^3/6) 작업 (N^3/6) 작업 (N의 큰 값)에서 수행 할 수 있습니다.

b*c (i) = y (i) 또는 l*l '*c (i) = y (i) (Cholesky)를 해결하는 것은 2*o (n^2/2) 또는 O (n^2)이지만, BC = y를 해결하면 이러한 방정식의 N을 해결하고 있습니다 (Y는 NXN이기 때문에)이므로 전체적으로 O (N^3)가 있습니다.

d '를 해결하는 것은 분명히 이것과 유사하므로 다른 o (n^3).

d '를 d로 전송하는 것은 끔찍한 o (n^2)이며 계산은 없지만 데이터를 바꾸는 것만 (물론 동일한 대각선 요소를 제외하고).

두 번째 공식에서 e = a에서 e를 해결하는 것은 Cholesky 인수화를 다시 한 번 대체하는 것이므로 o (n^3)

a ' * e는 n^2 * (n mult 및 n -1 add)입니다. O (2 * n^3 -n^2)

이것은 다음과 같습니다. /6) ~ o (5*n^3) (N의 큰 값의 경우)

매트릭스 첨가/뺄셈을 계산하지는 않았지만 B를 반전시키기로 결정한 경우 동일하지 않기 때문에 관련이 없습니다.

자, 매트릭스를 반전시키는 데 얼마나 비싸나요? 글쎄, 우리는 행렬 방정식을 해결하기 위해

b * inv (b) = i는 i = 1..n의 경우 b * x (i) = e (i)를 해결하는 것과 동일합니다. 여기서 e (i)는 I의 기본 단위 벡터입니다. 이것은 일반적으로입니다. 가우스 제거를 사용하여 시스템을 삼각형 형태로 변환하여 O (n^3/3) 작업이 필요합니다. 삼각 측량이 이루어지면 O (N^2/2) 작업을 해결하려면 (후진 대체) 작업이 필요합니다. 그러나 이것은 n 번 이루어져야하며, 이는 우리에게 총 o (n^4/3) + o (n^3/2) 작업을 제공해야합니다.

그러나 inv (b) 계산 B의 cholesky 인수를 알 때 o (n^3) (l*l '*inv (b) = i를 해결하기 때문에 e = a).

그래서 우리는 다음과 같습니다. O (n^3/6) (B) + O (n^3) (Cholesky와 함께 Inv (b) 계산) + 4*O (2n^3-n^2) (4 개의 매트릭스 곱하기) ~ o (9*n^3)는 조금 더 좋지만 여전히 더 나쁩니다.

그래서 나는 당신이 당신의 현재 접근 방식을 유지하는 것이 좋습니다. 그러나 이것은 N의 큰 값을위한 것임을 명심해야합니다. N이 100+가 아니라면 어쨌든 그렇게 중요하다고 생각하지 않습니다.