1) non-homogeneous sparse linear equations
非齐次稀疏线性方程组
2) non-symmetric sparse linear systems
非对称稀疏线性方程组
1.
Employing an intrinsic property of the GCR(k) algorithm and eliminating data interdependence for inner product computation in the GCR(k) algorithm,an improved parallel GCR(k) algorithm called IGCR(k) algorithm is established for solving large non-symmetric sparse linear systems derived from multi-scale prediction model.
针对多尺度预报模式离散得到的非对称稀疏线性方程组的求解,通过利用GCR(k)算法的固有性质,消除GCR(k)算法的内积计算数据相关性,给出了一种改进的GCR(k)(IGCR(k))算法。
3) nonhomogeneous linear equations
非齐次线性方程组
1.
This paper principally reviews the identity authentication protocol and message authentication protocol based on nonhomogeneous linear equations in [1],analyzes the security defects in these two protocols in combination with [2],and modifies them by introducing in trap-door one-way function.
文中主要回顾了《基于非齐次线性方程组的认证协议的研究》一文中给出的基于具有无穷多个解的非齐次线性方程组而建立的一个身份认证协议和一个消息认证协议,结合《两个认证协议的安全缺陷》一文,对这两个认证协议中存在的安全缺陷进行具体分析;然后通过引入陷门单向函数对这两个认证协议进行改进,保障其安全缺陷和可操作性;并用RSA算法作为实例,对改进后的认证协议进行讨论分析。
2.
The problem two fewer and one more in information hiding was transformed to find the solution vector,which had the least weight,of the nonhomogeneous linear equations whose elements amount wasn t fixed,on binary domain,built a mathematical model,and gave the solution models.
将信息隐藏中的两少一多问题转换为求二值域上变量元数不确定的非齐次线性方程组的最小权值解向量,构建了一个数学模型,对模型进行求解,作为问题模型的解给出了答案模型。
3.
By introducing first the concept of coset in the sub-space of linear space,we have testified an im- portant property of the coset and finally give the necessary and sufficient condition for the same solution of the solva- ble nonhomogeneous linear equations.
两个n元有解的非齐次线性方程组同解的根本原因是什么?为了回答这个问题,首先引入线性空间的子空间的陪集概念,然后证明了F~n的陪集的一个重要性质,最后给出了两个n元有解非齐次线性方程组同解的充分必要条件,从而完善了线性方程组的同解性理论。
4) non homogeneous and linear differential equations
非齐次线性微分方程组
1.
A method to solve non homogeneous and linear differential equations by homogenization high precision direct integration (HHPD P) was proposed.
根据函数分段插值逼近的思想 ,在一个积分步长内用多项式近似表示方程的非齐次项 ,提出了一种原理简单、实施容易的求解非齐次线性微分方程组的新型齐次扩容精细积分法 ,该方法不涉及矩阵的求逆运算 ,不需要计算傅里叶级数展开系数的振荡函数积分 ,且在一个积分步长内只求解一个相应的齐次扩容微分方程组 ,因而本方法和已有的同类方法相比具有更高的计算精度和效率 ,数值算例表明了该方法的有效
5) nonhomogeneous system of linear left equations
非齐次左线性方程组
1.
In this pqper we give a sufficient and necessary consistency condition of a nonhomogeneous system of linear left equations over an arbitrary skew field F, and a convenient, simple method of solving the system.
给出了任意体F上非齐次左线性方程组相容的一个充要条件和求解的简便方法,利用此法还能同时求出其导出组的基础解系,而且顺便讨论了F上一般左线性方程组的解,给出了其有解判定定理及解的结构定理。
补充资料：非线性方程组数值解法
n个变量n个方程(n >1)的方程组表示为 (1)式中??i(x1,x2,...,xn)是定义在n维欧氏空间Rn 的开域D上的实函数。若??i中至少有一个非线性函数，则称(1)为非线性方程组。在Rn 中记 ??＝ 则(1)简写为??(尣)=0。若存在尣*∈D，使??(尣*)＝0，则称尣*为非线性方程组的解。方程组(1)可能有一个解或多个解，也可能有无穷多解或无解。对非线性方程组解的存在性的研究远不如线性方程组那样成熟，现有的解法也不象线性方程组那样有效。除极特殊的方程外，一般不能用直接方法求得精确解，目前主要采用迭代法求近似解。根据不同思想构造收敛于解尣*的迭代序列{尣k}(k=0，1，...)，即可得到求解非线性方程组的各种迭代法，其中最著名的是牛顿法。
牛顿法及其变形 牛顿法基本思想是将非线性问题逐步线性化而形成如下迭代程序： (2)式中是??(尣k)的雅可比矩阵,尣0是方程(1)的解尣*的初始近似。
这个程序至少具有2阶收敛速度。由尣k算到尣k+的步骤为:①由尣k算出??(尣k)及;②用直接法求线性方程组的解Δ尣k；③求。
由此看到迭代一次需计算n个分量函数值和 n2个分量偏导数值，并求解一次n阶线性方程组。
为了评价非线性方程组不同迭代法的优劣，通常用效率作为衡量标准,其中P为迭代法的收敛阶,W为每迭代步计算函数值??i及偏导数值的总个数（每迭代步中求一次逆的工作量相同,均不算在W 内）。效率e越大表示此迭代法花费代价越小,根据效率定义，牛顿法(2)的效率为。
牛顿法有很多变形,如当奇异或严重病态时，可引进阻尼因子λk，得到阻尼牛顿法，即式中I是单位矩阵。牛顿法是局部收敛方法,因而对初始近似尣0限制较严，为放宽对尣0的要求,扩大收敛范围,通常可引进松弛因子ωk，得到牛顿下降法： (3)式中ωk的选择应使成立。
为减少解线性方程组次数，提高效率，可使用修正牛顿程序 (4)这种算法也称为萨马斯基技巧，它的收敛阶为 p =m+1，由尣k 计算 的工作量为W =n2+mn，于是该法的效率。当n=10,m＝7时,当n＝100,m＝37时,，由此看到修正牛顿法(4)比牛顿法效率高，且m 越大效果越明显。
在计算机上往往采用不计算偏导数的离散牛顿法，即 (5)式中，其中ej为基向量,,若取，则(5)仍具有2阶收敛速度。其效率与牛顿法相同。
若在牛顿法(2)中解线性方程组不用直接法,而采用迭代法则得到一类解非线性方程组的双重迭代法。按解线性方程组采用的方法不同就得到不同名称的迭代法，如牛顿－赛德尔迭代法，牛顿－SOR迭代法，牛顿－ADI迭代法，等等。这些方法都具有超线性收敛速度，工作量也比牛顿法大，除了对某些特殊稀疏方程组外，通常用得校少。若将解线性方程组迭代法的思想直接用于非线性方程组(1)，然后把(1)化为一维方程求解，可得到另一类双重迭代法，由于采用的迭代法与解一维非线性方程的方法不同，则得到不同的双重迭代法。如果利用SOR迭代法后再用牛顿法解一维方程则得SOR－牛顿迭代法，在牛顿法中只计算一步而不进行迭代，则得一步的SOR－牛顿迭代，其计算公式可表示为式中记号嬠i??i表示；ω为迭代参数，当ω=1时就是赛德尔-牛顿迭代法,这类方法对解维数高的稀疏的非线性方程组是有效的。
割线法 若对方程组 (1)线性化时使用插值方法确定线性方程组
(6)中的Ak和bk,则可得到一类称为割线法的迭代序列。假定已知第k步近似尣k，为确定Ak和bk,可在尣k附近取n个辅助点у忋(j=1,2,...,n),使n个向量线性无关，由插值条件可知由此可求得由(6)解得以此作为方程 (1)的新近似，记作，于是得到 (7)(7)称为解非线性方程组的割线法。辅助点у忋 取得不同就得到不同的割线法程序，例如取为常数(j=1,2,...,n)，就得到与(5)相同的程序，由于它只依赖于尣k点的信息，故也称一点割线法,若取它依赖于点尣k及, 称为两点割线法。其他多点割线法由于稳定性差，使用较少。
布朗方法 布朗采用对每个分量方程 ??i(尣)=0逐个进行线性化并逐个消元的步骤，即在每迭代步中用三角分解求线性方程组的解，得到了一个效率比牛顿法提高近一倍的迭代法，即式中
(8)中当i=n时求得xn记作,再逐次回代,求出(i=n-1,n-2,...,1)就完成了一个迭代步。布朗迭代程序的敛速仍保持p＝2，而每一迭代步的工作量，故效率对这方法还可与牛顿法一样进行改进，得到一些效率更高的算法。这类方法是70年代以来数值软件包中常用的求解非线性方程组的算法。
拟牛顿法 为减少牛顿法的计算量，避免计算雅可比矩阵及其逆，60年代中期出现了一类称为拟牛顿法的新算法,它有不同的形式，常用的一类是秩1的拟牛顿法，其中不求逆的程序为式中,,，称为逆拟牛顿公式。计算时先给出尣0及 B0，由(9)逐步迭代到满足精度要求为止。每步只算 n个分量函数值及O(n2)的计算量,比牛顿法一步计算量少得多。理论上已证明，当尣0及B0选得合适时,它具有超线性收敛速度,但实践表明效率并不高于牛顿法，理论上尚无严格证明。
最优化方法 求方程组 (1)的问题等价于求目标函数为的极小问题,因此可用无约束最优化方法求问题(1)的解（见无约束优化方法）。
连续法 又称嵌入法，它可以从任意初值出发求得方程组(1)的一个足够好的近似解,是一种求出好的迭代初值的方法。连续法的基本思想是引入参数 t∈[0,b]，构造算子H(尣,t)，使它满足条件：H(尣,0)=??0(尣),H(尣,b)=??(尣)，其中??0(尣)=0的解尣0是已知，方程：
(10)在t∈[0,b]上有解尣=尣(t)，则尣(b)=尣*就是方程(1)的解。当b有限时，通常取b=1，例如可构造。 (11)这里尣0是任意初值,显然H(尣0,0)=0,H(尣,1)=??(尣)。为了求得(10)在t=1的解尣*=尣(1),可取分点0=t01<...N=1在每个分点ti(i=1,2,...,N)上，求方程组H(尣,ti)=0 (i=1,2,...,N) (12)的解尣i，如果取尣i-1为初值，只要足够小，牛顿迭代就收敛，但这样做工作量较大。已经证明，如果方程组(12)只用一步牛顿法，当t=tN=1时，再用牛顿迭代，结果仍具有2阶收敛速度。以(11)为例,得到连续法的程序为：
若H(尣,t)的偏导数Ht(尣,t)及在D×[0,1]嶅R上连续。且非奇异，则由(10)对t求导可得到等价的微分方程初值问题:
(13)于是求方程(10)的解就等价于求常微初值问题(13)的解，求(13)的解可用数值方法由t=0计算到t=tN=b得到数值解。已经证明只要N足够大,以尣N为初值再进行牛顿迭代可收敛到方程(1)的解x*，这种算法称为参数微分法。
20世纪60年代中期以后，发展了两种求解非线性方程组(1)的新方法。一种称为区间迭代法或称区间牛顿法，它用区间变量代替点变量进行区间迭代，每迭代一步都可判断在所给区间解的存在惟一性或者是无解。这是区间迭代法的主要优点，其缺点是计算量大。另一种方法称为不动点算法或称单纯形法，它对求解域进行单纯形剖分，对剖分的顶点给一种恰当标号，并用一种有规则的搜索方法找到全标号单纯形,从而得到方程(1)的近似解。这种方法优点是，不要求??(尣)的导数存在,也不用求逆，且具有大范围收敛性，缺点是计算量大。
参考书目
J.M.Ortega and W.G.Rheinboldt,Iterative Solution of Nonlinear Equations in Several variables,Academic Press,New York,1970.
牛顿法及其变形 牛顿法基本思想是将非线性问题逐步线性化而形成如下迭代程序： (2)式中是??(尣k)的雅可比矩阵,尣0是方程(1)的解尣*的初始近似。
这个程序至少具有2阶收敛速度。由尣k算到尣k+的步骤为:①由尣k算出??(尣k)及;②用直接法求线性方程组的解Δ尣k；③求。
由此看到迭代一次需计算n个分量函数值和 n2个分量偏导数值，并求解一次n阶线性方程组。
为了评价非线性方程组不同迭代法的优劣，通常用效率作为衡量标准,其中P为迭代法的收敛阶,W为每迭代步计算函数值??i及偏导数值的总个数（每迭代步中求一次逆的工作量相同,均不算在W 内）。效率e越大表示此迭代法花费代价越小,根据效率定义，牛顿法(2)的效率为。
牛顿法有很多变形,如当奇异或严重病态时，可引进阻尼因子λk，得到阻尼牛顿法，即式中I是单位矩阵。牛顿法是局部收敛方法,因而对初始近似尣0限制较严，为放宽对尣0的要求,扩大收敛范围,通常可引进松弛因子ωk，得到牛顿下降法： (3)式中ωk的选择应使成立。
为减少解线性方程组次数，提高效率，可使用修正牛顿程序 (4)这种算法也称为萨马斯基技巧，它的收敛阶为 p =m+1，由尣k 计算 的工作量为W =n2+mn，于是该法的效率。当n=10,m＝7时,当n＝100,m＝37时,，由此看到修正牛顿法(4)比牛顿法效率高，且m 越大效果越明显。
在计算机上往往采用不计算偏导数的离散牛顿法，即 (5)式中，其中ej为基向量,,若取，则(5)仍具有2阶收敛速度。其效率与牛顿法相同。
若在牛顿法(2)中解线性方程组不用直接法,而采用迭代法则得到一类解非线性方程组的双重迭代法。按解线性方程组采用的方法不同就得到不同名称的迭代法，如牛顿－赛德尔迭代法，牛顿－SOR迭代法，牛顿－ADI迭代法，等等。这些方法都具有超线性收敛速度，工作量也比牛顿法大，除了对某些特殊稀疏方程组外，通常用得校少。若将解线性方程组迭代法的思想直接用于非线性方程组(1)，然后把(1)化为一维方程求解，可得到另一类双重迭代法，由于采用的迭代法与解一维非线性方程的方法不同，则得到不同的双重迭代法。如果利用SOR迭代法后再用牛顿法解一维方程则得SOR－牛顿迭代法，在牛顿法中只计算一步而不进行迭代，则得一步的SOR－牛顿迭代，其计算公式可表示为式中记号嬠i??i表示；ω为迭代参数，当ω=1时就是赛德尔-牛顿迭代法,这类方法对解维数高的稀疏的非线性方程组是有效的。
割线法 若对方程组 (1)线性化时使用插值方法确定线性方程组
(6)中的Ak和bk,则可得到一类称为割线法的迭代序列。假定已知第k步近似尣k，为确定Ak和bk,可在尣k附近取n个辅助点у忋(j=1,2,...,n),使n个向量线性无关，由插值条件可知由此可求得由(6)解得以此作为方程 (1)的新近似，记作，于是得到 (7)(7)称为解非线性方程组的割线法。辅助点у忋 取得不同就得到不同的割线法程序，例如取为常数(j=1,2,...,n)，就得到与(5)相同的程序，由于它只依赖于尣k点的信息，故也称一点割线法,若取它依赖于点尣k及, 称为两点割线法。其他多点割线法由于稳定性差，使用较少。
布朗方法 布朗采用对每个分量方程 ??i(尣)=0逐个进行线性化并逐个消元的步骤，即在每迭代步中用三角分解求线性方程组的解，得到了一个效率比牛顿法提高近一倍的迭代法，即式中
(8)中当i=n时求得xn记作,再逐次回代,求出(i=n-1,n-2,...,1)就完成了一个迭代步。布朗迭代程序的敛速仍保持p＝2，而每一迭代步的工作量，故效率对这方法还可与牛顿法一样进行改进，得到一些效率更高的算法。这类方法是70年代以来数值软件包中常用的求解非线性方程组的算法。
拟牛顿法 为减少牛顿法的计算量，避免计算雅可比矩阵及其逆，60年代中期出现了一类称为拟牛顿法的新算法,它有不同的形式，常用的一类是秩1的拟牛顿法，其中不求逆的程序为式中,,，称为逆拟牛顿公式。计算时先给出尣0及 B0，由(9)逐步迭代到满足精度要求为止。每步只算 n个分量函数值及O(n2)的计算量,比牛顿法一步计算量少得多。理论上已证明，当尣0及B0选得合适时,它具有超线性收敛速度,但实践表明效率并不高于牛顿法，理论上尚无严格证明。
最优化方法 求方程组 (1)的问题等价于求目标函数为的极小问题,因此可用无约束最优化方法求问题(1)的解（见无约束优化方法）。
连续法 又称嵌入法，它可以从任意初值出发求得方程组(1)的一个足够好的近似解,是一种求出好的迭代初值的方法。连续法的基本思想是引入参数 t∈[0,b]，构造算子H(尣,t)，使它满足条件：H(尣,0)=??0(尣),H(尣,b)=??(尣)，其中??0(尣)=0的解尣0是已知，方程：
(10)在t∈[0,b]上有解尣=尣(t)，则尣(b)=尣*就是方程(1)的解。当b有限时，通常取b=1，例如可构造。 (11)这里尣0是任意初值,显然H(尣0,0)=0,H(尣,1)=??(尣)。为了求得(10)在t=1的解尣*=尣(1),可取分点0=t0
若H(尣,t)的偏导数Ht(尣,t)及在D×[0,1]嶅R上连续。且非奇异，则由(10)对t求导可得到等价的微分方程初值问题:
(13)于是求方程(10)的解就等价于求常微初值问题(13)的解，求(13)的解可用数值方法由t=0计算到t=tN=b得到数值解。已经证明只要N足够大,以尣N为初值再进行牛顿迭代可收敛到方程(1)的解x*，这种算法称为参数微分法。
20世纪60年代中期以后，发展了两种求解非线性方程组(1)的新方法。一种称为区间迭代法或称区间牛顿法，它用区间变量代替点变量进行区间迭代，每迭代一步都可判断在所给区间解的存在惟一性或者是无解。这是区间迭代法的主要优点，其缺点是计算量大。另一种方法称为不动点算法或称单纯形法，它对求解域进行单纯形剖分，对剖分的顶点给一种恰当标号，并用一种有规则的搜索方法找到全标号单纯形,从而得到方程(1)的近似解。这种方法优点是，不要求??(尣)的导数存在,也不用求逆，且具有大范围收敛性，缺点是计算量大。
参考书目
J.M.Ortega and W.G.Rheinboldt,Iterative Solution of Nonlinear Equations in Several variables,Academic Press,New York,1970.
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条