Gram-Schmidt 과정과 최소제곱법 문제

Gram-Schmidt 과정과 최소제곱법 문제

Gram-Schmidt Process

and Least-squares method problems

Keon M. Lee

 Gram-Schmidt 과정

 QR-분해

 최소제곱법 (least-square method) 문제

 최소제곱해

 선형독립인 두 벡터

 직교 기저로 변환



 x₂에서 x₁에 직교인 성분만 선택

선형독립 기저의 직교 기저 변환

선형독립 기저의 직교 기저 변환

선형 독립

선형독립 기저의 직교 기저 변환

Gram-Schmidt 과정(process)

 선형독립인(linearly independent) k개의 벡터로 부터 k개의 직교벡터(orthogonal vector)를 생성하는 방법

직교 기저의 정규직교 기저 변환

 정규 직교 기저(orthonormal basis)

 norm으로 나누어서 정규화

QR 분해

 QR 분해 (QR decomposition, QR factorization)

 mxn 행렬 A의 열벡터 x₁, …, x_n이 선형독립(linearly independent)이면, x₁, …, x_n 에 Gram-Schmidt 과정을 적용하여 A를 인수분해하는 것

A = QR

 방정식의 해법, eigenvalue 문제 해법에 활용

 증명

• Gram-Schmidt 과정 적용

QR 분해

𝑅 = 𝑄⁻¹𝐴 = 𝑄^T𝐴

QR 분해

 Octave/MatLab code

[m,n] = size(A);

Q = zeros(m,n);

R = zeros(n,n);

for j = 1:n

v = A(:,j);

for i = 1:j-1

R(i,j) = Q(:,i)'*A(:,j);

v = v - R(i,j)*Q(:,i);

end

R(j,j) = norm(v);

Q(:,j) = v/R(j,j);

end

QR 분해

정규직교 기저 Gram-Schmidt 과정 적용

QR 분해

 Octave/MatLab

[q, r] = qr(A)

𝑅 = 𝑄^T𝐴

최소제곱 문제

 일반적인 최소제곱법 문제(least-square methods)

 ||b – Ax||가 최소가 되는 x를 구하는 문제

 최소 제곱해

 A는 mxn 행렬이고, b  R^m일 때, 모든 x  Rⁿ에 대하여, 다음 조건을 만족하는 𝐱 를 Ax = b의 최소제곱해라 함

 선택한 x에 대해 벡터 Ax는 열공간 Col A에 속하게 됨

 최소제곱해 𝐱 는 A𝐱 가 Col A에 속하면서, b에 가장 가까운 점

최적근사 (best approximation)

 Col A의 원소들에 의한 b의 최적근사

 Col A에 대한 b의 직교 정사영

x에 대한 정규방정식 (normal equation)

는 Col A에 있는 와 직교해야하기 때문

최소제곱해 예

mxn 행렬의 동치관계

 mxn 행렬에 A에 대한 등가(equivalent) 명제

 R^m에 속하는 어떤 b에 대해서도 Ax = b는 유일한 최소제곱해를 갖는다.

 행렬 A의 열들은 선형독립이다.

 A^TA는 가역행렬이다.

 Ax = b는 유일한 최소제곱해 𝐱 를 갖는다.

 최소제곱오차

 b와 A𝐱 사이의 거리

QR 분해와 최소제곱해

 선형독립인 열들로 구성된 mxn 행렬 A의 QR 분해 A = QR

 임의의 b  R^m에 대하여, Ax = b는 만족하는 최소제곱해

는 b의 Col A위로의 직교 정사영 (Q가 Col A의 정규직교기저이므로)

QR 분해에 의한 최소제곱해

Summary

 Gram-Schmidt 과정은 선형독립인 k개의 벡터로 부터 k개의 직교 벡터를 생성하는 방법이다.

 QR 분해(QR decomposition)은 선형독립인 열벡터로 구성된 행렬 A 을 직교하는 열벡터로 구성된 행렬 Q와 상삼각행렬 R의 곱으로 표 현하는 것이다.

 선형시스템 Ax = b에 대해서, ||b – Ax*||를 최소로 하는 x*를 최소제곱해라고 한다.

 선형시스템 Ax = b에 대해서, A^T

Ax = A

b를 x에 대한 정규방정식

A)

A

b가 된다.

 Ax = b의 최소제곱해는 A의 열벡터가 서로 선형독립이면 존재한다.

 QR분해를 사용하면 최소제곱해를 역행렬을 계산하지 않고도 계산 할 수 있다.

 Ax = b의 최소제곱해의 집합

 A^TAx = A^Tb의 공집합이 아닌 해집합과 일치

 최소제곱해 A^TAx = A^Tb (앞 슬라이드에서 증명)

 A^TAx = A^Tb 최소제곱해

최소제곱해와 정규방정식

직교분해의 유일성으로 부터

는 Col A위로의 벡터 b의 직교정사영

는 최소제곱해의 하나