Search
Duplicate

이상엽/ 선형대수학/ 최적화 문제

곡선 적합

보간법

개념

주어진 특징 점들을 포함하는 함수를 구하는 방법
정리) 좌표평면에 있는 임의의 서로 다른 nn개의 점을 지나는 kk차 다항함수는 유일하게 존재한다. (단 nnk<nk < n인 자연수)

사례

네 점 (1,3),(2,2),(3,5),(4,0)(1, 3), (2, -2), (3, -5), (4, 0)을 모두 지나는 3차 함수
f(x)=a0+a1x+a2x2+a3x3f(x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3}
를 구하자. 우선 다음의 방정식을 세운다.
Step 1)
(1x1x12x131x2x22x231x3x32x331x4x42x43)(a0a1a2a3)=(y1y2y3y4)\left( \begin{array}{rrrr} 1 & x_{1} & x_{1}^{2} & x_{1}^{3} \\ 1 & x_{2} & x_{2}^{2} & x_{2}^{3} \\ 1 & x_{3} & x_{3}^{2} & x_{3}^{3} \\ 1 & x_{4} & x_{4}^{2} & x_{4}^{3} \end{array} \right) \left( \begin{array}{rrrr} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{array} \right) = \left( \begin{array}{rrrr} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{array} \right)
Step 2) 네 점을 대입하고 첨가행렬을 만든다.
(11113124821392751416640)\left( \begin{array}{rrrrr} 1 & 1 & 1 & 1 & 3 \\ 1 & 2 & 4 & 8 & -2 \\ 1 & 3 & 9 & 27 & -5 \\ 1 & 4 & 16 & 64 & 0 \end{array} \right)
Step 3) 첨가행렬을 가우스-조던 소거법을 이용하여 풀이한다.
(11113124821392751416640)(10004010030010500011)\left( \begin{array}{rrrrr} 1 & 1 & 1 & 1 & 3 \\ 1 & 2 & 4 & 8 & -2 \\ 1 & 3 & 9 & 27 & -5 \\ 1 & 4 & 16 & 64 & 0 \end{array} \right) \Rightarrow \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 4 \\ 0 & 1 & 0 & 0 & 3 \\ 0 & 0 & 1 & 0 & -5 \\ 0 & 0 & 0 & 1 & 1 \end{array} \right)
Step 4)
a0=4,a1=3,a2=5,a3=1a_{0} = 4, a_{1} = 3, a_{2} = -5, a_{3} = 1 이므로 f(x)=4+3x5x2+x3f(x) = 4 + 3 x - 5 x^{2} + x^{3}이다.
곡선 접합은 현재 가진 데이터에 대해 분석은 잘 할 수 있지만, 신규 데이터가 현재 그려 놓은 곡선 위에 존재한다는 보증이 없음. 유연성이 매우 떨어진다.
애초에 데이터를 모두 포함하는 함수가 존재하지 않는 경우도 많음.

최소제곱법

곡선 접합의 단점을 보완할 수 있는 방법.
가우스가 창안한 방법으로 가우스는 이 방법을 통해 소행성 '세레스' 의 궤도를 정확히 예측해 냄.

개념

특징 점들을 포함하는 함수를 특정 지을 수 없을 때, 실제 해와의 오차 제곱 합이 최소가 되는 근사적인 해를 구하는 방법
정리) 방정식 Ax=BAx = B을 변형한 방정식 ATAx=ATBA^{T}Ax = A^{T}B (정규방정식)의 모든 해는 Ax=BAx = B의 최소제곱해이다.
요게 결국 선형회귀이다.
ATAx=ATBA^{T}Ax = A^{T}B(정규방정식)의 모든 해는 Ax=BAx = B의 최소제곱해이라는 부분은 증명이 복잡하므로 강의 상에서는 생략.

사례

