求解逆特征值问题的全局性非精确牛顿类方法.pdf

该【求解逆特征值问题的全局性非精确牛顿类方法 】是由【贾赦】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【求解逆特征值问题的全局性非精确牛顿类方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第卷第期浙江师范大学学报自然科学版
45年3月(),
20228 JournalofZhejiangNormalUniversity(.)
DOI
:.1001-
求解逆特征值问题的全局性非精确牛顿类方法
沈卫平,王悦
(浙江师范大学数学与计算机 科学学 院,浙江金华)
321004
摘要:为了研究求解逆特征值问题的全局性算法利用反幂法获得近似特征向量提出了一种求解逆特征值
,,
问题的全局性非精确牛顿类算法在一定的条件下给出了该全局算法的收敛性分析并且证明了该算法的超
.,,
线性二阶收敛性质最后通过数值例子进一步验证所提出算法的全局收敛性
/.,.
关键词:逆特征值问题非精确牛顿类方法反幂法全局收敛性
;;;
中图分类号:文献标识码:文章编号:()
A 1001-5051202203-0275-09
AgloballyconvergentinexactNewton-likemethod
forsolvinginverseeigenvalueproblems
,
SHENWeiping WANGYue
(CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,Jinhua,China)
321004
Abstract:,
InordertostudytheglobalalgorithmforsolvinginverseeigenvalueproblemsaglobalinexactNew-
ton-likealgorithmforsolvinginverseeigenvalueproblemswasproposedbyusingtheinversepowermethodto
-
,
ditonsthesuperlinear/second--
genceoftheproposedalgorithmwasfurtherverifiedbynumericalexamples.
Keywords:;;;
inverseeigenvalueprobleminexactNewton-likemethodinversepowermethodglobalconver-
gence
引言
0
多年以来众多数学工作者对如下逆特征值问题的理论分析和算法实现都表现出了极大的兴
,nn
趣[1-3]设Aii是n个实对称的nn阶矩阵对任意的ccccnTR定义
=1×=12
:{},n[,,…,]∈,
Ac=ciAi.
()i=(1)
1
n∑

=112
(){()},n()≤()≤…≤()n
如下对于给定的n个实特征值λi∗i且λ∗λ∗λn∗求向量c∗R使得
:{}=11≤2≤…≤,∈,
λc∗=λ∗i=n.
i()i, 1,2,…,
收文日期:修订日期:
2021-11-10;2021-12-07
基金项目:国家自然科学基金资助项目
(12071441)
作者简介:沈卫平女浙江湖州人教授博士研究方向非线性数值代数
(1979—),,,,.:.
浙江师范大学学报自然科学版年
276() 2022
称c∗
,Strum-Liouville′s、Toeplitz
问题核光谱和分子光谱问题反振弦问题等[4-16]
eigenvalue、、.
众所周知求解该逆特征值问题等价于求解如下非线性方程组问题[17-18]
,:
fc=λc-λ∗λc-λ∗λnc-λn∗T=.
()[1()1,2()2,…,()]0
基于这种等价关系求解一般非线性方程组的牛顿法可用于求解该逆特征值问题[19]虽然牛顿法的收
,.

,()

,,[19]Cayley.
较于牛顿法这种方法在保持二阶收敛速度的同时又避免了求解特征向量之后很多学者针对这
,2,.,2
种方法的收敛性及其非精确形式进行了研究[1-2,20]除了上述提到的方法外还有一些方法在降低运算
.,
的难度与加强算法的稳定性方面也有显著的成效例如文献中的类方法
,[3,21]Ulm.
但这些方法仅仅具有局部收敛性只有在解的附近选取初值才能保证迭代序列收敛基于文献
,.
中的变换法文献提出了一种求解逆特征值问题的全局性算法即使初值离解很远该
[19]Cayley,[22].,
全局算法产生的迭代序列也能收敛一个自然的问题是能否基于文献中的非精确牛顿类方
.,[1,19]()
法构造一种新的具有全局收敛性质的非精确牛顿类方法
,().
本文提出了一种用以求解逆特征值问题的全局性非精确牛顿类方法不同于文献中的全局算
.[22]
法本文的全局算法通过反幂法获得近似特征向量并采用经典回溯法进行全局化在一定的条件下给
,,.,
出了该全局算法的收敛性分析并证明了它的收敛阶最后通过数值例子验证了该算法的全局收敛性
,.,
质及其收敛阶
.
全局性非精确牛顿类方法
1
本节将构造一种全局收敛的非精确牛顿类方法为此定义符号为范数令λ∗λ∗λ∗
.,‖·‖2-,=[1,2,
λ∗T.
…,n]
算法1 全局性的非精确牛顿类方法
n

