Tridiagonal matrix algorithm (original) (raw)
Der Thomas-Algorithmus (nach Llewellyn Thomas) oder auch Tridiagonalmatrix-Algorithmus (TDMA) ist eine vereinfachte Form des Gaußschen Eliminationsverfahrens, der zum schnellen Lösen von linearen Gleichungssystemen mit einer Tridiagonalmatrix benutzt wird.
| Property | Value |
|---|---|
| dbo:abstract | Der Thomas-Algorithmus (nach Llewellyn Thomas) oder auch Tridiagonalmatrix-Algorithmus (TDMA) ist eine vereinfachte Form des Gaußschen Eliminationsverfahrens, der zum schnellen Lösen von linearen Gleichungssystemen mit einer Tridiagonalmatrix benutzt wird. (de) El algoritmo para matrices tridiagonales o algoritmo de Thomas (por ) es un algoritmo del álgebra lineal numérica para resolver matrices tridiagonales de forma eficiente. Una matriz tridiagonal se corresponde a un sistema de ecuaciones de la forma donde y .lo que se puede representar matricialmente como Para este tipo de sistemas se puede obtener con este algoritmo una solución con solo operaciones en vez de las que requiere la eliminación gaussiana. El algoritmo primero elimina las y luego usa una sustitución para obtener la solución. Este tipo de matrices suelen salir al plantear discretizaciones por métodos de diferencias finitas, o elementos finitos de problemas unidimensionales. Algunos de los problemas físicos que se plantean así son la Ecuación de Poisson, la ecuación de calor, la ecuación de onda o la interpolación por splines. (es) In numerical linear algebra, the tridiagonal matrix algorithm, also known as the Thomas algorithm (named after Llewellyn Thomas), is a simplified form of Gaussian elimination that can be used to solve tridiagonal systems of equations. A tridiagonal system for n unknowns may be written as where and . For such systems, the solution can be obtained in operations instead of required by Gaussian elimination. A first sweep eliminates the 's, and then an (abbreviated) backward substitution produces the solution. Examples of such matrices commonly arise from the discretization of 1D Poisson equation and natural cubic spline interpolation. Thomas' algorithm is not stable in general, but is so in several special cases, such as when the matrix is diagonally dominant (either by rows or columns) or symmetric positive definite; for a more precise characterization of stability of Thomas' algorithm, see Higham Theorem 9.12. If stability is required in the general case, Gaussian elimination with partial pivoting (GEPP) is recommended instead. (en) Het tridiagonale-matrix-algoritme, kortweg TDMA genoemd, en ook bekend als het Thomas-algoritme, is een numerieke methode om een vierkant stelsel van lineaire vergelijkingen op te lossen dat wordt beschreven door een tridiagonale matrix. Dit is een matrix waarbij de elementen buiten de diagonaal en de twee nevendiagonalen alle gelijk aan nul zijn, zoals in onderstaande matrix. De methode is niets anders dan een toepassing van de Gauss-eliminatiemethode, met als doel de elementen onder de hoofddiagonaal nul te maken, waardoor het stelsel een geschikte vorm krijgt om te worden opgelost door achterwaartse substitutie. (nl) In , l'algoritmo di soluzione dei sistemi tridiagonali, anche conosciuto come algoritmo di Thomas (da ), è una forma più efficiente del metodo di eliminazione di Gauss che può essere usato per la soluzione di sistemi di equazioni nella forma dove la matrice è tridiagonale. Il sistema di equazioni si può scrivere più sinteticamente nella seguente maniera: Dove Questo genere di matrici compare comunemente nella discretizzazione di equazioni di Poisson 1D e nelle interpolazioni con spline. (it) Em álgebra linear, o Algoritmo de Thomas (ou Algoritmo de matriz tridiagonal), é um método algébrico oriundo de uma simplificação da eliminação gaussiana para resolução de sistemas de . Uma matriz tridiagonal é uma matriz quadrada onde apenas os elementos da diagonal principal e as que estão acima e abaixo a ela são não nulas. Quando a matriz é tridiagonal, torna-se um desperdício computacional armazenar os zeros, já que eles nunca serão utilizados para a solução do sistema. Pensando nisso, Llewellyn Thomas propôs um algoritmo que requer um custo computacional inferior aos métodos de eliminação. Este algoritmo ficou conhecido como Algoritmo de Thomas, o qual requer apenas 8n-7 operações, sendo 3(n-1) operações para a fatorização e 5n-4 operações para o procedimento de substituição. (pt) Метод прогонки (англ. tridiagonal matrix algorithm) или алгоритм Томаса (англ. Thomas algorithm) используется для решения систем линейных уравнений вида , где — трёхдиагональная матрица. Представляет собой вариант метода последовательного исключения неизвестных. Метод прогонки был предложен И. М. Гельфандом и О. В. Локуциевским (в 1952 году; опубликовано в 1960 и 1962 годах), а также независимо другими авторами. (ru) 三对角矩阵算法（英語：tridiagonal matrix algorithm），又称为托马斯算法（Thomas algorithm，名称源于英国数学家）是数值线性代数中的一种算法，通过简化形式的高斯消元法求解三对角矩阵。包含n个未知数的三对角方程组可以写成 其中、 。写成矩阵形式则为 高斯消去法在求解一般线性方程组时需要时间复杂度，但对于三对角系统则只需复杂度。 (zh) Метод прогонки, також відомий як алгоритм Томаса, дозволяє розв'язувати СЛАР з Тридіагональною матрицею, і є спрощенням методу Гауса для таких обмежень. Працює за лінійний час. Система має такий вигляд: де та . В матричній формі це записується так: В цілому, метод не є числово стійким, але є таким у декількох випадках, таких як діагонально панівна матриця або додатноозначена матриця. (uk) |
| dbo:wikiPageExternalLink | http://apps.nrbook.com/empanel/index.html%3Fpg=56 https://archive.org/details/elementarynumeri00samu |
| dbo:wikiPageID | 4068264 (xsd:integer) |
| dbo:wikiPageLength | 17625 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117006478 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Numerical_linear_algebra dbr:Tridiagonal_matrix dbr:Dev-C++ dbr:Visual_Basic_for_Applications dbr:Gaussian_elimination dbr:Llewellyn_Thomas dbr:Periodic_boundary_conditions dbr:Numerical_stability dbr:Sherman–Morrison_formula dbc:Numerical_linear_algebra dbr:Block_matrix dbc:Articles_with_example_BASIC_code dbr:Spline_interpolation dbr:Symmetric_positive_definite dbr:Poisson_equation dbr:Poisson_equation_discretized_into_block_tridiagonal dbr:Diagonally_dominant dbr:Partial_pivoting |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Short_description dbt:Wikibooks dbt:Numerical_linear_algebra dbt:CFDWiki |
| dcterms:subject | dbc:Numerical_linear_algebra dbc:Articles_with_example_BASIC_code |
| rdfs:comment | Der Thomas-Algorithmus (nach Llewellyn Thomas) oder auch Tridiagonalmatrix-Algorithmus (TDMA) ist eine vereinfachte Form des Gaußschen Eliminationsverfahrens, der zum schnellen Lösen von linearen Gleichungssystemen mit einer Tridiagonalmatrix benutzt wird. (de) Het tridiagonale-matrix-algoritme, kortweg TDMA genoemd, en ook bekend als het Thomas-algoritme, is een numerieke methode om een vierkant stelsel van lineaire vergelijkingen op te lossen dat wordt beschreven door een tridiagonale matrix. Dit is een matrix waarbij de elementen buiten de diagonaal en de twee nevendiagonalen alle gelijk aan nul zijn, zoals in onderstaande matrix. De methode is niets anders dan een toepassing van de Gauss-eliminatiemethode, met als doel de elementen onder de hoofddiagonaal nul te maken, waardoor het stelsel een geschikte vorm krijgt om te worden opgelost door achterwaartse substitutie. (nl) In , l'algoritmo di soluzione dei sistemi tridiagonali, anche conosciuto come algoritmo di Thomas (da ), è una forma più efficiente del metodo di eliminazione di Gauss che può essere usato per la soluzione di sistemi di equazioni nella forma dove la matrice è tridiagonale. Il sistema di equazioni si può scrivere più sinteticamente nella seguente maniera: Dove Questo genere di matrici compare comunemente nella discretizzazione di equazioni di Poisson 1D e nelle interpolazioni con spline. (it) Метод прогонки (англ. tridiagonal matrix algorithm) или алгоритм Томаса (англ. Thomas algorithm) используется для решения систем линейных уравнений вида , где — трёхдиагональная матрица. Представляет собой вариант метода последовательного исключения неизвестных. Метод прогонки был предложен И. М. Гельфандом и О. В. Локуциевским (в 1952 году; опубликовано в 1960 и 1962 годах), а также независимо другими авторами. (ru) 三对角矩阵算法（英語：tridiagonal matrix algorithm），又称为托马斯算法（Thomas algorithm，名称源于英国数学家）是数值线性代数中的一种算法，通过简化形式的高斯消元法求解三对角矩阵。包含n个未知数的三对角方程组可以写成 其中、 。写成矩阵形式则为 高斯消去法在求解一般线性方程组时需要时间复杂度，但对于三对角系统则只需复杂度。 (zh) Метод прогонки, також відомий як алгоритм Томаса, дозволяє розв'язувати СЛАР з Тридіагональною матрицею, і є спрощенням методу Гауса для таких обмежень. Працює за лінійний час. Система має такий вигляд: де та . В матричній формі це записується так: В цілому, метод не є числово стійким, але є таким у декількох випадках, таких як діагонально панівна матриця або додатноозначена матриця. (uk) El algoritmo para matrices tridiagonales o algoritmo de Thomas (por ) es un algoritmo del álgebra lineal numérica para resolver matrices tridiagonales de forma eficiente. Una matriz tridiagonal se corresponde a un sistema de ecuaciones de la forma donde y .lo que se puede representar matricialmente como Para este tipo de sistemas se puede obtener con este algoritmo una solución con solo operaciones en vez de las que requiere la eliminación gaussiana. El algoritmo primero elimina las y luego usa una sustitución para obtener la solución. (es) In numerical linear algebra, the tridiagonal matrix algorithm, also known as the Thomas algorithm (named after Llewellyn Thomas), is a simplified form of Gaussian elimination that can be used to solve tridiagonal systems of equations. A tridiagonal system for n unknowns may be written as where and . (en) Em álgebra linear, o Algoritmo de Thomas (ou Algoritmo de matriz tridiagonal), é um método algébrico oriundo de uma simplificação da eliminação gaussiana para resolução de sistemas de . Uma matriz tridiagonal é uma matriz quadrada onde apenas os elementos da diagonal principal e as que estão acima e abaixo a ela são não nulas. Quando a matriz é tridiagonal, torna-se um desperdício computacional armazenar os zeros, já que eles nunca serão utilizados para a solução do sistema. (pt) |
| rdfs:label | Thomas-Algorithmus (de) Algoritmo para matrices tridiagonales (es) Algoritmo di soluzione dei sistemi tridiagonali (it) Tridiagonale-matrix-algoritme (nl) Метод прогонки (ru) Tridiagonal matrix algorithm (en) Algoritmo de Thomas (pt) Метод прогонки (uk) 三对角矩阵算法 (zh) |
| owl:sameAs | freebase:Tridiagonal matrix algorithm wikidata:Tridiagonal matrix algorithm dbpedia-de:Tridiagonal matrix algorithm dbpedia-es:Tridiagonal matrix algorithm http://hi.dbpedia.org/resource/त्रिविकर्णिक_आव्यूह_कलनविधि dbpedia-it:Tridiagonal matrix algorithm dbpedia-nl:Tridiagonal matrix algorithm dbpedia-pt:Tridiagonal matrix algorithm dbpedia-ru:Tridiagonal matrix algorithm dbpedia-tr:Tridiagonal matrix algorithm dbpedia-uk:Tridiagonal matrix algorithm dbpedia-zh:Tridiagonal matrix algorithm https://global.dbpedia.org/id/mEnQ |
| prov:wasDerivedFrom | wikipedia-en:Tridiagonal_matrix_algorithm?oldid=1117006478&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Tridiagonal_matrix_algorithm |
| is dbo:wikiPageRedirects of | dbr:Thomas_algorithm dbr:Tridiagonal_linear_equations dbr:Tridiagonal_matrix_algorithm/Derivation |
| is dbo:wikiPageWikiLink of | dbr:Beam_and_Warming_scheme dbr:List_of_algorithms dbr:Tridiagonal_matrix dbr:List_of_numerical_analysis_topics dbr:Computational_methods_for_free_surface_flow dbr:Crank–Nicolson_method dbr:Pidgin_code dbr:TDMA dbr:EAS3 dbr:Alternating-direction_implicit_method dbr:Thomas_algorithm dbr:Rybicki_Press_algorithm dbr:Tridiagonal_linear_equations dbr:Tridiagonal_matrix_algorithm/Derivation |
| is foaf:primaryTopic of | wikipedia-en:Tridiagonal_matrix_algorithm |