{"id":466,"date":"2013-09-08T22:40:52","date_gmt":"2013-09-09T02:40:52","guid":{"rendered":"http:\/\/zhanxw.com\/blog\/?p=466"},"modified":"2013-09-08T22:40:52","modified_gmt":"2013-09-09T02:40:52","slug":"%e7%9f%a9%e9%98%b5%e6%9c%80%e5%a4%a7%e7%89%b9%e5%be%81%e5%80%bc%e7%9a%84%e6%b1%82%e6%b3%95","status":"publish","type":"post","link":"https:\/\/zhanxw.com\/blog\/2013\/09\/%e7%9f%a9%e9%98%b5%e6%9c%80%e5%a4%a7%e7%89%b9%e5%be%81%e5%80%bc%e7%9a%84%e6%b1%82%e6%b3%95\/","title":{"rendered":"\u77e9\u9635\u6700\u5927\u7279\u5f81\u503c\u7684\u6c42\u6cd5"},"content":{"rendered":"<p>\u77e9\u9635\u6700\u5927\u7279\u5f81\u503c\u7684\u6c42\u6cd5<\/p>\n<p>Largest Eigenvalue of Matrix<\/p>\n<p>&nbsp;<\/p>\n<p>\u77e9\u9635\u7684\u7279\u5f81\u503c\u5206\u89e3\u662f\u5728\u79d1\u5b66\u8ba1\u7b97\u5e38\u89c1\u7684\u7ebf\u6027\u4ee3\u6570\u65b9\u6cd5\u3002\u5728\u4e00\u4e9b\u60c5\u51b5\u4e0b\uff0c\u6211\u4eec\u4e0d\u9700\u8981\u5168\u90e8\u7279\u5f81\u503c\uff0c\u53ea\u9700\u8981\u4e00\u90e8\u5206\u7279\u5f81\u503c\u3002\u6216\u8005\u56e0\u4e3a\u77e9\u9635\u7684\u4e00\u4e9b\u6027\u8d28\uff0c\u6211\u4eec\u53ea\u5bf9\u4e00\u90e8\u5206\u7279\u5f81\u503c\u611f\u5174\u8da3\u3002\u6bd4\u5982\u5bf9\u4e8e\u77e9\u9635 B = A&#8217; * A\uff0c \u5982\u679cA\u662fm by n\u7684\u5b9e\u77e9\u9635\uff0cm\u5f88\u5927\uff0cn\u5f88\u5c0f\u3002\u6839\u636e\u7ebf\u6027\u4ee3\u6570\u7406\u8bba\uff0cA, B\u77e9\u9635\u7684Rank\u6700\u591a\u662fn\uff0c\u5e76\u4e14B\u77e9\u9635\u662f\u534a\u6b63\u5b9a\u77e9\u9635\u3002\u5bf9\u77e9\u9635B\u505a\u7279\u5f81\u503c\u5206\u89e3\u65f6\uff0c\u5176\u7279\u5f81\u503c\u90fd\u662f\u975e\u8d1f\u5b9e\u6570\uff0c\u5e76\u4e14\u6700\u591a\u6709n\u4e2a\u6b63\u6570\u3002\u56e0\u6b64\uff0c\u5982\u679c\u6c42\u89e3B\u77e9\u9635\u7684\u7279\u5f81\u503c\uff0c\u53ea\u9700\u8981\u77e5\u9053\u5176\u6700\u5927\u7684n\u4e2a\u7279\u5f81\u503c\uff0c\u56e0\u4e3a\u5176\u4f59\u7279\u5f81\u503c\u90fd\u662f\u96f6\u3002<\/p>\n<p>\u6c42\u89e3\u4e00\u822c\u77e9\u9635\u7684\u7279\u5f81\u503c\u4e3b\u8981\u6709\u4e24\u79cd\uff1a\uff081\uff09\u7279\u5f81\u591a\u9879\u5f0f\uff082\uff09Power Method\uff08\u5305\u62ec Arnoldi\u65b9\u6cd5\u548cQR\u5206\u89e3)\u3002 \u5bf9\u4e8e\u5b9e\u5bf9\u79f0\u6b63\u5b9a\u77e9\u9635\uff0c\u53ef\u4ee5\u4f7f\u7528Choleskey\u5206\u89e3\u3002\u8fd9\u4e9b\u65b9\u6cd5\u53ef\u4ee5\u6c42\u51fa\u6240\u6709\u7684\u7279\u5f81\u503c\u3002\u800c\u5bf9\u4e8e\u6211\u4eec\u7279\u522b\u5173\u5fc3\u7684\u5b9e\u5bf9\u79f0(Hermitain\/Symmetric)\u6b63\u5b9a(Positive Definite)\u77e9\u9635\uff0c\u6bd4\u5982\u534f\u65b9\u5dee\u77e9\u9635\uff0c\u8fd9\u91cc\u6211\u4eec\u5173\u5fc3\u7684\u662f\u5176\u6700\u5927\uff08\u6216\u8005\u6700\u5c0f\uff09\u7684\u7279\u5f81\u503c\u3002\u8fd9\u91cc\u5e38\u7528\u7684\u65b9\u6cd5\u7684\u65b9\u6cd5\u53eb\u505aLinczos\u65b9\u6cd5\uff0c\u53ef\u4ee5\u770b\u505a\u662fArnoldi\u65b9\u6cd5\u7684\u7279\u4f8b\u3002Linczos\u65b9\u6cd5\u8ba1\u7b97A\u7684\u7279\u5f81\u503c\u662f\uff081\uff09\u5148\u968f\u673a\u751f\u6210\u4e00\u4e2a\u5411\u91cfv\uff0c\uff082\uff09\u518d\u5229\u7528\u4e00\u7cfb\u5217\u5411\u91cf\uff1a v, A*v, A*A*v, &#8230;\uff0c A^(n-1) * v \u6765\u5f97\u5230\u4e00\u4e2a\u7279\u6b8a\u77e9\u9635T\uff0c\u8fd9\u4e2a\u77e9\u9635\u7684\u5927\u5c0f\u662fm by m\uff0c\u8fd9\u91ccm\u5f80\u5f80\u8fdc\u5927\u4e8en\u3002\uff083\uff09\u5f97\u5230T\u4e4b\u540e\uff0c\u53ef\u4ee5\u4ee5O(m^2)\u7684\u590d\u6742\u5ea6\u6765\u7684\u5230\u7279\u5f81\u503c\u3002<\/p>\n<p>\u5b9e\u73b0Lanczos\u65b9\u6cd5\u65f6\u4f1a\u4f7f\u7528Multiple restart\uff0c\u6700\u6709\u540d\u7684\u5b9e\u73b0\u662fARPACK\u3002ARPACK\u662f\u7528Fortran\u5b9e\u73b0\u7684\uff0c\u5bf9Fortran\u4e0d\u719f\u6089\u5c31\u4e0d\u5bb9\u6613\u76f4\u63a5\u8c03\u7528ARPACK\u7684\u51fd\u6570\u3002\u4e0d\u8fc7\u5f88\u591a\u5176\u4ed6\u8f6f\u4ef6\u90fd\u5bf9ARPACK\u7684\u529f\u80fd\u8fdb\u884c\u4e86\u5c01\u88c5\u3002\u5728R\u91cc\u9762\u4f7f\u7528ARPACK\uff0c\u53ef\u4ee5\u7528igraph\u5305\uff0cR-blogger\u6709\u4e00\u4e2a\u8fd9\u65b9\u9762\u7684\u4f8b\u5b50\uff08<a href=\"http:\/\/www.r-bloggers.com\/using-arpack-to-compute-the-largest-eigenvalue-of-a-matrix\/\">\u94fe\u63a5<\/a>\uff09\u3002\u5176\u4ed6\u8f6f\u4ef6\u4e2d\u4e00\u822c\u4e5f\u90fd\u6709\u7528ARPACK\u6765\u5b9e\u73b0\u6c42\u4e00\u90e8\u5206\u7279\u5f81\u503c\u7684\u529f\u80fd\uff1aMatlab\u7684eigs\uff0cScipy\u7684eigs\u548ceighs\uff08\u5206\u522b\u5bf9\u5e94\u5b9e\u5bf9\u79f0\u77e9\u9635\u548cHermitian\u77e9\u9635\uff0c <a href=\"https:\/\/github.com\/scipy\/scipy\/blob\/master\/scipy\/sparse\/linalg\/eigen\/arpack\/arpack.py\">\u94fe\u63a5<\/a>\uff09\uff0cJulia\u7684eigs\uff08<a href=\"https:\/\/github.com\/JuliaLang\/julia\/blob\/master\/base\/linalg\/arnoldi.jl\">\u94fe\u63a5<\/a>\uff09\u3002<\/p>\n<p>\u540e\u8bdd\uff1a\u73b0\u5728\u5f00\u6e90\u7684\u79d1\u5b66\u8ba1\u7b97\u8f6f\u4ef6\u5f88\u591a\uff0c\u5f53\u6211\u4eec\u60f3\u5bfb\u627e\u5408\u9002\u9ad8\u6548\u7684\u6570\u503c\u8ba1\u7b97\u5de5\u5177\u65f6\uff0c\u53ef\u4ee5\u4ece\u6e90\u4ee3\u7801\u51fa\u53d1\u3002\u6bd4\u5982\u6211\u4eec\u77e5\u9053Matlab\u6709eigs\u51fd\u6570\uff0c\u5c31\u53ef\u4ee5\u7528\u201cjulia eigs\u201d\u6765\u770bjulia\u8bed\u8a00\u91cc\u662f\u600e\u4e48\u5b9e\u73b0eigs\u7684\u3002<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u77e9\u9635\u6700\u5927\u7279\u5f81\u503c\u7684\u6c42\u6cd5 Largest Eigenvalue of Matrix &nbsp; \u77e9\u9635\u7684\u7279\u5f81\u503c\u5206\u89e3\u662f\u5728\u79d1\u5b66\u8ba1\u7b97\u5e38\u89c1\u7684\u7ebf\u6027\u4ee3\u6570\u65b9\u6cd5\u3002\u5728\u4e00\u4e9b\u60c5\u51b5\u4e0b\uff0c\u6211\u4eec\u4e0d\u9700\u8981\u5168\u90e8\u7279\u5f81\u503c\uff0c\u53ea\u9700\u8981\u4e00\u90e8\u5206\u7279\u5f81\u503c\u3002\u6216\u8005\u56e0\u4e3a\u77e9\u9635\u7684\u4e00\u4e9b\u6027\u8d28\uff0c\u6211\u4eec\u53ea\u5bf9\u4e00\u90e8\u5206\u7279\u5f81\u503c\u611f\u5174\u8da3\u3002\u6bd4\u5982\u5bf9\u4e8e\u77e9\u9635 B = A&#8217; * A\uff0c \u5982\u679cA\u662fm by n\u7684\u5b9e\u77e9\u9635\uff0cm\u5f88\u5927\uff0cn\u5f88\u5c0f\u3002\u6839\u636e\u7ebf\u6027\u4ee3\u6570\u7406\u8bba\uff0cA, B\u77e9\u9635\u7684Rank\u6700\u591a\u662fn\uff0c\u5e76\u4e14B\u77e9\u9635\u662f\u534a\u6b63\u5b9a\u77e9\u9635\u3002\u5bf9\u77e9\u9635B\u505a\u7279\u5f81\u503c\u5206\u89e3\u65f6\uff0c\u5176\u7279\u5f81\u503c\u90fd\u662f\u975e\u8d1f\u5b9e\u6570\uff0c\u5e76\u4e14\u6700\u591a\u6709n\u4e2a\u6b63\u6570\u3002\u56e0\u6b64\uff0c\u5982\u679c\u6c42\u89e3B\u77e9\u9635\u7684\u7279\u5f81\u503c\uff0c\u53ea\u9700\u8981\u77e5\u9053\u5176\u6700\u5927\u7684n\u4e2a\u7279\u5f81\u503c\uff0c\u56e0\u4e3a\u5176\u4f59\u7279\u5f81\u503c\u90fd\u662f\u96f6\u3002 \u6c42\u89e3\u4e00\u822c\u77e9\u9635\u7684\u7279\u5f81\u503c\u4e3b\u8981\u6709\u4e24\u79cd\uff1a\uff081\uff09\u7279\u5f81\u591a\u9879\u5f0f\uff082\uff09Power Method\uff08\u5305\u62ec Arnoldi\u65b9\u6cd5\u548cQR\u5206\u89e3)\u3002 \u5bf9\u4e8e\u5b9e\u5bf9\u79f0\u6b63\u5b9a\u77e9\u9635\uff0c\u53ef\u4ee5\u4f7f\u7528Choleskey\u5206\u89e3\u3002\u8fd9\u4e9b\u65b9\u6cd5\u53ef\u4ee5\u6c42\u51fa\u6240\u6709\u7684\u7279\u5f81\u503c\u3002\u800c\u5bf9\u4e8e\u6211\u4eec\u7279\u522b\u5173\u5fc3\u7684\u5b9e\u5bf9\u79f0(Hermitain\/Symmetric)\u6b63\u5b9a(Positive Definite)\u77e9\u9635\uff0c\u6bd4\u5982\u534f\u65b9\u5dee\u77e9\u9635\uff0c\u8fd9\u91cc\u6211\u4eec\u5173\u5fc3\u7684\u662f\u5176\u6700\u5927\uff08\u6216\u8005\u6700\u5c0f\uff09\u7684\u7279\u5f81\u503c\u3002\u8fd9\u91cc\u5e38\u7528\u7684\u65b9\u6cd5\u7684\u65b9\u6cd5\u53eb\u505aLinczos\u65b9\u6cd5\uff0c\u53ef\u4ee5\u770b\u505a\u662fArnoldi\u65b9\u6cd5\u7684\u7279\u4f8b\u3002Linczos\u65b9\u6cd5\u8ba1\u7b97A\u7684\u7279\u5f81\u503c\u662f\uff081\uff09\u5148\u968f\u673a\u751f\u6210\u4e00\u4e2a\u5411\u91cfv\uff0c\uff082\uff09\u518d\u5229\u7528\u4e00\u7cfb\u5217\u5411\u91cf\uff1a v, A*v, A*A*v, &#8230;\uff0c A^(n-1) * v \u6765\u5f97\u5230\u4e00\u4e2a\u7279\u6b8a\u77e9\u9635T\uff0c\u8fd9\u4e2a\u77e9\u9635\u7684\u5927\u5c0f\u662fm by m\uff0c\u8fd9\u91ccm\u5f80\u5f80\u8fdc\u5927\u4e8en\u3002\uff083\uff09\u5f97\u5230T\u4e4b\u540e\uff0c\u53ef\u4ee5\u4ee5O(m^2)\u7684\u590d\u6742\u5ea6\u6765\u7684\u5230\u7279\u5f81\u503c\u3002 \u5b9e\u73b0Lanczos\u65b9\u6cd5\u65f6\u4f1a\u4f7f\u7528Multiple restart\uff0c\u6700\u6709\u540d\u7684\u5b9e\u73b0\u662fARPACK\u3002ARPACK\u662f\u7528Fortran\u5b9e\u73b0\u7684\uff0c\u5bf9Fortran\u4e0d\u719f\u6089\u5c31\u4e0d\u5bb9\u6613\u76f4\u63a5\u8c03\u7528ARPACK\u7684\u51fd\u6570\u3002\u4e0d\u8fc7\u5f88\u591a\u5176\u4ed6\u8f6f\u4ef6\u90fd\u5bf9ARPACK\u7684\u529f\u80fd\u8fdb\u884c\u4e86\u5c01\u88c5\u3002\u5728R\u91cc\u9762\u4f7f\u7528ARPACK\uff0c\u53ef\u4ee5\u7528igraph\u5305\uff0cR-blogger\u6709\u4e00\u4e2a\u8fd9\u65b9\u9762\u7684\u4f8b\u5b50\uff08\u94fe\u63a5\uff09\u3002\u5176\u4ed6\u8f6f\u4ef6\u4e2d\u4e00\u822c\u4e5f\u90fd\u6709\u7528ARPACK\u6765\u5b9e\u73b0\u6c42\u4e00\u90e8\u5206\u7279\u5f81\u503c\u7684\u529f\u80fd\uff1aMatlab\u7684eigs\uff0cScipy\u7684eigs\u548ceighs\uff08\u5206\u522b\u5bf9\u5e94\u5b9e\u5bf9\u79f0\u77e9\u9635\u548cHermitian\u77e9\u9635\uff0c \u94fe\u63a5\uff09\uff0cJulia\u7684eigs\uff08\u94fe\u63a5\uff09\u3002 \u540e\u8bdd\uff1a\u73b0\u5728\u5f00\u6e90\u7684\u79d1\u5b66\u8ba1\u7b97\u8f6f\u4ef6\u5f88\u591a\uff0c\u5f53\u6211\u4eec\u60f3\u5bfb\u627e\u5408\u9002\u9ad8\u6548\u7684\u6570\u503c\u8ba1\u7b97\u5de5\u5177\u65f6\uff0c\u53ef\u4ee5\u4ece\u6e90\u4ee3\u7801\u51fa\u53d1\u3002\u6bd4\u5982\u6211\u4eec\u77e5\u9053Matlab\u6709eigs\u51fd\u6570\uff0c\u5c31\u53ef\u4ee5\u7528\u201cjulia eigs\u201d\u6765\u770bjulia\u8bed\u8a00\u91cc\u662f\u600e\u4e48\u5b9e\u73b0eigs\u7684\u3002 &nbsp; &nbsp;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,15],"tags":[122,121,120],"class_list":["post-466","post","type-post","status-publish","format-standard","hentry","category-code","category-statistics","tag-computation","tag-eigen","tag-linear-algebra"],"_links":{"self":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/posts\/466","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/comments?post=466"}],"version-history":[{"count":0,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/posts\/466\/revisions"}],"wp:attachment":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/media?parent=466"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/categories?post=466"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/tags?post=466"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}