maxminmax
1)n∈[0,1),∈(1,2],∈(0,1),0<n<<1∈,()

{()}=1{()}=1
ρc0=ρc0ρc0ρnc0T=λc0λc0λnc0T
()[1(),2(),…,()][1(),2(),…,()];
P=p0p0p0n=qc0qc0qnc0.
0[1,2,…,][1(),2(),…,()]
计算雅可比矩阵Jc0其元素为
(),
Jc0ij=p0iTAjp0iijn.
[()](), 1≤,≤
求解雅可比方程
Jc0c1=λ∗.
()(2)
对于k直到ck收敛具体步骤如下
2)=1,2,…,:
非精确求解方程
①kkk-k
Ac-λi∗Ivi=pi1+tiin
[()], 1≤≤,(3)
得到vk直到残差tk满足
i,‖i‖
tk1in.
‖i‖≤, 1≤≤(4)
kn4kn
对vii进行标准化得到近似特征向量pii即
②{}=1{}=1,
vk
ki
pi=kin.
vi, 1≤≤
kn‖‖
计算近似特征值ρici即
=1
③{()},kkkk
ρic=piTAcpiin
kkk()k()(), 1≤≤,
且令ρcρcρcρncT.
()=[1(),2(),…,()]
第期沈卫平等求解逆特征值问题的全局性非精确牛顿类方法
3 ,:277
计算近似雅可比矩阵Jk其元素为
④,kk
J=pTApijn.
[k]ij(i)ji, 1≤,≤
非精确求解雅可比方程
⑤kk
Jc+ρc-λ∗=
kΔ()0,(5)
得到ck使其满足
􀭰
Δ,kkk
ρc-λ∗+Jcηρc-λ∗.
‖()kΔ‖≤k‖()‖
其中
,kβkβ
ρc-λ∗ρc-λ∗
ηk=‖()β‖‖(k-)‖βηk=.
min{λ∗,ρc1-λ∗,max}, 1,2,…(6)
‖‖‖()‖
重复步骤计算ρckck.
⑥①②③,(+Δ)
若
⑦kkk
ρc+c-λ∗-t-ηρc-λ∗
‖(Δ)‖≤(1(1k))‖()‖,(7)
kkkk

minmax
Δ=Δ,=,⑧(7),∈[,],ΔΔ,
.
--k
1(1)⑥k,⑦kk
计算下一个迭代点c+1cc.
⑧:=+Δ
注1
[22]
的算法利用反幂法得到近似特征向量而文献的算法则是基于变换求得近似特征向量
,[22]Cayley.
收敛性分析
2
n
接下来给出全局性非精确牛顿类方法的收敛性分析为此假设λici为矩阵Ac的特征
.,{()}=1()
nnn

,{()}=1{()}=1∈,(),
Jcij=qicTAjqicijn.
[()]((n))(), 1≤,≤
同文献一样假设给定的特征值λi∗i是互异的且雅可比矩阵Jc∗是可逆的.
[22],{}=1()

