臺灣博碩士論文加值系統

隨著社會經濟和交通事業的發展，交通擁擠的問題日漸受到重視。為了有效避免塞車，旅行時間的計算扮演著不可或缺的角色。針對此議題，我們運用高階的馬可夫鏈，預測路段每單位時間內的平均車速。馬可夫鏈已被廣泛應用於隨機過程的預測，藉由一段狀態的觀測，推測未來不同狀態的發生率。將馬可夫鏈運用於交通流，可以藉由資料的收集，推測長期的交通狀況。二階馬可夫鏈的轉移矩陣僅能描述一步的狀態變化率。然而，交通狀況的變化可能不僅僅只與前一期的狀態有關。為了更為精確地預測交通狀況，我們利用高階馬可夫鏈來表現其複雜的關係。本研究以真實的交通狀況為例，先將大量的交通數據經過分析，利用分析後的數據構造出高階馬可夫鏈的轉移張量，並求解張量特徵值問題。我們陳列不同階馬可夫鏈的數值結果，探討H/Z-特徵對在此問題的差異。此外，我們也比較不同階馬可夫鏈對於交通狀態的預測能力，最後預估其旅程時間

With the development of social economy and transportation, the problem of traffic congestion is getting much more attention. In order to avoid traffic congestion, the calculation of travel time plays an important role. For this issue, we use the high-order Markov chain to predict the average flow rate of each road. Markov chain has been widely applied in the prediction of random processes. The occurrences of statuses are estimated via a sequence of observations. In the traffic flow, the long-term traffic condition can be estimated via a sequence of observations by applying the Markov chains. The one-step rate of state change can be described by the transfer matrix of the second-order Markov chain. However, changes in traffic conditions might be related to a few previous states. In order to more accurately predict the traffic condition, we use the high-order Markov chain to express the relationship between states. In this study, the real traffic data is used. First, we analyze the large quantity of traffic data. Then, the tensor of high-order Markov chain is formulated. Finally, we solve the tensor eigenvalue problem. We show the numerical results for the Markov chains of different orders and discuss the difference between H/Z-eigenpairs in this problem. In addition, we compare the accuracy between Markov chains of different orders and estimate the travel time.

1 介紹1
2 背景4
2.1 張量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 克羅内克積. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 張量積的等價公式. . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Axm

