Re: [理工] 線代
※ 引述《ILzi ( 並不好笑 )》之銘言：
: ※ 引述《kiki86151 (白飯)》之銘言：
: : 99
: : 2. S=Σ xk*xk+1 | x1,x2,.....,x100為實數 x1^2+x2^2+.....+x100^2=1
: : k=1
: : 求 S最大為多少
: : S=x1*x2+x2*x3+........+x99*x100
: 這題轉成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
=====
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: 114.33.166.150
※ 編輯: doom8199 來自: 114.33.166.150 (12/09 13:09)
推
12/09 15:57, , 1F
12/09 15:57, 1F
→
12/09 16:07, , 2F
12/09 16:07, 2F
推
12/09 16:22, , 3F
12/09 16:22, 3F
推
12/09 19:50, , 4F
12/09 19:50, 4F
推
12/09 22:23, , 5F
12/09 22:23, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
理工
1
4
以下文章回應了本文：
完整討論串 (本文為第 65 之 120 篇)：
理工
5
8
理工
理工
1
5
理工
0
1
理工
1
1
理工
理工
1
2
理工
1
2
理工
4
15