γ-循环线性方程组的快速算法

1．引言在数学以及应用科学中的许多问题都与周期性有关，从而导致一类特殊形式的TOeelitZ系统，即r一循环线性系统的求解，其计算复杂性为O（N”）［’j或渐近复杂性O（NlogZN）p］．由于循环矩阵与离散富里时变换之间的关系，我们也可通过快速富里叶变换（＊＊n来求解r一循环线性方程组，计算复杂性降为O（NlogZN）［‘，’］．事实上，到目前为止所有与厂循环矩阵有关问题的快速算法全部建立在富里叶变换某础之卜IZ，9，10，17，19，20］但另一方面富里叶交换定义在复数域上，而实际问题中的数据大多为实数，因此用FFT快速求解r…     

关于一种循环类预条件方程组的快速求解

１引言考虑下列Ｎ阶线性方程组其中Ｃ１＝,Ｃ２＝０≤ｉ,ｊ≤Ｎ－１,是Ｎ阶循环矩阵,Ｊ１＝（Ｊ）是Ｎ阶置换矩阵,其元素分别满足１９９３年,Ｔ,Ｋ．Ｋｕ,Ｃ．Ｃ．Ｊ．Ｋｕｏ在［１］中取Ｃ１,Ｃ２为实对称循环矩阵,而Ｃ１＋Ｊ１Ｃ２作为预条件矩阵来求解在数字信号处理中有一定应用的Ｔｏｅｐｌｉｔｚ加Ｈａｎｋｅｌ线性方程组［２］,得到了一种高效的预处理其轭梯度算法．当Ｔｏｅｅｌｉｔｚ与Ｈａｎｋｅｌ矩阵之和为正定矩阵且条件数适中时,所需运算量可达到０（Ｎｌｏｇ２Ｎ）,比原有算法［２,３,４］的运算量０（Ｎ２）…     

关于Jacobi矩阵逆特征值问题的扰动分析

１预备 若不特别说明,本文沿用［６］中记号． Ｈｏｃｈｓｔａｄｔ于１９６７年提出如下问题［１］： 问题Ⅰ　给定两组实数｛λ｝ｎｊ＝１＝１和｛μ｝ｎ＝１ｉ＝１,满足构造一个ｎ阶实对称三对角矩阵Ｊｎ,使得λ１,…λｎ为人的特征值,而Ｊｎ－１阶顺序主子阵的特征值为μ１,…,μｎ－１． 问题Ⅱ　给定一组实数｛λｊ｝ｎｊ＝１,满足构造一个ｎ阶全对称三对角矩阵Ｊｎ（ｓ）,使得Ｊｎ（ｓ）的特征值为λ１,λ２,…λｎ． ｄｅ Ｂｏｏｒ和Ｇｏｌｕｂ［４］提出如下问题： 问题Ⅲ　给定两组实数满足构造ｎ阶实对称三对角矩阵Ｊ…     

代数特征值反问题Hermite情形可解的充分条件

１　引言及主要结果 本论文将要讨论如下问题［２,４］： 问题ＨＧ给定ｎ＋１个Ｈｅｒｍｉｔｅ矩阵Ａ＝（ａｉｊ）ｎ×ｎ和Ａｋ＝Ｓ和ｎ个实数　,求个实数ｃ１,…,ｃｎ,使得Ａ（ｃ）＝ ．的特征值为 对于上述问题,有解的充分条件已有许多研究结果,如［２,４,６］．下面将利用Ｂｒｏｕｗｅｒ不动点定理给出新的充分条件． 本文的符号和定义如下： 对任意ｎ阶Ｈｅｒｍｉｔｅ矩阵Ｂ＝（ｂｉｊ）,记Ｂ（０）＝Ｂ－ｄｉａｇ（ｂ１１,ｂ２２,…,ｂｎｎ）,ρ（Ｂ）表示Ｂ的谱半径, ｛λ（Ｂ）｝表示Ｂ的特征值（谱）集合,且设　表…     

解非对称矩阵特征值问题的一种并行分治算法