네 점 (0,1),(1,3),(2,4),(3,4)(0, 1), (1, 3), (2, 4), (3, 4)에 근사하는 일차 함수 f(x)=a0+a1xf(x) = a_{0} + a_{1} x을 구하자. 우선 다음의 방정식을 세운다.
Step 1) Ax=BAx = B
(1x11x21x31x4)(a0a1)=(y1y2y3y4)\Leftrightarrow \left( \begin{array}{rrrr} 1 & x_{1} \\ 1 & x_{2} \\ 1 & x_{3} \\ 1 & x_{4} \end{array} \right) \left( \begin{array}{rr} a_{0} \\ a_{1} \end{array} \right) = \left( \begin{array}{rrrr} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{array} \right)
Step 2) 네 점을 대입하고 정규방정식 ATAx=ATBA^{T}Ax = A^{T}B 으로부터 방정식 x=(ATA)1ATBx = (A^{T}A)^{-1} A^{T}B 을 구성한다.
ATA=(46614 )A^{T}A = \left( \begin{array}{rr} 4 & 6 \\ 6 & 14  \end{array} \right) 이므로
(ATA)1=(46614)1=110(7332)(A^{T}A)^{-1} = \left( \begin{array}{rr} 4 & 6 \\ 6 & 14 \end{array} \right)^{-1} = {1 \over 10} \left( \begin{array}{rr} 7 & -3 \\ -3 & 2 \end{array} \right)
x=110(7332)(11110123)(1344)\therefore x = {1 \over 10} \left( \begin{array}{rr} 7 & -3 \\ -3 & 2 \end{array} \right) \left( \begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \end{array} \right) \left( \begin{array}{rrrr} 1 \\ 3 \\ 4 \\ 4 \end{array} \right)
Step 3) x=(a0a1)=(231)x = \left( \begin{array}{rr} a_{0} \\ a_{1} \end{array} \right) = \left( \begin{array}{rr} {2 \over 3} \\ 1 \end{array} \right)이므로 구하고자 하는 함수는 f(x)=32+xf(x) = {3 \over 2} + x 이다.

n차 일반화

mm개의 자료점 (x1,y1),(x2,y2),...,(xm,ym)(x_{1}, y_{1}), (x_{2}, y_{2}), ... , (x_{m}, y_{m})에 대해 nn차 다항식 y=a0+a1x+...+anxny = a_{0} + a_{1} x + ... + a_{n} x^{n}을 최소제곱법을 이용하여 근사하기 위해서는 Ax=BAx = B
A=(1x1...x1n1x2...x2n............1xm...xmn),x=(a0a1...an),B=(y1y2...ym)A = \left( \begin{array}{rrrr} 1 & x_{1} & ... & x_{1}^{n} \\ 1 & x_{2} & ... & x_{2}^{n} \\ ... & ... & ... & ... \\ 1 & x_{m} & ... & x_{m}^{n} \end{array} \right), x = \left( \begin{array}{rrrr} a_{0} \\ a_{1} \\ ... \\ a_{n} \end{array} \right), B = \left( \begin{array}{rrrr} y_{1} \\ y_{2} \\ ... \\ y_{m} \end{array} \right)
로 설정하면 된다.

두 방법의 비교

Search
보간법
최소제곱법
데이터의 수
Open
적을 수록 좋음
많아도 무방함
정밀도
Open
매우 높음
상대적으로 낮음
신축성
Open
조절이 어려움
조절이 자유로움

이차형식의 최적화

이차형식

가환환 KK위의 가군 VV에 대해 다음 세 조건을 만족시키는 함수 Q:VKQ : V \to K
k,lK,u,v,wV\forall k, l \in K, \forall u, v, w \in V
Q(kv)=k2Q(v)Q(kv) = k^{2} Q(v)
Q(u+v+w)=Q(u+v)+Q(v+w)+Q(u+w)Q(u)Q(v)Q(w)Q(u + v + w) = Q(u + v) + Q(v+w) + Q(u+w) - Q(u) - Q(v) - Q(w)
Q(kv+lv)=k2Q(u)+l2Q(v)+klQ(u+v)klQ(u)klQ(v)Q(kv + lv) = k^{2} Q(u) + l^{2} Q(v) + kl Q(u+v) - klQ(u) - klQ(v)
ex 1) R2R^{2}상의 일반적인 이차형식은 다음과 같다.
a1x12+a2x22+2a3x1x2(x1x2)(a1a3a3a2)(x1x2)a_{1}x_{1}^{2} + a_{2}x_{2}^{2} + 2a_{3}x_{1}x_{2} \Leftrightarrow \left( \begin{array}{rr} x_{1} & x_{2} \end{array} \right) \left( \begin{array}{rr} a_{1} & a_{3} \\ a_{3} & a_{2} \end{array} \right) \left( \begin{array}{rr} x_{1} \\ x_{2} \end{array} \right)
ex 2) R3R^{3}상의 일반적인 이차형식은 다음과 같다.
a1x12+a2x22+a3x32+ 2a4x1x2+2a5x1x3+2a6x2x2a_{1}x_{1}^{2} + a_{2}x_{2}^{2} + a_{3}x_{3}^{2} +  2a_{4}x_{1}x_{2} + 2a_{5}x_{1}x_{3} + 2a_{6}x_{2}x_{2}
(x1x2x3)(a1a4a5a4a2a6a5a6a3)(x1x2x3)\Leftrightarrow \left( \begin{array}{rrr} x_{1} & x_{2} & x_{3} \end{array} \right) \left( \begin{array}{rrr} a_{1} & a_{4} & a_{5} \\ a_{4} & a_{2} & a_{6} \\ a_{5} & a_{6} & a_{3} \end{array} \right) \left( \begin{array}{rrr} x_{1} \\ x_{2} \\ x_{3} \end{array} \right)

