LAPACK xgeqr2.f 算法总结推导

2024-02-24 03:44

本文主要是介绍LAPACK xgeqr2.f 算法总结推导,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

以 DGEQR2 函数为例,其分为两步:

先计算Householder vector,调用了 DLARFG(  )

然后实施了Householder 变换,调用了 DLARF(  )

接下来先分析DLARFG(  )的算法

源代码如下:

*> \brief \b DLARFG generates an elementary reflector (Householder matrix).
*
*  =========== DOCUMENTATION ===========
*
* Online html documentation available at
*            http://www.netlib.org/lapack/explore-html/
*
*> \htmlonly
*> Download DLARFG + dependencies
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/dlarfg.f">
*> [TGZ]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/dlarfg.f">
*> [ZIP]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/dlarfg.f">
*> [TXT]</a>
*> \endhtmlonly
*
*  Definition:
*  ===========
*
*       SUBROUTINE DLARFG( N, ALPHA, X, INCX, TAU )
*
*       .. Scalar Arguments ..
*       INTEGER            INCX, N
*       DOUBLE PRECISION   ALPHA, TAU
*       ..
*       .. Array Arguments ..
*       DOUBLE PRECISION   X( * )
*       ..
*
*
*> \par Purpose:
*  =============
*>
*> \verbatim
*>
*> DLARFG generates a real elementary reflector H of order n, such
*> that
*>
*>       H * ( alpha ) = ( beta ),   H**T * H = I.
*>           (   x   )   (   0  )
*>
*> where alpha and beta are scalars, and x is an (n-1)-element real
*> vector. H is represented in the form
*>
*>       H = I - tau * ( 1 ) * ( 1 v**T ) ,
*>                     ( v )
*>
*> where tau is a real scalar and v is a real (n-1)-element
*> vector.
*>
*> If the elements of x are all zero, then tau = 0 and H is taken to be
*> the unit matrix.
*>
*> Otherwise  1 <= tau <= 2.
*> \endverbatim
*
*  Arguments:
*  ==========
*
*> \param[in] N
*> \verbatim
*>          N is INTEGER
*>          The order of the elementary reflector.
*> \endverbatim
*>
*> \param[in,out] ALPHA
*> \verbatim
*>          ALPHA is DOUBLE PRECISION
*>          On entry, the value alpha.
*>          On exit, it is overwritten with the value beta.
*> \endverbatim
*>
*> \param[in,out] X
*> \verbatim
*>          X is DOUBLE PRECISION array, dimension
*>                         (1+(N-2)*abs(INCX))
*>          On entry, the vector x.
*>          On exit, it is overwritten with the vector v.
*> \endverbatim
*>
*> \param[in] INCX
*> \verbatim
*>          INCX is INTEGER
*>          The increment between elements of X. INCX > 0.
*> \endverbatim
*>
*> \param[out] TAU
*> \verbatim
*>          TAU is DOUBLE PRECISION
*>          The value tau.
*> \endverbatim
*
*  Authors:
*  ========
*
*> \author Univ. of Tennessee
*> \author Univ. of California Berkeley
*> \author Univ. of Colorado Denver
*> \author NAG Ltd.
*                                                                   
*> \ingroup doubleOTHERauxiliary
*
*  =====================================================================SUBROUTINE DLARFG( N, ALPHA, X, INCX, TAU )
*
*  -- LAPACK auxiliary routine --
*  -- LAPACK is a software package provided by Univ. of Tennessee,    --
*  -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
*
*     .. Scalar Arguments ..INTEGER            INCX, NDOUBLE PRECISION   ALPHA, TAU
*     ..
*     .. Array Arguments ..DOUBLE PRECISION   X( * )
*     ..
*
*  =====================================================================
*
*     .. Parameters ..DOUBLE PRECISION   ONE, ZEROPARAMETER          ( ONE = 1.0D+0, ZERO = 0.0D+0 )
*     ..
*     .. Local Scalars ..INTEGER            J, KNTDOUBLE PRECISION   BETA, RSAFMN, SAFMIN, XNORM
*     ..
*     .. External Functions ..DOUBLE PRECISION   DLAMCH, DLAPY2, DNRM2EXTERNAL           DLAMCH, DLAPY2, DNRM2
*     ..
*     .. Intrinsic Functions ..INTRINSIC          ABS, SIGN
*     ..
*     .. External Subroutines ..EXTERNAL           DSCAL
*     ..
*     .. Executable Statements ..
*IF( N.LE.1 ) THENTAU = ZERORETURNEND IF
*XNORM = DNRM2( N-1, X, INCX )
*IF( XNORM.EQ.ZERO ) THEN
*
*        H  =  I
*TAU = ZEROELSE
*
*        general case
*BETA = -SIGN( DLAPY2( ALPHA, XNORM ), ALPHA )SAFMIN = DLAMCH( 'S' ) / DLAMCH( 'E' )KNT = 0IF( ABS( BETA ).LT.SAFMIN ) THEN
*
*           XNORM, BETA may be inaccurate; scale X and recompute them
*RSAFMN = ONE / SAFMIN10       CONTINUEKNT = KNT + 1CALL DSCAL( N-1, RSAFMN, X, INCX )BETA = BETA*RSAFMNALPHA = ALPHA*RSAFMNIF( (ABS( BETA ).LT.SAFMIN) .AND. (KNT .LT. 20) )$         GO TO 10
*
*           New BETA is at most 1, at least SAFMIN
*XNORM = DNRM2( N-1, X, INCX )BETA = -SIGN( DLAPY2( ALPHA, XNORM ), ALPHA )END IFTAU = ( BETA-ALPHA ) / BETACALL DSCAL( N-1, ONE / ( ALPHA-BETA ), X, INCX )
*
*        If ALPHA is subnormal, it may lose relative accuracy
*DO 20 J = 1, KNTBETA = BETA*SAFMIN20      CONTINUEALPHA = BETAEND IF
*RETURN
*
*     End of DLARFG
*END

