極大代數(shù)矩陣本征值問題簡介

概念及算法

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

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

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

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

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

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

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

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

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

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