Conjugate gradient method (original) (raw)

About DBpedia

共役勾配法（きょうやくこうばいほう、英: conjugate gradient method、CG法とも呼ばれる）は対称正定値行列を係数とする連立一次方程式を解くためのアルゴリズムである。反復法として利用され、コレスキー分解のような直接法では大きすぎて取り扱えない、大規模な疎行列を解くために利用される。そのような問題は偏微分方程式などを数値的に解く際に常に現れる。 共役勾配法は、エネルギー最小化などの最適化問題を解くために用いることもできる。 は、共役勾配法の非対称問題への拡張である。また、非線形問題を解くために、さまざまな非線形共役勾配法が提案されている。

thumbnail

Property Value
dbo:abstract In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems. The conjugate gradient method can also be used to solve unconstrained optimization problems such as energy minimization. It is commonly attributed to Magnus Hestenes and Eduard Stiefel, who programmed it on the Z4, and extensively researched it. The biconjugate gradient method provides a generalization to non-symmetric matrices. Various nonlinear conjugate gradient methods seek minima of nonlinear optimization problems. (en) Das CG-Verfahren (von engl. conjugate gradients oder auch Verfahren der konjugierten Gradienten) ist eine effiziente numerische Methode zur Lösung von großen linearen Gleichungssystemen der Form mit symmetrischer, positiv definiter Systemmatrix . Das Verfahren liefert, in exakter Arithmetik, nach spätestens Schritten die exakte Lösung, wobei die Größe der quadratischen Matrix ist. Insbesondere ist es aber als iteratives Verfahren interessant, da der Fehler monoton fällt. Das CG-Verfahren kann in die Klasse der Krylow-Unterraum-Verfahren eingeordnet werden. Es wurde zuerst 1952 von Eduard Stiefel und Magnus Hestenes vorgeschlagen. Ein für bestimmte Gleichungssysteme äquivalentes Verfahren schlug auch Cornelius Lanczos Anfang der 1950er Jahre mit dem Lanczos-Verfahren vor. (de) En matemática, el método del gradiente conjugado es un algoritmo para resolver numéricamente los sistemas de ecuaciones lineales cuyas matrices son simétricas y definidas positivas. Es un método iterativo, así que se puede aplicar a los sistemas dispersos que son demasiado grandes para ser tratados por métodos directos como la descomposición de Cholesky. Tales sistemas surgen frecuentemente cuando se resuelve numéricamente las ecuaciones en derivadas parciales. El método del gradiente conjugado se puede utilizar también para resolver los problemas de optimización sin restricciones como la . El proporciona una generalización para matrices no simétricas. Varios busca los mínimos de las ecuaciones no lineales. (es) En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d'équations linéaires dont la matrice est symétrique définie positive. Cette méthode, imaginée en 1950 simultanément par Cornelius Lanczos, Eduard Stiefel et Magnus Hestenes, est une méthode itérative qui converge en un nombre fini d'itérations (au plus égal à la dimension du système linéaire). Toutefois, son grand intérêt pratique du point de vue du temps de calcul vient de ce qu’une initialisation astucieuse (dite « préconditionnement ») permet d'aboutir en seulement quelques passages à une estimation très proche de la solution exacte : c'est pourquoi, en pratique, on se borne à un nombre d'itérations bien inférieur au nombre d'inconnues. La méthode du gradient biconjugué fournit une généralisation pour les matrices non symétriques. (fr) 共役勾配法（きょうやくこうばいほう、英: conjugate gradient method、CG法とも呼ばれる）は対称正定値行列を係数とする連立一次方程式を解くためのアルゴリズムである。反復法として利用され、コレスキー分解のような直接法では大きすぎて取り扱えない、大規模な疎行列を解くために利用される。そのような問題は偏微分方程式などを数値的に解く際に常に現れる。 共役勾配法は、エネルギー最小化などの最適化問題を解くために用いることもできる。 は、共役勾配法の非対称問題への拡張である。また、非線形問題を解くために、さまざまな非線形共役勾配法が提案されている。 (ja) In analisi numerica, il metodo del gradiente coniugato (spesso abbreviato in CG, dall'inglese conjugate gradient) è un algoritmo per la risoluzione numerica di un sistema lineare la cui matrice sia simmetrica e definita positiva. Il metodo è stato inizialmente proposto nel 1952 dai matematici Magnus Hestenes e Eduard Stiefel e costituisce una variante del metodo del gradiente in cui la direzione di discesa a ogni passo è scelta in modo tale da garantire la convergenza del metodo (in aritmetica esatta) in un numero di iterazioni pari al più alla dimensione del sistema da risolvere. Il ne fornisce una generalizzazione al caso di matrici non simmetriche. (it) 켤레기울기법 또는 공역기울기법(영어: Conjugate Gradient Method, 일본어: 共役勾配法)이란 수학에서 대칭인 양의 준정부호행렬(陽-準定符號行列, 영어: positive-semidefinite matrix)을 갖는 선형계의 해를 구하는 수치 알고리즘이다. 이는 보통 으로 풀리고, 따라서 숄레스키 분해와 같은 방법이나 직접 풀기에 너무 큰 계가 갖는 희소행렬 등에 사용하기 적합하다. 그러한 계는 편미분 방정식들이나 최적화 문제들을 수치적으로 풀 때 자주 등장한다. 켤레기울기법은 또한 에너지 최소화같은 제약조건이 없는 최적화문제를 풀 수 있다. 이것은 와 에 의해 개발 되었다. (ko) Metoda gradientu sprzężonego (ang. conjugate gradient method, w skrócie CG) jest algorytmem numerycznym służącym do rozwiązywania niektórych układów równań liniowych. Pozwala rozwiązać te, których macierz jest symetryczna i dodatnio określona. Metoda gradientu sprzężonego jest metodą iteracyjną, więc może być zastosowana do układów o rzadkich macierzach, które mogą być zbyt duże dla algorytmów bezpośrednich takich jak np. rozkład Choleskiego. Takie układy pojawiają się często w trakcie numerycznego rozwiązywania równań różniczkowych cząstkowych. Metoda gradientu sprzężonego może również zostać użyta do rozwiązania problemu optymalizacji bez ograniczeń. (pl) Em matemática, o método do gradiente conjugado é um algoritmo para a de sistemas particulares de equações lineares, aqueles cuja matriz é simétrica e positiva definida. O método do gradiente conjugado é um método iterativo, então ele pode ser aplicado a sistemas esparsos que são grandes demais para ser tratados por métodos diretos como a decomposição de Cholesky. Tais sistemas surgem frequentemente quando se resolve numericamente equações diferenciais parciais. (pt) Метод сопряженных градиентов — численный метод решения систем линейных алгебраических уравнений, является итерационным методом Крыловского типа. (ru) У математиці метод спря́женого градієнта є алгоритмом чисельного рішення окремих систем лінійних рівнянь, а саме тих, чия матриця симетрична і позитивно-визначена. Метод спряженого градієнта часто реалізовується як ітераційний алгоритм, застосовний до розріджених систем, які занадто великі, щоб обробляти їх шляхом прямої реалізації або інших прямих методів, таких як декомпозиція Холеського. Великі розріджені системи часто виникають при чисельному вирішенні часткових диференціальних рівнянь або задачах оптимізації. Метод спряженого градієнта також може бути використаний для вирішення необмежених задач оптимізації, таких як мінімізація енергії . Його в основному розробили Магнус Гестенес та Едуард Стіфель які запрограмували його на Z4 . Метод двобічного спряженого градієнта забезпечує узагальнення до несиметричних матриць. Різні методи нелінійного спряженого градієнта шукають мінімуми нелінійних рівнянь. (uk) 共轭梯度法（英語：Conjugate gradient method），是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法。共轭梯度法是一个迭代方法，它适用于系数矩阵为稀疏矩阵的线性方程组，因为使用像Cholesky分解这样的直接方法求解这些系统所需的计算量太大了。这种方程组在数值求解偏微分方程时很常见。 共轭梯度法也可以用于求解无约束的最優化问题。 （英語：BiConjugate gradient method）提供了一种处理非对称矩阵情况的推广。 (zh)
dbo:thumbnail wiki-commons:Special:FilePath/Conjugate_gradient_illustration.svg?width=300
dbo:wikiPageExternalLink https://archive.org/details/iterativemethods0000saad https://archive.org/details/introductiontonu0000atki https://archive.org/details/iterativemethods0000saad%7Cchapter-url-access=registration%7Cedition=2nd%7Cchapter=Chapter https://web.stanford.edu/group/SOL/software/lsqr/
dbo:wikiPageID 1448821 (xsd:integer)
dbo:wikiPageLength 40691 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1122529017 (xsd:integer)
dbo:wikiPageWikiLink dbr:Belief_propagation dbr:Quadratic_function dbr:Rounding_errors dbr:Energy_minimization dbr:Nonlinear_conjugate_gradient dbr:Normal_equations dbr:Basis_(linear_algebra) dbr:Algorithm dbr:Residual_(numerical_analysis) dbr:Double-precision_floating-point_format dbr:Double_integrator dbr:Incomplete_Cholesky_factorization dbr:Jacobi_method dbr:Preconditioner dbr:Conjugate_gradient_method dbr:Conjugate_transpose dbr:Mathematical_optimization dbr:Mathematics dbr:Gauss–Seidel_method dbr:Symmetric_matrix dbr:Eigenvalue dbr:GNU_Octave dbr:Gradient_descent dbr:Condition_number dbr:Conjugate_residual_method dbr:Anne_Greenbaum dbr:Arnoldi_iteration dbr:MATLAB dbr:Magnus_Hestenes dbr:Cholesky_decomposition dbr:Krylov_subspace dbr:Spectrum_of_a_matrix dbr:Transpose dbr:Line_search dbr:Eduard_Stiefel dbr:Partial_differential_equation dbr:Gram–Schmidt_process dbr:Iterative_method dbr:Nonlinear_conjugate_gradient_method dbr:Preconditioning dbr:Hermitian dbc:Numerical_linear_algebra dbr:Biconjugate_gradient_method dbc:Gradient_methods dbr:Hessian_matrix dbc:Articles_with_example_MATLAB/Octave_code dbr:Polynomial_ring dbr:Positive-definite_matrix dbr:Sparse_matrix dbr:Inner_product_space dbr:Optimal_control dbr:Real_number dbr:Numerical_solution dbr:Round-off_error dbr:System_of_linear_equations dbr:Sparse_matrix–vector_multiplication dbr:Feedback_Control dbr:Z4_(computer) dbr:Steepest_descent dbr:Lanczos_iteration dbr:File:Conjugate_gradient_illustration.svg
dbp:id p/c025030 (en)
dbp:title Conjugate gradients, method of (en)
dbp:wikiPageUsesTemplate dbt:Springer dbt:= dbt:Authority_control dbt:Cite_book dbt:Div_col dbt:Div_col_end dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:See_also dbt:Short_description dbt:Numerical_linear_algebra
dcterms:subject dbc:Numerical_linear_algebra dbc:Gradient_methods dbc:Articles_with_example_MATLAB/Octave_code
gold:hypernym dbr:Algorithm
rdf:type owl:Thing dbo:Software yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 yago:WikicatGradientMethods
rdfs:comment 共役勾配法（きょうやくこうばいほう、英: conjugate gradient method、CG法とも呼ばれる）は対称正定値行列を係数とする連立一次方程式を解くためのアルゴリズムである。反復法として利用され、コレスキー分解のような直接法では大きすぎて取り扱えない、大規模な疎行列を解くために利用される。そのような問題は偏微分方程式などを数値的に解く際に常に現れる。 共役勾配法は、エネルギー最小化などの最適化問題を解くために用いることもできる。 は、共役勾配法の非対称問題への拡張である。また、非線形問題を解くために、さまざまな非線形共役勾配法が提案されている。 (ja) 켤레기울기법 또는 공역기울기법(영어: Conjugate Gradient Method, 일본어: 共役勾配法)이란 수학에서 대칭인 양의 준정부호행렬(陽-準定符號行列, 영어: positive-semidefinite matrix)을 갖는 선형계의 해를 구하는 수치 알고리즘이다. 이는 보통 으로 풀리고, 따라서 숄레스키 분해와 같은 방법이나 직접 풀기에 너무 큰 계가 갖는 희소행렬 등에 사용하기 적합하다. 그러한 계는 편미분 방정식들이나 최적화 문제들을 수치적으로 풀 때 자주 등장한다. 켤레기울기법은 또한 에너지 최소화같은 제약조건이 없는 최적화문제를 풀 수 있다. 이것은 와 에 의해 개발 되었다. (ko) Em matemática, o método do gradiente conjugado é um algoritmo para a de sistemas particulares de equações lineares, aqueles cuja matriz é simétrica e positiva definida. O método do gradiente conjugado é um método iterativo, então ele pode ser aplicado a sistemas esparsos que são grandes demais para ser tratados por métodos diretos como a decomposição de Cholesky. Tais sistemas surgem frequentemente quando se resolve numericamente equações diferenciais parciais. (pt) Метод сопряженных градиентов — численный метод решения систем линейных алгебраических уравнений, является итерационным методом Крыловского типа. (ru) 共轭梯度法（英語：Conjugate gradient method），是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法。共轭梯度法是一个迭代方法，它适用于系数矩阵为稀疏矩阵的线性方程组，因为使用像Cholesky分解这样的直接方法求解这些系统所需的计算量太大了。这种方程组在数值求解偏微分方程时很常见。 共轭梯度法也可以用于求解无约束的最優化问题。 （英語：BiConjugate gradient method）提供了一种处理非对称矩阵情况的推广。 (zh) In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems. (en) Das CG-Verfahren (von engl. conjugate gradients oder auch Verfahren der konjugierten Gradienten) ist eine effiziente numerische Methode zur Lösung von großen linearen Gleichungssystemen der Form mit symmetrischer, positiv definiter Systemmatrix . Das Verfahren liefert, in exakter Arithmetik, nach spätestens Schritten die exakte Lösung, wobei die Größe der quadratischen Matrix ist. Insbesondere ist es aber als iteratives Verfahren interessant, da der Fehler monoton fällt. Das CG-Verfahren kann in die Klasse der Krylow-Unterraum-Verfahren eingeordnet werden. (de) En matemática, el método del gradiente conjugado es un algoritmo para resolver numéricamente los sistemas de ecuaciones lineales cuyas matrices son simétricas y definidas positivas. Es un método iterativo, así que se puede aplicar a los sistemas dispersos que son demasiado grandes para ser tratados por métodos directos como la descomposición de Cholesky. Tales sistemas surgen frecuentemente cuando se resuelve numéricamente las ecuaciones en derivadas parciales. El método del gradiente conjugado se puede utilizar también para resolver los problemas de optimización sin restricciones como la . (es) En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d'équations linéaires dont la matrice est symétrique définie positive. Cette méthode, imaginée en 1950 simultanément par Cornelius Lanczos, Eduard Stiefel et Magnus Hestenes, est une méthode itérative qui converge en un nombre fini d'itérations (au plus égal à la dimension du système linéaire). Toutefois, son grand intérêt pratique du point de vue du temps de calcul vient de ce qu’une initialisation astucieuse (dite « préconditionnement ») permet d'aboutir en seulement quelques passages à une estimation très proche de la solution exacte : c'est pourquoi, en pratique, on se borne à un nombre d'itérations bien inférieur au nombre d'inconnues. (fr) In analisi numerica, il metodo del gradiente coniugato (spesso abbreviato in CG, dall'inglese conjugate gradient) è un algoritmo per la risoluzione numerica di un sistema lineare la cui matrice sia simmetrica e definita positiva. Il metodo è stato inizialmente proposto nel 1952 dai matematici Magnus Hestenes e Eduard Stiefel e costituisce una variante del metodo del gradiente in cui la direzione di discesa a ogni passo è scelta in modo tale da garantire la convergenza del metodo (in aritmetica esatta) in un numero di iterazioni pari al più alla dimensione del sistema da risolvere. (it) Metoda gradientu sprzężonego (ang. conjugate gradient method, w skrócie CG) jest algorytmem numerycznym służącym do rozwiązywania niektórych układów równań liniowych. Pozwala rozwiązać te, których macierz jest symetryczna i dodatnio określona. Metoda gradientu sprzężonego jest metodą iteracyjną, więc może być zastosowana do układów o rzadkich macierzach, które mogą być zbyt duże dla algorytmów bezpośrednich takich jak np. rozkład Choleskiego. Takie układy pojawiają się często w trakcie numerycznego rozwiązywania równań różniczkowych cząstkowych. (pl) У математиці метод спря́женого градієнта є алгоритмом чисельного рішення окремих систем лінійних рівнянь, а саме тих, чия матриця симетрична і позитивно-визначена. Метод спряженого градієнта часто реалізовується як ітераційний алгоритм, застосовний до розріджених систем, які занадто великі, щоб обробляти їх шляхом прямої реалізації або інших прямих методів, таких як декомпозиція Холеського. Великі розріджені системи часто виникають при чисельному вирішенні часткових диференціальних рівнянь або задачах оптимізації. (uk)
rdfs:label CG-Verfahren (de) Método del gradiente conjugado (es) Conjugate gradient method (en) Méthode du gradient conjugué (fr) Metodo del gradiente coniugato (it) 켤레기울기법 (ko) 共役勾配法 (ja) Metoda gradientu sprzężonego (pl) Método do gradiente conjugado (pt) Метод сопряжённых градиентов (для решения СЛАУ) (ru) 共轭梯度法 (zh) Метод спряженого градієнта (uk)
rdfs:seeAlso dbr:Preconditioner
owl:sameAs freebase:Conjugate gradient method yago-res:Conjugate gradient method http://d-nb.info/gnd/4255670-3 wikidata:Conjugate gradient method dbpedia-de:Conjugate gradient method dbpedia-es:Conjugate gradient method dbpedia-fa:Conjugate gradient method dbpedia-fr:Conjugate gradient method dbpedia-hu:Conjugate gradient method dbpedia-it:Conjugate gradient method dbpedia-ja:Conjugate gradient method dbpedia-ko:Conjugate gradient method dbpedia-pl:Conjugate gradient method dbpedia-pt:Conjugate gradient method dbpedia-ru:Conjugate gradient method dbpedia-uk:Conjugate gradient method dbpedia-zh:Conjugate gradient method https://global.dbpedia.org/id/Er79
prov:wasDerivedFrom wikipedia-en:Conjugate_gradient_method?oldid=1122529017&ns=0
foaf:depiction wiki-commons:Special:FilePath/Conjugate_gradient_illustration.svg
foaf:isPrimaryTopicOf wikipedia-en:Conjugate_gradient_method
is dbo:wikiPageDisambiguates of dbr:Gradient_(disambiguation) dbr:CG dbr:CGM
is dbo:wikiPageRedirects of dbr:Preconditioned_conjugate_gradient_method dbr:Conjugate_Gradient_method dbr:Method_of_conjugate_gradient dbr:Method_of_conjugate_gradients dbr:Polak-Ribier dbr:Polak-Ribièr dbr:Polak–Ribièr dbr:Conjugate_Gradient_Squared dbr:Conjugate_gradient dbr:Conjugate_gradient_algorithm dbr:Conjugate_gradient_descent dbr:Conjugate_gradients dbr:CG_method
is dbo:wikiPageWikiLink of dbr:Belief_propagation dbr:Neighbourhood_components_analysis dbr:Non-linear_least_squares dbr:Numerical_linear_algebra dbr:MINRES dbr:Memetic_algorithm dbr:Probabilistic_numerics dbr:Biconjugate_gradient_stabilized_method dbr:Uzawa_iteration dbr:Vowpal_Wabbit dbr:Derivation_of_the_conjugate_gradient_method dbr:Descent_direction dbr:Dynamic_substructuring dbr:Incomplete_Cholesky_factorization dbr:Incomplete_LU_factorization dbr:List_of_numerical_analysis_topics dbr:Numerical_methods_for_partial_differential_equations dbr:Preconditioner dbr:Conjugate_gradient_method dbr:Cornelius_Lanczos dbr:Mathematical_optimization dbr:Matrix_(mathematics) dbr:Gauss–Newton_algorithm dbr:Wolfe_conditions dbr:Encog dbr:Gradient_descent dbr:NAS_Parallel_Benchmarks dbr:Conjugate_residual_method dbr:Conjugation dbr:LOBPCG dbr:Lis_(linear_algebra_library) dbr:Magnus_Hestenes dbr:Henk_van_der_Vorst dbr:PCG dbr:Pidgin_code dbr:Plane_wave_expansion_method dbr:Preconditioned_conjugate_gradient_method dbr:Mathematics_of_artificial_neural_networks dbr:Matrix-free_methods dbr:CASTEP dbr:Adaptive_beamformer dbr:Distance_geometry dbr:Domain_decomposition_methods dbr:Line_search dbr:Data_assimilation dbr:Eduard_Stiefel dbr:Alternating-direction_implicit_method dbr:Numerical_analysis dbr:Chebyshev_iteration dbr:Discrete_dipole_approximation dbr:Folded_spectrum_method dbr:Gradient_method dbr:Hill_climbing dbr:Iterative_method dbr:Gradient_(disambiguation) dbr:Nonlinear_conjugate_gradient_method dbr:Quadratic_programming dbr:Marvin_Stein_(computer_scientist) dbr:Soft-body_dynamics dbr:Kaczmarz_method dbr:Biconjugate_gradient_method dbr:Biology_Monte_Carlo_method dbr:Edge-preserving_smoothing dbr:HiGHS_optimization_solver dbr:BDDC dbr:Conjugate_Gradient_method dbr:Method_of_conjugate_gradient dbr:Method_of_conjugate_gradients dbr:Method_of_moments_(electromagnetics) dbr:Minimum_mean_square_error dbr:Newton's_method_in_optimization dbr:CG dbr:CGM dbr:Maximum_a_posteriori_estimation dbr:IML++ dbr:Finite_element_method dbr:Quantum_algorithm_for_linear_systems_of_equations dbr:Roland_Andrew_Sweet dbr:Multigrid_method dbr:Proximal_gradient_method dbr:Schur_complement_method dbr:Outline_of_statistics dbr:Sparse_dictionary_learning dbr:Polak-Ribier dbr:Polak-Ribièr dbr:Polak–Ribièr dbr:Conjugate_Gradient_Squared dbr:Conjugate_gradient dbr:Conjugate_gradient_algorithm dbr:Conjugate_gradient_descent dbr:Conjugate_gradients dbr:CG_method
is foaf:primaryTopic of wikipedia-en:Conjugate_gradient_method