※ 引述《doom8199 (～口卡口卡 修～)》之銘言：
: ※ 引述《ILzi ( 並不好笑 )》之銘言：
: : 這題轉成quadraic form好像不好算
: : 所以提供另一個方法
: : 首先
: : [ x2 ]
: : [ x3 ]
: : [ x4 ] 2 2 2
: : S=[x1 x2 x3 ... x99] [ . ]，由柯西不等式我們知道 S ≦(1-x100 )(1-x1 )
: : [ . ] ↑
: : [ . ] │
: : [x100] │
: : │
: : 同時，由柯西不等式亦可得知 │
: : 當[x1 x2 x3 ... x99] = [x2 x3 x4 ... x100]時，S會有最大值 │
: : │
: : 即 x1 = x2 = x3 = ... = x100 時有最大值 │
: : │
: : 則 x1 = x2 = x3 = ... = x100 = 1/10 │
: : │
: : S = 99 * 1/10 * 1/10 = 99/100，同時也符合上述柯西不等式───┘
: ----
: 柯西不等式等號等成立時，不代表是 極/最 值發生處
: 收斂性 + 有界 成立，你才能說極值存在
: 回想一下高中時期，在用各種常用不等式來算最值時
: 不等式某一邊常常會湊成一個常數值
: 這 implies 該系統有上/下界 globally
: 因此才會下一個結論: "當等號成立時， xxx 有最大/小值 xxx"
: -----
: 算這類問題，in general 就是使用 lagrange multipliers
: 寫成矩陣型態只是讓表達上比較有系統
: 因此考慮一向量 v = [x1, x2, ..., x_n]' (single-quote rep. transpose)
: 1
: A_n = ──(L_n + U_n)
: 2
: ( Note: L_n (/U_n) 代表上(/下)平移矩陣
: 可參照 http://en.wikipedia.org/wiki/Shift_matrix )
: 則原問題可改寫成: S_n = v'(A_n)v - λ(v'v - 1)
: δ S_n
: ──── = 0 => (A_n + A_n')v - 2λv = 0
: δv
: => (A_n)v - λv = 0 ( 注意到 A_n' = A_n )
: 可知 S_n 的極值發生於 eigenvectors of the matrix A_n
: 此時 S_n = v'(A_n)v = λv'v = λ corresponding to eigenvalues of A_n
: 所以 S_n ≦ λ_max
: ( ps: 有學過 PCA 或相關 estimation 的人應該對這結果不陌生XD )
: 因此接下來的重點在於如何求得 A_n 的所有 eigenvalues
對於Sn ，這邊提供一個另一種方法，雖然比較笨，但是似乎也得到一樣的結果
[ 0 1/2 0 0 ... 0 0]
[1/2 0 1/2 0 ... 0 0]
T [ 0 1/2 0 1/2... 0 0]
令X=[x1 x2 ... x100] A=[ . . . . . . .]
[ . . . . . . .]
[ . . . . . . .]
[ 0 0 0 0 1/2 0]
Sn=x1x2+x2x3+...+x99x100
T
=X A X
因為A是對稱矩陣，所以可以對角化得
[λ1 . . . 0 ] [ v1^T ]
[ . . . ] [ . ] T T
A=[v1 v2 ... v100][ . . . ] [ . ] = PDP ， 其中PP = I
[ . . . ] [ . ]
[ 0 . . . λ100] [v100^T]
當然，v1~v100分別是λ1~λ100的 orthonormal eigenvector
T T T T T
則Sn = X PDP X = (X P)D(X P)
2
= Σ λi (X．vi)
利用光譜分解定理，我們知道對所有X，都存在有一組(c1,c2,...,c100)
使得X = Σci vi
2
Sn = Σ λi [(Σci vi)．vi]
2
= Σ λi (ci)
2 2 2
= λ1 c1 + λ2 c2 + ... + λ100 c100
又，依照題目條件，我們知道||X|| = 1
2
=>(Σci vi)．(Σci vi) = Σ ci = 1
Sn ≦ λ1*0 + λ2*0 + ... +λmax*1 + ... + λ100*0 = λmax
接下來就如同以下解法..
提供另一個做法給大家參考，有錯誤的話請大家提出
: =====
: assume d[n] = determinant of the matrix [A_n - λ*(I_n)]
: where I_n is a n by n identity matrix
: 不難得出以下遞迴式:
: ┌ d[n] = -λ*d[n-1] - (1/4)*d[n-2] , n>1 ____(1)
: │ d[1] = -λ
: └ d[0] = 1
: -λ + √(λ^2 - 1) n -λ - √(λ^2 - 1) n
: 由 (1)式可得 d[n] = c1*[─────────] + c2*[─────────]
: 2 2
: 為了簡化問題，令 λ = cosh(θ)
: e^(-nθ) e^(nθ)
: 則 d[n] 可被改寫成 c1*───── + c2*────
: (-2)^n (-2)^n
: e^(-θ) e^θ
: 根據初始條件可解出 (c1, c2) = ( ───────, ────── )
: (-2)*sinh(θ) 2*sinh(θ)
: 1 -(n+1)θ (n+1)θ
: 套回 d[n] = ───────────*[ e - e ]
: (-2)^(n+1) * sinh(θ)
: ikπ
: solve d[n] = 0 => θ = ─── , k€{1,2,...,n}
: (n+1)
: (Note that θ is undef. occurring k=0)
: kπ
: => λ €{ cos(──) │ k = 1 to n }
: n+1
: π
: 因此 S_n ≦ λ_max = cos(──)
: n+1
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.19.249.253