Hack your life

[선형대수] 너무 쉬운 고유값(eigenvalue)과 고유벡터(eigenvector)

고유값과 고유벡터의 의미는 나중에 설명하기로 하고 아래의 행렬 곱을 보자.

계산 결과 값에 어떤 값을 곱해서 원래의 111행렬을 만들 수 없다.

이번엔 1 1 0 행렬을 곱해보자.

이 경우엔 결과 값에 1/3을 곱해서 1 1 0을 만들 수 있다.

여기서  

에서 3이 고유값이고 이 고유벡터이다.

정의

n x n 행렬 A가 있을 때 아래의 식을 만족하는 는 고유값, X는 고유벡터이다.

이식을 방정식 형태로 쓰면 

 이 된다. 고유벡터는 영이 아닌 벡터로 정의 되어있으므로 x의 계수행렬이 특이행렬이어야 한다.

 는 A의 특성방정식(characteristic equation)이라고 부른다.

이 방정식을 풀면 고유값과 고유벡터를 구할 수 있다.

예제1

의 특성다항식은 아래와 같다.

그리고 행렬식 계산을 통해 구한 특성방정식은 아래와 같다.

방정식을 풀면 해는 2 또는 -1이다.

즉, A의 고유값은 2와 -1이다.

람다 2를 위의 식에 다시 대입하면,

이고

이 되어 의 관계를 얻는다. 이 방정식 계의 해는 r을 스칼라로 놓고 

로 나타낼 수 있다. 즉 에 대응하는 고유벡터는  의 형태인 영이 아닌 벡터가 된다.

마찬가지로 을 대입하면 형태의 고유벡터를 구할 수 있다. (s는 스칼라)

마코프체인(Markov chain)

마코프체인은 과거의 상태와 현재 상태가 주어질 때, 미래 상태의 조건부 분포는 과거 상태에는 독립이고 오직 현재 상태에만 종속한다.

예를 들어보자,

1. 날씨 예측

 내일 비가 올 가능성은 오직 오늘 비가 오는지 안 오는지에만 종속하고 과거의 날씨에는 종속하지 않는다고 가정한다. 또한, 오늘 비가 올 때 내일 비가 올 확률은 a이고 오늘 비가 오지 않을 때 내일 비가 올 확률은 b라고 가정하자.

비가 올 때는 상태를 0이라고 하고 비가 오지 않을 때는 상태를 1이라고 하면, 이 과정은 다음의 전이확률을 갖는 2-상태 마코프체인이 된다.

2. 확률 과정을 마코프체인으로 변환하기

오늘 비가 올지의 여부가 과거 날씨 중 최근 이틀의 날씨에만 영향을 받는다고 가정하자. 

1. 지난 이틀 동안 비가 왔으면 내일도 비가 올 확률은 0.7이다.

2. 어제는 비가 오지 않고 오늘 비가 왔다면 내일 비가 올 확률은 0.5이다.

3. 어제는 비가 왔지만 오늘은 오지 않았다면 내일 비가 올 확률은 0.4이다.

4. 지난 이틀 간 비가 오지 않았다면 내일 비가 올 확률은 0.2이다. 

상태 0 : 오늘과 어제 모두 비가 옴

상태 1 : 오늘 비가 오고 어제는 안 옴

상태 2 : 어제 비가 오고 오늘은 안 옴

상태 3 : 어제와 오늘 모두 비가 안 옴

위 상태는 다음과 같은 전이확률 행렬을 갖는 4-상태 마코프체인을 나타낼 것이다.

3. 랜덤보행 모형

상태공간이 정수로 주어진 마코프체인이 어떤 상수 0<p<1에 대해 다음 관계를 만족하면 랜덤보행(random walk)라고 말한다.

이 마코프체인이 랜덤보행이라고 불리는 이유는, 직선 위를 걷고 있는 사람이 각 시점마다 확률 p로 오른쪽으로 한걸음 가든 1-p의 확률로 왼쪽으로 한걸음 가는 것에 대한 모형으로 볼 수 있기 때문이다. (무한도전에서 위에서 공 떨어뜨리면 중간에 막대에 맞고 아래로 내려가는 복불복 게임이랑 비슷한 것 같다. 사진은 못 찾음 ㅎㅎ)

4. 인구이동 모델

2007년에 미국의 도시에 살고 있는 사람의 수는 8천2백만이고 주변 교외에 살고 있는 사람의 수는 1억6천3백만으로 추정된다. 이 정보를 행렬 로 나타내자. 

2007년 인구 흐름은 도시에 그대로 머물 확률은 0.96이었고 교외로 이사 갈 확률은 0.04였다. 거꾸로 교외에서 도시로 이주할 확률은 0.01이었고 교외에 남아 있을 확률은 0.99였다. 이 확률을 원소로 하여 확률행렬 P를 다음과 같이 쓸 수 있다.

       도시 교외(에서)  (로)

2008년도의 인구는 행렬 곱으로 얻을 수 있다.

