極大代數(shù)矩陣本征值問(wèn)題

概念及算法

極大代數(shù)矩陣本征值問(wèn)題(eigenvalue problem of matrix in max-algebra)由極大代數(shù)導(dǎo)出的一類(lèi)矩陣本征值問(wèn)題.按照極大代數(shù)中的加法①和乘法⑧的規(guī)則，可以和常規(guī)線(xiàn)性代數(shù)類(lèi)同地定義矩陣及其運(yùn)算.例如，若A=(Q;j}rnXpe}=(}J;j}pxn，則

許多實(shí)際問(wèn)題可以歸結(jié)為研究由下列矩陣關(guān)系定義的線(xiàn)性變換:二((t十1>=A⑧二(t>，其中x

這里極大代數(shù)意義下的}k壘,l②,l⑧ ...②,1= k.1，表明每演化一拍，x的各分量均增加相同的值又.由于極大代數(shù)描述的問(wèn)題中，x(t)常表示第t拍時(shí)各事件發(fā)生的時(shí)刻，若求出本征值和本征向量，則可斷言對(duì)應(yīng)的系統(tǒng)行為進(jìn)入了一種以又為周期的周期態(tài)，而這通常是人們期望并常在實(shí)際中觀察到的.當(dāng)系統(tǒng)能進(jìn)人某種周期態(tài)或周期態(tài)的組合時(shí)，則稱(chēng)此(極大代數(shù)意義下的)系統(tǒng)為穩(wěn)定的.

極大代數(shù)矩陣本征值問(wèn)題與普通線(xiàn)性代數(shù)有完全不同的結(jié)論.為敘述這些結(jié)果，首先要將矩陣A 與下列加權(quán)有向圖對(duì)應(yīng)起來(lái).該圖有n個(gè)結(jié)點(diǎn)，分別代表二的一個(gè)分量，僅當(dāng)矩陣A的(}i,j)元素a;;; 一二時(shí)，圖中有一條由結(jié)點(diǎn)i到結(jié)點(diǎn)7的權(quán)為a;;的有向邊.對(duì)該圖的每一條長(zhǎng)為l的回路(i } } i I } ... } i t

為該回路的權(quán)(其中運(yùn)算為普通算術(shù)意義下的). 可以證明，當(dāng)該圖為強(qiáng)連通亦即矩陣A為不可約時(shí)，各回路最大的權(quán)幾即為該矩陣的惟一本征值. 按定義它可簡(jiǎn)潔地表達(dá)為

其中所有運(yùn)算都是在極大代數(shù)意義下的. 當(dāng)該圖不是強(qiáng)連通時(shí)，其本征值不僅應(yīng)為某回路r，的平均權(quán)重a，而且這些r，到其他平均權(quán)重大于幾的回路均無(wú)通道.反之，這些條件也保證了凡必為本征值.應(yīng)當(dāng)指出，本征向量的求法也是比較復(fù)雜的.對(duì)這種極大代數(shù)意義下的“線(xiàn)性”系統(tǒng)，亦可用狀態(tài)反饋或輸 出反饋來(lái)使受控系統(tǒng)穩(wěn)定并具有指定的本征值(運(yùn)行周期).

開(kāi)關(guān)代數(shù)是二值代數(shù)，即所有的變量和常數(shù)只取兩個(gè)值之一：0或1。不是自然二進(jìn)制的量必須被編碼為二進(jìn)制格式。在物理上，它們可以代表一個(gè)燈的開(kāi)和關(guān)，一個(gè)開(kāi)關(guān)的合和開(kāi)，一個(gè)低電壓和一個(gè)高電壓，一個(gè)在一個(gè)方向或另一個(gè)方向的磁場(chǎng)。開(kāi)關(guān)代數(shù)是邏輯代數(shù)的一種應(yīng)用。研究由開(kāi)關(guān)的并聯(lián)和串聯(lián)所構(gòu)成的電路的通斷情況。以變?cè)硎鹃_(kāi)關(guān);數(shù)字0，1分別表示開(kāi)關(guān)的斷開(kāi)與接通;3種基本運(yùn)算“-”、“∧”、“∨”（即： -，∩，∪）表示開(kāi)關(guān)的基本連接方式：反相、串聯(lián)、并聯(lián)（反向可以用字母上加短橫線(xiàn)也可以用'表示）。用代數(shù)方法解決開(kāi)關(guān)線(xiàn)路的分析和設(shè)計(jì)問(wèn)題。在電子計(jì)算機(jī)、自動(dòng)程序控制、電話(huà)交換系統(tǒng)中有廣泛應(yīng)用。依據(jù)代數(shù)的觀點(diǎn)，是什么物理意義無(wú)關(guān)緊要。在實(shí)驗(yàn)室中，將選擇其中一種物理表象來(lái)表示其中一個(gè)值。

下面首先定義開(kāi)關(guān)代數(shù)的三個(gè)運(yùn)算符號(hào)，然后研究開(kāi)關(guān)代數(shù)的若干性質(zhì) 。

奇異值分解 (singular value decomposition,SVD) 是另一種正交矩陣分解法；SVD是最可靠的分解法，但是它比QR 分解法要花上近十倍的計(jì)算時(shí)間。[U,S,V]=svd(A)，其中U和V分別代表兩個(gè)正交矩陣，而S代表一對(duì)角矩陣。 和QR分解法相同， 原矩陣A不必為正方矩陣。使用SVD分解法的用途是解最小平方誤差法和數(shù)據(jù)壓縮。

MATLAB以svd函數(shù)來(lái)執(zhí)行svd分解法， 其語(yǔ)法為[S,V,D]=svd(A)。2100433B