MATLAB과 함께하는 가우스 소거법 (수치해석)

--- ---

선형방정식 in 수치해석 with MATLAB

4일남은 수치해석 중간고사를 대비하여 복습겸 수치해석 정리를 해보려합니다.

📔단순 가우스 소거법

미지수가 동일한 1차 연립방정식의 체계를 연구하는 것이 선형대수(Linear Algebra)입니다.

가우스 소거법은 연립 일차방정식을 풀이하는 알고리즘이다.

보통 행렬을 사용한다.

예를 통해서 가우스 소거법의 알고리즘을 알아봅시다.
가우스 소거법은 후방대입과정(Back Substitution) 을 통해서 구하는 방법입니다.

1. 행렬을 생성
   
   
   $A = \begin{bmatrix} a_{11} & a_{12}& a_{13}\\ a_{21} & a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33} \end{bmatrix},b = \begin{bmatrix} b_1\\b_2\\b_3 \end{bmatrix},x = \begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}$
   
   

$a_{11} \mathrlap{\,/}{=} 0$ 으로가정하고 행렬을 만듭니다.

우선적으로 가우스소거법을 사용하려면 행렬A와 b를 결합해야합니다.
결합된 행렬은 다음과 같습니다.

$A = \begin{bmatrix} a_{11} & a_{12}& a_{13} & b_1\\ a_{21} & a_{22}& a_{23}&b_2\\ a_{31}& a_{32}& a_{33} &b_3 \end{bmatrix}$


2. Pivot을 설정


우선적으로 Pivot을 설정해야합니다. Pivot은 대각행렬(Diaogna Matrix)로 이 행렬에서는 $a_{11}, a_{22}, a_{33}$ 원소를 의미합니다.
그러므로 처음 Pivot값은 $a_{11}$입니다.

4. 행곱수(Row Multiplier)을 설정
   
   

Multiplier을 설정해야합니다. Multiplier란 Pivot아래 원소의 값을 Pivot으로 나눈 값입니다.

$m_{21} = \frac {a_{21}} {a_{11}}, m_{31} = \frac {a_{31}} {a_{11}}$


5. Pivot을 가진 행의 모든 원소에 Multiplier을 곱하고 해당 Multiplier가 있는 행에 빼준다.

$R(2) - R(1)m_{21}\\ R(3) - R(1)m_{31}$

그렇다면 $a_{21},a_{31}$ 이 두 원소는 무조건 0 즉 Pivot아래의 모든 원소들은 0으로 바뀌게 되고, 1행을 제외한 다른 행의 원소들 모두 바뀌게 됩니다.

$A = \begin{bmatrix} a_{11} & a_{12}& a_{13} & b_1\\ 0 & a_{22}^2& a_{23}^2&b_2^2\\ 0& a_{32}^2& a_{33}^2 &b_3^2 \end{bmatrix}$

6. Pivot을 재설정 위의경우는 $a_{22}$로 설정한다.

Pivot을 재설정하여 같은 식으로 연산해줍니다.
$A = \begin{bmatrix} a_{11} & a_{12}& a_{13} & b_1\\ 0 & a_{22}^2& a_{23}^2&b_2^2\\ 0& 0& a_{33}^3 &b_3^3 \end{bmatrix}$
연산결과 다음과 같은 삼각행렬을 얻을 수 있습니다.
위 행렬을 통해서 x3의 값을 구할 수 있습니다.

$x_3 = \frac {c_3^3} {a_{33}^3}$
이 $x_3$값을 위 행에 넣으면 $x_2$가 구해지고 $x_2$를 그 위 행에 넣으면 남은 $x_1$을 구할 수 있습니다.

이를 General하게 표현하면
$x_i = \frac {b_i^{(i)} - \sum^n_{j=i+1} a_{ij}^{(i)}x_n} {a_{ii}^i}$
으로 표현이 가능합니다.

---

한계

위 가우스 소거법은 $a_{kk}^k$가 0이 아니라는 전제하에서만 가능합니다. 그리고 연산횟수는 O($\frac {n^3} 3$)으로 매우 비효율적입니다.

Matlab Code

MATLAB을 통한 가우스 소거법을 알아봅시다.

function gauss(A,b)

C = [A b];

n = length(b); % 몇번 반복할지는 b행렬의 길이를 기준으로 합니다.
for i=1:n-1 % 반복
for k=i+1:n % 반복
C(k,:) = -C(k,i)/C(i,i) * C(i,:)+C(k,:); % k를 변화시키면서 연산을 해줍니다. 
% 초기값은 2이므로 C(2,:) 즉 2행에서의 연산을 하게되면 위의 나와있는 설명처럼 k = 2,3에서의 연산을 수행합니다.
end
end
A =C(:,1:n)
b =C(:,n+1)
x(n) = b(n)/A(n,n) 
for k = n-1:-1:1 % 출력용 코드

x(k) = (b(k)-sum(A(k,k+1:n).*(x(k+1:n))))/A(k,k)

end

C = [A b]를 통해서 행렬을 합쳐줍니다.

결과값은 아래와 같습니다.

>> A = [1 1 1 1;2 3 1 5;-1 1 -5 3;3 1 7 -2];
>> b = [10; 31; -2; 18];
>> gauss(A,b)

A =

     1     1     1     1
     0     1    -1     3
     0     0    -2    -2
     0     0     0    -1


b =

    10
    11
   -14
    -4


x =

     0     0     0     4


x =

     0     0     3     4


x =

     0     2     3     4


x =

     1     2     3     4

이상으로 수치해석의 가우스소거법을 알아보았습니다. 감사합니다.

Written with StackEdit.