臺灣博碩士論文加值系統

Perron-Frobenius 定理在非負不可約矩陣上展示了一些重要的結果。此定理目前已有許多的應用及推廣。在本論文中，我們著重在非負不可約矩陣上。在建構出一線性同倫後，我們分析解曲線並證明任意一個非負不可約矩陣有一正特徵對。這個是Perron-Frobenius定理主要的結果。此證明技巧可被推廣用來證明張量上的Perron-Frobenius定理。除此之外，我們也呈現了延拓法在非負不可約矩陣及張量上的數值結果。

The Perron-Frobenius theorem shows some important results on nonnegative irreducible matrices. This theorem has various applications and extensions. In this paper, we focus on the nonnegative irreducible matrices. After constructing a linear homotopy, we analyze the solution curve of the linear homotopy and prove that any nonnegative irreducible matrix has the positive eigenpair. This is the main result of the Perron-Frobenius theorem. The skill of the proof can be extended to prove the Perron-Frobenius theorem on tensors. Furthermore, the numerical results computed by the homotopy continuation method on nonnegative irreducible matrices and tensors are presented.

1 Introduction
2 Preliminaries for matrices
2.1 Irreducible matrices
2.2 Gershgorin's disk theorem
2.3 Implicit function theorem
3 Perron-Frobenis theorem
3.1 Analysis of nonnegative irreducible matrices
3.2 Proof of Theorem 3.1
4 Numerical experiments
4.1 Homotopy continuation method
4.2 Other numerical method
4.3 Compare the numerical results
5 Preliminaries for tensors
5.1 Tensor notations and operations
5.2 Eigenvalue of tensors
5.3 Symmetric and semi-symmetric tensors
5.4 Irreducible tensors
5.5 Rank-1 tensors
6 Perron-Frobenius theorem on tensors
6.1 Analysis of nonnegative irreducible tensors
6.2 Proof of Theorem 6.1
7 Numerical experiments on tensors
7.1 Jacobian matrix
7.2 Other algorithms for tensors
7.3 Compare the numerical results on tensors
8 Conclusion

[1] C.S. Liu, C.H. Guo, and W. W. Lin, Newton–Noda iteration for finding the Perron pair of a weakly irreducible nonnegative tensor, preprint, (2017).

[2] DIMACS10: DIMACS10 test set and the University of Florida Sparse Matrix Collection. $https://sparse.tamu.edu/DIMACS10$

[3] H.B. Keller, Lectures on Numerical Methods in Bifurcation problems, 1987.

[4] K.C. Chang, K. Pearson, and T. Zhang, \emph{A survey on the spectral theory of nonnegative tensors}, Numer. Linear A;gebra Appl., 20 (2013), pp.891-912.

[5] K.C. Chang, K. Pearson, and T. Zhang, \emph{Perron-Frobenius theorem for nonnegative tensors}, Commum. Math. Sci., 6(2008) no. 1, 507-520.

[6] K Kontovasilis, RJ Plemmons and WJ Stewart, Block Cyclic SOR for Markov Chains With p-cyclic Infinitesimal Generator, 1991.

[7] M. Ng, L. Qi, and G. Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1090–1099.

[8] P. Chanchana, An algorithm for computing the Perron root of a nonnegative irreducible matrices, 2007.

[9] Q. Ni and L. Qi, A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map, J. Global Optim., 61 (2015) pp. 627–641

[10] R. A. Horn, and C. R. Johnson, (2012)Matrix analysis, Cambridge University Press.

[11] S. Hu, L. Qi and J. Xie, The largest Laplacian and signless Laplacian H-eigenvalues of a uniform hypergraph, Linear Algebra Appl., 469 (2015), pp. 1–27.

[12] S. Hu, Z.-H. Huang, C. Ling, and L. Qi, On determinants and eigenvalue theory of tensors, J. Symb. Comput., 50 (2013), pp. 508–531.

[13] T.G. Kolda and B.W. Bader, \emph{Tensor Decompositions and Applications}, SIAM Review, vol. 51, no. 3, pp. 455-500, September 2009.

[14] Y.C. Kuo, W.W. Lin and C.S. Liu, \emph{Continuation Method For Computing Z-/H-Eigenpairs of Nonnegative Tensors}, arXiv preprint arXiv:1702.05841.

[15] Y. Wei, and W. Ding, Theory and Computation of Tensors : Multi-Dimensional Arrays, 2016.