１引言考虑矩阵特征值问题其中Ａ是非对称矩阵．通过正交变换（如Ｈｏｕｓｅｈｏｌｄｅｒ变换或Ｇｉｖｅｎｓ变换）,Ａ可化为上Ｈｅｓｓｅｎｂｅｒｇ形．因而,本文假设Ａ为上Ｈｅｓｓｅｎｂｅｒｇ矩阵,表示如下：不失一般性,进一步假设所有的（ｊ＝２,…,ｎ）,即认为Ａ是不可约的关于如何求解上述问题,人们进行了不懈的努力,提出了许多行之有效的算法［１－８］．其中分治算法因具有良好的并行性而引人注目．分治算法的典型代表是基于同伦连续的分治算法［２,３,４］和基于Ｎｅｗｔｏｎ迭代的分治算法［１］．本文提出一种新的分…     

（r）循环矩阵的Kronecker积

（ｒ）循环矩阵的Ｋｒｏｎｅｃｋｅｒ积韩瑞珠（东南大学）循环矩阵是一类很重要的矩阵，它有着广泛的应用［１］，并且有许多独特的性质。例如，循环阵的广义道［１］、逆矩阵［２］、伴随阵［３］仍为循环阵；循环阵的乘积仍为循环阵。自然地，作为矩阵论中有极其重要的...     

按环路α-连对角占优阵及应用

１．引言与记号 利用矩阵的对角占优性研究矩阵的特征值分布和非奇Ｈ矩阵的判定,是数值代数的重要课题．［１］－［４］给出了利用 Ｏｓｔｒｏｗｓｋｉ定理及连对角占优性判定非奇 Ｈ－矩阵的最新成果．本文引入按环路α－连对角占优概念,给出了非奇Ｈ－矩阵的判定条件及等价表征,简化了计算,改进与推广了［１］－［９］的相应结果． 设Ａ＝．Γ（Ａ）表 Ａ的方向图,其顶点集及弧集分别记作 Ｖ（Ａ）及 Ｅ（Ａ）,ｅｉｊ表从顶点ｉ到顶点 ｊ的弧, Ｃ（Ａ）表 Γ（Ａ）中非平凡环路集合．对任意固定 α Ｅ［０,１］还记＊ｋ伪行、列足…     

Lyapunov不等式的最佳解与一般线性方法的可行性

１引言在刚性常微分方程初值问题数值解法理论中,常要求数值方法中的某个系数矩阵Ｂ具有性质：使Ｌｙａｐｕｎｏｖ不等式有对角正定解Ｄ存在,即存在对角正定矩阵Ｄ,使ＤＢ＋ＢＴＤ为正定矩阵·在许多情形,这种解Ｄ是存在的,例如Ｇ－Ｌ-、ＩＡ-和ⅡＡ－ＲＫ方法［３］．然而也存在一些方法,它是Ａ－稳定、Ｌ－稳定,甚至是代数稳定的,但这种Ｄ却不存在．例如ⅢＣ（ｓ≥３）ＲＫ方法［３］和当θ＝１时的块θ－方法［５］（至少对ｒ＝２,３,４是如此）．前者是Ｌ－稳定的,也是代数稳定的,后者也是Ｌ－稳定的．这意味着,可能有不少…     

一类超线性收敛的广义拟Newton算法

１引言考虑无约束最优化问题其中目标函数ｆ（ｘ）二阶连续可微,记ｆｋ＝ｆ（ｘ）,当充分小时,有如下近似关系：它们对二次函数皆严格成立．考虑选代其中Ｂ（Ｇ的近似）已知,为某种线搜索确定的步长．对Ｂ修正产生Ｂ,即Ｕ为待定ｎ阶矩阵．若要求Ｂ＋满足关系即Ｂ满足拟Ｎｅｗｔｏｎ方程,由它可导出许多著名的拟Ｎｅｗｔｏｎ算法［１－［４］）．若要求Ｂ满足关系则可导出伪Ｎｅｗｔｏｎ－δ族校正公式,它不再是Ｈｕａｎｇ族成员［６］．从信息资源的利用看,（１．６）仅利用了与信息,（１．７）仅利用了与信息．一般而言,较多的信…     