행렬 P로 표현된 인구흐름이 매년 변하지 않는다고 가정하면, n년 후의 인구 분포는,

로 나타낼 수 있다. 즉, 

 이고 은 n-단계 전이행렬로 불린다.

사실 인구 인구이동의 확률행렬 P는 매년 같다고 하기 어려운 점이 있다. 그래서 인구 이동 보다는 유전 법칙이 마코프체인을 적용하기에 적절하다고 생각한다.

[선형대수] 선형계획법 Linear Programming 개론

선형계획법(linear programming 줄여서 LP라고도 한다.)은 한정된 자원(제한조건)을 효율적으로 할당하여 목적함수를 최대회하거나 최소화하는 문제를 다룬다.

선형계획법이 말은 어렵지만 중학교 수학에서도 나왔던 것으로 기억한다. 문제의 예를 들면, 어떤 회사가 계산기 A와 B 두 종류를 생산하는데, 생산하는데 각각 5시간과 2시간이 소요된다. 회사는 계산기를 생산하는데 1주일에 900시간을 사용할 수 있다. A와 B를 생산하는데 드는 비용은 각각 8만원, 10만원이며, 사용가능한 자금은 2800만원이다. 대 당 이익은 각각 3만원 2만원이다. 회사의 목표는 이익을 최대화 하는 것이다.

이러한 문제를 푸는 방법은 

1) 조건을 부등식으로 나타내고, 2) 제약조건을 그래프로 표현한 다음 3)가능한 영역에서 최적의 해를 찾는 것이다.

보통 부등식은 선형부등식이고 2개의 부등식 (x>0, y>0과 같은 기본 조건제외)로 이루어져있다.

이러한 부등식은 영역의 꼭짓점이나 모서리에서 최적해를 갖는다는 사실이 증명되어있다. *1)

꼭지점을 최적해로 갖는 경우엔 해가 1개이고 모서리의 모든 점을 최적해로 갖는 경우엔 많은 해를 가진다.

함수의 최소값

목적함수의 최소값을 결정하는 문제는 가능영역에서 -f, 즉 f의 음의 최대값을 구함으로써 풀 수 있다.

이러한 방법은 가능영역(부등식을 만족하는 영역)이 볼록(convex)한 모양인 경우이다.

볼록한 모양이라는 것은 영역을 이루는 형태가 안으로 들어가는 부분이 없다는 뜻이고, 영역 내에 빈공간이 없다는 뜻이다.

*1) 목적함수의 최대값이 한 꼭지점이나 모서리에 생기는 이유?

가능영역이 있고 목적함수가 있을 때, 목적함수 직선의 y절편을 어떻게 조절하느냐에 따라서 직선이 가능영역의 안 밖으로 평행하게 움직이게 된다.

그 중 값이 최대가 되려면 자연스럽게 목적함수 직선이 가능영역에 걸치는 형태가 되어야 한다.

가능한 경우는 아래 그림과 같이 꼭지점 또는 모서리 2가지 경우가 있다.

선형계획 문제를 해결하기 위해 소개된 위의 그래프 방법에는 한계가 있다. 세 개 이상의 변수를 포함하는 경우에 대해 기하학적 접근은 비현실적이기 때문에 많은 변수를 가진 문제애 대해서는 대수적인 방법인 심플렉스 방법(simplex method)를 사용한다.

Simplex method는 쉽게 컴퓨터 프로그램화 할 수 있는 장점도 있다.  최적해는 심플렉스 알고리즘이라 불리는 알고리즘에서 기본 행 연산들을 사용하여 열에 영을 만든다. 심플렉스 알고리즘에서도 축들을 선택하여 열의 원소들에 영을 만드는데 사용하지만, 가우스-요르단 소거와는 다른 기준을 적용한다.

심플렉스 알고리즘

1. 선형방정식계의 첨가행렬을 구성한다. 이것을 초기 심플렉스 표(inital simpex tableau)라고 한다.

2. 마지막 행에서 마지막 원소 이외의 크기가 가장 큰 음의 원소를 찾는다(만일 둘 혹은 그 이상의 원소가 이 성질을 갖는다면 이들 중 어떤 것을 선택해도 상관없다). 만일 그런 원소들이 모두 음이 아니라면 그 표는 최종 형태이다.

3. 이 음의 원소가 들어 있는 열의 각 원소에 대해, 원소가 양이면 이 원소로 마지막 열의 대응하는 원소를 나눈다.

4. 3에서 나눈 결과가 가장 작은 행을 선택한다. 이 행과 2에서 선택된 열에 해당하는 원소를 축 원소(pivot element)라고 한다. 

5. 행연산을 사용하여 축 위치에 1을 하나 만들고, 축 열의 다른 원소들은 모두 0으로 만든다.

6. 마지막 행에서 음의 원소들이 모두 없어질 때까지 단계 2-5를 반복한다. 최종 행렬을 최종 심플렉스 표(final simplex tableau)라고 하며, 이 표로부터 최적해를 얻을 수 있다.

