政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/52849
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113393/144380 (79%)
Visitors : 51235942      Online Users : 930
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/52849


    Title: 熱帶線性系統之研究
    On tropical linear systems
    Authors: 游竣博
    You, Jiun Bo
    Contributors: 蔡炎龍
    Tsai, Yen Lung
    游竣博
    You, Jiun Bo
    Keywords: 熱帶線性系統
    tropical linear system
    Date: 2011
    Issue Date: 2012-04-17 10:25:01 (UTC+8)
    Abstract: 本篇論文主要在探討熱帶線性系統(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.
    Reference: [1] Fran{\\c{c}}ois Baccelli, Guy Cohen, Geert Jan Olsder, and Jean Pierre Quadrat. Synchronization and linearity-an algebra for discrete event systems, 1992. 1
    [2] Diane Maclagan and Bernd Sturmfels. Introduction to tropical geometry, Nov 2009. 1
    [3] Grigory Mikhalkin. Tropical geometry and its applications, May 2006. 1
    [4] J{"{u}}rgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald. First steps in tropical geometry, Dec 2003. 1
    [5] David Speyer and Bernd Sturmfels. Tropical mathematics, Aug 2004. 1
    [6] P. Butkovi{\\v{c}} and R.A. Cuninghame-Green. The equation A x = B y over (max, +). Theoretical Computer Science, 293(1):3-12, Feb 2003. 1, 3, 16, 24
    [7] E. Lorenzo and M. J. de la Puente. An algorithm to describe the solution set of any tropical linear system A x = B x, jul 2010. 1, 3
    [8] Stephen H. Friedberg, Arnold J. Insel, and Lawrence E. Spence. Linear algebra, Jul 2003. 3
    [9] MathWorks. http://www.mathworks.com/products/matlab/. 27
    [10] 張智星. Matlab 程式設計與應用, Sep 2000. 27
    [11] David Fass. http://www.mathworks.com/matlabcentral/ leexchange/5475-cartprod-cartesian-product-of-multiple-sets, Jul 2004. 40
    [12] David Fass. http://www.mathworks.com/matlabcentral/ leexchange/5476-ind2subvect-multiple-subscript-vector-from-linear-index, Jul 2004. 42
    Description: 碩士
    國立政治大學
    應用數學研究所
    98751001
    100
    Source URI: http://thesis.lib.nccu.edu.tw/record/#G0098751001
    Data Type: thesis
    Appears in Collections:[Department of Mathematical Sciences] Theses

    Files in This Item:

    File SizeFormat
    100101.pdf893KbAdobe PDF2865View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback