Lanczos algorithm (original) (raw)
Das Lanczos-Verfahren (nach Cornelius Lanczos) ist sowohl ein iterativer Algorithmus zur Bestimmung einiger Eigenwerte und eventuell der zugehörigen Eigenvektoren einer Matrix als auch ein iterativer Algorithmus zur approximativen Lösung eines linearen Gleichungssystems. Der Algorithmus für Eigenwerte konvergiert am schnellsten gegen die gut von den anderen Eigenwerten separierten, meist gegen die betragsgrößten Eigenwerte. Der Algorithmus für lineare Gleichungssysteme ist im allgemeinen Fall dem BiCG-Verfahren und für spezielle Matrizen dem CG-Verfahren mathematisch äquivalent.
| Property | Value |
|---|---|
| dbo:abstract | Das Lanczos-Verfahren (nach Cornelius Lanczos) ist sowohl ein iterativer Algorithmus zur Bestimmung einiger Eigenwerte und eventuell der zugehörigen Eigenvektoren einer Matrix als auch ein iterativer Algorithmus zur approximativen Lösung eines linearen Gleichungssystems. Der Algorithmus für Eigenwerte konvergiert am schnellsten gegen die gut von den anderen Eigenwerten separierten, meist gegen die betragsgrößten Eigenwerte. Der Algorithmus für lineare Gleichungssysteme ist im allgemeinen Fall dem BiCG-Verfahren und für spezielle Matrizen dem CG-Verfahren mathematisch äquivalent. (de) The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an Hermitian matrix, where is often but not necessarily much smaller than . Although computationally efficient in principle, the method as initially formulated was not useful, due to its numerical instability. In 1970, Ojalvo and Newman showed how to make the method numerically stable and applied it to the solution of very large engineering structures subjected to dynamic loading. This was achieved using a method for purifying the Lanczos vectors (i.e. by repeatedly reorthogonalizing each newly generated vector with all previously generated ones) to any degree of accuracy, which when not performed, produced a series of vectors that were highly contaminated by those associated with the lowest natural frequencies. In their original work, these authors also suggested how to select a starting vector (i.e. use a random-number generator to select each element of the starting vector) and suggested an empirically determined method for determining , the reduced number of vectors (i.e. it should be selected to be approximately 1.5 times the number of accurate eigenvalues desired). Soon thereafter their work was followed by Paige, who also provided an error analysis. In 1988, Ojalvo produced a more detailed history of this algorithm and an efficient eigenvalue error test. (en) El algoritmo de Lanczos es un algoritmo iterativo creado por Cornelius Lanczos,este es una adaptación de los métodos iterativos para encontrar los valores propios más útiles y vectores propios de un sistema lineal de dimensión realizando un número de operaciones, , donde es más pequeño que . Aunque computacionalmente eficiente, en principio, el método formulado inicialmente no era útil, debido a su inestabilidad numérica. En 1970, Ojalvo y Newman mostraron cómo hacer el método numéricamente estable. Esto se logró utilizando un método para la corrección de los vectores a cualquier grado de precisión que, cuando no se realiza, produce una serie de vectores que están altamente contaminados por los asociados con las frecuencias naturales más bajas. En su trabajo original, estos autores también sugirieron cómo seleccionar un vector de partida (utilizan un generador de números aleatorios para seleccionar cada elemento del vector de partida) y propusieron un método determinado empíricamente para determinar , el reducido número de vectores (debe ser seleccionado para ser de aproximadamente 1 ½ veces el número de valores propios exactos que se desea). Poco después su trabajo fue seguido por más artículos que también proporciaron un análisis del error cometido. En el año 1988, Ojalvo produjo una historia más detallada de este algoritmo y una prueba de error eficiente para un valor propio. Actualmente, el método es ampliamente utilizado en una variedad de campos técnicos y ha dado lugar una serie de variantes. (es) Algoritma Lanczos adalah algoritma iteratif adaptasi dari metode daya (power method) untuk menemukan nilai dan vektor eigen yang "paling berguna" (umumnya yang tertinggi/terendah) dari sebuah matriks Hermite berukuran , dengan tidak perlu jauh lebih kecil dari . Algoritma ini dirancang oleh pada tahun 1950. Meskipun secara prinsip metode ini efisien dalam aspek komputasi, metode yang dirancang pada awalnya tidak berguna karena sifatnya yang tidak stabil secara numerik. Pada tahun 1970, Ojalvo dan Newman menunjukkan cara membuat metode ini stabil secara numerik, dan mengaplikasikannya untuk menemukan mode getaran dari sebuah struktur teknik berukuran besar. Hal ini dicapai dengan menggunakan sebuah teknik untuk 'memurnikan' vektor-vektor Lanczos (misal dengan mengortogonalkan secara berulang setiap vektor yang baru ditemukan dengan semua vektor yang sudah ditemukan) sampai ke suatu akurasi yang diinginkan. Jika teknik tidak diterapkan, metode akan menghasilkan vektor-vektor yang sangat 'terkontaminasi' oleh vektor-vektor yang berasosiasi dengan frekuensi alami yang rendah. Dalam karyanya, Ojalvo dan Newman juga mengusulkan cara memilih vektor awal (starting vector; misalnya dengan menggunakan pembangkit bilangan acak), dan mengusulkan metode menentukan nilai secara empiris (sebaiknya dipilih kurang lebih 1.5 kali dari banyak nilai eigen akurat yang diinginkan). Kontribusi lain diberikan oleh Paige, yang juga memberikan analisis galat untuk metode ini. Pada tahun 1988, Ojalvo memberikan sejarah yang lebih akurat dari algoritma ini, dan sebuah uji galat nilai eigen yang efisien. (in) En algèbre linéaire, l’algorithme de Lanczos (ou méthode de Lanczos) est un algorithme itératif pour déterminer les valeurs et vecteurs propres d'une matrice carrée, ou la décomposition en valeurs singulières d'une matrice rectangulaire. Cet algorithme n'a pas de lien avec le fenêtrage de Lanczos (utilisé par exemple pour le redimensionnement d'images), si ce n'est que tous les deux tirent leur nom du même inventeur, le physicien et mathématicien hongrois Cornelius Lanczos. (fr) ランチョス法（ランチョスほう、英: Lanczos algorithm）とは、対象となる対称行列を三重対角化する手法。 コルネリウス・ランチョスによって開発された反復計算法である。クリロフ部分空間法の一つ。 (ja) Lanczos 算法是设计的一种直接算法，它由改编而来，用于找出厄米矩阵的各组特征值和特征向量中“最有用的”（趋于极高/极低的）的组，通常（但不一定）远小于。最初指定的方法尽管从原则上将计算效率应该很高，但是由于其数值不稳定而不敷实用。 1970 年，Ojalvo 和 Newman 提出了使该方法在数值上变稳定的方式，并将其应用于承受动态载荷的大型工程结构的求解。实现方式是，采取措施纯化了 Lanczos 向量（即，反复地把每个新生成的向量同所有先前生成的向量一起重新归一化），纯化到任意的准确度即可，先前没有执行这一步，因而产生了一系列被那些联系于最低自然频率的向量严重污染了的向量。 在最初的文章中，这些作者还建议了选择起始向量的方式（即，使用随机数生成器来选择起始向量的每个元素），并提出了一种根据经验确定下来的方法，用来确定向量数量的减少量（即，应选为所需准确特征值数量的约 1.5 倍）。此后不久，Paige 跟进了他们的工作，而 Paige 提供了错误分析。 1988 年，Ojalvo 为该算法制作了更详细的历史记录和有效的特征值误差测试。 (zh) |
| dbo:wikiPageExternalLink | http://www.mathworks.com/help/techdoc/ref/eigs.html https://ai.stanford.edu/~ang/papers/ijcai01-linkanalysis.pdf https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.eigsh.html http://www.cs.wm.edu/~andreas/software/ https://books.google.com/books%3Fid=mlOa7wPX6OYC&pg=PA470 https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html%23doc_002deigs https://www.cs.cmu.edu/~bickson/gabp/%23download |
| dbo:wikiPageID | 2593852 (xsd:integer) |
| dbo:wikiPageLength | 43782 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112826364 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:SciPy dbr:NAG_Numerical_Library dbr:Tridiagonal_matrix dbr:Jon_Kleinberg dbr:Peter_Montgomery_(mathematician) dbr:Characteristic_polynomial dbr:Uniform_distribution_(continuous) dbr:Inverse_iteration dbr:Power_iteration dbr:Cornelius_Lanczos dbr:Matrix_diagonalization dbr:Nuclear_physics dbr:Eigenvalue dbr:Eigenvalues_and_eigenvectors dbr:Eigenvector dbr:GF(2) dbr:GNU_Octave dbr:Gradient dbr:GraphLab dbr:Condensed_matter_physics dbr:Orthonormality dbr:Arnoldi_iteration dbr:MATLAB dbr:Cache_(computing) dbr:Hamiltonian_matrix dbr:Householder_transformation dbr:Krylov_subspace dbr:Stationary_point dbr:Numerical_stability dbr:Spectrum_of_a_matrix dbr:Synchronization_(computer_science) dbr:Divide-and-conquer_eigenvalue_algorithm dbr:HITS_algorithm dbr:Euclidean_norm dbr:Normal_distribution dbr:Nuclear_shell_model dbr:PageRank dbr:Gram–Schmidt_process dbr:Iterative_method dbr:QR_algorithm dbr:Rayleigh_quotient dbr:Hermitian_matrix dbr:ARPACK dbc:Numerical_linear_algebra dbr:Chebyshev_polynomial dbr:Kernel_(matrix) dbr:Collaborative_filtering dbr:Eigengap dbr:Hessenberg_matrix dbr:Strongly_correlated_material dbr:Sparse_matrix dbr:Orthogonal_polynomials dbr:Real_number dbr:Lossy_compression dbr:Unitary_matrix dbr:Latent_semantic_indexing dbr:Ill-conditioned dbr:Power_method |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:For dbt:Main dbt:Notetag dbt:R dbt:Reflist dbt:Numerical_linear_algebra |
| dcterms:subject | dbc:Numerical_linear_algebra |
| rdf:type | yago:WikicatMatrices yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Arrangement107938773 yago:Array107939382 yago:Event100029378 yago:Group100031264 yago:Matrix108267640 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | Das Lanczos-Verfahren (nach Cornelius Lanczos) ist sowohl ein iterativer Algorithmus zur Bestimmung einiger Eigenwerte und eventuell der zugehörigen Eigenvektoren einer Matrix als auch ein iterativer Algorithmus zur approximativen Lösung eines linearen Gleichungssystems. Der Algorithmus für Eigenwerte konvergiert am schnellsten gegen die gut von den anderen Eigenwerten separierten, meist gegen die betragsgrößten Eigenwerte. Der Algorithmus für lineare Gleichungssysteme ist im allgemeinen Fall dem BiCG-Verfahren und für spezielle Matrizen dem CG-Verfahren mathematisch äquivalent. (de) En algèbre linéaire, l’algorithme de Lanczos (ou méthode de Lanczos) est un algorithme itératif pour déterminer les valeurs et vecteurs propres d'une matrice carrée, ou la décomposition en valeurs singulières d'une matrice rectangulaire. Cet algorithme n'a pas de lien avec le fenêtrage de Lanczos (utilisé par exemple pour le redimensionnement d'images), si ce n'est que tous les deux tirent leur nom du même inventeur, le physicien et mathématicien hongrois Cornelius Lanczos. (fr) ランチョス法（ランチョスほう、英: Lanczos algorithm）とは、対象となる対称行列を三重対角化する手法。 コルネリウス・ランチョスによって開発された反復計算法である。クリロフ部分空間法の一つ。 (ja) Lanczos 算法是设计的一种直接算法，它由改编而来，用于找出厄米矩阵的各组特征值和特征向量中“最有用的”（趋于极高/极低的）的组，通常（但不一定）远小于。最初指定的方法尽管从原则上将计算效率应该很高，但是由于其数值不稳定而不敷实用。 1970 年，Ojalvo 和 Newman 提出了使该方法在数值上变稳定的方式，并将其应用于承受动态载荷的大型工程结构的求解。实现方式是，采取措施纯化了 Lanczos 向量（即，反复地把每个新生成的向量同所有先前生成的向量一起重新归一化），纯化到任意的准确度即可，先前没有执行这一步，因而产生了一系列被那些联系于最低自然频率的向量严重污染了的向量。 在最初的文章中，这些作者还建议了选择起始向量的方式（即，使用随机数生成器来选择起始向量的每个元素），并提出了一种根据经验确定下来的方法，用来确定向量数量的减少量（即，应选为所需准确特征值数量的约 1.5 倍）。此后不久，Paige 跟进了他们的工作，而 Paige 提供了错误分析。 1988 年，Ojalvo 为该算法制作了更详细的历史记录和有效的特征值误差测试。 (zh) The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an Hermitian matrix, where is often but not necessarily much smaller than . Although computationally efficient in principle, the method as initially formulated was not useful, due to its numerical instability. (en) El algoritmo de Lanczos es un algoritmo iterativo creado por Cornelius Lanczos,este es una adaptación de los métodos iterativos para encontrar los valores propios más útiles y vectores propios de un sistema lineal de dimensión realizando un número de operaciones, , donde es más pequeño que . (es) Algoritma Lanczos adalah algoritma iteratif adaptasi dari metode daya (power method) untuk menemukan nilai dan vektor eigen yang "paling berguna" (umumnya yang tertinggi/terendah) dari sebuah matriks Hermite berukuran , dengan tidak perlu jauh lebih kecil dari . Algoritma ini dirancang oleh pada tahun 1950. Meskipun secara prinsip metode ini efisien dalam aspek komputasi, metode yang dirancang pada awalnya tidak berguna karena sifatnya yang tidak stabil secara numerik. (in) |
| rdfs:label | Lanczos-Verfahren (de) Algoritmo de Lanczos (es) Algoritma Lanczos (in) Algorithme de Lanczos (fr) Lanczos algorithm (en) ランチョス法 (ja) 兰佐斯算法 (zh) |
| owl:sameAs | freebase:Lanczos algorithm yago-res:Lanczos algorithm wikidata:Lanczos algorithm dbpedia-de:Lanczos algorithm dbpedia-es:Lanczos algorithm dbpedia-fr:Lanczos algorithm dbpedia-he:Lanczos algorithm dbpedia-id:Lanczos algorithm dbpedia-ja:Lanczos algorithm dbpedia-zh:Lanczos algorithm https://global.dbpedia.org/id/3PQZV |
| prov:wasDerivedFrom | wikipedia-en:Lanczos_algorithm?oldid=1112826364&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Lanczos_algorithm |
| is dbo:knownFor of | dbr:Cornelius_Lanczos |
| is dbo:wikiPageRedirects of | dbr:Lanczos_iteration dbr:Lanczos_method dbr:Block_Lanczos |
| is dbo:wikiPageWikiLink of | dbr:Energy_minimization dbr:Numerical_linear_algebra dbr:Tridiagonal_matrix dbr:Beresford_Parlett dbr:List_of_numerical_analysis_topics dbr:Segmentation-based_object_categorization dbr:Continued_fraction dbr:Cornelius_Lanczos dbr:SLEPc dbr:Operator_norm dbr:Eigenvalue_algorithm dbr:Eigenvalues_and_eigenvectors dbr:GPUOpen dbr:LOBPCG dbr:Arnoldi_iteration dbr:Light-front_computational_methods dbr:Lis_(linear_algebra_library) dbr:Singular_value_decomposition dbr:Density_matrix_renormalization_group dbr:Henk_van_der_Vorst dbr:Matrix-free_methods dbr:Galahad_library dbr:Lippmann–Schwinger_equation dbr:Principal_component_analysis dbr:Hamiltonian_truncation dbr:Hungarian_Americans dbr:ARPACK dbr:Bidiagonalization dbr:Block_Lanczos_algorithm dbr:Hubbard_model dbr:LBD dbr:Exact_diagonalization dbr:Spectral_clustering dbr:Lanczos_iteration dbr:Lanczos_method dbr:Block_Lanczos |
| is dbp:knownFor of | dbr:Cornelius_Lanczos |
| is foaf:primaryTopic of | wikipedia-en:Lanczos_algorithm |