L'algorisme QMR, de l'anglés Quasi-Minimal Residual es deu a Roland W. Freund i Noël M. Nachtigal, els quals el 1991 van publicar aquest algorisme, el qual es basa en la biortogonalització de Lanczos, una extensió per a matrius no simètriques de la ortogonalització simètrica de Lanczos.
Biortogonalització de Lanczos
modifica
El procés de Biortogonalització per a matrius no simètriques de Lanczos, consisteix a construir dues bases ortogonals als subespais
K
m
(
A
,
v
1
)
=
s
p
a
n
{
v
1
,
A
v
1
,
…
,
A
m
−
1
v
1
}
{\displaystyle {\mathcal {K}}_{m}\left(A,v_{1}\right)=\mathrm {span} \left\{v_{1},Av_{1},\ldots ,A^{m-1}v_{1}\right\}}
K
m
(
A
T
,
w
1
)
=
s
p
a
n
{
w
1
,
A
T
w
1
,
…
,
(
A
T
)
m
−
1
v
1
}
{\displaystyle {\mathcal {K}}_{m}\left(A^{T},w_{1}\right)=\mathrm {span} \left\{w_{1},A^{T}w_{1},\ldots ,\left(A^{T}\right)^{m-1}v_{1}\right\}}
Per construir aquestes bases biortogonals en els subespais
K
m
(
A
,
v
1
)
{\displaystyle {\mathcal {K}}_{m}\left(A,v_{1}\right)}
K
m
(
A
T
,
w
1
)
{\displaystyle {\mathcal {K}}_{m}\left(A^{T},w_{1}\right)}
Després d'usar aquest algorisme es garanteix en aritmètica exacta que
(
v
i
,
w
j
)
=
0
{\displaystyle \left(v_{i},w_{j}\right)=0}
i
≠
j
{\displaystyle i\neq j}
(
v
i
,
w
j
)
=
1
{\displaystyle \left(v_{i},w_{j}\right)=1}
i
=
j
{\displaystyle i=j}
α
j
{\displaystyle \alpha _{j}}
β
j
{\displaystyle \beta _{j}}
δ
j
{\displaystyle \delta _{j}}
T
m
{\displaystyle T_{m}}
T
m
=
(
α
1
β
2
0
…
0
δ
2
α
2
β
3
0
0
⋱
⋱
⋱
⋮
0
…
δ
m
−
1
α
m
−
1
β
m
0
…
0
δ
m
α
m
)
{\displaystyle T_{m}=\left({\begin{array}{ccccc}\alpha _{1}&\beta _{2}&0&\ldots &0\\\delta _{2}&\alpha _{2}&\beta _{3}&&0\\0&\ddots &\ddots &\ddots &\vdots \\0&\ldots &\delta _{m-1}&\alpha _{m-1}&\beta _{m}\\0&\ldots &0&\delta _{m}&\alpha _{m}\end{array}}\right)}
Algorisme Quasi-Minimal Residual
modifica
Es construeix la matriu
T
¯
m
{\displaystyle {\overline {T}}_{m}}
T
¯
m
=
(
T
m
δ
m
+
1
e
m
T
)
{\displaystyle {\overline {T}}_{m}=\left({\begin{array}{c}T_{m}\\\delta _{m+1}e_{m}^{T}\end{array}}\right)}
factorització QR , la qual s'obté aplicant les rotacions
Ω
i
{\displaystyle \Omega _{i}}
Ω
i
=
(
I
i
−
1
0
0
0
c
i
s
1
−
s
i
c
i
0
0
0
I
n
−
(
i
+
1
)
)
{\displaystyle \Omega _{i}=\left({\begin{array}{ccc}I_{i-1}&0&0\\0&{\begin{array}{cc}c_{i}&s_{1}\\-s_{i}&c_{i}\end{array}}&0\\0&0&I_{n-(i+1)}\end{array}}\right)}
on
c
i
{\displaystyle c_{i}}
s
i
{\displaystyle s_{i}}
s
i
=
a
i
+
1
,
i
(
a
i
i
(
i
−
1
)
)
2
+
a
i
+
1
,
i
2
,
c
i
=
a
i
i
(
i
−
1
)
(
a
i
i
(
i
−
1
)
)
2
+
a
i
+
1
,
i
2
{\displaystyle s_{i}={\frac {a_{i+1,i}}{\sqrt {\left(a_{ii}^{(i-1)}\right)^{2}+a_{i+1,i}^{2}}}},\quad c_{i}={\frac {a_{ii}^{(i-1)}}{\sqrt {\left(a_{ii}^{(i-1)}\right)^{2}+a_{i+1,i}^{2}}}}}
a
i
i
(
i
−
1
)
{\displaystyle a_{ii}^{(i-1)}}
a
i
+
1
,
i
{\displaystyle a_{i+1,i}}
Ω
1
,
…
,
Ω
i
−
1
{\displaystyle \Omega _{1},\ldots ,\Omega _{i-1}}