摘取将其常规运算部分归结如下,并加入了注释:

*   计算(x_1, x_2, ..., x_n-1)的模长norm,即 sqrt(x1*x1 + x2*x2 + ... xn-1*xn-1)XNORM = DNRM2( N-1, X, INCX )*   计算(x_0, x_1, x_2, ..., x_n-1)的模长,并且取符号正好与 x0 == ALPHA 的符号相反
*   其中的 DLAPY2(s, t) = sqrt(s*s + t*t);BETA = -SIGN( DLAPY2( ALPHA, XNORM ), ALPHA )*   按照Householder常规, TAU = 2.0/X^T*X = 2.0/(  1.0*1.0 + (x1/(ALPHA-BETA))**2 + (x2/(ALPHA-BETA))**2 + ... + (x_n-1/(ALPHA-BETA))**2  ) 然后就可以推导出 TAU = (BETA-ALPHA)/BETATAU = ( BETA-ALPHA ) / BETA
*   对 X 做缩放, st. 理念中的 X(0) == 1.0 ,但是下面语句中的 X 中只包含了从X(1) 到 X(n-1)CALL DSCAL( N-1, ONE / ( ALPHA-BETA ), X, INCX )
*   ALPHA 即 Y(0) = (Px)(0) = ((I - beta*V*V^T)x)(0) = Y(0)ALPHA = BETA

 

至此,这个Householder vector 就计算出来了。

效果相当于给定

X=\left[ \begin{array}{c} ALPHA\\ x_1\\ \vdots\\ x_{n-1}\\ \end{array} \right ]

计算出其Householder vector:

H=\left[ \begin{array}{c} 1.0\\ h_1\\ \vdots\\h_{n-1}\\ \end{array} \right ]

同时计算出了 Y=PX:

Y=H*X =\left[ \begin{array}{c} h_0\\ h_1=0\\ \vdots\\ h_{n-1}=0\\ \end{array} \right ]

