Power iteration (original) (raw)
En mathématiques, la méthode de la puissance itérée ou méthode des puissances est un algorithme pour calculer la valeur propre dominante d'une matrice. Bien que cet algorithme soit simple à mettre en œuvre et populaire, il ne converge pas très vite.
| Property | Value |
|---|---|
| dbo:abstract | Die Potenzmethode, Vektoriteration oder Von-Mises-Iteration (nach Richard von Mises) ist ein numerisches Verfahren zur Berechnung des betragsgrößten Eigenwertes und des dazugehörigen Eigenvektors einer Matrix. Der Name kommt daher, dass Matrixpotenzen gebildet werden, wesentlicher Aufwand sind also Matrix-Vektor-Produkte. Deswegen ist das Verfahren insbesondere für dünnbesetzte Matrizen geeignet. Eine direkte Verallgemeinerung zur Berechnung mehrerer betragsgrößter Eigenwerte dünnbesetzter Matrizen ist die Unterraumiteration. Die Potenzmethode lässt sich als nicht-optimales Krylow-Unterraum-Verfahren interpretieren, welches nur den jeweils letzten berechneten Vektor zur Eigenwertnäherung verwendet. Die Potenzmethode ist hinsichtlich der Konvergenzgeschwindigkeit den anderen Krylow-Raum-Verfahren, wie etwa dem Verfahren von Lanczos oder dem Verfahren von Arnoldi unterlegen. Dafür schneidet die Potenzmethode hinsichtlich der Stabilitätsanalyse besser ab. (de) En análisis numérico, el método de las potencias es un método iterativo que calcula sucesivas aproximaciones a los autovectores y autovalores de una matriz. El método se usa principalmente para calcular el autovector de mayor autovalor en matrices grandes. En particular, Google lo emplea para calcular el PageRank de los documentos en su motor de búsqueda. Para aplicar el método de las potencias se supone que la matriz A de n x n tiene n valores característicos con un conjunto asociado de vectores característicos linealmente independientes . Es más, se supone que A tiene exactamente un valor característico cuya magnitud es la mayor, por lo que . El método converge lentamente y solo puede determinar uno de los autovectores de la matriz. (es) In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix , the algorithm will produce a number , which is the greatest (in absolute value) eigenvalue of , and a nonzero vector , which is a corresponding eigenvector of , that is, .The algorithm is also known as the Von Mises iteration. Power iteration is a very simple algorithm, but it may converge slowly. The most time-consuming operation of the algorithm is the multiplication of matrix by a vector, so it is effective for a very large sparse matrix with appropriate implementation. (en) En mathématiques, la méthode de la puissance itérée ou méthode des puissances est un algorithme pour calculer la valeur propre dominante d'une matrice. Bien que cet algorithme soit simple à mettre en œuvre et populaire, il ne converge pas très vite. (fr) Il metodo delle potenze è un semplice metodo iterativo per il calcolo approssimato dell'autovalore di modulo massimo di una matrice e il corrispondente autovettore. (it) べき乗法とはある行列の固有値のうち、絶対値最大のものを求める手法の総称であり、いくつかのバリエーションがある。累乗法とも呼ばれる。 典型的には、与えられた行列に対して、適当な初期ベクトルから始めて、逐次 を計算することで、がの絶対値最大の固有値に属する固有ベクトルの方向に漸近していくことを利用し、 により絶対値最大の固有値を得る。ただしベクトル列が定ベクトルに収束していくわけではないことに注意する。 また、べき乗法に類似した、絶対値最小の固有値を求める方法として逆べき乗法がある。 (ja) Em matemática, o método das potências é um algoritmo para calcular autovalores: dada uma matriz A, o algoritmo irá produzir um número λ (o autovalor) e um vetor v não nulo (o autovetor), tal que Av = λv. O algoritmo também é conhecido como a iteração de Von Mises. O método da potência é um algoritmo muito simples. Ele não computa a decomposição matricial, e portanto pode ser usada quando A é uma grande matriz esparsa. No entanto, ele irá encontrar apenas um autovalor (aquele com o maior módulo) e poderá convergir lentamente. (pt) Степенной метод, или метод степенных итераций, — итерационный алгоритм поиска собственного значения с максимальной абсолютной величиной и одного из соответствующих собственных векторов для произвольной матрицы. Алгоритм прост и сходится со скоростью геометрической прогрессии, если все максимальные по модулю собственные значения совпадают, в противном случае сходимости нет. При близких по модулю собственных значениях сходимость может оказаться медленной. В силу того, что алгоритм сводится к последовательному умножению заданной матрицы на вектор, при правильной реализации он хорошо работает для больших разреженных матриц. Алгоритм предложен в 1929 году Рихардом фон Мизесом и Хильдой Гейрингер. (ru) Степеневий метод або метод степеневих ітерацій — ітераційний алгоритм пошуку власного значення з найбільшою абсолютною величиною і одного з відповідних власних векторів для довільної матриці. Алгоритм простий і збігається зі швидкістю геометричної прогресії якщо всі найбільші за модулем власні значення збігаються, в іншому випадку збіжності немає. За близьких за модулем власних значень збіжність може виявитися повільною. Оскільки алгоритм зводиться до послідовного множення заданої матриці на вектор, за правильної реалізації він добре працює для великих розріджених матриць. Алгоритм запропонували 1929 року Ріхард фон Мізес і Гільда Гейрінгер. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Animation_of_the_Power_Iteration_Algorithm.gif?width=300 |
| dbo:wikiPageID | 5975550 (xsd:integer) |
| dbo:wikiPageLength | 12074 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116811946 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Almost_surely dbr:Inverse_iteration dbr:Mathematics dbr:Matrix_(mathematics) dbr:Eigenvalue dbr:Eigenvalue_algorithm dbr:Eigenvector dbr:Google dbr:Condition_number dbr:LOBPCG dbr:Arnoldi_iteration dbr:Computational_problem dbr:Krylov_subspace dbr:Matrix-free_methods dbr:Twitter dbr:PageRank dbr:Rayleigh_quotient dbr:Recurrence_relation dbc:Numerical_linear_algebra dbc:Articles_with_example_Python_(programming_language)_code dbr:Rayleigh_quotient_iteration dbr:Sparse_matrix dbr:Spectral_radius dbr:Diagonalizable dbr:Jordan_canonical_form dbr:Lanczos_iteration dbr:Geometric_sequence dbr:0.5,_0.5],_[0.2,_0.8 dbr:File:Animation_of_the_Power_Iteration_Algorithm.gif |
| dbp:wikiPageUsesTemplate | dbt:Clarify dbt:Reflist dbt:Use_dmy_dates dbt:Numerical_linear_algebra |
| dct:subject | dbc:Numerical_linear_algebra dbc:Articles_with_example_Python_(programming_language)_code |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software |
| rdfs:comment | En mathématiques, la méthode de la puissance itérée ou méthode des puissances est un algorithme pour calculer la valeur propre dominante d'une matrice. Bien que cet algorithme soit simple à mettre en œuvre et populaire, il ne converge pas très vite. (fr) Il metodo delle potenze è un semplice metodo iterativo per il calcolo approssimato dell'autovalore di modulo massimo di una matrice e il corrispondente autovettore. (it) べき乗法とはある行列の固有値のうち、絶対値最大のものを求める手法の総称であり、いくつかのバリエーションがある。累乗法とも呼ばれる。 典型的には、与えられた行列に対して、適当な初期ベクトルから始めて、逐次 を計算することで、がの絶対値最大の固有値に属する固有ベクトルの方向に漸近していくことを利用し、 により絶対値最大の固有値を得る。ただしベクトル列が定ベクトルに収束していくわけではないことに注意する。 また、べき乗法に類似した、絶対値最小の固有値を求める方法として逆べき乗法がある。 (ja) Em matemática, o método das potências é um algoritmo para calcular autovalores: dada uma matriz A, o algoritmo irá produzir um número λ (o autovalor) e um vetor v não nulo (o autovetor), tal que Av = λv. O algoritmo também é conhecido como a iteração de Von Mises. O método da potência é um algoritmo muito simples. Ele não computa a decomposição matricial, e portanto pode ser usada quando A é uma grande matriz esparsa. No entanto, ele irá encontrar apenas um autovalor (aquele com o maior módulo) e poderá convergir lentamente. (pt) Die Potenzmethode, Vektoriteration oder Von-Mises-Iteration (nach Richard von Mises) ist ein numerisches Verfahren zur Berechnung des betragsgrößten Eigenwertes und des dazugehörigen Eigenvektors einer Matrix. Der Name kommt daher, dass Matrixpotenzen gebildet werden, wesentlicher Aufwand sind also Matrix-Vektor-Produkte. Deswegen ist das Verfahren insbesondere für dünnbesetzte Matrizen geeignet. Eine direkte Verallgemeinerung zur Berechnung mehrerer betragsgrößter Eigenwerte dünnbesetzter Matrizen ist die Unterraumiteration. (de) En análisis numérico, el método de las potencias es un método iterativo que calcula sucesivas aproximaciones a los autovectores y autovalores de una matriz. El método se usa principalmente para calcular el autovector de mayor autovalor en matrices grandes. En particular, Google lo emplea para calcular el PageRank de los documentos en su motor de búsqueda. (es) In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix , the algorithm will produce a number , which is the greatest (in absolute value) eigenvalue of , and a nonzero vector , which is a corresponding eigenvector of , that is, .The algorithm is also known as the Von Mises iteration. (en) Степенной метод, или метод степенных итераций, — итерационный алгоритм поиска собственного значения с максимальной абсолютной величиной и одного из соответствующих собственных векторов для произвольной матрицы. Алгоритм предложен в 1929 году Рихардом фон Мизесом и Хильдой Гейрингер. (ru) Степеневий метод або метод степеневих ітерацій — ітераційний алгоритм пошуку власного значення з найбільшою абсолютною величиною і одного з відповідних власних векторів для довільної матриці. Алгоритм простий і збігається зі швидкістю геометричної прогресії якщо всі найбільші за модулем власні значення збігаються, в іншому випадку збіжності немає. За близьких за модулем власних значень збіжність може виявитися повільною. Оскільки алгоритм зводиться до послідовного множення заданої матриці на вектор, за правильної реалізації він добре працює для великих розріджених матриць. (uk) |
| rdfs:label | Potenzmethode (de) Método de las potencias (es) Méthode de la puissance itérée (fr) Metodo delle potenze (it) べき乗法 (ja) Power iteration (en) Método das potências (pt) Степенной метод (ru) Степеневий метод (uk) |
| owl:sameAs | freebase:Power iteration yago-res:Power iteration wikidata:Power iteration dbpedia-de:Power iteration dbpedia-es:Power iteration dbpedia-fr:Power iteration dbpedia-he:Power iteration dbpedia-it:Power iteration dbpedia-ja:Power iteration dbpedia-pt:Power iteration dbpedia-ru:Power iteration dbpedia-uk:Power iteration https://global.dbpedia.org/id/SERm |
| prov:wasDerivedFrom | wikipedia-en:Power_iteration?oldid=1116811946&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Animation_of_the_Power_Iteration_Algorithm.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Power_iteration |
| is dbo:wikiPageRedirects of | dbr:Von_Mises_iteration dbr:Power_method |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Inverse_iteration dbr:List_of_numerical_analysis_topics dbr:Preconditioner dbr:Operator_norm dbr:Eigendecomposition_of_a_matrix dbr:Eigenvalue_algorithm dbr:Arnoldi_iteration dbr:Computational_physics dbr:Krylov_subspace dbr:Lanczos_algorithm dbr:PageRank dbr:Centrality dbr:Principal_component_analysis dbr:QR_algorithm dbr:Eigenvector_centrality dbr:Rayleigh_quotient_iteration dbr:The_Computer_Language_Benchmarks_Game dbr:Spectral_clustering dbr:Von_Mises_iteration dbr:Power_method |
| is foaf:primaryTopic of | wikipedia-en:Power_iteration |
