共軛梯度法(英語:Conjugate gradient method),是求解係數矩陣為對稱正定矩陣的線性方程組的數值解的方法。共軛梯度法是一個迭代方法,它適用於係數矩陣為稀疏矩陣的線性方程組,因為使用像Cholesky分解這樣的直接方法求解這些系統所需的計算量太大了。這種方程組在數值求解偏微分方程時很常見。
共軛梯度法也可以用於求解無約束的最優化問題。
雙共軛梯度法(英語:BiConjugate gradient method)提供了一種處理非對稱矩陣情況的推廣。
方法的表述[編輯]
設我們要求解下列線性系統
![{\displaystyle Ax=b,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66dbdc9ace4de8b9bdcf2bd7eb7bfb117307e90b)
其中
矩陣
是對稱的(即
),正定的(即
),並且是實係數的。 將系統的唯一解記作
。
最後算法[編輯]
經過一些簡化,可以得到下列求解
的算法,其中
是實對稱正定矩陣。
![{\displaystyle {\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&k:=0\\&{\text{repeat}}\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad {\hbox{if }}r_{k+1}{\text{ is sufficiently small, then exit loop}}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad k:=k+1\\&{\text{end repeat}}\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65c4a04b3745ab744633eabb5eb2194013f8b240)
結果為
.
外部連結[編輯]
共軛梯度法最初出現於
- Magnus R. Hestenes and Eduard Stiefel(1952),Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49, 409–436.
下列教科書中可以找到該方法的描述
- Kendell A. Atkinson(1988),An introduction to numerical analysis(2nd ed.),Section 8.9, John Wiley and Sons. ISBN 0-471-50023-2.
- Gene H. Golub and Charles F. Van Loan, Matrix computations(3rd ed.),Chapter 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.