关于外梯度法的步长规则

１．引言 设为Ｒｎ中的一个非空闭凸集,Ｆ（ｘ）为Ｒｎ　Ｒｎ中的一个连续向量函数．变分不等式问题（Ｆ,）就是：找一向量ｘ　使得当 ＝Ｒ时,（１．１）退化成非线性互补问题。在这篇文章中总假定：（Ｈ１） ,这里表示（１．１）的解集;（Ｈ２）Ｆ（ｘ）是单调的,即对,（ｘ－ｙ）（Ｆ（ｘ）－Ｆ（ｘ）－Ｆ（ｙ））． 这类问题出现在工程物理、经济管理等领域,有着极为广泛的应用．因此,其数值解近年来受到重视,提出许多有效算法,见综述［１, ２］．在现有的算法中, Ｋｏｒｐｅｌｅｖｉｃｈ的外梯度法［３］（何炳生称它为投影…     

块H－矩阵的进一步推广

对Ｎａｂｂｅｎ［２］提出的块Ｈ－矩阵做进一步推广，使得非对角块矩阵不必是Ｈｅｒｍｉｔｅ矩阵．但仍保留其基本特征不变．对块Ｈ－矩阵提出块Ｈ－分裂及块相容Ｈ－分裂．证明了矩阵的任意块相容Ｈ－分裂都是收敛分裂．对ＪＯＲ迭代法给出松驰参数的上界．     

矩阵方程X＋A^TX^—1A=Q存在可稳定化解的充分必要条件

１引言一般的时离散代数Ｒｉｃｃａｔｉ方程具有下面的形式：这里如果方程（１）中的系数矩阵满足：（ｎ＝ｍ）则方程（１）变为当Ｑ＝ＱＴ＞０时,Ｅｎｇｗｅｒｄａ,詹兴致等人研究了方程（２）存在正定解的充分必要条件［１］［２］［３］．本章利用方程（２）与（１）的关系,从另一角度讨论了Ｑ为对称矩阵时,方程（２）存在可稳定化解的充分必要条件．２基本概念与记号首先我们简单回顾一下以前的概念与记号．矩阵束Ｍ—Ｎ,Ｍ,Ｎ为正则的,也就是说ｄｅｔ（λＭ－Ｎ）＝０;如果λ０为ｄｅｔ（λＭ－Ｎ）的ｋ重根,则称λ０为它的ｋ…     

一类亚半正定矩阵的左右逆特征值问题

1．引言在工程技术中常常遇到这样一类逆特征值问题：要求在一个矩阵集合S中，找具有给定的部分右特征对（特征值及相应的特征向量）和给定的部分左特征对（特征值及相应的特征向量）的矩阵．文［2］，［3］讨论了S为。x。实矩阵集合的情形．文［4］－［7］对S为nxn实对称矩阵．对称正定矩阵，对称半正定矩阵集合的情形进行了讨论．文【川讨论了S为亚正定阵集合的情形．并提到了对于亚半正定矩阵的情形目下无人涉及，有待进一步研究．本文将对S为nxn亚半正定矩阵集合的情形进行讨论．给出了亚半正定矩阵的左右逆特征值问题有解的充要条件…     

求解一类非单调线性互补问题的路径跟踪法及其计算复杂性

１．引言及记号 线性互补问题的一般形式是;求（ｘ,ｓ） 　　　　　　　 使其中 众所周知,当Ω＋非空时,单调线性互补问题可在多项式时间内求解,而且人们已经设计出了多种求解单调线性互补问题的有效的内点算法（见［１］和［７］）．然而,对于求解非单调线性互补问题的内点算法的研究可以说才刚刚开始．文［２］讨论了当Ｍ为Ｐ矩阵时问题（１）的中心路径的存在唯一性;文［３］给出了设计求解一类非单调线性互补问题的内点算法的一般框架;文［４］给出了求解一类非单调线性互补问题的一种势能函数约减法并讨论了其算法的计算复杂…     

改进HS共轭梯度算法及其全局收敛性

