光滑核緊積分算子特征值的多尺度Galerkin快速算法*

陳 劍，曾泰山

(1.佛山科學技術學院理學院數學系，廣東 佛山 528000；2.華南師范大學數學科學學院，廣東 廣州 510631)

設E:=[0,1], 記X：=L2(E), 算子K:X→X定義如下

其中K(t,s):E×E→R是一個光滑對稱核, 即

K(t,s)∈Ck(E×E),K(t,s)=K(s,t)

于是,K為X上的自共軛緊算子K參看[1])。 考慮K的特征值問題：

Ku(t)=λu(t)

(1)

其中數λ和向量u∈X,u≠0 是待求的特征值和相應的特征向量。特征值問題具有廣泛的實際應用背景, 在結構力學、工程設計、計算物理等諸多學科和技術領域都會遇到特征值問題。 設計一個有效的求解特征值問題的算法, 對科學計算和工程應用都有著巨大的意義。目前數值求解(1)的主要數值方法有: 有限元方法、(迭代)Galerkin方法、配置法、退化核方法以及外推法等等, 參看文獻[2-8]。 本文運用多尺度Galerkin方法來近似求解(1)的特征值, 由于所用的多尺度正交小波基底具有消失矩和緊支集(參看[9-11]), 使得離散所得矩陣數值稀疏(絕大部分元素小的可以忽略不計), 從而可以實現矩陣壓縮, 快速得到系數矩陣稀疏的線性方程組, 為后面矩陣特征值的求解提供極大的方便。

1 多尺度Galerkin格式

設Xn是L2(E)上的一個有限維子空間, 則求解 (1) 的 Galerkin 方法為：求數λn和向量un∈Xn,un≠0, 使得

(Kun,v)=λn(un,ν) ?ν∈Xn

(2)

其中 (·,·) 表示空間L2(E) 上的內積。

設μ≥2是一正整數, 我們取Xn為以j/μn,j-1∈Zμn-1為節點次數小于k的分片多項式空間, 其中ZN:={0,1,…,N-1}, 顯然dim(Xn)=kμn,Xn?Xn+1, 從而Xn可以寫成Xn-1與其在Xn中的正交補空間Wn的直和。記w(i)為空間Wi的維數。按照文獻[9-11]的構造方法, 我們得到Xn的一組具有k階消失矩和緊支集的多尺度正交小波基{wi,j:(i,j)∈Un},其中Un:={(i,j):i∈Zn+1,j∈Zw(i)}。 利用多尺度小波基, 可以將(2)的特征向量表示成

(3)

其中ci,j是待求系數。 將上式代入方程(2)中, 得到多尺度Galerkin格式：

(4)

定義

Kn:=[(wi′,j′,Kwi,j)](i′,j′),(i,j)∈Un,

En:=[(wi′,j′,wi,j)](i′,j′),(i,j)∈Un,

Cn:=[ci,j:(i,j)∈Un]

于是方程(4)可導出如下線性方程組

(Kn-λnEn)Cn=0

(5)

2 矩陣壓縮算法

引理1 存在正常數c>0, 使得

(6)

其中p(t,·)和q(s,·)分別表示t和s的次數低于k的多項式,

