论文总字数：10853字

摘 要

Abstract II

第一章 引言 1

1.1 对特征值的阐述 1

1.2 国内外研究现状 1

1.3 对迭代法的简述 2

第二章 迭代法 4

2.1 简单迭代法 4

2.1.1 迭代格式的构造 4

2.1.2 迭代法的收敛性 5

2.1.3 迭代法的收敛速度 5

2.2 Newton法 6

2.2.1 Newton迭代格式 6

2.2.2 收敛性 7

2.2.3 求重根的修正Newton法 8

2.2.4 Newton法的变形 8

第三章 用迭代法求解特征值 10

3.1 将特征值问题转化为迭代问题 10

3.2 迭代法的修正 12

第四章 数值实验 14

4.1 例1. 14

4.2 例2. 14

4.3 总结 16

致谢 19

求解非线性特征值问题的迭代算法研究

摘 要

非线性特征值问题来源于控制理论，梯形网络，动态规划，排队理论，随机过滤，统计学等应用领域。本文研究求解非线性矩阵特征值问题的迭代算法，并比较在不同情况下何种方法最为有效。

形如，，则为的特征值，若矩阵，则的特征值是关于变量λ的非线性函数，那么我们可以通过使特征值，再直接套用Newton迭代法来求零解得到特征值。而后在本文中，我们将简单介绍关于迭代的概念与递推方法，迭代法的基本思想是一种逐次逼近的方法，用给定的初始值和相应的迭代公式去求解特征值，直到满足预先给定的精度要求为止。迭代函数构造的好坏，不仅影响收敛速度，而且迭代格式有可能发散。为了保证迭代序列一定收敛，我们通过泰勒公式用近似线性方程来代替原方程去求根，从而引出Newton迭代法。

本文中我们将把求解特征值问题转换为运用迭代方法求最优解的问题，并通过比较迭代次数和迭代时间来判断各种迭代方法的优劣。本文给出的具体数据例证中，我们将通过Newton,Halley,Laugerre迭代方法来求近似特征值，并通过观察迭代次数来判断哪种方法最为快捷实用。

关键词：非线性,特征值,迭代,最优化

Study on Solving the Nonlinear Eigenvalue Problems by Algorithmic Iteration

Abstract

The nonlinear eigenvalue problems root in the control theory,ladder network,queuing theory,random filtering and statistics.In this paper,algorithmic iterations to solving the nonlinear eigenvalue problems will be studied and compared under different circumstance.

The number is a eigenvalue of A,if there exists a nonzero vector such that .If ,the eigenvalues of a matrix ,the element of which are functions of a variable λ, can be found with a zero finding method combined with the determinant function det.In this paper the concept of iteration will be simply described that it is a method about successive approximation.First take a rough initial value,the revise the initial value repeatedly with the same recursion formula,until the convergence criterion is satisfied with a predefined accuracy.The rate of convergence is influenced by the construction of the iterated function .The original function is replaced by a approximate linear function in order to ensure the convergence of the sequence of iterations.Then we get a Newton’s iteration and some superior iterations. It is supposed to be obtained by algorithmic differentiation applied to Newton’s,Halley’s or Laguerre’s iteration.In the numerical examples,we will compute differentiation with respect to the and work out the eigenvalues along with Newton’s,Halley’s and Laguerre’s iteration,and decide which of them is superior in each case.

Keywords:eigenvalue,nonlinear,iteration,optimization

第一章 引言

1.1 对特征值的阐述

假设是一个矩阵，它的元素都是与参数λ有关的可导函数。如果存在非零向量使得

，

那么λ是A的一个特征值。

非线性特征值问题指的是具以下形式的方程:

。

其中 x 是向量("特征向量"), A 是 ( "特征根")的函数矩阵。通常要求 为 (在某个定义域内)的全纯函数。

例如, 线性特征值问题 , 其中 为方阵, 对于 的特征值问题, 其中是单位矩阵。多项式特征值问题, 其中 为多项式矩阵。 特别的, 当多项式的次数为二次时被称作二次特征值问题, 此时具有以下形式:

,

其中,,为常数矩阵. 该问题可通过定义新的向量转化为正常的特征值问题, 即

其中 为单位矩阵. 更一般的, 如果 是次多项式矩阵，那么多项式特征值问题可以转化为 倍大小的(广义)线性特征值问题.

1.2 国内外研究现状

矩阵特征值问题是矩阵计算中举足轻重的一部分,具有非常重要的理论和实际意义,其数值解法的理论研究、算法设计和软件研制是当今计算数学和科学工程计算研究的重大课题,其研究具有重要的理论意义和广泛的应用价值。非线性特征值问题来源于控制理论，梯形网络，动态规划，排队理论，随机过滤，统计学等应用领域。本文研究求解非线性矩阵特征值问题的迭代算法，具有重要应用背景的非线性特征值问题的数值算法具有重要的理论意义和很高的实用价值。

