October 1, 2018 - Shawn Zhong

$Symmetric Positive Definite Matrix • Definition ○ Matrix A is called symmetric positive definite (s.p.d) if ○ A=A^T (symmetric) ○ x^T Ax0,∀x∈R(n×n)∖{0} (positive definite) • Proof: a_ii0 ○ a_ii=e_i^T Ae_i0, where [e_i ]_k={■8(1&if k=i@0&if k≠i)┤ • Proof: λ_i∈R+ for Ax_i=λ_i x_i ○ Use (λ_i ) ̅ to denote the conjugate of λ_i, we first need to show that (λ_i ) ̅=λ_i ○ Taking conjugate on both sides of Ax_i=λ_i x_i, we obtain A(x_i ) ̅=(λ_i ) ̅(x_i ) ̅ (note: A=A ̅) ○ {█(&x_i^T A(x_i ) ̅=x_i^T ((λ_i ) ̅(x_i ) ̅ )=(λ_i ) ̅x_i^T (x_i ) ̅@&x_i^T A(x_i ) ̅=┴sym x_i^T A^T (x_i ) ̅=(Ax_i )^T (x_i ) ̅=λ_i x_i^T (x_i ) ̅ )┤⇒(λ_i ) ̅x_i^T (x_i ) ̅=λ_i x_i^T (x_i ) ̅⇒(λ_i ) ̅=λ_i⇒λ_i∈R ○ x_i^T Ax_i=λ_i x_i^T x_i⇒λ_i=(x_i^T Ax_i)/(x_i^T x_i )0, since x_i^T Ax_i0 and x_i^T x_i0 ○ Note: λ_i∈R holds for all symmetric matrices • Proof: ⟨x_i,x_j ⟩=0 for λ_i≠λ_j ○ {█(&x_i^T Ax_j=x_i^T (λ_j x_j )=λ_j x_i^T x_j@&x_i^T A^T x_j=(Ax_i )^T x_j=λ_i x_i^T x_j )┤⇒(λ_j−λ_i ) x_i^T x_j=0 ○ If λ_i≠λ_j, then x_i^T x_j=⟨x_i,x_j ⟩=0 • Proof: det⁡〖(A)0〗 ○ A[(x_1 ) ⃗, (x_2 ) ⃗,…,(x_n ) ⃗ ]=[λ_1 (x_1 ) ⃗,λ_2 (x_2 ) ⃗,…,λ_n (x_n ) ⃗ ]=[(x_1 ) ⃗, (x_2 ) ⃗,…,(x_n ) ⃗ ][■(λ_1&&&@&λ_2&&@&&⋱&@&&&λ_n )] ○ Let X=[(x_1 ) ⃗, (x_2 ) ⃗,…,(x_n ) ⃗ ], Λ=[■(λ_1&&&@&λ_2&&@&&⋱&@&&&λ_n )], then AX=XΛ⇒A=XΛX^(−1) ○ Therefore, |A|=|XΛX^(−1) |=|X||Λ| |X|^(−1)=|Λ|=∏_(i=1)^n▒λ_i 0 • Proof: Let I⊊{1,2,…,n}, then B=A_II is also s.p.d. ○ A=A^T⇒A_II=A_II^T⇒B=B^T ○ Define y∈Rn s.t. [y]_i={■8([x]_i&i∈I@0&o.w.)┤, then x^T Bx=y^T Ay0,∀x∈R|I| ∖{0} • Cholesky Decomposition ○ If A is s.p.d., then ∃L lower diagonal s.t. A=LL^T ○ Note: This is saying that after LU decomposition, U=L^T Ordinary Differential Equation (Boundary Value Problem) • Suppose u(x)∈C^2 [0,1], find the solution for {█(u^′′+2u^′=−1@u(x=0)=0@u(x=1)=0)┤ • We can evenly sample N points on [0,1]: Δx=1/(N+1), x_i=iΔx • Compute first derivative u^′ (x_j ) using u(x_(j+1) ) and u(x_(j−1) ) ○ u^′ (x_j )=lim┬(δ→0)⁡〖(u(x_j+δ)−u(x_j−δ))/2δ〗≈(u(x_(j+1) )−u(x_(j−1) ))/2Δx ○ Note: ├ Du┤|_j=(u(x_(j+1) )−u(x_(j−1) ))/2Δx is called the discrete derivative of u at j • Compute second derivative u^′′ (x_j ) using u(x_(j+2) ), u(x_j ) and u(x_(j−2) ) u^′′ (x_j )=lim┬(δ→0)⁡〖(u^′ (x_j+δ)−u^′ (x_j−δ))/2δ〗 ≈(u^′ (x_(j+1) )−u^′ (x_(j−1) ))/2Δx ≈(((u(x_(j+2) )−u(x_j ))/2Δx)−((u(x_j )−u(x_(j−2) ))/2Δx))/2Δx, by substituting u^′ =(u(x_(j+2) )−2u(x_j )+u(x_(j−2) ))/(4Δx^2 ) • Compute second derivative u^′′ (x_j ) using u(x_(j+1) ), u(x_j ) and u(x_(j−1) ) ○ In practice, we want to only use neighboring points to have a local approximation ○ Thus, u^′′ (x_j )≈(u^′ (x_(j+1∕2) )−u^′ (x_(j−1∕2) ))/Δx=(u(x_(j+1) )−2u(x_j )+u(x_(j−1) ))/(Δx^2 ) • Substitute u^′,u^′′ into the ODE ○ (u(x_(j+1) )−2u(x_j )+u(x_(j−1) ))/(Δx^2 )+2((u(x_(j+1) )−u(x_(j−1) ))/2Δx)≈−1 ○ Define U≔[█(u(x_1 )@⋮@u(x_n ) )], then (U_(j+1)−2U_j+U_(j−1))/(Δx^2 )+(U_(j+1)−U_(j−1))/Δx=−1 ○ Let A∈R(n×n) s.t. [A]_ij={■8((Δx^2 )^(−1)−(Δx)^(−1)&i=j−1@−2(Δx^2 )^(−1)&i=j@(Δx^2 )^(−1)+(Δx)^(−1)&i=j+1@0&o.w.)┤, then AU=−1 ○ Note: A is said to be a tri-diagonal matrix [■(∗&∗&&&@∗&∗&∗&&@&∗&∗&∗&@&&∗&∗&∗@&&&∗&∗)]$

Shawn Zhong

Shawn Zhong

Math 514 – Ch 3

Search

WeChat Account