가우스 - 조던 소거법으로 계산한 A^-1

2022.12.15 - [미분방정식] - 4.4 역행렬

4.4 역행렬

Av = b 의 방정식을 풀기 위해 v = A^-1 b 로 풀 수 있다. 하지만 A^-1 을 계산하고 이를 b 에 곱하는 것은 비효율적이다.

가우스-조던 소거법을 사용하면 v 를 바로 계산할 수 있다.

A = np.array(([2,-1,0],[-1,2,-1],[0,-1,2]))
A
>>>
array([[ 2, -1,  0],
       [-1,  2, -1],
       [ 0, -1,  2]])
       
I = np.identity(A.shape[0])
I
>>>
array([[1., 0., 0.],
       [0., 1., 0.],
       [0., 0., 1.]])
       
AI = np.hstack([A,I])
AI
>>>
array([[ 2., -1.,  0.,  1.,  0.,  0.],
       [-1.,  2., -1.,  0.,  1.,  0.],
       [ 0., -1.,  2.,  0.,  0.,  1.]])

임의의 정사각 행렬 A 와 동일한 크기의 단위 행렬의 생성,

두 행렬의 가로 방향 결합

a10 = AI[1,0] / AI[0,0]
a10
>>>
-0.5

AI[1] = AI[1] - AI[0] * a10
AI[1]
>>>
array([ 0. ,  1.5, -1. ,  0.5,  1. ,  0. ])

a21 = AI[2,1] / AI[1,1]
a21
>>>
-0.6666666666666666

AI[2] = AI[2] - AI[1] * a21
AI[2]
>>>
array([0.        , 0.        , 1.33333333, 0.33333333, 0.66666667, 1.        ])

AI
>>>
array([[ 2.        , -1.        ,  0.        ,  1.        ,  0.        , 0.        ],
       [ 0.        ,  1.5       , -1.        ,  0.5       ,  1.        , 0.        ],
       [ 0.        ,  0.        ,  1.33333333,  0.33333333,  0.66666667, 1.        ]])

처음 세 열의 행렬은 U 이다. 피봇 2, 3/2, 4/3 은 이들의 대각선에 있다. 

가우스는 역대입법으로 마무리할 것이고, 조던의 아이디어는 소거를 계속하는 것이다.

항등 행렬을 만들기 위해 계속한다.

위의 행에서 행이 빼지고, 피봇 위에 0을 만든다.

a12 = AI[1,2] / AI[2,2]
a12
>>>
-0.7499999999999999

AI[1] = AI[1] - AI[2] * a12
AI[1]
>>>
array([0.  , 1.5 , 0.  , 0.75, 1.5 , 0.75])

a11 = AI[0,1] / AI[1,1]
a11
>>>
-0.6666666666666666

AI[0] = AI[0] - AI[1] * a11
AI[0]
>>>
array([2. , 0. , 0. , 1.5, 1. , 0.5])

AI
>>>
array([[2.        , 0.        , 0.        , 1.5       , 1.        , 0.5       ],
       [0.        , 1.5       , 0.        , 0.75      , 1.5       , 0.75      ],
       [0.        , 0.        , 1.33333333, 0.33333333, 0.66666667, 1.        ]])

가우스 조던 소거법의 마지막 단계는 각 행을 이의 피봇으로 나누는 것이다. 이때 새로운 피봇은 1이다. 

AI[0] = AI[0] / AI[0,0]
AI[1] = AI[1] / AI[1,1]
AI[2] = AI[2] / AI[2,2]
AI
>>>
array([[1.  , 0.  , 0.  , 0.75, 0.5 , 0.25],
       [0.  , 1.  , 0.  , 0.5 , 1.  , 0.5 ],
       [0.  , 0.  , 1.  , 0.25, 0.5 , 0.75]])

위와 같이 행렬의 왼쪽에 있는 절반에서 I 를 구했다. 이는 A 가 가역이기 때문이다. A^-1 의 세 열은 I A^-1 의 오른쪽에 있는 절반이다.

AI 에 A^-1 을 곱해 I A^-1 을 얻었다

A 를 I 로 바꾸면서 소거 단계는 역행렬을 만든다. 

가우스 조던 소거법은 A^-1 의 계산량이 많은 이유를 보여준다. 우리는 n 개의 열에 대해 n 개의 방정식을 풀어야 한다.