令 A , B ∈ R n × n {\displaystyle A,B\in R^{n\times n}\!\,} 為對稱正定矩陣，令 b ∈ R n {\displaystyle b\in R^{n}\!\,} 。考慮二次函式 Q ( x ) = 1 2 x T A x − x T b {\displaystyle Q(x)={\frac {1}{2}}x^{T}Ax-x^{T}b\!\,} ，其中 x ∈ R n {\displaystyle x\in R^{n}\!\,} ，並使用一種下降方法來逼近 A x = b {\displaystyle Ax=b\!\,} 的解
x k + 1 = x k + α k d k {\displaystyle x_{k+1}=x_{k}+\alpha _{k}d_{k}\!\,}
定義最速下降 d k {\displaystyle d_{k}\!\,} 的概念，並說明如何計算最佳步長 α k {\displaystyle \alpha _{k}\!\,}
∇ Q ( x k ) ⋅ d k < 0 {\displaystyle \nabla Q(x_{k})\cdot d_{k}<0\!\,}
選擇 α k {\displaystyle \alpha _{k}\!\,} 使 Q ( x k + α k d k ) {\displaystyle Q(x_{k}+\alpha _{k}d_{k})\!\,} 最小化，即
α k : min α k Q ( x k + α k d k ) {\displaystyle \alpha _{k}:\min _{\alpha _{k}}Q(x_{k}+\alpha _{k}d_{k})\!\,}
Q ( x k + α k d k ) = ⟨ x k + α k d k , A x k + α k A d k ⟩ − ⟨ x k + α k d k , b ⟩ {\displaystyle Q(x_{k}+\alpha _{k}d_{k})=\langle x_{k}+\alpha _{k}d_{k},Ax_{k}+\alpha _{k}Ad_{k}\rangle -\langle x_{k}+\alpha _{k}d_{k},b\rangle \!\,}
d d α Q ( x k + α k d k ) = ⟨ A d k , x k ⟩ + α k ⟨ A d k , d k ⟩ − ⟨ d k , b ⟩ {\displaystyle {\frac {d}{d\alpha }}Q(x_{k}+\alpha _{k}d_{k})=\langle Ad_{k},x_{k}\rangle +\alpha _{k}\langle Ad_{k},d_{k}\rangle -\langle d_{k},b\rangle \!\,}
將上述表示式設為零，得到最優 α k {\displaystyle \alpha _{k}\!\,}
α k = ⟨ d k , b − A x k ⟩ ⟨ A d k , d k ⟩ {\displaystyle \alpha _{k}={\frac {\langle d_{k},b-Ax_{k}\rangle }{\langle Ad_{k},d_{k}\rangle }}\!\,}
注意，由於 A {\displaystyle A\!\,} 是對稱的
⟨ d k , A x k ⟩ = ⟨ A d k , x k ⟩ {\displaystyle \langle d_{k},Ax_{k}\rangle =\langle Ad_{k},x_{k}\rangle \!\,}
制定最速下降法（或梯度法），並編寫實現該方法的虛擬碼。
請注意 d k = − ∇ Q ( x k ) = b − A x k = r k {\displaystyle d_{k}=-\nabla Q(x_{k})=b-Ax_{k}=r_{k}\!\,} . 然後，最小 α k {\displaystyle \alpha _{k}\!\,} 由 ⟨ r k , r k ⟩ ⟨ r k , r k ⟩ A {\displaystyle {\frac {\langle r_{k},r_{k}\rangle }{\langle r_{k},r_{k}\rangle _{A}}}\!\,} 給出。
給定 x 0 ∈ R n {\displaystyle x_{0}\in R^{n}\!\,}
For k = 0 , 1 , 2 , … {\displaystyle k=0,1,2,\ldots \!\,} r k = b − A x k If r k = 0 , then quit d k = r k α k = ⟨ r k , r k ⟩ ⟨ r k , r k ⟩ A x k + 1 = x k + α k d k {\displaystyle {\begin{aligned}r_{k}&=b-Ax_{k}\\&{\mbox{If }}r_{k}=0,{\mbox{ then quit }}\\d_{k}&=r_{k}\\\alpha _{k}&={\frac {\langle r_{k},r_{k}\rangle }{\langle r_{k},r_{k}\rangle _{A}}}\\x_{k+1}&=x_{k}+\alpha _{k}d_{k}\end{aligned}}}
令 B − 1 {\displaystyle B^{-1}\!\,} 是 A {\displaystyle A\!\,} 的預處理器。展示如何修改最速下降法使其適用於 B − 1 A x = B − 1 b {\displaystyle B^{-1}Ax=B^{-1}b\!\,} 並編寫虛擬碼。請注意， B − 1 A {\displaystyle B^{-1}A\!\,} 可能不是對稱的。（提示：按照共軛梯度法進行）。
由於 B {\displaystyle B\!\,} 是對稱的，正定的， B = E T E {\displaystyle B=E^{T}E\!\,} ，其中 E {\displaystyle E\!\,} 是上三角矩陣（Cholesky 分解）。
那麼 B − 1 = E − 1 E − T {\displaystyle B^{-1}=E^{-1}E^{-T}\!\,}
因此，
B − 1 A x = B − 1 b E − 1 E − T A x = E − 1 E − T b E − T A x = E − T b E − T A E − 1 ⏟ A ~ E x ⏟ x ~ = E − T b ⏟ b ~ {\displaystyle {\begin{aligned}B^{-1}Ax&=B^{-1}b\\E^{-1}E^{-T}Ax&=E^{-1}E^{-T}b\\E^{-T}Ax&=E^{-T}b\\\underbrace {E^{-T}AE^{-1}} _{\tilde {A}}\underbrace {Ex} _{\tilde {x}}&=\underbrace {E^{-T}b} _{\tilde {b}}\end{aligned}}\!\,}
A ~ {\displaystyle {\tilde {A}}\!\,} 是對稱的
( E − T A E − 1 ) T = E − T A E − 1 {\displaystyle (E^{-T}AE^{-1})^{T}=E^{-T}AE^{-1}\!\,} 因為 A {\displaystyle A\!\,} 是對稱的
A ~ {\displaystyle {\tilde {A}}\!\,} 是正定的
x T E − T A E − 1 x = ( E − 1 x ) T A ( E − 1 x ) > 0 {\displaystyle x^{T}E^{-T}AE^{-1}x=(E^{-1}x)^{T}A(E^{-1}x)>0\!\,} 因為 A {\displaystyle A\!\,} 是正定的
For k = 0 , 1 , 2 , … {\displaystyle k=0,1,2,\ldots \!\,} x k ~ = E x k r k = b ~ − A ~ x k ~ If r k = 0 , then quit d k = r k α k = ⟨ r k , r k ⟩ ⟨ r k , r k ⟩ A ~ x k + 1 = x k + α k d k {\displaystyle {\begin{aligned}{\tilde {x_{k}}}&=Ex_{k}\\r_{k}&={\tilde {b}}-{\tilde {A}}{\tilde {x_{k}}}\\&{\mbox{If }}r_{k}=0,{\mbox{ then quit }}\\d_{k}&=r_{k}\\\alpha _{k}&={\frac {\langle r_{k},r_{k}\rangle }{\langle r_{k},r_{k}\rangle _{\tilde {A}}}}\\x_{k+1}&=x_{k}+\alpha _{k}d_{k}\end{aligned}}}
的概念，並說明如何計算最佳步長 
使 
最小化，即
是對稱的
. 然後，最小 由 
給出。
是對稱的，正定的，
，其中 
是上三角矩陣（Cholesky 分解）。
是對稱的
因為 是對稱的 是正定的
因為 是正定的