(1-θ)k-1(1-θ')k-1dθdθ'

其中0<θ′<1,0<θ<1.由于K(t,s)∈Ck([0,1]×[0,1]), 則存在M>0使

注意到wi,j和wi',j'具有k階消失矩, 從而

引理得證。

上述引理表明, 當i+i′ 比較大時, 矩陣元素Ki′,j′;i,j的絕對值非常小, 這使得我們可以采用相應的截斷策略。 為此, 我們將矩陣Kn按以下方式分塊

Kn:=[Ki′,i]i′,i∈Zn+1

其中Ki′,i=[Ki′,j′;i,j]j′∈Zw(i′),j∈Zw(i)。對塊矩陣Ki′,i我們給出如下壓縮策略,并將壓縮而產生的新的塊矩陣記為

其中

(8)

(9)

(10)

3 壓縮格式的收斂性和復雜性分析

引理2 存在一個與n無關的常數c>0,使得

‖Ki′,i‖2≤cμ-k(i+i′)

(11)

證明注意到w(i)～μi,w(i′)～μi′有

同理

于是

其中s(n)=dimXn=kμn。

證明對任意u,v∈L2[0,1], 有

其中P-1:=0。由Cauchy-Schwarz不等式可得

‖(Pi-Pi-1)u‖‖(Pi′-Pi′-1)v‖

注意到Pn為正交投影, 由引理2和截斷策略(8)可知

‖(Pi-Pi-1)u‖‖(Pi′-Pi′-1)v‖≤

因為

記c=c′c″, 于是

cμ-nklog(s(n))‖u‖

引理獲證。

從而

于是我們可以得到以下結論

定理1 存在一個與n無關的常數c>0, 使得

(12)

下面這個引理將在特征值誤差估計中被用到, 是一個很有用的結論(參看[1])。

(13)

(14)

證明由引理4有

‖K-Kn‖=‖K-PnK‖=

因為u∈Hk(E),Pn為正交投影,K為緊算子, 從而

‖(K-PnK)u‖≤c′μ-kn‖u‖Hk:=c″μ-kn

于是

定理得證。

下面我們討論壓縮格式的計算復雜度。記

其中

Ei′,i=[(wi′,j′,wi,j)]j′∈Zw(i′),j∈Zw(i)

定理3 存在兩個與n無關的常數c1>0,c2>0, 使得

從而

從而, 存在與n無關的常數c′>0, 使得

w(i′)×w(i)≤c′μi+i′

簡單計算可得

定理得證。

4 數值算例

考慮如下積分算子的最大特征值逼近

W1的基底為：

圖 1 采用截斷策略需要計算的矩陣元素(n=10)

表 1 多尺度Galerkin方法的數值結果

Table 1 Numerical results of multiscale Galerkin method

n| λn-λ|Conv.RateComp.Rate22.174e-051.00031.385e-063.972 30.75048.732e-083.987 80.50055.489e-093.991 70.31263.447e-103.992 70.18772.165e-113.992 60.10981.359e-123.993 50.062 598.992e-143.918 40.035 1109.992e-153.169 60.019 5

參考文獻：

[1]CHEN M, CHEN Z, CHEN G.Approximate solutions of operator equations [M].World Scientific Publishing Co, 1997.

[2]BABUSK I, OSBORN J.Eigenvalue problems, handbook of numercial analysis [M].II.Vol.llFinite Element Methods(PartI)，North-Holand, 1991.

[3]SLOAN I H.Iterated Galerkin method for eigenvalue problem [J].SIAM J Numer Anal, 1976, 13: 753-760.

[4]KULKARNI R P.A new superconvergent collocation method for eigenvalue problem [J].Comp Math, 2006,75: 847-857.

[5]CHEN Z, GNANESHWAR N, XU Y, et al.A fast collocation method for eigen-problems of weakly singular integral operators [J].J Sci Comput, 2009,41: 256-272.

[6]GNANESHWAR N.A degenerate kernel method for eigenvalue problems of compact integral operator [J].Adv Comput Math, 2007, 27: 339-354.

[7]KULKARNI R P.Use of extrapolation for improving the order of convergence of eigenelement approximations [J].IMA J Numer Anal, 1997,17: 271-284.

[8]CHEN Z, LONG G, GNANESHWAR N.Richardson extrapolation of iterated discrete projection methods for eigenvalue approximation [J].J Comp App Math, 2009, 223: 48-61.

[9]CHEN Z, MICCHELLI C A, XU Y.The Petrov-Galerkin methods for second kind integral equations II: multiwavelets scheme [J].Adv Comput Math, 1997, 7 : 199-233.

[10]黃敏.Fredholm第二型積分方程的小波Petrov-Galerkin算法[D].北京：中國科學院,2003.

[11]HUANG M.A construction of multiscale bases for Petrov-Galerkin methods for integral equations [J].Adv Comput Math, 2006, 25:7-22.