,1[23]47;23
明分别类似于文献中的引理及引理引理及引理的证明分别类似于文献中的引理.
[22]46;45[1]41
及引理..为了节省篇幅将其证明省略.
42,k
引理1[23]任意ε存在充分小的正数δ对任意kN当cδ时
00
>0,kk,k∈k,‖Δ‖k≤,
ρc+c-ρc-Jkcεc.
‖(Δ)()Δ‖≤‖Δ‖k
引理2[22]设kN则存在ηkmin使对任意的ηkηkmin存在c满足下面个不等式
∈,k∈[0,1),k∈[k,1),Δ2:
ρc-λ∗+Jkcηkρc-λ∗
k‖(k)Δ‖≤‖()k‖;(8)
ρc+c-λ∗-t-ηρc-λ∗.
‖(Δ)‖≤(1(1k))‖()‖(9)
引理3[22]假设kN且近似雅可比矩阵Jk可逆则
∈k,k
cτ-ηρc-λ∗.
‖Δ‖≤k(1k)‖()‖(10)
η
式中τ1+maxJ-1.
(10),k=η‖k‖
max
1-
引理4[1]
∈
kkk-k
λc-λ∗γ>ijnqcTp1+t1in
j()i≥0, 1≤≠≤; i()(ii)≥, 1≤≤,
4
则
kkk
p-qc8λc-λ∗in.
‖ii()‖≤γi()i, 1≤≤(11)
k
引理5[1]存在正数δξ与γ对任意kN当cc∗δ时下列式子成立
1,0,∈,‖-‖≤1,:
浙江师范大学学报自然科学版年
278() 2022
kk
λic-λi∗ξc-c∗in
0
k()≤‖k‖, 1≤≤;(12)
qic-qic∗ξc-c∗in
0
‖()k()‖≤‖‖, 1≤≤;(13)
λc-λ∗γ>ijn.
j()i≥0, 1≤≠≤(14)
下面给出的命题说明了在一定的条件下全局性非精确牛顿类方法产生的近似特征向量pk与
1,i
qc∗.
i()(1≤≤)
命题1 设K为任意正整数则存在正数δ及ξ不依赖于K若
121
K,K(),
p1-qc∗ξc1-c∗in
‖ii()‖≤‖‖, 1≤≤(15)
且
k
c-c∗δkK
‖‖≤2, ∀≥1,(16)
则对任意kK式式及下面个式子成立
≥1,(12)、(14)2:
kk
p-qc∗ξc-c∗in
‖ii()‖≤‖‖, 1≤≤;(17)
k+kk+
qc1Tp+t11in.
i()(ii)≥, 1≤≤(18)
4

0,15
ξ=8+ξδ=δ1.
(γ1)0, 2min{1,ξ+ξ}(19)
0

21,(15)(16)(16)2,

5,≥1,(12)~(14)≥1,

(17)(18),1≤≤,(15),=1,(17)
三角不等式有
,KK+KK+
p1-qc11p1-qc∗+qc∗-qc11.
‖ii()‖≤‖ii()‖‖i()i()‖(20)
于是结合式和式kK可得
=1+
,(15)(13K)(K1+)KK+
111111
pi-qicξc-c∗+ξc-c∗.
‖()‖≤‖‖0‖‖(21)
进一步再利用式和δ的定义容易推得
2
,(16),KK+
111
pi-qicξ+ξδ.
02
k‖k()‖≤()≤1
-
又因为对任意kNpi1与qic是标准化的向量所以
K∈K,+()KKK+,KK+K+K+K
p1-qc112p1Tp1-qc11Tp1+qc11Tqc11=-qc11Tp1
1≥‖ii()‖≥(i)i2i()ii()i()22i()i,
KK
即qc1+
i()i≥,(4),:
2
K+KK+K+K+K+K+
qc11Tp1+t111+qc11Tt111-qc11t111.
i()(ii)≥i()i≥‖i()‖‖i‖≥
224
从而当kK时式成立.
,=1,(18)

≤-1,(17)(18),4(12)(=),
llll
pi-qic8λic-λi∗8ξc-c∗.
‖()‖≤γ()≤γ0‖‖(22)
因此结合式及ξ的定义可得
,(13),
llllll
pi-qic∗pi-qic+qic-qic∗8+ξc-c∗=ξc-c∗.
‖()‖≤‖()‖‖()()‖≤(γ1)0‖‖‖‖

