本篇論文主要在探討熱帶線性系統(tropical linear system) A x = b 與雙邊齊次熱帶線性系統(two-sided homogeneous tropical linear system) A x = B y 的求解方法。我們將明確的描述任何熱帶線性系統與雙邊齊次熱帶線性系統的解。 如同古典的論述, 當求解線性系統 A x = b 時, 我們首先會先找到對應的 ``齊次'' 系統 A x = 0 來求解。而對於雙邊齊次熱帶線性系統, 我們將利用勝序列的概念, 將雙邊齊次熱帶線性系統轉化為 k 組古典熱帶線性系統: 含等式系統 S: C[x^t -y^t 1]^t = 0 與不等式系統 T: D[x^t -y^t 1]^t <= 0 。除此之外, 利用相容性條件來減少 k 的數量。 過程中我們處理的 S, T 均為雙變量的系統, 係數分別為 1 與 -1, 對於 S 我們以高斯-喬登消去法(Gauss–Jordan elimination)處理。對於 T 我們將以類似高斯-喬登消去法的方式進行列運算, 因此我們定義次特殊矩陣(sub-special matrix), 而進行的過程我們稱之為次特殊化(sub–specialization)。 最後將以 MATLAB 作為工具來求解出這兩類的熱帶線性系統。 / The thesis mainly discusses the methods of finding solutions of tropical linear systems A x = b and two-sided homogeneous tropical linear systems A x = B y. We are able to give explicit descriptions of all solutions of any tropical linear systems A x = b and two-sided homogeneous tropical linear systems A x = B y. As the classical situations, when solving the linear systems of the form A x = b, we first find the solutions for the corresponding ``homogeneous'' case A x = 0. For two-sided homogeneous tropical linear systems A x = B y, we use the concept of win sequence to convert it into a finite number k of classical linear systems: either a system S: C[x^t -y^t 1]^t = 0 of equations or a system T: D[x^t -y^t 1]^t <= 0 of inequalities. Moreover, we used so called ``compatibility conditions'' to reduce the number of k. The particular feature of both S and T is that each item (equation or inequality) is bivariate. It involves exactly two variables; one variable with coefficient 1, and the other one with -1. S is solved by Gauss-Jordon elimination. We explain how to solve T by a method similar to Gauss-Jordon elimination. To achieve this, we introduce the notion of sub–special matrix. The procedure applied to T is called sub–specialization. Finally, we will use MATLAB to solve tropical linear systems of these two types.

當用內部點方法來解含有稠密行或退化的大型線性規劃問題，在解最小平方問題中， 當解趨近最佳解時，系統會趨近於singular的線性系統，在這種情況之下我們提出一 種有效而且穩定的方法來解決此問題。 Choi提出，對於有綢密行的矩陣Schur complement直接法會比加速的conjugate gra- dient 方法來的有效，可是前者常會導致數值上的不穩定。Tomlin用 QR 分解法來解 I ．ｓ．ｐ．可是此法會導致fill-ins，破壞稀疏的特性。用Given rotations 會比 上述方法來得有效且較穩定。而我們的新方法將更進一步的改進它的穩定性。雖然 S VD 是最穩定的方法，可是它會破壞矩陣的稀疏性，為了保持稀疏性，所以我們不採 用SVD 方法，我們的方法最主要的是在於將樓梯形矩陣分割成小塊，再用 QR 和局部 調換來分解此小塊以保持稀疏性和穩定性。 B =[EF/GH]，E 為樓梯形矩陣，對此矩陣的小塊，根據以下四規則由左上角到右 下角一個一個再分割和分解。 規則１：在處理現在的塊M 右下角最高位置的小塊之前，先將Ｍ底下的小塊處理完。 ＜有可能底下的小塊有部份已處理過，但尚未完全處理＞ 規則２：假如M 和參考的塊N 有共同的列＜行＞，則以Ｎ最高列＜最左行＞的位置為 準，向＜向上＞將M 分割成上下＜左右＞，M 和M ，兩小塊。 規則３：用 QR 加上行調換的方法，對M 做分解得到上三角矩陣R ．假如R 的底下還 有其它小塊，則用R 對角線元素和Giver rotation方法，由上往下將底下小塊的元素 消去。 規則４：任何在R 右邊的部份或做分解時所產生的零矩陣皆不做分解和分割。E 分解 完後，再對Ｆ剩餘的部份分解，經過行和列的調換，即可得到上三角矩陣R ．接著把 rank-deficient的部份和G ，用R 及高期消去法消掉並對Ｈ的部份做分解，得到我們 所要的分解。再經推導便可得到解ｌ．ｓ．ｐ．的式子。由誤差估計和數值結果告訴 我們，此法是穩定而且有效的。