１．引 言 １９５２年 Ｍ．Ｈｅｓｔｅｎｅｓ和Ｅ．Ｓｔｉｅｆｅｌ提出了求解正定线性方程组的共轭梯度法［１］．１９６４年Ｒ．Ｆｌｅｔｃｈｅｒ和Ｃ．Ｒｅｅｖｅｓ将该方法推广到求解下列无约束优化问题： ｍｉｎｆ（ｘ）,ｘ∈Ｒｎ,（１）其中ｆ：Ｒｎ→Ｒ１为连续可微函数,记ｇｋ＝ ｆ（ｘｋ）,ｘｋ∈ Ｒｎ． 若点列｛ｘｋ｝由如下算法产生：其中 βｋ＝［ｇＴｋ（ｇｋ－ｇｋ－１）］／［ｄＴｋ－１（ｇｋ－ｇｋ－１）］．（Ｈｅｓｔｅｎｅｓ－Ｓｔｉｅｆｅｌ）　　（４）则称该算法为 Ｈｅｓｔｅｎｅｓ—Ｓｔｉｅｆｅｌ共轭梯度算…     

mn阶分块(R,r)-循环矩阵相乘和特征值计算的快速算法

本文利用快速富里叶变换（FFT），给出了mn阶分块（R，r)－循环矩阵相乘和特征值计算的快速算法，其时间复杂性均为O（mnlog2mn）。     

一类求解单调变分不等式的隐式方法

1．引言变分不等式是一个非常有趣。非常困难的数学问题［"］．它具有广泛的应用（例如，数学规划中的许多基本问题都可以归结为一个变分不等式问题），因而得到深入的研究并有了不少算法［1，2，5－8，17－21］．对线性单调变分不等式，我们最近提出了一系列投影收缩算法Ig－13］．本文考虑求解单调变分不等式其中0CW是一闭凸集，F是从正p到自身的一个单调算子，一即有我们用比（·）表示到0上的投影．求解单调变分不等式的一个简单方法是基本投影法［1，6］，它的迭代式为然而，如果F不是仿射函数，只有当F一致强单调且LIPSChitZ连续…     

关于三基本量的一个不等式及其应用

设Ｒ、ｒ与ｓ是△ＡＢＣ的三基本量（外接圆半径、内切圆半径与半周长）,则有［１］、［２］ｓ４－２ｓ２（２Ｒ２＋１０Ｒｒ－ｒ２）＋ｒ（４Ｒ＋ｒ）３≤０（１）（当且仅当△ＡＢＣ为等腰三角形时取等号）．（１）称为三角形基本不等式．本文中,我们将应用它导出关于Ｒ、ｒ与ｓ的一个含双参数（λ,ｔ）的不等式．适当选择参数λ、ｔ的值,便可得到包括Ｇｅｒｒｅｔｓｅｎ不等式、Ｏ．Ｋｏｏｉ不等式等著名不等式在内的一大批有用的不等式．定理　对△ＡＢＣ中的三基本量Ｒ、ｒ、ｓ及任意实数λ、ｔ,都有　－（ｔ－１）２Ｒ３＋２［ｔ…     

关于具优势对称部分的不定线性代数方程组的分裂极小残量算法

１．引 言 考虑大型稀疏线性代数方程组 为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销，Ｋｒｙｌｏｖ子空间迭代算法［１，１６，２３］及其预处理变型［６，８，１３，１８，１９］通常是求解（１）的有效而实用的方法．当系数矩阵对称正定时，共轭梯度法（ＣＧ（     

关于函数f（x＋λ）＝af（x）＋b／cf（x）＋d的周期性的讨论

关于函数ｆ（ｘ＋λ）＝ａｆ（ｘ）＋ｂ／ｃｆ（ｘ）＋ｄ的周期性的讨论华中师范大学数学系刘永华，邓乐斌文［１］的作者用矩阵的方法，使分式线性递推数列，二阶循环数列，等差数列，等比数列求通项的问题全部统一到二阶矩阵的乘方上来了．文［２］、文［３］讨论了一类...