1] M. Bando, K. Hasebe, A. Nakayama, A. Shibata, and Y. Sugiyama. Dynamical
model of traffic congestion and numerical simulation. Physical review E,
51(2):1035, 1995.
[2] A. Berman and R.J. Plemmons. Nonnegative matrices in the mathematical
sciences. SIAM, 1994.
[3] K. Chang, L. Qi, and T. Zhang. A survey on the spectral theory of nonnegative
tensors. Numerical Linear Algebra with Applications, 20(6):891–912, 2013.
[4] K.C. Chang, K. Pearson, T. Zhang, et al. Perron-frobenius theorem for nonnegative
tensors. Commun. Math. Sci, 6(2):507–520, 2008.
[5] K.C. Chang, K.J. Pearson, and T. Zhang. Primitivity, the convergence of the
nqz method, and the largest eigenvalue for nonnegative tensors. SIAM Journal
on Matrix Analysis and Applications, 32(3):806–819, 2011.
[6] K.C. Chang, K.J. Pearson, and T. Zhang. Some variational principles for
z-eigenvalues of nonnegative tensors. Linear Algebra and its Applications,
438(11):4166–4182, 2013.
[7] K.C. Chang and T. Zhang. On the uniqueness and non-uniqueness of the positive
z-eigenvector for transition probability tensors. Journal of Mathematical
Analysis and Applications, 408(2):525–540, 2013.
[8] L. Chen, L. Han , and L. Zhou. Computing tensor eigenvalues via homotopy
methods. SIAM Journal on Matrix Analysis and Applications, 37(1):290–319,
2016.
[9] W.K. Ching, E.S. Fung, and M.K. Ng . Higher-order markov chain models for
categorical data sequences. Naval Research Logistics (NRL), 51(4):557–574,
2004.
[10] S.N. Chow, J. Mallet-Paret, and J.A. Yorke. Finding zeroes of maps: homotopy
methods that are constructive with probability one. Mathematics of
Computation, 32(143):887–899, 1978.
[11] D. Chowdury, L. Santen, and A. Schadschneider. Statistical physics of vehicular
traffic and some related systems. Physics Reports, 329(4):199–329, 2000.
[12] V. Coscia, M. Delitala, and P. Frasca. On the mathematical theory of vehicular
traffic flow ii: Discrete velocity kinetic models. International Journal of Non-
Linear Mechanics, 42(3):411–421, 2007.
[13] M. Delitala and A. Tosin. Mathematical modeling of vehicular traffic: a discrete
kinetic theory approach. Mathematical Models and Methods in Applied
Sciences, 17(06):901–932, 2007.
[14] S. Friedland, S. Gaubert, and L. Han. Perron–frobenius theorem for nonnegative
multilinear forms and extensions. Linear Algebra and its Applications,
438(2):738–749, 2013.
[15] K.C. Gowda and E. Diday. Symbolic clustering using a new dissimilarity measure.
pattern recognition, 24(6):567–578, 1991.
[16] D. Helbing. Traffic and related self-driven many-particle systems. Reviews of
modern physics, 73(4):1067, 2001.
[17] S. Hu, Z.H. Huang, and L. Qi. Finding the spectral radius of a nonnegative
tensor. arXiv preprint arXiv:1111.2138, 2011.
[18] H.B. Keller. Lectures on numerical methods in bifurcation problems. Applied
Mathematics, 217:50, 1987.
[19] B.S. Kerner. Introduction to modern traffic flow theory and control: the long
road to three-phase traffic theory. Springer Science & Business Media, 2009.
[20] Y.C. Kuo, W.W. Lin, and C.S. Liu. Continuation methods for computing z-
/h-eigenpairs of nonnegative tensors. arXiv preprint arXiv:1702.05841, 2017.
[21] W. Li and M.K. Ng. On the limiting probability distribution of a transition
probability tensor. Linear and Multilinear Algebra, 62(3):362–385, 2014.
[22] L.H. Lim. Singular values and eigenvalues of tensors: a variational approach. In
Computational Advances in Multi-Sensor Adaptive Processing, 2005 1st IEEE
International Workshop on, pages 129–132. IEEE, 2005.
[23] C.S. Liu, C.H. Guo, and W.W. Lin. Newton–noda iteration for finding the perron
pair of a weakly irreducible nonnegative tensor. Numerische Mathematik,
pages 1–28, 2017.
[24] T. Nagatani. The physics of traffic jams. Reports on progress in physics,
65(9):1331, 2002.
[25] M. Ng, L. Qi, and G. Zhou. Finding the largest eigenvalue of a nonnegative
tensor. SIAM Journal on Matrix Analysis and Applications, 31(3):1090–1099,
2009.
[26] G. Ni, L. Qi, F. Wang, and Y. Wang. The degree of the e-characteristic
polynomial of an even order tensor. Journal of Mathematical Analysis and
Applications, 329(2):1218–1229, 2007.
[27] Q. Ni and L. Qi. A quadratically convergent algorithm for finding the largest
eigenvalue of a nonnegative homogeneous polynomial map. Journal of Global
Optimization, 61(4):627–641, 2015.
[28] J. Peter, A.D. Richard, et al. Time series: theory and methods. Is, 1:60–61,
2001.
[29] L. Qi. Eigenvalues of a real supersymmetric tensor. Journal of Symbolic Computation,
40(6):1302–1324, 2005.
[30] L. Qi. Eigenvalues and invariants of tensors. Journal of Mathematical Analysis
and Applications, 325(2):1363–1377, 2007.
[31] L. Qi, W. Sun, and Y. Wang. Numerical multilinear algebra and its applications.
Frontiers of Mathematics in China, 2(4):501–526, 2007.
[32] L. Qi, Y. Wang, and E.X. Wu. D-eigenvalues of diffusion kurtosis tensors.
Journal of Computational and Applied Mathematics, 221(1):150–157, 2008.
[33] A.E. Raftery. A model for high-order markov chains. Journal of the Royal
Statistical Society. Series B (Methodological), pages 528–539, 1985.
[34] Y. Sugiyama, M. Fukui, M. Kikuchi, K. Hasebe, A. Nakayama, K. Nishinary,
S.I. Tadaki, and S. Yukawa. Traffic jams without bottlenecks—experimental
evidence for the physical mechanism of the formation of a jam. New journal
of physics, 10(3):033001, 2008.