在數值線性代數 中,穩定雙共軛梯度法 (英語:Biconjugate gradient stabilized method ,通常簡稱為BiCGSTAB )是一種由荷蘭數學家 H. A. van der Vorst 提出的用於數值求解非對稱線性方程組 的迭代方法 。它是雙共軛梯度法 (BiCG)的一個變種,比雙共軛梯度法本身以及諸如共軛梯度平方法 (CGS)等其他變種有更快速和更平滑的收斂性。它是一種 Krylov 子空間 方法。
要求解線性方程組
A
x
=
b
{\displaystyle {\boldsymbol {Ax}}={\boldsymbol {b}}}
,穩定雙共軛梯度法從初始解
x
0
{\displaystyle {\boldsymbol {x}}_{0}}
開始按以下步驟迭代:
r
0
=
b
−
A
x
{\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax}}}
任意選擇向量
r
^
0
{\displaystyle {\boldsymbol {\hat {r}}}_{0}\;}
使得
(
r
^
0
,
r
0
)
≠
0
{\displaystyle ({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{0})\neq 0\;}
,例如,
r
^
0
=
r
0
{\displaystyle {\boldsymbol {\hat {r}}}_{0}={\boldsymbol {r}}_{0}\;}
ρ
0
=
α
=
ω
0
=
1
{\displaystyle \rho _{0}=\alpha =\omega _{0}=1\;}
v
0
=
p
0
=
0
{\displaystyle {\boldsymbol {v}}_{0}={\boldsymbol {p}}_{0}={\boldsymbol {0}}}
對
i
=
1
,
2
,
3
,
…
{\displaystyle i=1,2,3,\ldots }
ρ
i
=
(
r
^
0
,
r
i
−
1
)
{\displaystyle \rho _{i}=({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{i-1})\;}
β
=
(
ρ
i
/
ρ
i
−
1
)
(
α
/
ω
i
−
1
)
{\displaystyle \beta =(\rho _{i}/\rho _{i-1})(\alpha /\omega _{i-1})\;}
p
i
=
r
i
−
1
+
β
(
p
i
−
1
−
ω
i
−
1
v
i
−
1
)
{\displaystyle {\boldsymbol {p}}_{i}={\boldsymbol {r}}_{i-1}+\beta ({\boldsymbol {p}}_{i-1}-\omega _{i-1}{\boldsymbol {v}}_{i-1})}
v
i
=
A
p
i
{\displaystyle {\boldsymbol {v}}_{i}={\boldsymbol {Ap}}_{i}}
α
=
ρ
i
/
(
r
^
0
,
v
i
)
{\displaystyle \alpha =\rho _{i}/({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {v}}_{i})\;}
s
=
r
i
−
1
−
α
v
i
{\displaystyle {\boldsymbol {s}}={\boldsymbol {r}}_{i-1}-\alpha {\boldsymbol {v}}_{i}}
t
=
A
s
{\displaystyle {\boldsymbol {t}}={\boldsymbol {As}}}
ω
i
=
(
t
,
s
)
/
(
t
,
t
)
{\displaystyle \omega _{i}=({\boldsymbol {t}},{\boldsymbol {s}})/({\boldsymbol {t}},{\boldsymbol {t}})}
x
i
=
x
i
−
1
+
α
p
i
+
ω
i
s
{\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{i-1}+\alpha {\boldsymbol {p}}_{i}+\omega _{i}{\boldsymbol {s}}}
若
x
i
{\displaystyle {\boldsymbol {x}}_{i}}
足夠精確則退出
r
i
=
s
−
ω
i
t
{\displaystyle {\boldsymbol {r}}_{i}={\boldsymbol {s}}-\omega _{i}{\boldsymbol {t}}}
預處理 通常被用來加速迭代方法的收斂。要使用預處理子
K
=
K
1
K
2
≈
A
{\displaystyle {\boldsymbol {K}}={\boldsymbol {K}}_{1}{\boldsymbol {K}}_{2}\approx {\boldsymbol {A}}}
來求解線性方程組
A
x
=
b
{\displaystyle {\boldsymbol {Ax}}={\boldsymbol {b}}}
,預處理穩定雙共軛梯度法從初始解
x
0
{\displaystyle {\boldsymbol {x}}_{0}}
開始按以下步驟迭代:
r
0
=
b
−
A
x
{\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax}}}
任意選擇向量
r
^
0
{\displaystyle {\boldsymbol {\hat {r}}}_{0}\;}
使得
(
r
^
0
,
r
0
)
≠
0
{\displaystyle ({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{0})\neq 0\;}
,例如,
r
^
0
=
r
0
{\displaystyle {\boldsymbol {\hat {r}}}_{0}={\boldsymbol {r}}_{0}\;}
ρ
0
=
α
=
ω
0
=
1
{\displaystyle \rho _{0}=\alpha =\omega _{0}=1\;}
v
0
=
p
0
=
0
{\displaystyle {\boldsymbol {v}}_{0}={\boldsymbol {p}}_{0}={\boldsymbol {0}}}
對
i
=
1
,
2
,
3
,
…
{\displaystyle i=1,2,3,\ldots }
ρ
i
=
(
r
^
0
,
r
i
−
1
)
{\displaystyle \rho _{i}=({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{i-1})\;}
β
=
(
ρ
i
/
ρ
i
−
1
)
(
α
/
ω
i
−
1
)
{\displaystyle \beta =(\rho _{i}/\rho _{i-1})(\alpha /\omega _{i-1})\;}
p
i
=
r
i
−
1
+
β
(
p
i
−
1
−
ω
i
−
1
v
i
−
1
)
{\displaystyle {\boldsymbol {p}}_{i}={\boldsymbol {r}}_{i-1}+\beta ({\boldsymbol {p}}_{i-1}-\omega _{i-1}{\boldsymbol {v}}_{i-1})}
y
=
K
−
1
p
i
{\displaystyle {\boldsymbol {y}}={\boldsymbol {K}}^{-1}{\boldsymbol {p}}_{i}}
v
i
=
A
y
{\displaystyle {\boldsymbol {v}}_{i}={\boldsymbol {Ay}}}
α
=
ρ
i
/
(
r
^
0
,
v
i
)
{\displaystyle \alpha =\rho _{i}/({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {v}}_{i})\;}
s
=
r
i
−
α
v
i
{\displaystyle {\boldsymbol {s}}={\boldsymbol {r}}_{i}-\alpha {\boldsymbol {v}}_{i}}
z
=
A
s
{\displaystyle {\boldsymbol {z}}={\boldsymbol {As}}}
t
=
K
−
1
z
{\displaystyle {\boldsymbol {t}}={\boldsymbol {K}}^{-1}{\boldsymbol {z}}}
ω
i
=
(
K
1
−
1
t
,
K
1
−
1
s
)
/
(
K
1
−
1
t
,
K
1
−
1
t
)
{\displaystyle \omega _{i}=({\boldsymbol {K}}_{1}^{-1}{\boldsymbol {t}},{\boldsymbol {K}}_{1}^{-1}{\boldsymbol {s}})/({\boldsymbol {K}}_{1}^{-1}{\boldsymbol {t}},{\boldsymbol {K}}_{1}^{-1}{\boldsymbol {t}})}
x
i
=
x
i
−
1
+
α
y
+
ω
i
z
{\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{i-1}+\alpha {\boldsymbol {y}}+\omega _{i}{\boldsymbol {z}}}
若
x
i
{\displaystyle {\boldsymbol {x}}_{i}}
足夠精確則退出
r
i
=
s
−
ω
i
t
{\displaystyle {\boldsymbol {r}}_{i}={\boldsymbol {s}}-\omega _{i}{\boldsymbol {t}}}
這個形式等價於將無預處理的穩定雙共軛梯度法應用於顯式預處理後的方程組
A
~
x
~
=
b
~
{\displaystyle {\boldsymbol {{\tilde {A}}{\tilde {x}}}}={\boldsymbol {\tilde {b}}}}
,
其中
A
~
=
K
1
−
1
A
K
2
−
1
{\displaystyle {\boldsymbol {\tilde {A}}}={\boldsymbol {K}}_{1}^{-1}{\boldsymbol {AK}}_{2}^{-1}}
,
x
~
=
K
2
x
{\displaystyle {\boldsymbol {\tilde {x}}}={\boldsymbol {K}}_{2}{\boldsymbol {x}}}
,
b
~
=
K
1
−
1
b
{\displaystyle {\boldsymbol {\tilde {b}}}={\boldsymbol {K}}_{1}^{-1}{\boldsymbol {b}}}
。換句話說,左預處理和右預處理都可以通過這個形式實施。
在雙共軛梯度法中,搜索方向
p
i
{\displaystyle {\boldsymbol {p}}_{i}}
和
p
^
i
{\displaystyle {\boldsymbol {\hat {p}}}_{i}}
以及殘量
r
i
{\displaystyle {\boldsymbol {r}}_{i}}
和
r
^
i
{\displaystyle {\boldsymbol {\hat {r}}}_{i}}
通過以下遞推關係更新:
p
i
=
r
i
+
β
i
p
i
−
1
,
{\displaystyle {\boldsymbol {p}}_{i}={\boldsymbol {r}}_{i}+\beta _{i}{\boldsymbol {p}}_{i-1}{\text{,}}}
p
^
i
=
r
^
i
+
β
i
p
i
−
1
,
{\displaystyle {\boldsymbol {\hat {p}}}_{i}={\boldsymbol {\hat {r}}}_{i}+\beta _{i}{\boldsymbol {p}}_{i-1}{\text{,}}}
r
i
=
r
i
−
1
−
α
i
A
p
i
,
{\displaystyle {\boldsymbol {r}}_{i}={\boldsymbol {r}}_{i-1}-\alpha _{i}{\boldsymbol {Ap}}_{i}{\text{,}}}
r
^
i
=
r
^
i
−
1
−
α
A
T
p
^
i
.
{\displaystyle {\boldsymbol {\hat {r}}}_{i}={\boldsymbol {\hat {r}}}_{i-1}-\alpha {\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\hat {p}}}_{i}{\text{.}}}
常數
α
i
{\displaystyle \alpha _{i}\;}
和
β
i
{\displaystyle \beta _{i}\;}
取值為
α
i
=
ρ
i
/
(
p
^
i
,
A
p
i
)
,
{\displaystyle \alpha _{i}=\rho _{i}/({\boldsymbol {\hat {p}}}_{i},{\boldsymbol {Ap}}_{i}){\text{,}}}
β
i
=
ρ
i
/
ρ
i
−
1
,
{\displaystyle \beta _{i}=\rho _{i}/\rho _{i-1}{\text{,}}\;}
其中
ρ
i
=
(
r
^
i
−
1
,
r
i
−
1
)
{\displaystyle \rho _{i}=({\boldsymbol {\hat {r}}}_{i-1},{\boldsymbol {r}}_{i-1})}
,使得殘量和搜索方向分別滿足雙正交性和雙共軛性,也就是對於
i
≠
j
{\displaystyle i\neq j}
,
(
r
^
i
,
r
j
)
=
0
,
{\displaystyle ({\boldsymbol {\hat {r}}}_{i},{\boldsymbol {r}}_{j})=0{\text{,}}}
(
p
^
i
,
A
p
j
)
=
0
.
{\displaystyle ({\boldsymbol {\hat {p}}}_{i},{\boldsymbol {Ap}}_{j})=0{\text{.}}}
不難證明,
r
i
=
P
i
(
A
)
r
0
,
{\displaystyle {\boldsymbol {r}}_{i}=P_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\text{,}}}
r
^
i
=
P
i
(
A
T
)
r
^
0
,
{\displaystyle {\boldsymbol {\hat {r}}}_{i}=P_{i}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0}{\text{,}}}
p
i
+
1
=
T
i
(
A
)
r
0
,
{\displaystyle {\boldsymbol {p}}_{i+1}=T_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\text{,}}}
p
^
i
+
1
=
T
i
(
A
T
)
r
^
0
,
{\displaystyle {\boldsymbol {\hat {p}}}_{i+1}=T_{i}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0}{\text{,}}}
其中
P
i
(
A
)
{\displaystyle P_{i}({\boldsymbol {A}})}
和
T
i
(
A
)
{\displaystyle T_{i}({\boldsymbol {A}})}
是關於
A
{\displaystyle {\boldsymbol {A}}}
的
i
{\displaystyle i\;}
次多項式。這些多項式滿足以下遞推關係:
P
i
(
A
)
=
P
i
−
1
(
A
)
−
α
i
A
T
i
−
1
(
A
)
,
{\displaystyle P_{i}({\boldsymbol {A}})=P_{i-1}({\boldsymbol {A}})-\alpha _{i}{\boldsymbol {A}}T_{i-1}({\boldsymbol {A}}){\text{,}}}
T
i
(
A
)
=
P
i
(
A
)
−
β
i
+
1
T
i
−
1
(
A
)
.
{\displaystyle T_{i}({\boldsymbol {A}})=P_{i}({\boldsymbol {A}})-\beta _{i+1}T_{i-1}({\boldsymbol {A}}){\text{.}}}
雙共軛梯度法的殘量和搜索方向不是必須顯式跟蹤的。換句話說,雙共軛梯度法的迭代是可以隱式進行的。穩定雙共軛梯度法中希望得到
r
~
i
=
Q
i
(
A
)
P
i
(
A
)
r
0
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}=Q_{i}({\boldsymbol {A}})P_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}}
的遞推關係,其中
Q
i
(
A
)
=
(
I
−
ω
1
A
)
(
I
−
ω
1
A
)
⋯
(
I
−
ω
i
A
)
{\displaystyle Q_{i}({\boldsymbol {A}})=({\boldsymbol {I}}-\omega _{1}{\boldsymbol {A}})({\boldsymbol {I}}-\omega _{1}{\boldsymbol {A}})\cdots ({\boldsymbol {I}}-\omega _{i}{\boldsymbol {A}})}
,
ω
j
{\displaystyle \omega _{j}\;}
為適當選取的常數。以此代替
r
i
=
P
i
(
A
)
{\displaystyle {\boldsymbol {r}}_{i}=P_{i}({\boldsymbol {A}})}
的目的是希望
Q
i
(
A
)
{\displaystyle Q_{i}({\boldsymbol {A}})}
可以使
r
~
i
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}}
有比
r
i
{\displaystyle {\boldsymbol {r}}_{i}}
更快速和更平滑的收斂性。
根據
P
i
(
A
)
{\displaystyle P_{i}({\boldsymbol {A}})}
和
T
i
(
A
)
{\displaystyle T_{i}({\boldsymbol {A}})}
的遞推關係以及
Q
i
(
A
)
{\displaystyle Q_{i}({\boldsymbol {A}})}
的定義,
Q
i
(
A
)
P
i
(
A
)
r
0
=
(
I
−
ω
i
A
)
(
Q
i
−
1
(
A
)
P
i
−
1
(
A
)
r
0
−
α
i
A
Q
i
−
1
(
A
)
P
i
−
1
(
A
)
r
0
)
.
{\displaystyle Q_{i}({\boldsymbol {A}})P_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}=({\boldsymbol {I}}-\omega _{i}{\boldsymbol {A}}){\bigl (}Q_{i-1}({\boldsymbol {A}})P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}-\alpha _{i}{\boldsymbol {A}}Q_{i-1}({\boldsymbol {A}})P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}{\text{.}}}
於是還需要一條關於
Q
i
(
A
)
T
i
(
A
)
r
0
{\displaystyle Q_{i}({\boldsymbol {A}})T_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}}
的遞推關係。這同樣可以從雙共軛梯度法的遞推關係中導出:
Q
i
(
A
)
T
i
(
A
)
r
0
=
Q
i
(
A
)
P
i
(
A
)
r
0
−
β
i
+
1
(
I
−
ω
i
A
)
Q
i
−
1
(
A
)
T
i
−
1
(
A
)
r
0
.
{\displaystyle Q_{i}({\boldsymbol {A}})T_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}=Q_{i}({\boldsymbol {A}})P_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}-\beta _{i+1}({\boldsymbol {I}}-\omega _{i}{\boldsymbol {A}})Q_{i-1}({\boldsymbol {A}})T_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\text{.}}}
類似於
r
~
i
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}}
,穩定雙共軛梯度法定義
p
~
i
+
1
=
Q
i
(
A
)
T
i
(
A
)
r
0
.
{\displaystyle {\boldsymbol {\tilde {p}}}_{i+1}=Q_{i}({\boldsymbol {A}})T_{i}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\text{.}}}
寫成向量形式,
p
~
i
{\displaystyle {\boldsymbol {\tilde {p}}}_{i}}
和
r
~
i
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}}
的遞推關係就是
p
~
i
=
r
~
i
−
1
+
β
i
(
I
−
ω
i
−
1
A
)
p
~
i
−
1
,
{\displaystyle {\boldsymbol {\tilde {p}}}_{i}={\boldsymbol {\tilde {r}}}_{i-1}+\beta _{i}({\boldsymbol {I}}-\omega _{i-1}{\boldsymbol {A}}){\boldsymbol {\tilde {p}}}_{i-1}{\text{,}}}
r
~
i
=
(
I
−
ω
i
A
)
(
r
~
i
−
1
−
α
i
A
p
~
i
)
.
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}=({\boldsymbol {I}}-\omega _{i}{\boldsymbol {A}})({\boldsymbol {\tilde {r}}}_{i-1}-\alpha _{i}{\boldsymbol {A{\tilde {p}}}}_{i}){\text{.}}}
為了導出
x
i
{\displaystyle {\boldsymbol {x}}_{i}}
的遞推關係,定義
s
i
=
r
~
i
−
1
−
α
i
A
p
~
i
.
{\displaystyle {\boldsymbol {s}}_{i}={\boldsymbol {\tilde {r}}}_{i-1}-\alpha _{i}{\boldsymbol {A{\tilde {p}}}}_{i}{\text{.}}}
於是
r
~
i
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}}
的遞推關係就可以寫成
r
~
i
=
r
~
i
−
1
−
α
i
A
p
~
i
−
ω
i
A
s
i
,
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}={\boldsymbol {\tilde {r}}}_{i-1}-\alpha _{i}{\boldsymbol {A{\tilde {p}}}}_{i}-\omega _{i}{\boldsymbol {As}}_{i}{\text{,}}}
這對應於
x
i
=
x
i
−
1
+
α
i
p
~
i
+
ω
i
s
i
.
{\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{i-1}+\alpha _{i}{\boldsymbol {\tilde {p}}}_{i}+\omega _{i}{\boldsymbol {s}}_{i}{\text{.}}}
現在只需確定雙共軛梯度法的常數
α
i
{\displaystyle \alpha _{i}\;}
和
β
i
{\displaystyle \beta _{i}\;}
以及選擇一個合適的
ω
i
{\displaystyle \omega _{i}\;}
。
在雙共軛梯度法中,
β
i
=
ρ
i
/
ρ
i
−
1
{\displaystyle \beta _{i}=\rho _{i}/\rho _{i-1}\;}
, 其中
ρ
i
=
(
r
^
i
−
1
,
r
i
−
1
)
=
(
P
i
−
1
(
A
T
)
r
^
0
,
P
i
−
1
(
A
)
r
0
)
.
{\displaystyle \rho _{i}=({\boldsymbol {\hat {r}}}_{i-1},{\boldsymbol {r}}_{i-1})={\bigl (}P_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}{\text{.}}}
由於穩定雙共軛梯度法不顯式跟蹤
r
^
i
{\displaystyle {\boldsymbol {\hat {r}}}_{i}}
或
r
i
{\displaystyle {\boldsymbol {r}}_{i}}
,
ρ
i
{\displaystyle \rho _{i}\;}
不能立即用這條公式計算出來。但是,它可以和純量
ρ
~
i
=
(
Q
i
−
1
(
A
T
)
r
^
0
,
P
i
−
1
(
A
)
r
0
)
=
(
r
^
0
,
Q
i
−
1
(
A
)
P
i
−
1
(
A
)
r
0
)
=
(
r
^
0
,
r
i
−
1
)
{\displaystyle {\tilde {\rho }}_{i}={\bigl (}Q_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}={\bigl (}{\boldsymbol {\hat {r}}}_{0},Q_{i-1}({\boldsymbol {A}})P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}=({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {r}}_{i-1})}
關聯起來。由於雙正交性,
r
i
−
1
=
P
i
−
1
(
A
)
r
0
{\displaystyle {\boldsymbol {r}}_{i-1}=P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}}
正交於
U
i
−
2
(
A
T
)
r
^
0
{\displaystyle U_{i-2}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0}}
,其中
U
i
−
2
(
A
T
)
{\displaystyle U_{i-2}({\boldsymbol {A}}^{\mathrm {T} })}
是關於
A
T
{\displaystyle {\boldsymbol {A}}^{\mathrm {T} }}
的任意
i
−
2
{\displaystyle i-2\;}
次多項式。因此在點積
(
P
i
−
1
(
A
T
)
r
^
0
,
P
i
−
1
(
A
)
r
0
)
{\displaystyle {\bigl (}P_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}}
和
(
Q
i
−
1
(
A
T
)
r
^
0
,
P
i
−
1
(
A
)
r
0
)
{\displaystyle {\bigl (}Q_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}}
中只需考慮
P
i
−
1
(
A
T
)
{\displaystyle P_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
和
Q
i
−
1
(
A
T
)
{\displaystyle Q_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
的最高次項。
P
i
−
1
(
A
T
)
{\displaystyle P_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
和
Q
i
−
1
(
A
T
)
{\displaystyle Q_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
的最高次項係數分別是
(
−
1
)
i
−
1
α
1
α
2
⋯
α
i
−
1
{\displaystyle (-1)^{i-1}\alpha _{1}\alpha _{2}\cdots \alpha _{i-1}}
和
(
−
1
)
i
−
1
ω
1
ω
2
⋯
ω
i
−
1
{\displaystyle (-1)^{i-1}\omega _{1}\omega _{2}\cdots \omega _{i-1}}
。因此
ρ
i
=
(
α
1
/
ω
1
)
(
α
2
/
ω
2
)
⋯
(
α
i
−
1
/
ω
i
−
1
)
ρ
~
i
,
{\displaystyle \rho _{i}=(\alpha _{1}/\omega _{1})(\alpha _{2}/\omega _{2})\cdots (\alpha _{i-1}/\omega _{i-1}){\tilde {\rho }}_{i}{\text{,}}}
於是
β
i
=
ρ
i
/
ρ
i
−
1
=
(
ρ
~
i
/
ρ
~
i
−
1
)
(
α
i
−
1
/
ω
i
−
1
)
.
{\displaystyle \beta _{i}=\rho _{i}/\rho _{i-1}=({\tilde {\rho }}_{i}/{\tilde {\rho }}_{i-1})(\alpha _{i-1}/\omega _{i-1}){\text{.}}}
關於
α
i
{\displaystyle \alpha _{i}\;}
的簡單公式可以類似地導出。在雙共軛梯度法中,
α
i
=
ρ
i
/
(
p
^
,
A
p
i
)
=
(
P
i
−
1
(
A
T
)
r
^
0
,
P
i
−
1
(
A
)
r
0
)
/
(
T
i
−
1
(
A
T
)
r
^
0
,
A
T
i
−
1
(
A
)
r
0
)
.
{\displaystyle \alpha _{i}=\rho _{i}/({\boldsymbol {\hat {p}}},{\boldsymbol {Ap}}_{i})={\bigl (}P_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}{\big /}{\bigl (}T_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},{\boldsymbol {A}}T_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}{\text{.}}}
類似於上面的情況,由於雙正交性和雙共軛性,在點積中只需考慮
P
i
−
1
(
A
T
)
{\displaystyle P_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
和
T
i
−
1
(
A
T
)
{\displaystyle T_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
的最高次項。
P
i
−
1
(
A
T
)
{\displaystyle P_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
和
T
i
−
1
(
A
T
)
{\displaystyle T_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
的最高次項係數恰巧是相同的。因此,它們可以在公式中被同時替換為
Q
i
−
1
(
A
T
)
{\displaystyle Q_{i-1}({\boldsymbol {A}}^{\mathrm {T} })}
,於是
α
i
=
(
Q
i
−
1
(
A
T
)
r
^
0
,
P
i
−
1
(
A
)
r
0
)
/
(
Q
i
−
1
(
A
T
)
r
^
0
,
A
T
i
−
1
(
A
)
r
0
)
=
ρ
~
i
/
(
r
^
0
,
A
Q
i
−
1
(
A
)
T
i
−
1
(
A
)
r
0
)
=
ρ
~
i
/
(
r
^
0
,
A
p
~
i
)
.
{\displaystyle \alpha _{i}={\bigl (}Q_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},P_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}{\big /}{\bigl (}Q_{i-1}({\boldsymbol {A}}^{\mathrm {T} }){\boldsymbol {\hat {r}}}_{0},{\boldsymbol {A}}T_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}={\tilde {\rho }}_{i}{\big /}{\bigl (}{\boldsymbol {\hat {r}}}_{0},{\boldsymbol {A}}Q_{i-1}({\boldsymbol {A}})T_{i-1}({\boldsymbol {A}}){\boldsymbol {r}}_{0}{\bigr )}={\tilde {\rho }}_{i}/({\boldsymbol {\hat {r}}}_{0},{\boldsymbol {A{\tilde {p}}}}_{i}){\text{.}}}
最後,穩定雙共軛梯度法選擇
ω
i
{\displaystyle \omega _{i}\;}
使得
r
~
i
=
(
I
−
ω
i
A
)
s
i
{\displaystyle {\boldsymbol {\tilde {r}}}_{i}=({\boldsymbol {I}}-\omega _{i}{\boldsymbol {A}}){\boldsymbol {s}}_{i}}
的 2-範數作為
ω
i
{\displaystyle \omega _{i}\;}
的函數被最小化。這在
(
(
I
−
ω
i
A
)
s
i
,
A
s
i
)
=
0
{\displaystyle {\bigl (}({\boldsymbol {I}}-\omega _{i}{\boldsymbol {A}}){\boldsymbol {s}}_{i},{\boldsymbol {As}}_{i}{\bigr )}=0}
時達到,因此
ω
i
{\displaystyle \omega _{i}\;}
的最優值是
ω
i
=
(
A
s
i
,
s
i
)
/
(
A
s
i
,
A
s
i
)
.
{\displaystyle \omega _{i}=({\boldsymbol {As}}_{i},{\boldsymbol {s}}_{i})/({\boldsymbol {As}}_{i},{\boldsymbol {As}}_{i}){\text{.}}}