关于一般的非线性特征值问题的解法，可以按照系数矩阵的大小和系数程度来分类。对于稠密矩阵的非线性特征值问题， Anselone和Rall给出了逆迭代方法求解非线性特征值问题，方法将求解非线性特征值问题转化为牛顿法求解非线性方程组问题的运用，因此逆迭代方法具有局部二次收敛性。但是运用逆迭代方法求解特征对的过程中，影响逆迭代法效率的问题是每一迭代步都要求解一个系数矩阵依赖于特征值的线性方程组。为了尽可能的克服上述不足，每一迭代步采用简化牛顿法，即使得线性方程组的系数矩阵不依赖于特征值。但一般情形下，这样修正之后的方法未必收敛于非线性特征值问题的特征对。 Neumaier结合简化牛顿法提出具有超线性收敛的残量逆迭代方法，此方法求解对称非线性特征值问题具有二次收敛性。Ruhe提出了序列线性化方法求解非线性特征值问题，这种方法可以认为是残量逆迭代法的变形运用。因为序列线性化方法本质上是将非线性特征值问题中的以特征值为非线性参数的矩阵进行一次插值逼近，从而将非线性特征值问题转化为一系列线性特征值问题来求解。为了提高插值逼近的精度，将一次插值变为为高次插值。这种在单个点附近的一次或高次的泰勒展开的插值逼近，一次求解一组特征对，属于单变量迭代法。

为了能够同时求出属于某个指定区间或者是复平面上某个指定区域的多个特征值，2011年，Effenberger 和Kressner提出对以特征值为非线性参数的矩阵采用以Chebyshev多项式为插值基函数的插值逼近，然后在采用Krylov方法求解其伴随形式的线性特征值问题。2013年Beerumen等提出基于Hermit插值的有理Krylov方法来求解非线性特征值问题。

1.3 对迭代法的简述

迭代法是数值计算中一类典型方法，应用于方程求根，方程组求解，矩阵求特征值等方面。其基本思想是逐次逼近，用给定的初始值和相应的迭代公式去求解特征值，直到满足预先给定的精度要求为止。数学中的迭代可以指函数迭代的过程，即反复地运用同一函数计算，前一次迭代得到的结果被用于作为下一次迭代的输入。即使是看上去很简单的函数，在经过迭代之后也可能产生复杂的行为，衍生出具有难度的问题。迭代在数学中的另一应用是迭代法，用来对特定数学问题作数值解估计。牛顿法就是迭代法的一个例子。而最常见的迭代法除了牛顿法之外，其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。

第二章 迭代法

借助数学工具研究社会和自然现象,或解决工程技术等问题时,常常将一些问题归结为非线性方程的求解问题,因此无论在理论研究方面还是在实际应用中,求解非线性方程都占了非常重要的地位。迭代法是求解非线性方程的根的一种最重要的方法,而迭代法的优劣对于非线性问题求解速度的快慢和结果的好坏都有很大的影响,所以从实际出发,构造高效能的迭代算法之研究具有重要的科学价值和实际意义。

2.1 简单迭代法

迭代法是数值计算中一类典型方法，不仅用于方程求根，而且用于方程组求解、矩阵求特征值等方面。

迭代法的基本思想是一种逐次逼近的方法。用给定的初始值和相应的迭代公式去求解特征值，直到满足预先给定的精度要求为止。所以下面所讲的各种求根方法，实质上就是如何构造一个合适的递推公式。

2.1.1 迭代格式的构造

已知方程

(2.1.1)

在区间[a,b]内有一个根x*。在[a,b]内将方程（2.1.1）改写为等价形式（同解方程）

(2.1.2)

取x₀∈[a,b],用递推公式

(k=0,1,2,…) (2.1.3)

可得序列。如果当k→∞时，序列有极限,且在附近连续，则在式（2.1.3）两遍取极限，得

即为方程（2.1.2）的根。由于方程（2.1.1）和方程（2.1.2）等价，所以

即

称式（2.1.3）为迭代格式，也称迭代公式；称为迭代函数；称所求得的序列为迭代序列。当时可知为方程（2.1.2）的根，及所取。一般假设。当迭代序列收敛时，称迭代格式收敛，否则称迭代格式发散。称为第k次迭代误差。用迭代格式（2.1.3）求得方程近似根的方法称为简单迭代法，也称为迭代法。

2.1.2 迭代法的收敛性

定理1 （压缩不动点定理）设在内存在一阶连续导数，且满足条件：

1. 当时，；
2. 存在正常数，使得。

则

1. 在上有唯一根；
2. 对任意初值，迭代格式（2.1.3）收敛，且；

定理2 设方程（2.1.2）在区间内有根，且，则对任意初值，且。迭代格式（2.1.3）发散。

定理3 （局部收敛定理）对于方程，若在的某个领域内，对任意的初值，迭代格式（2.1.3）都收敛，则称该迭代法在的附近局部收敛。

2.1.3 迭代法的收敛速度

一种迭代法具有使用价值，不但需要肯定它是收敛的，而且还应该要求它收敛得比较快。所谓迭代的收敛速度是指迭代误差的下降速度。

设序列收敛于，并记(k=0,1,2,…)。如果存在常数p≥1及非零常数，使得

则称序列是p阶收敛的。

显然p的大小反映了序列收敛的快慢，p越大，收敛越快。当p=1且0lt;lt;1时称为线性收敛；当pgt;1时称为超线性收敛，特别当p=2时，称为平方收敛。

如果由一个迭代格式产生的序列是p阶收敛的，则称该迭代格式是p阶收敛的。

2.2 Newton法

2.2.1 Newton迭代格式

用迭代法求方程

(2.2.1)

的根时，首先要把它写成等价形式

请支付后下载全文，论文总字数：10853字