,=,(17)=,(18)=1,
.
,,1

,3,6
.
[1]44;78[22]79
第期沈卫平等求解逆特征值问题的全局性非精确牛顿类方法
3 ,:279
引理6[1]对任意kN由算法产生的近似雅可比矩阵Jk满足
∈,1k
Jkc∗-λ∗nλ∗pi-qic∗2.
∞in
‖‖≤2‖‖1m≤a≤x‖()‖(23)
k
引理7[22]∗0且近似雅可比矩阵J可逆则当算法中步骤的内循环
∈()-≠k,1⑦
停止时
,
δθ
-η-η0min.
k{kk}
1≥min1,τρc-λ∗(24)
k‖()‖
η
+max-
式中δ为充分小的正数τk1Jk1.
(24):0;=η‖‖
-max
k1k
引理8[22]假设序列c有定义且c∗∗可逆则存在正数
k {}{}(),
δ当piqic∗δ时Jk可逆且满足
3in3
,1m≤a≤x‖-()‖≤,
--
J1Jc∗1.
‖k‖≤2‖()‖(25)
下面给出本文的主要定理.
nkk
定理1 假设给定的特征值λi∗i是互异的序列c有定义且c∗是序列c的聚点雅可比矩
=1
{};{}{}k;
阵Jc∗∗δ且
4224
()K,K,≥,∈(,)
22
pi-qic∗ξc-c∗in
k‖k()‖≤‖k‖, 1≤≤,(26)
则当k时cc∗且ρcλ∗并且序列c至少具有β阶的收敛速度.
→∞,→()→,{}

3443
8;k≤,11
∗
22in3
,≥,(17),≥,1m≤a≤x‖-()‖≤,8,
kK时Jk可逆且式成立.
2
≥,(25)kk
∗则存在δδ和子列
54
{}→∞,→,∈(0,)
ktktk
c使得cBc∗∗是序列c的聚点故存在序列kjN使得当j
5=
{}k,∉(,),1,2,…klk{i},{}⊂,→∞
jj+jj+
时cc∗.选择lj满足kjljkjcBc∗δcBc∗
,→>0+<+1,∉(,5),∈(,5)(=0,1,…,-1)
+η-
τ=1maxJ1.
k-η‖k‖
1max
结合式可知对任意的kK
(25),≥2,
-+η
τJc∗11max.
k≤2‖()‖-η(27)
max
k+kk1
又因为c1=c+c所以存在充分大的正整数KK对任意的jK有
323
Δ,k+l-k+l≥-,≥,
jj1jj1
kj+ljkjkk
δc-ccτk-ηkρc-λ∗
5≤‖‖≤=‖Δ‖≤=(1)‖()‖≤
∑kkj∑kkj
k+l-
+ηjj1
-maxk
Jc∗11-ηkρc-λ∗
2‖()‖-ηk=k(1)‖()‖,(28)
1max∑j

23(9)
kkkk
-ηρc-λ∗1ρc-λ∗-ρc+c-λ∗kN.
(1k)‖()‖≤t(‖()‖‖(Δ)‖), ∀∈
因此
,k+l-k+l-
jj1jj1
kkkk
-ηkρc-λ∗1ρc-λ∗-ρc+c-λ∗=
k=k(1)‖()‖≤k=kt(‖()‖‖(Δ)‖)
∑j∑j
kjkj+lj
1ρc-λ∗-ρc-λ∗.
t(‖()‖‖()‖)(29)
另一方面因为tη所以由式可知
,,k∈(0,1),(9)
浙江师范大学学报自然科学版年
280() 2022
k+k
ρc1-λ∗ρc-λ∗kN.
‖()‖≤‖()‖, ∀∈
因此
,
kjkj+ljkjkj+
1ρc-λ∗-ρc-λ∗1ρc-λ∗-ρc1-λ∗.
t(‖()‖‖()‖)≤t(‖()‖‖()‖)(30)
于是结合式式有
,(28)~(30),
+η
kj+ljkj-kjkj+
δc-c2Jc∗11maxρc-λ∗-ρc1-λ∗.
5≤‖‖≤t‖()‖-η(‖()‖‖()‖)(31)
1max
kjkjkj
又因为当j时有cc∗所以ρcλ∗ρc+1λ∗.
→∞,k→,,‖()-‖-‖()-‖→0,,
从而当k时cc∗.
,→∞,→k
接下来证明当k时ρcλ∗.由定理条件并应用命题可得对任意kK式式
→∞,()→11,≥2,(12)、

