Re: [線代] 矩陣高次方跟向量的乘積
※ 引述《aegius1r (SC)》之銘言：
: 標題: [線代] 矩陣高次方跟向量的乘積
: 時間: Tue Oct 22 00:48:38 2013
:
: 太久沒算線代了 做考古題卡住....
:
: 原題不是這樣, 這是化簡過後要計算的:
:
: 102
: A = [1 2 4], x = [1], 求 A x
: [0 1 0] [1] (A^102*x)
: [0 1 2] [1]
:
: 已經確認過A不能對角化
:
: [1] [4]
: 特徵值、特徵向量: 1 → [0]、2 → [0]
: [0] [1]
:
: 請大家幫忙~
:
: (原題: http://ppt.cc/dIo4 線代部份第8題 若這題可以用其他解法求出也可, 謝謝!)
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 1.34.78.147
: → THEJOY :多代入幾次，會發現有規律 10/22 01:08
: → THEJOY :只是常數項的規律很醜 10/22 01:09
: 我有計算過一些次方 發現有點規律 但應該有直接的計算方法去解這題?
: ※ 編輯: aegius1r 來自: 1.34.78.147 (10/22 01:12)
: 自問自答可以嗎..XD
:
:
: 剛剛找資料找到一種做法
:
: A的特徵多項式是char(A)=-(t-1)^2*(t-2)
:
: 由Cayley-Hamilton定理知(A-I)^2*(A-2I)=0
:
: 考慮x^102=q(x)*(x-1)^2*(x-2)+a(x-1)^2+b(x-1)+c
:
: 代入x=1、2和微分後代入x=1
:
: 不難發現a=2^102-103、b=102、c=1
:
: 因此A^102=(2^102-103)(A-I)^2+102(A-I)+1
:
: 後續就算出(A-I)、(A-I)^2之後代入 最後再乘上向量(1 1 1)^t即可
:
:
:
: (還是想知道其他做法XD
: ※ 編輯: aegius1r 來自: 1.34.78.147 (10/22 02:09)
: 推 alamabarry :不能對角化 jordan form嗎? 10/22 02:35
: jordan form不怎麼會做 煩請告知做法 謝謝~
: ※ 編輯: aegius1r 來自: 1.34.78.147 (10/22 02:40)
基本上，一般性的放大絕做法就是用 Cayley-Hamilton定理 和 Jordan form。
Cayley-Hamilton定理可得到將原冪次轉換成另一個一些次數低於矩陣大小的矩陣次方和。
Jordan form 則是 因為Jordan block 的次方是好算的，
http://en.wikipedia.org/wiki/Jordan_normal_form
基本上，運算核心也就只是算 (\lambda+1)^k 的二項次展開，
然後貼到矩陣的適當 entry 而已。
（看不太懂的話，你去算一下 \lambda 1 0 0
0 \lambda 1 0
0 0 \lambda 1
0 0 0 \lambda
這個矩陣的冪次，一直算到六次，再另外展開 (\lambda+1)^k, 一樣列到六次，比對一下
因此這兩招算是很強大的一般性招式。
=============================================================================
如果實在不喜歡放大的感覺的話，那因為你這個矩陣特殊設計過的，
我們可以來倒行逆施一下。
A = [1 2 4], x=(1 1 1)^t,
[0 1 0]
[0 1 2]
令 A^{n-1} x = (a_n,b_n,c_n)^t for n=1,2,3,4,5,...,
(a_1,b_1,c_1)= (1,1,1)
跟據a_n,b_n,c_n的定義，我們有：
a_{n+1} = a_n + 2 b_n + 4 c_n
b_{n+1} = b_n
c_{n+1} = b_n + 2 c_n
所以
b_{n+1}=b_{n}=b_{n-1}=...=b_{1}=1。 (b_i都是 1)
故
c_{n+1} = 1 + 2 c_n
c_{n+1} + 1 = 2 (c_n+1) （很routine的做法，就假設
(c_{n+1}+k) = 2(c_n+k) => c_{n+1}=2 c_n+k，k放1)
c_{n+1} +1 = 2 (c_n+1) = 2^2 (c_{n-1}+1) = 2^3 (c_{n-2}+1) = ... = 2^n(c_1+1)
=> c_{n+1} = 2^{n+1}-1
接著解 a_n 一般式。
a_{n+1} = a_n + 2 b_n + 4 c_n = a_n + 2 + 4 (2^n-1) = a_n +2^{n+2} -2
a_{n+1} = a_n + 2^{n+2} -2
a_{n} = a_{n-1} + 2^{n+1} -2
a_{n-1} = a_{n-2} + 2^{n} -2
....
....
a_{3} = a_2 + 2^{4} -2
+) a_{2} = a_1 + 2^{3} -2
------------------------------------------- (這一堆式子全加起來，左右消一消
a_{n+1} = a_1 + (2^3+2^4+...+2^{n}+2^{n+2}) - 2n
= 2^3(2^n-1) - 2n + 1
a_{n+1} = 2^{n+3} - 2n -7
A^{102} x = [ a_{103} ] = [ 2^{105} - 211 ]
[ b_{103} ] [ 1 ]
[ c_{103} ] [ 2^{103} - 1 ]
在一般的情況下，我們是用矩陣的冪次方來做為求數列一般式的工具，
即 真正的目標是求數列一般式，矩陣的冪次方是過程，
將遞迴關係轉換成一個矩陣後，再利用對角化的手法，
求出矩陣的冪次方，再轉換回一般式。
比方說，如果我們給定了費式數列的遞迴關係： a_n=a_{n-1}+ a_{n-2}，
被要求算 a_n的一般式。
首先用矩陣的符號寫成下面這樣的一個關係：
[ a_n ] = [ 1 1 ] [a_{n-1}]
[ a_{n-1} ] [ 1 0 ] [a_{n-2}]
令 A = [ 1 1 ]
[ 1 0 ]
所以 [ a_n ] = A [a_{n-1}] = A^2 [a_{n-2}] = ... = A^{n-2}[a_2]
[ a_{n-1}] [a_{n-2}] [a_{n-3}] [a_1]
接著將 A 對角化，近而求出 A^n ，那麼我們就可以得到 a_n 的一般式了。
而在這篇恰好是反過來，我們用數列去做為輔助工具，求出矩陣冪次方。
所以在這篇數列觀點的起頭，我們提到了 "倒行逆施" 這四個字。
當然，這樣的反向觀點之所以work，乃是你這邊的矩陣夠好，
所以那個列出的數列很好解。
一般情況，從硬算的弄法去弄數列，數列反而是會算到眼花的東西。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 182.235.182.218
※ 編輯: Eeon 來自: 182.235.182.218 (10/22 05:48)
推
10/22 10:29, , 1F
10/22 10:29, 1F
討論串 (同標題文章)