예제

다음의 제약조건 하에서 의 최대값을 구하자.

첫 번째 부등식을 만족하는 각각의 x, y 에 대해서 다음을 만족하는 음이 아닌 변수 u의 값이 존재할 것이다. 마찬가지로 두번째 부등식도 아래와 같이 표현할 수 있다. 이러한 u와 v를 원래 변수들의 느슨한 부분을 메워준다고 해서 여유변수(slack variable)라고 한다.

그리고 목적함수는 다음과 같은 형태로 쓰여진다.

이제 원래 문제는 다음 선형방정식계에서 f가 가능한 큰 값이 되도록 해를 결정하는 문제가 되었다.

심플렉스 알고리즘을 적용해보면, 우선 900/5 < 2800/8 이므로 1행이 축이된다.(1행의 x계수 5를 1로 만들것이다.)

최종 심플렉스표가 만들어졌다. 마지막 행에서 음의 원소들은 모두 제거되었고, 이 표는 다음의 선형방정식계에 대응된다.

u와 v가 양수이므로, 마지막 방정식에서 u, v = 0 일 때 f가 최대값 700을 갖는다. u, v의 값 0 을 위의 식에 대입하면 x=100, y=200을 얻는다. 이 결과는 기하학을 사용하여 얻은 결과와 일치한다.

도움이 되셨으면 공감 한번  눌러주세요^^

[선형대수] 가우스-요르단 소거법

행렬을 사용하여 선형방정식계를 풀 때 가우스-요르단 방법을 사용한다.

그전에 몇 가지 용어 설명!

계수행렬과 첨가행렬

아래의 선형방정식계를 변수의 계수들로 구성되는 계수행렬과 계수와 우변의 상수를 함께 포함하는 첨가행렬로 나타낼 수 있다.

  (계수행렬)         (첨가행렬)

기본변환(Elemetary transformations)를 통해 선형방정식계를 다른 선형방정식계로 바꿀 수 있다.

이 변환은 행렬의 기본 행연산(elemetary row operation)을 이용하는게 편하다. 컴퓨터에서도 선형방정식계가 행렬로 입력되고 처리된다.

기본 행연산

1. 두 행을 교환한다.

2. 한 행에 영이 아닌 상수를 곱한다.

3. 한 행의 원소들의 상수배를 다른 행의 해당 원소들에 더한다.

이렇게 기본 행연산을 통해 만들어진 행렬을 행동등 행렬(row equivalent matrices)라고 부른다. 

기호 를 사용하여 동등관계를 나타낸다.

그러면 방정식계를 풀어보자.

이 식을 행렬로 만들면, 

그리고 기본 행연산을 이용해서 행렬을 조작한다.

여기서 계속 진행하기 위해서는 (2, 2) 위치에 0이 아닌 원소가 필요하다. 이를 위해 2행과 3행을 교환한다.

첨가행렬은 계수행렬 A와 상수항 B의 열로 구성된다. 이 행렬을 [A : B]로 쓴다.

행연산을 사용하여 첨가행렬을 한 열씩 ;단위행렬 과 같은 형태로 만들수 있다.

이 마지막 행렬 를 원래 첨가행렬의 기약 사다리형(reduced echelon form)이라고 부른다.

만약 [A : B]가 기약 사다리형으로 변환될 수 없으면 방정식계는 유일한 해를 갖지 않는다.

기약사다리형의 조건

1. 모든 원소가 영인 행은 모두 행렬의 바닥에 모여있다.

2. 그 외의 각 행에서 영이 아닌 첫 원소는 1이다. 이 원소를 선도 1이라고 부른다.

3. 첫 행 이후의 각 행에서 선도 1은 윗 행의 선도 1의 오른쪽에 위치한다.

4. 선도 1을 포함하는 열의 다른 원소는 모두 0이다.

많은 해를 갖는 경우?!

아래의 기약 사다리형의 경우

여기서 x3에 임의의 값 r을 넣으면 계의 일반해를 얻을 수 있다.

매개변수 r은 실수 집합이기 때문에 많은 해를 갖는다. r에 특정한 값을 넣어주면 특정한 해들이 얻어진다.

도움이 되셨으면 공감 한번  눌러주세요^^

Boolean Algebra의 제2 분배법칙

정보처리기사 시나공 책에는 해설이 되어있지않고 "이해하지 말고 그냥 외우세요."라고 되어있다.

이해가 잘 안되어 조금 더 생각해보았다.

A + BC = (A+B)(A+C)

일반적인 대수식에서는 성립되지 않는다.

하지만 참거짓의 값만 있는 Boolean Algebra에서는 성립한다.

우변을 분배법칙으로 풀면

= AA + AC + AB + BC , 여기서 AB=BA이다. 그리고 AA = A 이므로

= A(1 + C + B) + BC, 1+ C + B  = 1이므로

= A + BC