(14)、(17)(18),4,≥2+1,
kkk
p-qc8λc-λ∗in.
‖ii()‖≤γi()i, 1≤≤(32)
因为
kkkkk
ρcλ∗nρicλi∗nρicλicλicλi∗
inin
‖()-‖≤1m≤a≤x()-≤1m≤a≤x(()-()+()-)≤
kkkkkkk
npiTAcpiqicTAcqicnλicλi∗
inin
1m≤a≤x()()-()()()+1m≤a≤x()-≤
kkkk
nAcpiqicnλicλi∗in
inin
21m≤a≤x(‖()‖·‖-()‖)+1m≤a≤x()-, 1≤≤,(33)
因此利用式式及式对任意kK
,(12)、(32)(33),≥2+1,
kkkk
ρc-λ∗nξ16Acc-c∗+nξc-c∗.
‖()‖≤0γ‖()‖·‖‖0‖‖(34)
又因为
n
kk/k
AcAc-Ac∗+Ac∗Ai212c-c∗+Ac∗
‖()‖≤‖()()‖‖()‖≤(i=‖‖)‖‖‖()‖,(35)
∑1
因此由式和式可推出
,(34)(35)kk
ρc-λ∗ρc-c∗kK+.
2
‖()n‖≤‖‖, ∀≥1(36)
é/ùk
ê212∗ú∗
式中ρ=nξê+16δAi+Acú.由于当k时cc因此式
(36),0ë1γ(4(i=‖‖)‖()‖)û→∞,→,,
∑1
k
说明当k时ρcλ∗.
(36)→∞k,()→k
∗所以由式及式
,{}→∞,()→,(24)

(27),4≥2+1,≥4,=,1
-ηk
ck=θck=1ck.
ΔΔ-ηΔ
1k

4=4
,≥,ΔΔk,kk≥
r=Jc+ρc-λ∗.
kΔ()(37)
那么根据算法中的步骤可知
,1⑤kk
rηkρc-λ∗.
kkkkk‖‖≤‖()‖(38)
注意到cc+
=-k=
Δ()k+2k(37),
Jc1-c∗=r-Jc∗-λ∗.
k()(k)(39)
--
由于Jk可逆且Jk1Jc∗1所以
‖‖≤k2+‖()‖,-k
c1-c∗Jc∗1r+Jkc∗-λ∗.
‖‖k≤2‖()‖(‖‖‖‖)(40)
应用引理并结合式及条件cBc∗δ有
4
6,(17)∈(,k),-βkβ
Jkc∗-λ∗nλ∗ξ2c-c∗2nξ2δ2λ∗c-c∗.
‖‖≤2‖‖∞‖‖≤24‖‖∞‖‖(41)
第期沈卫平等求解逆特征值问题的全局性非精确牛顿类方法
3 ,:281
另一方面利用式式和式容易推得
,(38)、(6)(36),+β
kβ1
kkρc-λ∗kρδkβ
∗∗4∗
rηkρc-λ‖()β‖ρc-λβc-c.
‖‖≤‖()‖≤λ∗‖()‖≤λ∗‖‖(42)
‖‖‖‖
将式与式代入式可得
(41)(42)(40),+β
1
k+-é-βρδùkβ
c1-c∗Jc∗1ê22λ∗+4úc-c∗
ênξδβú.
‖‖≤2‖()‖ë24‖‖∞λ∗û‖‖
‖‖
.
,{}1
数值算例
3

