论文标题
向后误误分析兰开斯双音节化，并重新定义
Backward error analysis of the Lanczos bidiagonalization with reorthogonalization
论文作者
论文摘要
$ k $ step lanczos bidiagonalizatization降低了一个矩阵$ a \ in \ mathbb {r}^{m \ times n} $中的bidiagonal form $ b_k \ in \ in \ mathbb {r} $ u_ {k+1} \ in \ mathbb {r}^{m \ times（k+1）} $和$ v_ {k+1} \ in \ mathbb {r}^n \ times {n \ times {（k+1）}}} $。但是，该算法的任何实际实施都遭受$ u_ {k+1} $和$ v_ {k+1} $的正交性损失，这是由于存在四舍五入错误，并且提出了几种重组策略，以维持某种水平的正交性。在本文中，通过以一般形式编写各种重新安装策略，我们对兰开斯比二拟化作用进行了向后的误差分析（LBRO）。我们的结果表明，$ k $ step lbro $ a $的计算$ b_k $与启动矢量$ b $是由$ k $ - step lanczos lanczos bidiagonalization $ a+e $与启动vector $ b+b+δ_{b} $（lb e+a+e e+e e e e+e e e a+e e a+efuly）所产生的$ b_k $。向量/矩阵$δ_{b} $和$ e $取决于$ u_ {k+1} $和$ v_ {k+1} $的圆形单位和正交级别。结果还表明，$ u_ {k+1} - \ bar {u} _ {k+1} $和$ v_ {k+1} - \ bar {v} _ {k+1} $由$ u__ {k+1} $ u_ {k+1} $ v _ {k+1}控制， $ \ bar {u} _ {k+1} $和$ \ bar {v} _ {k+1} $是由$ k $ -Step lb（$ a+e，b+e，b+δ_{b} $）生成的两个正式矩阵，因此，只要$ u_ {k+1} $和$ v_ {k+1} $的正交性就足够好，$ k $ - 步骤lbro是混合的前向稳定稳定的。我们使用此结果来研究基于LBRO的SVD计算算法和LSQR算法的向后稳定性。进行数值实验以确认我们的结果。
The $k$-step Lanczos bidiagonalization reduces a matrix $A\in\mathbb{R}^{m\times n}$ into a bidiagonal form $B_k\in\mathbb{R}^{(k+1)\times k}$ while generates two orthonormal matrices $U_{k+1}\in\mathbb{R}^{m\times (k+1)}$ and $V_{k+1}\in\mathbb{R}^{n\times {(k+1)}}$. However, any practical implementation of the algorithm suffers from loss of orthogonality of $U_{k+1}$ and $V_{k+1}$ due to the presence of rounding errors, and several reorthogonalization strategies are proposed to maintain some level of orthogonality. In this paper, by writing various reorthogonalization strategies in a general form we make a backward error analysis of the Lanczos bidiagonalization with reorthogonalization (LBRO). Our results show that the computed $B_k$ by the $k$-step LBRO of $A$ with starting vector $b$ is the exact one generated by the $k$-step Lanczos bidiagonalization of $A+E$ with starting vector $b+δ_{b}$ (denoted by LB($A+E,b+δ_{b}$)), where the 2-norm of perturbation vector/matrix $δ_{b}$ and $E$ depend on the roundoff unit and orthogonality levels of $U_{k+1}$ and $V_{k+1}$. The results also show that the 2-norm of $U_{k+1}-\bar{U}_{k+1}$ and $V_{k+1}-\bar{V}_{k+1}$ are controlled by the orthogonality levels of $U_{k+1}$ and $V_{k+1}$, respectively, where $\bar{U}_{k+1}$ and $\bar{V}_{k+1}$ are the two orthonormal matrices generated by the $k$-step LB($A+E,b+δ_{b}$) in exact arithmetic. Thus the $k$-step LBRO is mixed forward-backward stable as long as the orthogonality of $U_{k+1}$ and $V_{k+1}$ are good enough. We use this result to investigate the backward stability of LBRO based SVD computation algorithm and LSQR algorithm. Numerical experiments are made to confirm our results.