其中 h_0 存储在变量 ALPHA 中了。

然后又利用 DLARF(  )将Householder vector 应用到了 A矩阵的剩余部分。

接下来分析 DLARF(  ) 的算法实现。

\documentclass{article}
\title{House}\begin{document}
\maketitle
After we calculated $v$ and $\beta$:
$$[v,\beta]= house(A(j:m, j))$$
we should update A by:
$$A = (I-\beta vv^T)A$$Let
$$v=
\left[\begin{array}{c}v_1\\v_2\\\vdots\\v_m\end{array}
\right]
$$
then,
$$vv^T=
\left[\begin{array}{cccc}v_1v_1 & v_1v_2 & \cdots & v_1v_m\\v_2v_1 & v_2v_2 & \cdots & v_2v_m\\\vdots & \vdots & \ddots & \vdots\\v_mv_1 & v_mv_2 & \cdots & v_mv_m\end{array}
\right]
$$As
$$
A = (I-\beta vv^T)A=A - \beta vv^TA
$$
to calculat $(vv^TA)$,
$$
vv^TA=v(v^TA)=
\left[\begin{array}{c}v_1\\v_2\\\vdots\\v_m\end{array}
\right]
\left[ \sum_{k=1}^m(v_ka_{k1}) \,\, \sum_{k=1}^m(v_ka_{k2}) \cdots \sum_{k=1}^m(v_ka_{kn})\right]
$$Let $b_j=\sum_{k=1}^m(v_ka_{kj})$$$
W=vv^TA=v(v^TA)=
\left[\begin{array}{c}v_1\\v_2\\\vdots\\v_m\end{array}
\right]
\left[b_1\,\,b_2 \cdots b_n\right]
=
\left[\begin{array}{cccc}v_1b_1 & v_1b_2 & \cdots & v_1b_n\\v_2b_1 & v_2b_2 & \cdots & v_2b_n\\\vdots & \vdots & \ddots & \vdots\\v_mb_1 & v_mb_2 & \cdots & v_mb_n\\\end{array}
\right]
$$
Then,
$$
A=(I-\beta vv^T)A = A-\beta vv^TA = A-\beta W
$$$\mathbf{Algrithm}\,\, of\,\, QR$:\\
For(J=1; J<M; j++)\\
....$[v, \beta] = house(A(J:M, J))$\\
....For j=J; j$\le$N; j++;\\
................$b_j=\sum_{k=j}^M(v_ka_k^j)$;\\
................for i=J; i$\le$M; i++;\\
....................$a_{ij} = a_{ij}-\beta v_ib_j$\\
....A(J+1:M, J) = v(2:M-J+1)\\
EndFor
\end{document}

这篇关于LAPACK xgeqr2.f 算法总结推导的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/740848

相关文章

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中连接不同数据库的方法总结

《Python中连接不同数据库的方法总结》在数据驱动的现代应用开发中,Python凭借其丰富的库和强大的生态系统,成为连接各种数据库的理想编程语言,下面我们就来看看如何使用Python实现连接常用的几... 目录一、连接mysql数据库二、连接PostgreSQL数据库三、连接SQLite数据库四、连接Mo

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》:本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push

Kubernetes常用命令大全近期总结

《Kubernetes常用命令大全近期总结》Kubernetes是用于大规模部署和管理这些容器的开源软件-在希腊语中,这个词还有“舵手”或“飞行员”的意思,使用Kubernetes(有时被称为“... 目录前言Kubernetes 的工作原理为什么要使用 Kubernetes?Kubernetes常用命令总

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Python中实现进度条的多种方法总结

《Python中实现进度条的多种方法总结》在Python编程中,进度条是一个非常有用的功能,它能让用户直观地了解任务的进度,提升用户体验,本文将介绍几种在Python中实现进度条的常用方法,并通过代码... 目录一、简单的打印方式二、使用tqdm库三、使用alive-progress库四、使用progres