1Toeplitz
征值问题[16]例考虑了逆特征值问题[7]
,2Toeplitz-plus-Hankel.
所有的数值实验均采用中的函数求解算法中的式式及式另外当
Matlabqmkr1-(2)、(3)(5).,
PkTAcPk-Λ∗×10
F
kk‖k()‖≤510
时迭代终止其中PkpppnΛ∗λi∗.
,.=[1,2,…,];=diag();‖·‖FF-.,0=05,max=09,
t-..
=10,min=01,max=09,=16
例1 设Ai5i为阶的矩阵即
{}=15×5Toeplitz,
æöæöæö
ç10000÷ç01000÷ç00100÷
ç01000÷ç10100÷ç00010÷
A=ç÷A=ç÷A=ç÷
1ç00100÷, 2ç01010÷, 3ç10001÷,
ç00010÷ç00101÷ç01000÷
èøèøèø
0000**********
æöæö
ç00010÷ç00001÷
ç00001÷ç00000÷
A=ç÷A=ç÷.
4ç00000÷, 5ç00000÷
ç10000÷ç00000÷
èøèø
0100010000
给定的精确解与精确特征值向量分别为
c∗Tλ∗.....T.
=(2,3,4,5,6), =(-52361,-15876,-07639,-05555,181431)
例考虑以下个不同的初始值c0Tc0Tc0
13:1)=(1,2,3,4,5);2)=(21,38,46,63,81);3)=(150,159,
.
168,170,180)1~33,
表初值为c0(,,,,)T的数值实验结果
1 =12345
kkk
kcc∗PkTAcPkΛ∗c迭代次数
‖-‖‖()-‖F
..T
022361143178(1,2,3,4,5)
.T
121298E-(,,,,)
T3
--5(,,,,)
T
--10(,,,,)
表初值为c0(,,,,)T的数值实验结果
2 =2138466381
kkk
kcc∗PkTAcPkΛ∗c迭代次数
‖-‖‖()-‖F
..T
011108112354804(21,38,46,63,81)
.......T
**********(19999,27169,44840,52702,53177)
.......T
20383906737(19935,29317,40966,51837,56844)
.......T
32222600256(19990,30377,38716,51579,59179)52
…………
..T
5**********E-8(,,,,)
T
-10(,,,,)
浙江师范大学学报自然科学版年
282() 2022
表初值为c0(,,,,)T的数值实验结果
3 =150159168170180
kkk
kcc∗PkTAcPkΛ∗c迭代次数
‖-‖‖()-‖F
..T
036143748151638(150,159,168,170,180)
.......T
**********(20000,29969,40899,50476,59101)
.......T
20002400046(19997,29994,40001,50021,59993)4
.T
311308E--6(,,,,)
T
--10(,,,,)
例2 设Ai5i为阶的矩阵即
{}=15×5Toeplitz-plus-Hankel,
æöæöæö
ç-10000÷ç0-1000÷ç00-100÷
ç01000÷ç-10100÷ç0-2010÷
Aç÷Aç÷Aç÷
1=ç00100÷, 2=ç01010÷, 3=ç-10001÷,
ç÷ç÷ç÷
ç00010÷ç00101÷ç01000÷
èøèøèø
0000**********
æöæö
ç000-10÷ç0000-1÷
ç00-201÷ç000-20÷
Aç÷Aç÷.
4=ç0-2000÷, 5=ç00-200÷
ç÷ç÷
ç-10000÷ç0-2000÷
èøèø
01000-10000
给定的精确解与精确特征值分别为
:
c∗Tλ∗.....T.
=(15,16,17,18,19), =(-599514,-240485,-196964,232586,534377)
考虑以下个不同的初始值c0Tc0Tc0
3:1)=(31,32,33,34,35);2)=(35,45,60,80,95);3)=(150,
.
159,168,175,185)4~63,
表初值为c0(,,,,)T的数值实验结果
4 =3132333435
kkk
kcc∗PkTAcPkΛ∗c迭代次数
‖-‖‖()-‖F