제약된 극값

개념

특정 제약 하에 결정되는 원하는 식의 최댓값 또는 최솟값
정리) n×nn \times n 행렬 AA의 고윳값을 큰 순서대로 λ1,λ2,...,λn\lambda_{1}, \lambda_{2}, ... , \lambda_{n}이라 하자. 이때 v=1n\|v\| = 1n 제약 하에 vTAvv^{T}Av의 최댓(솟)값은 λ1(λn)\lambda_{1} (\lambda_{n})에 대응하는 단위고유벡터에서 존재한다.

사례

제약 x2+y2=1x^{2} + y^{2} = 1 하에서
위 제약 조건은 v=(x,y)\vec{v} = (x, y)로 정한 것과 같다. v=1\|v\| = 1이 된다.
z=5x2+5y2+4xyz = 5 x^{2} + 5 y^{2} + 4xy
의 최댓값과 최솟값을 구하자. 우선 zz를 이차형식 vTAvv^{T} Av 형태로 변환한다.
Step 1) a1x2+a2y2+2a3xya_{1}x^{2} + a_{2}y^{2} + 2a_{3}xy
(xy)(a1a3a3a2)(xy)=vTAv\Leftrightarrow \left( \begin{array}{rr} x & y \end{array} \right) \left( \begin{array}{rr} a_{1} & a_{3} \\ a_{3} & a_{2} \end{array} \right) \left( \begin{array}{rr} x \\ y \end{array} \right) = v^{T} A v
즉, z=(xy)(5225)(xy)z = \left( \begin{array}{rr} x & y \end{array} \right) \left( \begin{array}{rr} 5 & 2 \\ 2 & 5 \end{array} \right) \left( \begin{array}{rr} x \\ y \end{array} \right)
Step 2) 행렬 A=(5225)A = \left( \begin{array}{rr} 5 & 2 \\ 2 & 5 \end{array} \right)의 고윳값과 고유벡터를 구한다.
{λ1=7v1=(1,1)λ2=3v2=(1,1)\Rightarrow \begin{cases} \lambda_{1} = 7 & v_{1} = (1, 1) \\ \lambda_{2} = 3 & v_{2} = (-1, 1) \end{cases}
Step 3) 고유벡터를 정규화한다.
{λ1=7v1=(12,12)λ2=3v2=(12,12)\Rightarrow \begin{cases} \lambda_{1} = 7 & v_{1} = ({1 \over \sqrt{2}}, {1 \over \sqrt{2}}) \\ \lambda_{2} = 3 & v_{2} = (-{1 \over \sqrt{2}}, {1 \over \sqrt{2}}) \end{cases}
Step 4) 따라서 (x,y)=(12,12)(x, y) = ({1 \over \sqrt{2}}, {1 \over \sqrt{2}}) 일 때 zz는 최댓값 7을 갖고, (x,y)=(12,12)(x, y) = (-{1 \over \sqrt{2}}, {1 \over \sqrt{2}})일 때 zz 최솟값 3을 갖는다.
물론 v1=(1,1),v2=(1,1)v_{1} = (-1, -1), v_{2} = (1, -1) 등으로 설정해도 무방하며, 최댓(솟)값은 변하지 않는다.