关于Kaczmarz算法的一个注记
梁茂林; 代丽芳
【期刊名称】《《天水师范学院学报》》 【年(卷),期】2019(039)005 【总页数】2页(P118-119)
【关键词】Kaczmarz算法; 向量; 超平面; 最小二乘 【作 者】梁茂林; 代丽芳
【作者单位】天水师范学院 数学与统计学院 甘肃 天水 741001 【正文语种】中 文 【中图分类】O241.6
1 预备知识
线性方程组在工程和科学计算中扮演着重要角色，比如许多偏微分方程离散化后往往可以表示为此种形式[1,2].随着人们对运算精度要求的不断提高，网格剖分越来越精细，所导出的线性方程组往往是大规模稀疏的，如果运用直接方法求解此类问题是不可行的，而迭代法由于其存储量和运算速度的优势受到人们的青睐，从而涌现出了求解线性方程组的许多迭代算法，一些经典算法见文献[2-6]. 值得一提的是，Kaczmarz 算法是求解线性方程组的一类重要方法[5]，有关该算法进一步的研究及其推广非常深入，如文献[6-8]等，但是少有关于经典Kaczmarz 算法原理方面的讨论. 本文利用向量内积的性质和矩阵广义逆的有关理论，分别从几何和矩阵论
角度研究了Kaczmarz 算法的迭代原理. 给定线性方程组
其中系数矩阵
经典的Kaczmarz 算法的基本思想是，对于任意给定的初值x(0)，将其投影到线性方程组(1)中的第一个方程α1T x=b1 的解集合中，得到x(1)；然后将x(1)投影到方程(1)中的第二个方程α2T x=b2，得到x(2)；如此循环直到得到满意的结果. 对于i ∈{1,2,…,m}，Kaczmarz算法的第k 步迭代格式如下：这里符号＜·,·＞表示两个向量的内积，‖ ‖· 表示向量的2-范数.
2 主要结果
2.1 利用向量内积的性质
对给定α ∈Rn,d ∈R，根据Kaczmarz 算法的迭代步(2)，我们只需要考虑如下问题：将任意点z ∈Rn 投影到超平面αT x=d 内，记其投影点为P(z). 事实上,由超平面方程αT x=d 可得，
上式说明向量α 与向量β-x 正交,其中后者显然满足方程αT x=d.因此，我们可以得到如图一中的位置关系，其中CB所在加粗直线代表超平面方程αT x=d，而α 为其法向量，OA→ 表示初始向量z，OC→ 表示向量β，且与向量α 共线，则OB→ 表示点z 在超平面αT x=d 上的投影P(z). 图1 点Z在超平面内的投影示意图 在ΔABC 中，依据向量的加法法则可得
接下来需要求得向量的长度. 为此连接CA，从而根据内积的定义有 |A→B |=|C →D |=|C →A |cos∠DC . 另一方面，所以根据向量内积的性质有
结合式(3)可得点z 在超平面αT x=d 上的投影P(z)为
由式(4)可得Kaczmarz算法的迭代格式(2). 2.2 利用最小二乘理论
对于上述给定的α ∈Rn ,d ∈R ，将任意点z ∈Rn投影到超平面αT x=d 的投影等价于逼近问题
的极小范数解.根据矩阵广义逆的性质知[9]，非零向量α ∈Rn 的 广 义 逆 表 达 式 为，则 方 程αT y=d 的一般解为
其中w ∈Rn为任意向量，In 表示n 阶单位矩阵.将式(6)代入式(5)，则有
这是一个以w 为未知量的经典最小二乘问题.根据广义逆矩阵相关理论可知，其极小范数最小二乘解，即为点z 在超平面αT x=d 上的投影P(z)，且可以表示为
容易验证矩阵为投影矩阵，则
从而，上式可以简化为
显然，得到了与(4)式中相同的表达式.
【相关文献】
[1] J.DEMMEL.Applied numerical linear algebra[M].SIAM,Philadelphia,1997.
[2] G.H.GOLUB,C.F.VAN LOAN.Matrix computations[M].4th edn.Johns Hopkins University Press,Baltimore,2013.
[3] C.BREZINSKI.Projection methods for systems of equations[M].Elsevier Science,Amsterdam,1997.
[4] M.A.BROOKS.A survey of algebraic algorithms in computerized tomography[M].MSc.thesis,University of Ontario Institute of Technology,Oshawa,Ontario,2010.
[5] S.KACZMARZ.Angen aherte auflösung von systemen linearer gleichungen[J].Bull.Int.Acad.Polon.Sci.Lett.1937,(35):355-357.
[6] STROHMER,R.VERSHYNIN.A randomized Kaczmarz algorithm with exponential convergence,J.Fourier Anal.Appl,2009,(15):262-278.
[7] Z.-Z.BAI,W.-T.Wu,On convergence rate of the randomized Kaczmarz method,Linear Algebra Appl.,2018:252-269.
[8] Z.- Z.BAI,W.- T.Wu,On greedy randomized Kaczmarzmethod for solving large sparse linear systems,SIAM J.Sci.Comput.,2018,(40):A592-A606. [9] 王国荣.矩阵与算子广义逆[M].北京:科学出版社,1998.
