최적화문제
1. 곡선 적합
(1) 보간법
① 개념
주어진 특정 점을 포함하는 함수를 구하는 방법
정리) 좌표평면에 있는 임의의 서로 다른 n개의 점을 지나는 k차 다항함수는 유일하게 존재한다.
(단, k는 k<n인 자연수)
② 사례
네점 (1,3),(2,-2),(3,-5),(4,0)을 모두 지나는 3차 함수
$f(x)=a_{0}+a_{1}+a_{2}x^{2}+a_{3}x^{3}$
를 구하자. 우선 다음의 방정식을 세운다.
step 1>
\(\begin{pmatrix} 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{pmatrix} \begin{pmatrix} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \\ \end{pmatrix} = \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{pmatrix}\)
step 2> 네 점을 대입하고 첨가행렬을 만든다.
\(\begin{pmatrix} 1 & 1 & 1 & 1 & 3 \\ 1 & 2 & 4 & 8 & -2 \\ 1 & 3 & 9 & 27 & -5 \\ 1 & 4 & 16 & 64 & 0 \\ \end{pmatrix}\)
step 3> 첨가행렬을 가우스-조던 소거법을 이용하여 풀이한다.
\(\begin{pmatrix} 1 & 1 & 1 & 1 & 3 \\ 1 & 2 & 4 & 8 & -2 \\ 1 & 3 & 9 & 27 & -5 \\ 1 & 4 & 16 & 64 & 0 \\ \end{pmatrix} \Rightarrow \begin{pmatrix} 1 & 0 & 0 & 0 & 4 \\ 0 & 1 & 0 & 0 & 3 \\ 0 & 0 & 1 & 0 & -5 \\ 0 & 0 & 0 & 1 & 1 \\ \end{pmatrix}\)
step 4> $a_{0}=4, a_{1}=3, a_{2}=-5, a_{3}=1$이므로
$f(x)=4+3x-5x^{2}+x^{3}$ 이다.
(2) 최소제곱법
① 개념
특정 점들을 포함하는 함수를 특정 지을 수 없을때,
실제 해와의 오차 제곱 합이 최소가 되는 근사적인 해를 구하는 방법.
정리) 방정식 Ax=B를 변현한 방정식
$A^{T}Ax=A^{T}B$(정규방정식)의 모든 해는 Ax=B의 최소제곱해이다.
② 사례
네 점 (0,1),(1,3),(2,4),(3,4)에 근사하는 일차함수 $f(x)=a_{0}+a_{1}x$를 구하자.
우선 다음의 방정식을 세운다.
step 1> $Ax=B$
\(\Leftrightarrow \begin{pmatrix} 1 & x_{1} \\ 1 & x_{2} \\ 1 & x_{3} \\ 1 & x_{4} \\ \end{pmatrix} \begin{pmatrix} a_{0} \\ a_{1} \end{pmatrix} = \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ \end{pmatrix}\)
step 2> 네점을 대입하고 정규방정식 $A^{T}Ax=A^{T}B$으로 부터
방정식 $x=(A^{T}A)^{-1}A^{T}B$을 구성한다. \(A^{T}A=\begin{pmatrix} 4 & 6 \\ 6 & 14 \\ \end{pmatrix}\) 이므로
\((A^{T}A)^{-1}=\begin{pmatrix} 4 & 6 \\ 6 & 14 \\ \end{pmatrix}^{-1} = \frac{1}{10}\begin{pmatrix} 7 & -3 \\ -3 & 2 \\ \end{pmatrix}\) \(\therefore \frac{1}{10}\begin{pmatrix} 7 & -3 \\ -3 & 2 \\ \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ \end{pmatrix}\begin{pmatrix} 1 \\ 3 \\ 4 \\ 4 \end{pmatrix}\)
step 3> \(X=\begin{pmatrix} a_{0} \\ a_{1} \end{pmatrix} = \begin{pmatrix} \frac{3}{2} \\ 1 \end{pmatrix}\)이므로 구하고자하는 함수는
$f(x)=\frac{3}{2}+x$ 이다.
③ n차 일반화
m개의 자료점 $(x_{1},y_{1}),\cdots ,(x_{m},y_{m})$에 대해
n차 다항식 $y=a_{0}+a_{1}x+ \cdots +a{n}x^{n}$을 최소제곱법을 이용하여
근사하기 위해서는 Ax=B를
\(A = \begin{pmatrix} 1 & x_{1} & \cdots & x_{1}^{n} \\ 1 & x_{2} & \cdots & x_{2}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{m} & \cdots & x_{m}^{n} \\ \end{pmatrix}, x=\begin{pmatrix} a_{0} \\ a_{1} \\ \vdots \\ a_{n} \end{pmatrix}, B = \begin{pmatrix} y_{1} \\ y_{2} \\ \vdots \\ y_{m} \end{pmatrix}\)
로 설정하면 된다.
2. 이차형식의 최적화
(1) 이차형식
가환환 K위의 가군 V에 대해 다음 세조건을 만족시키는 함수
$Q : V \to K$
$ \forall k,l \in K, \forall u,v,w \in V$
1) $Q(kv) = k^{2}Q(v)$ 2) $Q(u+v+w) = Q(u+v)+Q(v+w)+Q(u+w)-Q(u)-Q(v)-Q(w) $ 3) $Q(ku+lv) = k^{2}Q(u)+l^{2}Q(v)+klQ(u+v)-klQ(u)-klQ(v)$
ex 1> $R^{2}$상의 일반적인 이차형식은 다음과 같다.
$a_{1}x_{1}^{2}+a_{2}x_{2}^{2}+2a_{3}x_{1}x_{2} $
\(\Leftrightarrow (x_{1},x_{2})\begin{pmatrix} a_{1} & a_{3} \\ a_{3} & a_{2} \\ \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}\)
ex 2> $R^{3}$상의 일반적인 이차형식은 다음과 같다.
$a_{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_{3}$
\(\Leftrightarrow \begin{pmatrix} x_{1} & x_{2} & x_{3} \\ \end{pmatrix}\begin{pmatrix} a_{1} & a_{4} & a_{5} \\ a_{4} & a_{2} & a_{6} \\ a_{5} & a_{6} & a_{3} \\ \end{pmatrix}\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix}\)
(2) 제약된 극값
① 개념
특정 제약 하에 결정되는 원하는 식의 최댓값 또는 최솟값
정리) $n\times n$행렬 A의 고윳값을 큰 순서대로 $\lambda _{1},\lambda _{2},…,\lambda _{n}$이라 하자.
이때 \(\left\| v \right\| = 1\) 제약하에 $v^{T}Av$이 최댓(솟)값은 \(\lambda_{1}(\lambda_{n})\)에 대응하는
단위 고유 벡터에서 존재한다.
② 사례
제약 $x^{2}+y^{2}=1$하에서 $z=5x^{2}+5y^{2}+4xy$의 최댓값과 최솟값을 구하자.
우선 z를 이차형식 $v^{T}Av$형태로 변환한다.
step 1> $a_{1}x^{2}+a_{2}y^{2}+2a_{3}xy$
\(\Leftrightarrow \begin{pmatrix} x & y \\ \end{pmatrix}\begin{pmatrix} a_{1} & a_{3} \\ a_{3} & a_{2} \\ \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = v^{T}Av\)
즉 \(z= \begin{pmatrix} x & y \\ \end{pmatrix}\begin{pmatrix} 5 & 2 \\ 2 & 5 \\ \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix}\)
step2 > 행렬 \(A = \begin{pmatrix} 5 & 2 \\ 2 & 5 \\ \end{pmatrix}\)의 고윳값과 고유벡터를 구한다.
\(\left\{\begin{matrix} \lambda_{1} = 7, v_{1}=(1,1) \\ \lambda_{2}=3, v_{2}=(-1,1) \end{matrix}\right.\)
step3 > 고유벡터를 정규화 한다.
\(\left\{\begin{matrix} \lambda_{1} = 7, v_{1}=(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}) \\ \lambda_{2} = 3, v_{2}=(-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}) \end{matrix}\right.\)
step4 > 따라서 $(x,y)=(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})$ 일 때 z는 최댓값 7을 갖고,
$(x,y)=(-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})$일때 z는 최솟값 3을 갖는다.
※ 물론 $v_{1}=(-1,-1),v_{2}=(1,-1)$등으로 설정해도 무방하며, 최댓(솟)값은 변하지 않는다.