행렬의 기초 개념 행렬에서 제일 중요한 두 문제는 연립방정식 A x = b Ax = b A x = b A x = λ x Ax = \lambda x A x = λ x A x = b Ax = b A x = b A x = λ x Ax = \lambda x A x = λ x
왜 그러는지 모르겠지만 여기서는 A A A A i A_i A i A j A^j A j A i j A_i^j A i j a i j a_{ij} a ij 아니 행렬 거듭제곱은 어쩌려고 이딴 notation을 e A e^A e A
그럼 A x = b Ax = b A x = b A i A^i A i b b b x = A − 1 b x = A^{-1}b x = A − 1 b A − 1 = A a d j det A A^{-1} = \frac{A^{adj}}{\det A} A − 1 = d e t A A a d j A A − 1 AA^{-1} A A − 1 A − 1 A A^{-1}A A − 1 A x i = det A i det A x_i = \frac{\det A_i}{\det A} x i = d e t A d e t A i A i A^i A i
소행렬 A i j A_{ij} A ij n × n n \times n n × n a 11 , … , a n n a_{11}, \ldots, a_{nn} a 11 , … , a nn 주대각 아래쪽이 0이면 위삼각행렬 (upper triangular matrix, U), 주대각 위쪽이 0이면 아래삼각행렬 (lower triangular matrix, L) 주대각이 아닌 모든 원소가 0이면 대각행렬 (diagonal matrix, D) 주대각이 모두 같은 대각행렬은 스칼라행렬 (scalar matrix, S) 그게 1이면 단위행렬 (unit matrix, I) 행렬의 기본행연산: 두 행 교환, 상수곱, 한 행의 상수배 더함 행 열 바꾸면 전치 (transpose) 주대각 합은 트레이스 (trace) x T y x^Ty x T y x ⋅ y x \cdot y x ⋅ y x y T xy^T x y T 행렬식
det A 2 × 2 = a d − b c \det A_{2 \times 2} = ad - bc det A 2 × 2 = a d − b c 두 행 바꾸면 det 부호 바뀜 한 행에 다른 행의 상수배를 더해도 det는 같음 한 행에 상수배를 하면 행렬식도 상수배가 됨 det ( s A ) = s n det A \det(sA) = s^n \det A det ( s A ) = s n det A det A B = det A det B \det AB = \det A \det B det A B = det A det B det A k = ( det A ) k \det A^k = (\det A)^k det A k = ( det A ) k k = − 1 k=-1 k = − 1 det A T = det A \det A^T = \det A det A T = det A det A ‾ = det A ‾ \det \overline{A} = \overline {\det A} det A = det A det L = det U = a 11 a 22 ⋯ a n n \det L = \det U = a_{11} a_{22} \cdots a_{nn} det L = det U = a 11 a 22 ⋯ a nn det A a d j = ( det A ) n − 1 \det A^{adj} = (\det A)^{n-1} det A a d j = ( det A ) n − 1 ∵ A a d j = det A ⋅ A − 1 \because A^{adj} = \det A \cdot A^{-1} ∵ A a d j = det A ⋅ A − 1 Einstein notation: A i x i A^ix_i A i x i i i i ∑ i A i x i \sum_i A^ix_i ∑ i A i x i
Crammer's rule: A x = b Ax = b A x = b A a d j A^{adj} A a d j I ⋅ det A x = A a d j b I \cdot \det A x = A^{adj}b I ⋅ det A x = A a d j b
역행렬
( A − 1 ) − 1 = A (A^{-1})^{-1} = A ( A − 1 ) − 1 = A ( A B ) − 1 = B − 1 A − 1 (AB)^{-1} = B^{-1}A^{-1} ( A B ) − 1 = B − 1 A − 1 ( A k ) − 1 = ( A − 1 ) k (A^k)^{-1} = (A^{-1})^k ( A k ) − 1 = ( A − 1 ) k ( s A ) − 1 = s − 1 A − 1 (sA)^{-1} = s^{-1}A^{-1} ( s A ) − 1 = s − 1 A − 1 A ‾ − 1 = A − 1 ‾ \overline{A}^{-1} = \overline{A^{-1}} A − 1 = A − 1 det A − 1 = ( det A ) − 1 \det A^{-1} = (\det A)^{-1} det A − 1 = ( det A ) − 1 c.f. A = A T A = A^T A = A T A − 1 = A T A^{-1} = A^T A − 1 = A T A = A − 1 = A T A = A^{-1} = A^T A = A − 1 = A T H = I − 2 v v T H = I - 2vv^T H = I − 2 v v T
가우스 소거, 가우스-조단 소거 기본행연산으로 삼각행렬 만들던가 I I I
만들면 연립방정식 풀기 가능
근데 피봇팅 중요!!
제일 큰 숫자를 1행으로 땡겨오고 가우스 소거를 해야 오차가 줄어든다
반복법 A x = b Ax = b A x = b ∑ j = 1 n a i j x j = b j \sum_{j=1}^n a_{ij}x_j = b_j ∑ j = 1 n a ij x j = b j x i = 1 a i i ( b i − ∑ j = 1 , j ≠ i n a i j x j ) x_i = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1, j \neq i}^n a_{ij}x_j \right) x i = a ii 1 ( b i − ∑ j = 1 , j = i n a ij x j )
수렴하려면 행렬이 대각지배성 ∣ a i i ∣ ≥ ∑ j = 1 , j ≠ i n ∣ a i j ∣ |a_{ii}| \geq \sum_{j=1, j \neq i}^n |a_{ij}| ∣ a ii ∣ ≥ ∑ j = 1 , j = i n ∣ a ij ∣
자코비 방식 (쓰레기):x i k + 1 = 1 a i i ( b i − ∑ j = 1 , j ≠ i n a i j x j k ) x_i^{k+1} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1, j \neq i}^n a_{ij}x_j^k \right) x i k + 1 = a ii 1 ( b i − ∑ j = 1 , j = i n a ij x j k )
가우스 자이델 방식 (조금 나음):x i k + 1 = 1 a i i ( b i − ∑ j = 1 i − 1 a i j x j k + 1 − ∑ j = i + 1 n a i j x j k ) x_i^{k+1} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{k+1} - \sum_{j=i+1}^{n} a_{ij}x_j^k \right) x i k + 1 = a ii 1 ( b i − ∑ j = 1 i − 1 a ij x j k + 1 − ∑ j = i + 1 n a ij x j k )
이걸 좀 더 생각해서 x ∗ x^* x ∗
x i k + 1 = 1 a i i ( b i − ∑ j = 1 i − 1 a i j x j k + 1 − ∑ j = i + 1 n a i j x j k ) = x i k + 1 a i i ( b i − ∑ j = 1 i − 1 a i j x j k + 1 − ∑ j = i n a i j x j k ) = x i k + 1 a i i ( b i − ∑ j = 1 n a i j x j ∗ ) \begin{align*} x_i^{k+1} &= \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{k+1} - \sum_{j=i+1}^{n} a_{ij}x_j^k \right) \\ &= x_i^k + \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{k+1} - \sum_{j=i}^{n} a_{ij}x_j^k \right) \\ &= x_i^k + \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{n} a_{ij}x_j^* \right) \end{align*} x i k + 1 = a ii 1 ( b i − j = 1 ∑ i − 1 a ij x j k + 1 − j = i + 1 ∑ n a ij x j k ) = x i k + a ii 1 ( b i − j = 1 ∑ i − 1 a ij x j k + 1 − j = i ∑ n a ij x j k ) = x i k + a ii 1 ( b i − j = 1 ∑ n a ij x j ∗ )
즉 컴퓨터에서 더 쉽게 할 수 있다! 벡터 저장하는 변수 하나만 사용하면 계속 반복법 사용 가능
이완법 위에껄 대략 x i k + 1 = x i k + Δ x k x_i^{k+1} = x_i^k + \Delta x^k x i k + 1 = x i k + Δ x k
이완법은 수렴속도를 조절하기 위해서 이완계수를 도입하여 x i k + 1 = x i k + ω Δ x k x_i^{k+1} = x_i^k + \omega \Delta x^k x i k + 1 = x i k + ω Δ x k
0 < ω < 1 0 < \omega < 1 0 < ω < 1 ω > 1 \omega > 1 ω > 1 ω ≥ 2 \omega \geq 2 ω ≥ 2
물론 뭘 쓸지는 시행착오로 정해야 함
수치적 난점 행렬 수치해석 특) 개판임
A의 원소가 조금만 변해도 해가 크게 변함 대각지배성 아니면 ㅈ됨 d e t A ⋅ d e t A − 1 det A \cdot det A^{-1} d e t A ⋅ d e t A − 1 A A − 1 AA^{-1} A A − 1 I I I ( A − 1 ) − 1 (A^{-1})^{-1} ( A − 1 ) − 1 A A A A − 1 ( A − 1 ) − 1 A^{-1}(A^{-1})^{-1} A − 1 ( A − 1 ) − 1 I I I 다행히(?) 수학자들이 어떤 행렬이 불량조건을 갖는지 (즉 개판인지) 알아냄
대표적인 불량조건 행렬: 힐버트 행렬 (a i j = 1 i + j − 1 a_{ij} = \frac{1}{i + j - 1} a ij = i + j − 1 1
불량조건의 정량화 행렬 정규(matrix norm) 아니 norm을 대체 왜 정규로 번역함
∥ A ∥ ∞ = max 1 ≤ i ≤ n ∑ j = 1 n ∣ a i j ∣ \|A\|_{\infty} = \max_{1 \leq i \leq n} \sum_{j=1}^{n} |a_{ij}| ∥ A ∥ ∞ = 1 ≤ i ≤ n max j = 1 ∑ n ∣ a ij ∣
으로 정의하면 행렬의 조건수 ∥ A ∥ ∞ ∥ A − 1 ∥ ∞ \|A\|_{\infty}\|A^{-1}\|_{\infty} ∥ A ∥ ∞ ∥ A − 1 ∥ ∞
일반적으로 조건수가 10 s 10^s 1 0 s s s s
3대각행렬과 TDMA 대각행렬은 대각에 하나
3장에서 반드시 알아야 할 것??
[ a 1 c 1 0 ⋯ 0 b 2 a 2 c 2 ⋯ 0 0 b 3 a 3 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ a n ] [ x 1 x 2 x 3 ⋮ x n ] = [ d 1 d 2 d 3 ⋮ d n ] \begin{bmatrix} a_1 & c_1 & 0 & \cdots & 0 \\ b_2 & a_2 & c_2 & \cdots & 0 \\ 0 & b_3 & a_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0& \cdots & a_n \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} d_1 \\ d_2 \\ d_3 \\ \vdots \\ d_n \end{bmatrix} a 1 b 2 0 ⋮ 0 c 1 a 2 b 3 ⋮ 0 0 c 2 a 3 ⋮ 0 ⋯ ⋯ ⋯ ⋱ ⋯ 0 0 0 ⋮ a n x 1 x 2 x 3 ⋮ x n = d 1 d 2 d 3 ⋮ d n
a i x i + b i x i − 1 + c i x i + 1 = d i a_ix_i + b_ix_{i-1} + c_ix_{i+1} = d_i a i x i + b i x i − 1 + c i x i + 1 = d i x i = P i x i + 1 + Q i x_i = P_ix_{i+1} + Q_i x i = P i x i + 1 + Q i
P 1 = − c 1 a 1 , Q 1 = d 1 a 1 P_1 = -\frac{c_1}{a_1}, Q_1 = \frac{d_1}{a_1} P 1 = − a 1 c 1 , Q 1 = a 1 d 1 ∵ a 1 x 1 + c 1 x 2 = d 1 \because a_1x_1 + c_1x_2 = d_1 ∵ a 1 x 1 + c 1 x 2 = d 1 P i = − c i a i + b i P i − 1 , Q i = d i − b i Q i − 1 a i + b i P i − 1 P_i = -\frac{c_i}{a_i + b_iP_{i-1}}, Q_i = \frac{d_i - b_iQ_{i-1}}{a_i + b_iP_{i-1}} P i = − a i + b i P i − 1 c i , Q i = a i + b i P i − 1 d i − b i Q i − 1 a i x i + b i x i − 1 + c i x i + 1 = d i a_ix_i + b_ix_{i-1} + c_ix_{i+1} = d_i a i x i + b i x i − 1 + c i x i + 1 = d i x i − 1 = P i − 1 x i + Q i − 1 x_{i-1} = P_{i-1}x_i + Q_{i-1} x i − 1 = P i − 1 x i + Q i − 1 x n = Q n x_n = Q_n x n = Q n ∵ c n = 0 \because c_n = 0 ∵ c n = 0 x i = P i x i + 1 + Q i x_i = P_ix_{i+1} + Q_i x i = P i x i + 1 + Q i LU분해 이것도 반드시 알아야함
A = L U A = LU A = LU A x = b Ax=b A x = b L U x = b LUx=b LUx = b
[ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ] = [ l 11 0 ⋯ 0 l 21 l 22 ⋯ 0 ⋮ ⋮ ⋱ ⋮ l n 1 l n 2 ⋯ l n n ] [ u 11 u 12 ⋯ u 1 n 0 u 22 ⋯ u 2 n ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ u n n ] \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} = \begin{bmatrix} l_{11} & 0 & \cdots & 0 \\ l_{21} & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{bmatrix}\begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{bmatrix} a 11 a 21 ⋮ a n 1 a 12 a 22 ⋮ a n 2 ⋯ ⋯ ⋱ ⋯ a 1 n a 2 n ⋮ a nn = l 11 l 21 ⋮ l n 1 0 l 22 ⋮ l n 2 ⋯ ⋯ ⋱ ⋯ 0 0 ⋮ l nn u 11 0 ⋮ 0 u 12 u 22 ⋮ 0 ⋯ ⋯ ⋱ ⋯ u 1 n u 2 n ⋮ u nn
사실 우변의 미지수가 더 많음 (좌변은 n 2 n^2 n 2 n 2 + n n^2 + n n 2 + n n n n
크라우트(Crout): u i i = 1 u_{ii} = 1 u ii = 1 두리틀(Dolittle): l i i = 1 l_{ii} = 1 l ii = 1 촐레스키(Choleski): l i i = u i i l_{ii} = u_{ii} l ii = u ii 크라우트 방식으로 구하면 방정식을 전부 만든 다음,
기본행연산을 활용한 LU분해 두리틀 방식 l i i = 1 l_{ii} = 1 l ii = 1
행연산을 통해 A를 U로 만들고, 같은 행연산을 I에도 함 I에 행연산 적용시킨 행렬의 주대각을 제외한 나머지 원소의 부호를 뒤집으면 L이 됨 사실 마지막 과정은 기본행연산의 역행렬을 구한 것임
크라우트가 보고싶으면 먼저 이렇게 두리틀을 구한 다음 대각성분을 빼서 U U U D U DU D U L D LD L D L L L
촐레스키 분해 사실 A = U T U A = U^TU A = U T U
만약 A가 양의 정부호라면 (Positive definite, i.e. ∀ x ≠ 0 , x T A x > 0 \forall x \neq 0, x^TAx > 0 ∀ x = 0 , x T A x > 0 A = U T U A = U^TU A = U T U 번역 레전드네
유일하게 분해되므로 그냥 LU분해 방식을 쓰고 대각만 맞추면 된다
양의 정부호를 잘 몰라서 시험에는 안 나오지만 양의 정부호가 뭔지 수학자들 앞에서 아는척 할 수 있음
QR 분해 Q는 직교행렬 (orthogonal matrix, i.e. Q − 1 = Q T Q^{-1} = Q^T Q − 1 = Q T
사실 Q를 구하는건 정규직교기저를 구하는 것과 같음A A A
p r o j v ( a ) = a ⋅ v v ⋅ v v = a ⋅ v v v ⋅ v proj_v(a) = \frac{a \cdot v}{v \cdot v} v = a \cdot \frac{vv}{v \cdot v} p ro j v ( a ) = v ⋅ v a ⋅ v v = a ⋅ v ⋅ v vv vv가 대체 무슨 notation임 몰라요 그렇게 쓰래 v v T v ⋅ v a \frac{vv^T}{v \cdot v} a v ⋅ v v v T a p r o j u ( a ) = ( a ⋅ u ) u = u u T ⋅ a proj_u(a) = (a \cdot u)u = uu^T \cdot a p ro j u ( a ) = ( a ⋅ u ) u = u u T ⋅ a
u 1 = a 1 ∣ a 1 ∣ u_1 = \frac{a_1}{|a_1|} u 1 = ∣ a 1 ∣ a 1 v 2 = a 2 − u 1 u 1 T ⋅ a 2 = ( I − u 1 u 1 T ) a 2 v_2 = a_2 - u_1 u_1^T \cdot a_2 = (I - u_1u_1^T) a_2 v 2 = a 2 − u 1 u 1 T ⋅ a 2 = ( I − u 1 u 1 T ) a 2 u 2 = v 2 ∣ v 2 ∣ u_2 = \frac{v_2}{|v_2|} u 2 = ∣ v 2 ∣ v 2 v 3 = a 3 − u 1 u 1 T ⋅ a 3 − u 2 u 2 T a 3 = ( I − u 1 u 1 T − u 2 u 2 T ) a 3 v_3 = a_3 - u_1 u_1^T \cdot a_3 - u_2 u_2^T a_3 = (I - u_1u_1^T - u_2u_2^T)a_3 v 3 = a 3 − u 1 u 1 T ⋅ a 3 − u 2 u 2 T a 3 = ( I − u 1 u 1 T − u 2 u 2 T ) a 3 위 과정 계속 반복 R은 Q T A Q^TA Q T A
곱하는 행렬을 P i P_i P i P 1 = I P_1 = I P 1 = I P i + 1 = P i − u i u i T P_{i+1} = P_i - u_iu_i^T P i + 1 = P i − u i u i T
만약 QR분해가 된다면 A x = b Ax = b A x = b R x = Q T b Rx = Q^Tb R x = Q T b