Levinson recursion (original) (raw)
레빈슨 재귀 알고리즘(Levinson recursion, 또는 Levinson-Durbin recursion)은 선형 대수학에서 퇴플리츠 행렬이 관여하는 방정식에 대한 해를 재귀적으로 계산하는 절차이다. 이 알고리즘은 의 시간복잡도에서 실행되며, 에서 실행되는 가우스-조르단 소거법 보다 더 강하게 개선된 절차이다.
| Property | Value |
|---|---|
| dbo:abstract | El algoritmo de Levinson o de Levinson-Durbin es un algoritmo del álgebra lineal para calcular en forma recursiva la solución de una ecuación que involucra una matriz de Toeplitz. El costo computacional es de Θ(n2), una mejora considerable frente a la eliminación de Gauss-Jordan, cuyo costo es de Θ(n3). Hay algoritmos nuevos, llamados asintóticamente rápidos o a menudo algoritmos de Toeplitz superrápidos, que pueden resolver con un costo de Θ(n logpn) para varios p (por ejemplo, para p = 2, p = 3). La recursión de Levinson sigue siendo popular por distintas razones; por un lado, es relativamente simple de comprender en comparación; por otro lado, puede ser más rápida que un algoritmo superrápido para n pequeño (normalmente para n < 256 [1] Archivado el 5 de septiembre de 2006 en Wayback Machine.). El algoritmo de Levinson-Durbin fue propuesto por primera vez por en 1947, mejorado por J. Durbin en 1960 y más tarde mejorado a 4n2 y luego a 3n2 multiplicaciones por W. F. Trench y S. Zohar, respectivamente. Otros métodos para procesar datos incluyen la descomposición de Schur y la descomposición de Cholesky. En comparación a estos, la recursión de Levinson (particularmente la recursión de Split-Levinson) tiende a ser más rápida computacionalmente, aunque más sensible a imperfecciones computacionales como errores de redondeo. (es) Levinson recursion or Levinson–Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in Θ(n2) time, which is a strong improvement over Gauss–Jordan elimination, which runs in Θ(n3). The Levinson–Durbin algorithm was proposed first by Norman Levinson in 1947, improved by James Durbin in 1960, and subsequently improved to 4n2 and then 3n2 multiplications by W. F. Trench and S. Zohar, respectively. Other methods to process data include Schur decomposition and Cholesky decomposition. In comparison to these, Levinson recursion (particularly split Levinson recursion) tends to be faster computationally, but more sensitive to computational inaccuracies like round-off errors. The Bareiss algorithm for Toeplitz matrices (not to be confused with the general Bareiss algorithm) runs about as fast as Levinson recursion, but it uses O(n2) space, whereas Levinson recursion uses only O(n) space. The Bareiss algorithm, though, is numerically stable, whereas Levinson recursion is at best only weakly stable (i.e. it exhibits numerical stability for well-conditioned linear systems). Newer algorithms, called asymptotically fast or sometimes superfast Toeplitz algorithms, can solve in Θ(n logpn) for various p (e.g. p = 2, p = 3 ). Levinson recursion remains popular for several reasons; for one, it is relatively easy to understand in comparison; for another, it can be faster than a superfast algorithm for small n (usually n < 256). (en) 레빈슨 재귀 알고리즘(Levinson recursion, 또는 Levinson-Durbin recursion)은 선형 대수학에서 퇴플리츠 행렬이 관여하는 방정식에 대한 해를 재귀적으로 계산하는 절차이다. 이 알고리즘은 의 시간복잡도에서 실행되며, 에서 실행되는 가우스-조르단 소거법 보다 더 강하게 개선된 절차이다. (ko) L'algoritmo di Levinson-Durbin, in algebra lineare, serve per calcolare, con metodo ricorsivo, la soluzione di un'equazione che coinvolge una matrice di Toeplitz. L'algoritmo viene eseguito in passi, il che rappresenta un forte miglioramento rispetto al Metodo di eliminazione di Gauss, il quale richiede passaggi. L'algoritmo Levinson–Durbin fu proposto prima da Norman Levinson, nel 1947, e migliorato da James Durbin nel 1960; successivamente fu ulteriormente migliorato, portandolo da fino a moltiplicazioni, da W. F. Trench e S. Zohar, rispettivamente. Altri metodi per elaborare i dati, includono la decomposizione di Schur e la decomposizione di Cholesky. In confronto a questi, la ricorsione di Levinson (in particolare la ricorsione di Levinson suddivisa) tende a essere più veloce dal punto di vista computazionale, ma più sensibile a inesattezze computazionali come gli errori di arrotondamento. L'algoritmo di Bareiss per le matrici di Toeplitz (da non confondere con l'algoritmo di Bareiss generale) è veloce quanto la ricorsione di Levinson-Durbin, ma utilizza passaggi, mentre la ricorsione di Levinson-Durbin richiede solo passaggi. L'algoritmo di Bareiss, tuttavia, è numericamente stabile, mentre la ricorsione di Levinson-Durbin, nella migliore delle ipotesi, è solo debolmente stabile (cioè mostra stabilità numerica per sistemi lineari ben condizionati). Gli algoritmi più recenti, chiamati algoritmi di Toeplitz asintoticamente veloci o, in alcuni testi, superveloci, possono risolvere il problema in per vari (es. , ). La ricorsione di Levinson-Durbin rimane popolare per diversi motivi; primo, è relativamente facile da comprendere; inoltre, può essere più veloce di un algoritmo superveloce per piccoli (di solito ). (it) |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20060921204908/http:/sep.stanford.edu/oldreports/fgdp2/fgdp_07.pdf http://dspace.mit.edu/bitstream/1721.1/4954/1/RLE-TR-538-20174000.pdf http://scitation.aip.org/getabs/servlet/GetabsServlet%3Fprog=normal&id=SJNAAM000030000005001498000001&idtype=cvips&gifs=yes http://lib.tkk.fi/Diss/2004/isbn9512269473/isbn9512269473.pdf https://doi.org/10.1137/0906025 http://apps.nrbook.com/empanel/index.html%3Fpg=96 |
| dbo:wikiPageID | 219847 (xsd:integer) |
| dbo:wikiPageLength | 17988 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1108404650 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Richard_P._Brent dbr:Vector_space dbr:Symmetric_matrix dbr:Condition_number dbr:Linear_algebra dbr:Cholesky_decomposition dbr:Gauss–Jordan_elimination dbr:Numerical_stability dbc:Matrices dbr:Linear_prediction dbr:Schur_decomposition dbc:Numerical_analysis dbr:Bareiss_algorithm dbr:Norman_Levinson dbr:Recursion dbr:James_Durbin dbr:Big_O_notation dbr:Block_matrix dbr:System_analysis dbr:Toeplitz_matrix dbr:Autoregressive_model dbr:Society_for_Industrial_and_Applied_Mathematics dbr:Round-off_error dbr:SIAM_Journal_on_Numerical_Analysis dbr:SIAM_Journal_on_Matrix_Analysis_and_Applications dbr:Split_Levinson_recursion |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_journal dbt:Math dbt:Reflist |
| dct:subject | dbc:Matrices dbc:Numerical_analysis |
| gold:hypernym | dbr:Procedure |
| rdf:type | dbo:AnatomicalStructure yago:WikicatMatrices yago:Abstraction100002137 yago:Arrangement107938773 yago:Array107939382 yago:Group100031264 yago:Matrix108267640 |
| rdfs:comment | 레빈슨 재귀 알고리즘(Levinson recursion, 또는 Levinson-Durbin recursion)은 선형 대수학에서 퇴플리츠 행렬이 관여하는 방정식에 대한 해를 재귀적으로 계산하는 절차이다. 이 알고리즘은 의 시간복잡도에서 실행되며, 에서 실행되는 가우스-조르단 소거법 보다 더 강하게 개선된 절차이다. (ko) El algoritmo de Levinson o de Levinson-Durbin es un algoritmo del álgebra lineal para calcular en forma recursiva la solución de una ecuación que involucra una matriz de Toeplitz. El costo computacional es de Θ(n2), una mejora considerable frente a la eliminación de Gauss-Jordan, cuyo costo es de Θ(n3). El algoritmo de Levinson-Durbin fue propuesto por primera vez por en 1947, mejorado por J. Durbin en 1960 y más tarde mejorado a 4n2 y luego a 3n2 multiplicaciones por W. F. Trench y S. Zohar, respectivamente. (es) Levinson recursion or Levinson–Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in Θ(n2) time, which is a strong improvement over Gauss–Jordan elimination, which runs in Θ(n3). The Levinson–Durbin algorithm was proposed first by Norman Levinson in 1947, improved by James Durbin in 1960, and subsequently improved to 4n2 and then 3n2 multiplications by W. F. Trench and S. Zohar, respectively. (en) L'algoritmo di Levinson-Durbin, in algebra lineare, serve per calcolare, con metodo ricorsivo, la soluzione di un'equazione che coinvolge una matrice di Toeplitz. L'algoritmo viene eseguito in passi, il che rappresenta un forte miglioramento rispetto al Metodo di eliminazione di Gauss, il quale richiede passaggi. L'algoritmo Levinson–Durbin fu proposto prima da Norman Levinson, nel 1947, e migliorato da James Durbin nel 1960; successivamente fu ulteriormente migliorato, portandolo da fino a moltiplicazioni, da W. F. Trench e S. Zohar, rispettivamente. (it) |
| rdfs:label | Algoritmo de Levinson (es) Algoritmo di Levinson-Durbin (it) Levinson recursion (en) 레빈슨 재귀 알고리즘 (ko) |
| owl:sameAs | freebase:Levinson recursion yago-res:Levinson recursion wikidata:Levinson recursion dbpedia-es:Levinson recursion dbpedia-it:Levinson recursion dbpedia-ko:Levinson recursion https://global.dbpedia.org/id/EBxf |
| prov:wasDerivedFrom | wikipedia-en:Levinson_recursion?oldid=1108404650&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Levinson_recursion |
| is dbo:knownFor of | dbr:Norman_Levinson dbr:James_Durbin |
| is dbo:wikiPageRedirects of | dbr:Block_Levinson_algorithm dbr:Block_Levinson_recursion dbr:Levinson_Recursion dbr:Levinson's_method dbr:Levinson-Durbin dbr:Levinson-Durbin_algorithm dbr:Levinson-Durbin_recursion dbr:Levinson_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Deconvolution dbr:List_of_numerical_analysis_topics dbr:Block_Levinson_algorithm dbr:Block_Levinson_recursion dbr:Linear_prediction dbr:Norman_Levinson dbr:List_of_Massachusetts_Institute_of_Technology_alumni dbr:James_Durbin dbr:Code-excited_linear_prediction dbr:Toeplitz_matrix dbr:Wiener_filter dbr:Autoregressive_model dbr:Minimum_mean_square_error dbr:System_of_linear_equations dbr:Levinson_Recursion dbr:Levinson's_method dbr:Levinson-Durbin dbr:Levinson-Durbin_algorithm dbr:Levinson-Durbin_recursion dbr:Levinson_algorithm |
| is dbp:knownFor of | dbr:Norman_Levinson dbr:James_Durbin |
| is foaf:primaryTopic of | wikipedia-en:Levinson_recursion |