QR algorithm (original) (raw)
QR algoritmus (také QR transformace) je numerická metoda pro výpočet vlastních čísel obecné regulární matice založená na principu QR rozkladu. Výhodou algoritmu je numerická stabilita.
.gif?width=300)
| Property | Value |
|---|---|
| dbo:abstract | QR algoritmus (také QR transformace) je numerická metoda pro výpočet vlastních čísel obecné regulární matice založená na principu QR rozkladu. Výhodou algoritmu je numerická stabilita. (cs) Der QR-Algorithmus ist ein numerisches Verfahren zur Berechnung aller Eigenwerte und eventuell der Eigenvektoren einer quadratischen Matrix. Das auch QR-Verfahren oder QR-Iteration genannte Verfahren basiert auf der QR-Zerlegung und wurde in den Jahren 1961 und 1962 unabhängig voneinander von John G. F. Francis und Wera Nikolajewna Kublanowskaja eingeführt. Ein Vorläufer war der LR-Algorithmus von Heinz Rutishauser (1958), der aber weniger stabil ist und auf der LR-Zerlegung basiert. Oft konvergieren die Iterierten aus dem QR-Algorithmus gegen die Schur-Form der Matrix. Das originale Verfahren ist recht aufwendig und damit – selbst auf heutigen Rechnern – für Matrizen mit hunderttausenden Zeilen und Spalten nicht praktikabel. Abgeleitete Varianten wie das Multishift-Verfahren von Z. Bai und James Demmel 1989 und die numerisch stabilere Variante von K. Braman, R. Byers und R. Mathias 2002 haben praktische Laufzeiten, die kubisch in der Größe der Matrix sind. Letzteres Verfahren ist in der numerischen Softwarebibliothek LAPACK implementiert, die wiederum in vielen Computeralgebrasystemen (CAS) für die numerischen Matrixalgorithmen verwendet wird. (de) El algoritmo QR es un algoritmo usado en álgebra lineal para el cálculo de valores y vectores propios de una matriz. Se basa en la descomposición QR, desarrollada en la década de 1950 por (Reino Unido) y Vera N. Kublánovskaya (URSS), de forma independiente. Esto es, usa la oportunidad de representar cualquier matriz regular H en forma de producto de de una matriz ortogonal Q por una matriz triangular superior R. La idea básica es usar dicha descomposición para reescribir la matriz como el producto de una matriz ortogonal y una matriz triangular superior. Si se multiplica a la inversa, la matriz resultante sigue teniendo los mismos valores propios e iterando se puede llegar a una matriz que los contenga en la diagonal. (es) In numerical linear algebra, the QR algorithm or QR iteration is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR algorithm was developed in the late 1950s by John G. F. Francis and by Vera N. Kublanovskaya, working independently. The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the reverse order, and iterate. (en) QR法（きゅーあーるほう、QR algorithm）は、行列Aの固有値を求める方法の一つで行列のQR分解を利用するものである。QR法は数値解析的に安定なアルゴリズムである。 (ja) Il metodo QR è il metodo più utilizzato per il calcolo degli autovalori e degli autovettori di una matrice diagonalizzabile. Il metodo è molto complesso sia nella descrizione che nell'implementazione, ma il principio su cui si basa, ovvero la fattorizzazione QR, è molto semplice. (it) QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В. Н. Кублановской и Дж. Фрэнсисом. (ru) QR-алгоритм — це чисельний метод у лінійній алгебрі, призначений для розв'язування повної задачі власних значень, тобто відшукання всіх власних значень і власних векторів матриці. Розробили в кінці 1950-х років незалежно В. М. Кублановська і . (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/QR_and_LR_visualizati...ixed_points_(corrected).gif?width=300 |
| dbo:wikiPageExternalLink | http://www-users.math.umn.edu/~olver/aims_/qr.pdf https://github.com/nom-de-guerre/Matrices https://web.archive.org/web/20081209042103/http:/math.fullerton.edu/mathews/n2003/QRMethodMod.html http://www.netlib.org/lapack/double/dbdsqr.f http://www.netlib.org/lapack/double/dgesvd.f |
| dbo:wikiPageID | 594072 (xsd:integer) |
| dbo:wikiPageLength | 16226 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119722889 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Numerical_linear_algebra dbr:Tridiagonal_matrix dbr:Peter_J._Olver dbr:Charles_F._Van_Loan dbr:Power_iteration dbr:Matrix_(mathematics) dbr:Symmetric_matrix dbr:Eigenbasis dbr:Eigendecomposition_of_a_matrix dbr:Eigenvalue_algorithm dbr:Eigenvalues_and_eigenvectors dbr:Ellipse dbr:Ellipsoid dbr:Gene_H._Golub dbr:LU_decomposition dbr:Similar_matrix dbr:Singular_value_decomposition dbr:Computable_analysis dbr:Householder_transformation dbr:Numerical_stability dbr:John_G._F._Francis dbr:Alexander_Aitken dbr:ETH_Zurich dbr:Eduard_Stiefel dbr:Fixed-point_iteration dbr:Fixed_point_(mathematics) dbr:Gershgorin_circle_theorem dbr:QR_decomposition dbr:Heinz_Rutishauser dbc:Numerical_linear_algebra dbr:LAPACK dbr:Schur_form dbr:Orthogonal_matrix dbr:Semi-major_and_semi-minor_axes dbr:Triangular_matrix dbr:Hessenberg_form dbr:Singular_values dbr:Vera_N._Kublanovskaya dbr:File:QR_and_LR_visualization_illustrating_fixed_points_(corrected).gif dbr:File:Qr_lr_eigenvalue_clash.gif |
| dbp:title | Eigenvalue problem (en) |
| dbp:urlname | eigenvalueproblem (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Clarify dbt:Harv dbt:Harvtxt dbt:Reflist dbt:Short_description dbt:PlanetMath dbt:Numerical_linear_algebra |
| dcterms:subject | dbc:Numerical_linear_algebra |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software |
| rdfs:comment | QR algoritmus (také QR transformace) je numerická metoda pro výpočet vlastních čísel obecné regulární matice založená na principu QR rozkladu. Výhodou algoritmu je numerická stabilita. (cs) El algoritmo QR es un algoritmo usado en álgebra lineal para el cálculo de valores y vectores propios de una matriz. Se basa en la descomposición QR, desarrollada en la década de 1950 por (Reino Unido) y Vera N. Kublánovskaya (URSS), de forma independiente. Esto es, usa la oportunidad de representar cualquier matriz regular H en forma de producto de de una matriz ortogonal Q por una matriz triangular superior R. La idea básica es usar dicha descomposición para reescribir la matriz como el producto de una matriz ortogonal y una matriz triangular superior. Si se multiplica a la inversa, la matriz resultante sigue teniendo los mismos valores propios e iterando se puede llegar a una matriz que los contenga en la diagonal. (es) In numerical linear algebra, the QR algorithm or QR iteration is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR algorithm was developed in the late 1950s by John G. F. Francis and by Vera N. Kublanovskaya, working independently. The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the reverse order, and iterate. (en) QR法（きゅーあーるほう、QR algorithm）は、行列Aの固有値を求める方法の一つで行列のQR分解を利用するものである。QR法は数値解析的に安定なアルゴリズムである。 (ja) Il metodo QR è il metodo più utilizzato per il calcolo degli autovalori e degli autovettori di una matrice diagonalizzabile. Il metodo è molto complesso sia nella descrizione che nell'implementazione, ma il principio su cui si basa, ovvero la fattorizzazione QR, è molto semplice. (it) QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В. Н. Кублановской и Дж. Фрэнсисом. (ru) QR-алгоритм — це чисельний метод у лінійній алгебрі, призначений для розв'язування повної задачі власних значень, тобто відшукання всіх власних значень і власних векторів матриці. Розробили в кінці 1950-х років незалежно В. М. Кублановська і . (uk) Der QR-Algorithmus ist ein numerisches Verfahren zur Berechnung aller Eigenwerte und eventuell der Eigenvektoren einer quadratischen Matrix. Das auch QR-Verfahren oder QR-Iteration genannte Verfahren basiert auf der QR-Zerlegung und wurde in den Jahren 1961 und 1962 unabhängig voneinander von John G. F. Francis und Wera Nikolajewna Kublanowskaja eingeführt. Ein Vorläufer war der LR-Algorithmus von Heinz Rutishauser (1958), der aber weniger stabil ist und auf der LR-Zerlegung basiert. Oft konvergieren die Iterierten aus dem QR-Algorithmus gegen die Schur-Form der Matrix. Das originale Verfahren ist recht aufwendig und damit – selbst auf heutigen Rechnern – für Matrizen mit hunderttausenden Zeilen und Spalten nicht praktikabel. (de) |
| rdfs:label | QR algoritmus (cs) QR-Algorithmus (de) Algoritmo QR (es) Metodo QR (it) QR法 (ja) QR algorithm (en) QR-алгоритм (ru) QR-алгоритм (uk) |
| owl:sameAs | freebase:QR algorithm wikidata:QR algorithm dbpedia-cs:QR algorithm dbpedia-de:QR algorithm dbpedia-es:QR algorithm dbpedia-fi:QR algorithm dbpedia-he:QR algorithm dbpedia-it:QR algorithm dbpedia-ja:QR algorithm dbpedia-ru:QR algorithm dbpedia-uk:QR algorithm https://global.dbpedia.org/id/4CVsM |
| prov:wasDerivedFrom | wikipedia-en:QR_algorithm?oldid=1119722889&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/QR_and_LR_visualizati...strating_fixed_points_(corrected).gif wiki-commons:Special:FilePath/Qr_lr_eigenvalue_clash.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:QR_algorithm |
| is dbo:knownFor of | dbr:John_G._F._Francis |
| is dbo:wikiPageDisambiguates of | dbr:QR |
| is dbo:wikiPageRedirects of | dbr:Francis_algorithm dbr:QR_iteration dbr:QR_method dbr:Bulge_chasing |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Numerical_linear_algebra dbr:Beresford_Parlett dbr:List_of_inventions_and_discoveries_by_women dbr:List_of_multiple_discoveries dbr:List_of_numerical_analysis_topics dbr:Segmentation-based_object_categorization dbr:Timeline_of_algorithms dbr:Timeline_of_mathematics dbr:Eigendecomposition_of_a_matrix dbr:Eigenvalue_algorithm dbr:Eigenvalues_and_eigenvectors dbr:Gauss–Legendre_quadrature dbr:Arnoldi_iteration dbr:Singular_value_decomposition dbr:Householder_transformation dbr:Matrix_pencil dbr:William_B._Gragg dbr:Divide-and-conquer_eigenvalue_algorithm dbr:John_G._F._Francis dbr:Lanczos_algorithm dbr:Schur_decomposition dbr:Bartels–Stewart_algorithm dbr:QR dbr:QR_decomposition dbr:Bidiagonal_matrix dbr:Hessenberg_matrix dbr:Christian_Reinsch dbr:Sylvester_equation dbr:Vera_Kublanovskaya dbr:Francis_algorithm dbr:QR_iteration dbr:QR_method dbr:Bulge_chasing |
| is dbp:knownFor of | dbr:John_G._F._Francis |
| is foaf:primaryTopic of | wikipedia-en:QR_algorithm |
