求解一般椭圆问
的交替方向迭代法
刘 蕴 贤
( )山东大学数学与系统科学学院 ,山东 济南 250100
5 5 u J ( ( ) ) ( ) ( ) 摘要 :对多维一般椭圆问题 - a x = f x , x ? D = 0 , 1, 采用两ij 5 x 5 x ij
层迭代格式给出其交替方向求解方法 , 并证明了该格式的收敛性 .
关键词 :交替方向 ; 迭代 ; 收敛性
中图分类号 :O241 . 82文献标识码 :A
0 引言
考虑矩形区域上的一般椭圆问题 :
5 5 u J )( ( ( )( )x ( ) - a ) Ω 0 . 1 = f x , x ?= 0 , 1, ij 5 x 5 x ij
( )0 . 2 u | = 0 . Ω 5
[ 1 ] Galerki n 方法是求解椭圆问题的一种很有用的方法, 但 Galerki n 方法求解椭圆问
[ 2 ] 题的美中不足之处在于计算量和存储量是很大的 . 由此 ,Do ugla s ,Dupo nt 在用交替方向 格式求解抛物型方程的基础上 , 提出了求解椭圆问题的交替方向迭代格式 , 使原来的多维 问题化为多个一维问题迭代求解 , 大大地减少了计算量和存储量.
[ 2 ] Do ugla s ,Dupo nt 已给出了一般二维椭圆方程及高维 L ap lace 方程的迭代格式. 本文 进一步给出一般高维椭圆问题的二层迭代格式 .
( ) 在研究方程 0 . 1时 , 我们假设 22 J ( )ξξαξξ0 . 3 αξ ? a 0 < | | ?| | , Π0 ?? R. ij i j0 1
ε本文中 , C ,分别代
一个一般常数和一个一般小正数 , 在不同地方有不同含义 .
收稿日期 :1999 206 208
( )基金项目 :国家自然科学基金资助项目 10972039
( ) 作者简介 :刘蕴贤 1974 - , 汉 , 女 , 博士 , 主要从事偏微分方程数值解法的研究.
1 二层迭代格式
原方程的弱形式为 :
5 u 5 v 1 ( )( ( ) a) (Ω) 1 . 1 = f , v , Π v ? H. ij , 0 5 x 5 xi j
为能够使用交替方向格式迭代求解原方程 , 需选有限维子空间 M 的基底为张量积的
2 N 1 i ( )α( ) α( ) < ( ) x , ?,x } H[ 0 , 1 ] , i = 0 i i i i i 1
? 1 , ?, J . 令 M = M M ? ? ? M . x 1 x 2xJ
原方程的 Galerki n 逼近格式为
5 U 5 V ( ) ( ) ( )a= f , V , ΠV ? M . 1 . 2 , ij 5 x 5 xji
J Ki ηα) ( ) ( 令 U = x. K= 1 , ?, N , 则 1 . 2可以写成 k k ?kii i i ?? 1 2 Ji = 1
( )η 1 . 3 B= < , l l ?l 1 2 J( ) 其中 , B = ?{ 1 , 2 , ?, N } , b , l, KKK?Ki i i1 2 J lKKK l l J1 2 J1 2 (αα)(αα)αα5 ? 5 ? l l ?l1 2 J 1 2 J 1 2 J( )b =1 . 4 KK?K , a, 1 2 J ij5 x 5 x ij
l l l 1 2J( )( αα) α1 . 5 = f ,?. < 1 2 J l l ?l1 2 J
( ) ( ) 由 1 . 1, 1 . 2可得
1 1 ‖u - U ‖? C ‖u - u ‖. ( )`1 . 6 HH0 0
u 取为 u 在 M 中的投影 . `
[ 2 , 3 ] ( ) 现在利用有限维子空间 M 给出 1 . 3的两层迭代格式. 外层迭代格式如下所述
n +1 n n η( )) Aηρ( η1 . 7 `<, = A- B- n
ρ其中 ,为迭代参数 , n
A = Q + Q + ? + Q, 1 2 J
? ? A ? ? ? C, Q= C? ? ? i = 1 , ?, J , CC i J i 1 i - 1i +1
Kl i i αα ddi iKl ii(α, ) , K, l ?{ 1 , 2 , ?, N } , C= , a , A = ii i i ii x ii dxdx i ix i
1 (αβ) βα,= d x . x i i ? 0
( ) 我们不直接来求解 1 . 7, 而采用一内层迭代格式求解. 令
n n Φρ( η) ( )= - B-<, 1 . 8 n
则有
n +1 n n ηη) Φ(A `- = . ( )1 . 9
β λ对 A= < , 2 ] 中已证明存在 使得如下迭代格式
J 1 n - 1 n n - 1 λ ( ) (ββ)( )βD+= < 1 . 10 + AE- i i ? λ i = 1
λλ收敛 , 取 为 [ 2 ] 中参数序列{} 中任意一个 , 其中 l
D= I ? ? ? I ? C? I ? ? ? I , i i
? I ? ? ? I . i = 1 , ?, J . E= I ? ? ? I ? A i i
( ) n +1 n 0(ηη) ( ) ( ) 从而可选初值 `- = 0 , 利用迭代格式 1 . 10来求解 1 . 9. 2 收敛性
由 [ 2 ] 知 , J 1 1 n +1 n +1 - 1 K n +1 n ( ηη( ) ) (ηη) `- ( )= I - D+ EA - .2 . 1 `i i ?λ λ i = 1
记 J 1 1 - 1 K ( ( ) ) Λ( )2 . 2 I - D+ EA = ,i i K ?λ λ i = 1
( ) 则 2 . 1可写成
n +1 n n +1 n +1 Λ(ηη) ( ) (ηη)= - ,2 . 3 ``- K
从而
n +1 n n +1 n Λ) (ηη) (ηη)`- .( )- ( 2 . 4 = I - K
记
- 1 Λ) ,( G = A I - K
则有
n +1 n n ( )ηηρ( η) 2 . 5 G= G- B- <.
- 1/ 2 - 1/ 2下面证明 G 是 Hermite 矩阵. 首先 , G 为 Hermite 矩阵等价于 A GA ( = I -
1/ 2- 1/ 2- 1 1/ 2- 1/ 2 Λ) ΛΛA A 是 Hermite 矩阵 , 即等价于 A A 是 Hertime 矩阵. 又 可以展开为 KKK J J 1 1 1 1 - 1 K - 1 K ( Λ( ( ) )) ( ( ) ) = I - K D+ EA + ? + - 1D+ EA ,Ki i i i ??λ λ λ λ i = 1i = 1若令 J 1 1 - 1 ( ) D= + E,F i i ?λ λ i = 1
则
K K Λ ( )) ( ( ) K FA = I - ? + - 1FA . + K 1/ 2 1/ 2 1/ 2- 1/ 2 1/ 2 1/ 2( )ΛK A FA A A = I - ( ( ) ) ( ) K+ K K - 1/ 2 A FA FA + ? +
K - 1个 FA 相乘 K1/ 2 1/ 2 ( ) 1A -FA FA ?FA FA . 1/ 2- 1/ 2 Λ显然 , A A 为 Hermite 矩阵 , 即 G 为 Hermite 矩阵. 由 [ 2 , P] 的分析知 , K203
( ζζ) B,( )( δ)α( δ)α2 . 6 ? [ 1 - , 1 + . 0 1 ( ζζ) G,
1/ 2 1 ζ( ζζ) 如果记 z 为与向量相关的函数 , 则 ‖azz ‖与 G,都等价于 ‖z ‖ , 从而 ijx x 2 H 0 j i
N ρ( ) 由 [ 4 ] 知存在参数序列{} 可取为 Che byshev 迭代参数, 使得 1 n
N 0 1 1 ( )ε2 . 7 ‖U - U‖?‖U - U ‖. HH0 0
( ) ( ) ( ) 由 1 . 6, 格式 1 . 10的收敛性 , 2 . 7及三角不等式知两层迭代计算格式是收敛的 . ( ) ( ) 定理 :设 u 为原方程的解 , U 是由外层迭代格式 1 . 7结合内层迭代格式 1 . 10的两 层迭代格式而得的解 , 则误差 u - U 收敛.
2( ) ) ( ( 下面给出两层迭代格式的工作量估计 , 格式 1 . 10每一次迭代需 O N 步操作 其
) (( ) )( ) 中 , N = max { N , N , ?, N } , 共需 O log N N ?N 迭代才能收敛 , 格式 1 . 7需 i 1 2 J 1 2 J
1 1 2 () ( ( ) ) O log 次迭代收敛 . 从而 , O N l?og N N ?N l?og 次操作使两层迭代格式有1 2 J ε ε
( ) 2 . 7的收敛.
致谢 :作者在此诚谢山东大学数学院袁益让教授的悉心指导.
参考文献 :
1 Aubin J P . Behavior of the Error of the Approximate Solutions of Boundary Value Problems for Linear Elliptic Operators by Galerkin and Finite2difference Methods J . Annali della scuola normale superiore di pisa . 1967 ,21 :599 ,637 . 2 Douglas J J r ,Dupont T. Alternating Direction Galerkin Method on Rectangles A . Symposium on Numerical Solution of Par 2 tial Differential Equation 2 C ,B . Hubbarded ,New York :Academic Press ,1971 ,133 ,214 .
3 Gunn J E. The Numerical Solution of A?a A u = f by a Semi2explicit Alternating2Direction Iterative Method J ,Numer Math . ,1964 ,6 :181,184 .
4 Dupont T , Kendall R P ,Rachford H H J r . An Approximate Factorization Procedure for Solving Self2adjoint Elliptic Differ2 ence Equations J . SIAM J Numer Anal . 1968 ,5 :559 ,573 .
AL TERNATIN G2DIRECTION ITERATIV E METHOD
FOR GEN ERAL ELL IPTIC EQAUTION
L IU Yun2xian
( School of M at hem atics and S ystem Science ,
)S handong Univ . , J i nan 250100 , S handong , Chi na
Abstract :Two2level alternating2direction iterative methods are given to treat the general multi2
5 5 u ( ) )= f x , and the convergence of the two2level ( ( )dimensional elliptic p roblem - a x ij 5 x5 x ij
p rocedure is demonstrated .
Key words :alternating direction ;iteration ;convergence