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

곡선 적합

보간법

곡선 적합

보간법

개념

주어진 특징 점들을 포함하는 함수를 구하는 방법

정리) 좌표평면에 있는 임의의 서로 다른

n

개의 점을 지나는

k

차 다항함수는 유일하게 존재한다. (단

n

는

k < n

인 자연수)

사례

네 점

(1, 3), (2, -2), (3, -5), (4, 0)

을 모두 지나는 3차 함수

f(x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3}

를 구하자. 우선 다음의 방정식을 세운다.

Step 1)

\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) 네 점을 대입하고 첨가행렬을 만든다.

\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) 첨가행렬을 가우스-조던 소거법을 이용하여 풀이한다.

\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)

a_{0} = 4, a_{1} = 3, a_{2} = -5, a_{3} = 1

이므로

f(x) = 4 + 3 x - 5 x^{2} + x^{3}

이다.

•

곡선 접합은 현재 가진 데이터에 대해 분석은 잘 할 수 있지만, 신규 데이터가 현재 그려 놓은 곡선 위에 존재한다는 보증이 없음. 유연성이 매우 떨어진다.

◦

애초에 데이터를 모두 포함하는 함수가 존재하지 않는 경우도 많음.

최소제곱법

•

곡선 접합의 단점을 보완할 수 있는 방법.

•

가우스가 창안한 방법으로 가우스는 이 방법을 통해 소행성 '세레스' 의 궤도를 정확히 예측해 냄.

개념

특징 점들을 포함하는 함수를 특정 지을 수 없을 때, 실제 해와의 오차 제곱 합이 최소가 되는 근사적인 해를 구하는 방법

정리) 방정식

Ax = B

을 변형한 방정식

A^{T}Ax = A^{T}B

(정규방정식)의 모든 해는

Ax = B

의 최소제곱해이다.

•

요게 결국 선형회귀이다.

•

ATAx=ATBA^{T}Ax = A^{T}BATAx=ATB(정규방정식)의 모든 해는 Ax=BAx = BAx=B의 최소제곱해이라는 부분은 증명이 복잡하므로 강의 상에서는 생략.

사례

네 점

(0, 1), (1, 3), (2, 4), (3, 4)

에 근사하는 일차 함수

f(x) = a_{0} + a_{1} x

을 구하자. 우선 다음의 방정식을 세운다.

Step 1)

Ax = B

\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) 네 점을 대입하고 정규방정식

A^{T}Ax = A^{T}B

으로부터 방정식

x = (A^{T}A)^{-1} A^{T}B

을 구성한다.

A^{T}A = \left( \begin{array}{rr} 4 & 6 \\ 6 & 14  \end{array} \right)

이므로

(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)

\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 = \left( \begin{array}{rr} a_{0} \\ a_{1} \end{array} \right) = \left( \begin{array}{rr} {2 \over 3} \\ 1 \end{array} \right)

이므로 구하고자 하는 함수는

f(x) = {3 \over 2} + x

이다.

n차 일반화

m

개의 자료점

(x_{1}, y_{1}), (x_{2}, y_{2}), ... , (x_{m}, y_{m})

에 대해

n

차 다항식

y = a_{0} + a_{1} x + ... + a_{n} x^{n}

을 최소제곱법을 이용하여 근사하기 위해서는

Ax = B

를

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)

로 설정하면 된다.

두 방법의 비교

Show All

보간법

최소제곱법

목표

Open

데이터를 모두 포함하는 함수

데이터의 경향을 반영하는 함수

데이터의 수

Open

적을 수록 좋음

많아도 무방함

정밀도

Open

매우 높음

상대적으로 낮음

신축성

Open

조절이 어려움

조절이 자유로움

이차형식의 최적화

이차형식

가환환

K

위의 가군

V

에 대해 다음 세 조건을 만족시키는 함수

Q : V \to K

•

∀k,l∈K,∀u,v,w∈V\forall k, l \in K, \forall u, v, w \in V∀k,l∈K,∀u,v,w∈V

◦

Q(kv)=k2Q(v)Q(kv) = k^{2} Q(v)Q(kv)=k2Q(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(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)Q(kv+lv)=k2Q(u)+l2Q(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 \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)

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_{2}

\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 \times n

행렬

A

의 고윳값을 큰 순서대로

\lambda_{1}, \lambda_{2}, ... , \lambda_{n}

이라 하자. 이때

\|v\| = 1n

제약 하에

v^{T}Av

의 최댓(솟)값은

\lambda_{1} (\lambda_{n})

에 대응하는 단위고유벡터에서 존재한다.

사례

제약

x^{2} + y^{2} = 1

하에서

•

위 제약 조건은 v⃗=(x,y)\vec{v} = (x, y)v=(x,y)로 정한 것과 같다. ∥v∥=1\|v\| = 1∥v∥=1이 된다.

z = 5 x^{2} + 5 y^{2} + 4xy

의 최댓값과 최솟값을 구하자. 우선

z

를 이차형식

v^{T} Av

형태로 변환한다.

Step 1)

a_{1}x^{2} + a_{2}y^{2} + 2a_{3}xy

\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 = \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 = \left( \begin{array}{rr} 5 & 2 \\ 2 & 5 \end{array} \right)

의 고윳값과 고유벡터를 구한다.

\Rightarrow \begin{cases} \lambda_{1} = 7 & v_{1} = (1, 1) \\ \lambda_{2} = 3 & v_{2} = (-1, 1) \end{cases}

Step 3) 고유벡터를 정규화한다.

\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) = ({1 \over \sqrt{2}}, {1 \over \sqrt{2}})

일 때

z

는 최댓값 7을 갖고,

(x, y) = (-{1 \over \sqrt{2}}, {1 \over \sqrt{2}})

일 때

z

최솟값 3을 갖는다.

물론

v_{1} = (-1, -1), v_{2} = (1, -1)

등으로 설정해도 무방하며, 최댓(솟)값은 변하지 않는다.