關于Kaczmarz算法的一個注記

梁茂林，代麗芳

（天水師范學院 數(shù)學與統(tǒng)計學院，甘肅 天水741001）

1 預備知識

線性方程組在工程和科學計算中扮演著重要角色，比如許多偏微分方程離散化后往往可以表示為此種形式[1,2].隨著人們對運算精度要求的不斷提高，網(wǎng)格剖分越來越精細，所導出的線性方程組往往是大規(guī)模稀疏的，如果運用直接方法求解此類問題是不可行的，而迭代法由于其存儲量和運算速度的優(yōu)勢受到人們的青睞，從而涌現(xiàn)出了求解線性方程組的許多迭代算法，一些經(jīng)典算法見文獻[2-6]. 值得一提的是，Kaczmarz 算法是求解線性方程組的一類重要方法[5]，有關該算法進一步的研究及其推廣非常深入，如文獻[6-8]等，但是少有關于經(jīng)典Kaczmarz 算法原理方面的討論. 本文利用向量內(nèi)積的性質(zhì)和矩陣廣義逆的有關理論，分別從幾何和矩陣論角度研究了Kaczmarz 算法的迭代原理.

給定線性方程組

經(jīng)典的Kaczmarz 算法的基本思想是，對于任意給定的初值x(0)，將其投影到線性方程組(1)中的第一個方程α1Tx=b1的解集合中，得到x(1)；然后將x(1)投影到方程(1)中的第二個方程α2Tx=b2，得到x(2)；如此循環(huán)直到得到滿意的結果. 對于i ∈{1,2,…,m}，Kaczmarz算法的第k 步迭代格式如下：這里符號＜·,·＞表示兩個向量的內(nèi)積，‖ ‖· 表示向量的2-范數(shù).

2 主要結果

2.1 利用向量內(nèi)積的性質(zhì)

對給定α ∈Rn,d ∈R，根據(jù)Kaczmarz 算法的迭代步(2)，我們只需要考慮如下問題：將任意點z ∈Rn投影到超平面αTx=d 內(nèi)，記其投影點為P(z).

事實上,由超平面方程αTx=d 可得，

圖1 點Z在超平面內(nèi)的投影示意圖

在ΔABC 中，依據(jù)向量的加法法則可得

|A→B |=|C →D |=|C →A |cos∠DC .

結合式(3)可得點z 在超平面αTx=d 上的投影P(z)為

由式(4)可得Kaczmarz算法的迭代格式(2).

2.2 利用最小二乘理論

對于上述給定的α ∈Rn,d ∈R ，將任意點z ∈Rn投影到超平面αTx=d 的投影等價于逼近問題

的極小范數(shù)解.根據(jù)矩陣廣義逆的性質(zhì)知[9]，非零向量α ∈Rn的 廣 義 逆 表 達 式 為，則 方 程αTy=d 的一般解為

其中w ∈Rn為任意向量，In表示n 階單位矩陣.將式(6)代入式(5)，則有

這是一個以w 為未知量的經(jīng)典最小二乘問題.根據(jù)廣義逆矩陣相關理論可知，其極小范數(shù)最小二乘解，即為點z 在超平面αTx=d 上的投影P(z)，且可以表示為

從而，上式可以簡化為

顯然，得到了與(4)式中相同的表達式.