数值代数期末论文

数值代数期末论文：写一篇关于数值代数的论文，格式---标题宋体、二号、加粗；标题下写班级，姓名，8位学号，宋体、三号；正文，宋体、小四。字数能达到两张A4纸就行。在12月30日之前交打印搞，女生交给陈凤姣！请大家相互转告！谢谢~~~数值代数的基本问题研究数值方法的必要性矩阵分解是设计算法的主要技巧敏度分析与误差分析算法复杂性与收敛速度自从1946年第一台电子计算机问世以来，经过半个世纪的发展，使得科学与工程计算已经成为本世纪最重要的科学进步之一。科学计算已与理论研究及科学试验并列成为当今世界科学活动的三种主要方式。在许多科学与工程领域如果没有计算就不可能有第一流的研究成果。为众多的科学与工程问题提供计算方法，提高计算的可靠性、有效性和精确性，便是科学与工程计算这一领域的主要研究内容。数值线性代数又称矩阵计算，它是科学与工程计算的核心。可以毫不夸张地讲，大部分科学与工程问题最终都要归结为一个矩阵计算问题，其中具有挑战性的问题是大规模矩阵计算问题。数值线性代数研究的主要内容就是，如何针对各类科学与工程问题所提出的矩阵计算问题的特点，设计出相应的快速可靠的算法。1.数值线性代数的基本问题数值线性代数主要包括如下三个大问题：（1）求解线性方程组的问题。即给定一个非奇异矩阵和一个向量，求使得（2）线性最小二乘问题。即给定一个矩阵和一个向量，求使得（3）矩阵特征值问题。即给定一个矩阵，求它的部分或全部特征值以及对应的特征向量。除此之外，还有一些其他问题也是十分重要和基本的，如约束最小二乘问题、完全最小二乘问题、矩阵方程的求解、矩阵函数的计算问题、广义特征问题、非线性特征问题、特征值反问题、奇异值分解的计算问题等。特别是奇异值分解的计算，由于其应用十分广泛，目前有的教科书已经将其列为数值线性代数的第四大问题。2.研究数值方法的必要性众所周知，线性线性组、线性最小二乘问题和矩阵特征值问题的数学理论已经相当完善了。但是这些理论上非常漂亮的结果应用于实际计算时往往是行不通的。例如，线性方程组的Gramer法则表明：如果阶线性方程组的系数矩阵A非奇异，则此方程组有唯一的解，并且其解可以通过系数表示为：其中：这里是将A的第i行换为b而得到的矩阵。这一结果把线性方程组的求解问题归结为计算n+1个n阶行列式的问题。而对于行列式的计算，理论上又有著名的Laplace展开定理：其中表示元素的代数余子式。按照这一定理我们就可以从二阶行列式出发逐步递推地计算出任意阶行列式的值。这样，理论上我们就有了一种非常漂亮的求解线性方程组的方法。然而我们做一简单的计算就会发现，由于这一方法的运算量大的惊人，以至于完全不能用于实际计算。设计算k阶行列式所需要的乘法运算的次数为，则容易推出，于是，我们有这样，利用Gramer法则和Laplace展开定理来求解一个n阶线性方程组，所需要的乘法运算的次数要高于因此，若在一个百亿次计算机上求解一个25阶线性方程组，则至少需要再如对矩阵特征征值问题，理论上有著名的Jordan分解定理。这一定理告诉我们，只要知道了一个矩阵的Jordan分解，我们就可很清楚地知道其所有与特征值有关的信息，如一个特征值的几何重数、代数重数以及对应的特征向量等。然而这一分解在实际计算时是难以实现的，这是因为矩阵的Jordan分解是十分不稳定的（即元素有微小变化时，其Jordan分解往往会发生很大的变化），而且其变换矩阵常常是非常病态的。事实上，真正用于实际计算的而是另一具有良好数值性态的Schur分解。因此，如何利用计算机快速有效地求解矩阵计算的三类基本问题并不是一件容易的事情，而是有许多理论和实际问题值得深入细致地研究的。经过这半个世纪来众多数值代数专家的不断探索和研究，目前有关的方法和理论已经发展的相对较为成熟，得到了一大批十分漂亮的实用算法，俣仍有不少问题有待进一步研究解决，特别是大规模矩阵计算问题仍然是目前科学与工程计算研究的核心问题之一。3.矩阵分解是设计算法的主要技巧对于一个给定的矩阵计算时，我们研究的首要问题就是，如何根据给定问题的特点，设计出求解这一问题的有效的计算方法。设计算法的基本思想就是设法将一个一般的矩阵计算问题转化为一个或几个易于求解的特殊问题，而通常完成这一转化任务的最主要的技巧就是矩阵分解，即将一个给定的矩阵分解为几个特殊类型的矩阵的乘积。例如，求解如下线性方程组，利用三角分解我们有这样，原方程组的解可以通过求解如下的两个三角形方程组，和求得。显然，这两个三角形线性方程组是极容易求解的。这就是著名的Gaussi消去法。4.敏度分析与误差分析由于误差的存在，用计算机做数值计算所得到的结果很少是精确的。通常误差主要有两个来源：一是原始数据本身应有误差，这是由测量或观察的不准确所引起的；二是由计算过程产生的误差。因此，当我们用某种算法求解某一矩阵计算问题得到计算解之后，自然要问：计算解与真解相差多少？这就是计算的精确性问题。要回答这一问题，需要做两个方面的理论分析：敏度分析与误差分析。敏度分析就是研究计算问题的原始数据有微小的变化将会引起解的多大变化，为了叙述简单起见，假定我们所考虑的计算问题是：给定自变量，计算函数值。对于这一计算问题，敏度分析就是研究有微小的变化之后函数值将会发生多大变化，当然，最理想的做法，应该是首先找到自变量的改变量与函数值的改变时之间的依赖关系。但实际上，这是相当困难的，有时即使碰巧找到了这种依赖关系，常常由于其太复杂而变得毫无实用价值。因此，通常的做法是在很小的前提下，设法寻找一个尽可能小的正数使得.这样，的大小就在一定程度上反映了自变量的微小变化对函数值的影响程度。因此，我们称数为在点的条件数。当很大时，自变量的微小变化就有可能引起函数值的巨大变化，因而称此种情况为在点是病态的；反之，当较小时我们就说在点是良态的。这里强调的一点是，一个计算问题是否病态是计算问题本身的固有属性，与所使用的计算方法无关。此外，对于刚才所讨论的计算问题，容易推出，当在点可微时，有但对于一般的计算问题要给出条件数的一个较为合适的估计是相当困难的，关于三类最基本的矩阵计算问题的条件数将在本书以后的有关章节加以讨论。大家知道，计算机只能表示出有限个数，即计算机的精度是有限的。因此，分析舍入误差对一个算法的计算结果是否影响很大显得尤为重要，它是衡量一个算法优劣的重要标志。即使一个十分良态的计算问题，由于使用的计算方法不当，也可使计算结果面貌全非而变得毫无用处。现在我们再以刚才讨论的计算问题为例来说明误差分析的要点。假设用某种算法计算得到的函数在点的函数值是，当然由于舍入误差的影响我们不能期望与相等，但是我们通过对每步具体运算做误差分析可以证明存在满足其中是一个与计算机精度和算法有关的正数。这种把计算结果归结为原始数据经扰动之后的精确结果的误差分析方法称作向后误差分析法。很显然，越小，说明舍入误差对算法的影响越小。因此，当较小时，我们就说该算法是数值稳定的；否则，就说该算法是数值不稳定的。一个算法是否数值稳定是算法本身的固有属性，与计算问题是否病态无关。当我们对给定的计算问题作了敏度分析，并且对所用的算法作了误差分析之后，我们就可给出计算结果的精度估计：由此可见，计算结果是否可靠，依赖于计算问题是否病态和所用的算法是否数值稳定。只有使用数值稳定的算法去求解良态的计算问题，才能期望得到可靠的计算结果。5.算法复杂性与收敛速度算法的快慢是衡量算法优劣的又一个重要标志。算法大致可分为两类：一类是直接法，是指在没有误差的情况下可在有限步得到计算问题的精确解的算法；另一类是迭代法，是指采取逐次逼近的方法来逼近问题的精确解，而在任意有限步都不能得到其精确解的算法。对于直接法，其运算量的大小通常可作为其快慢的一个主要标志。算法复杂性分析就是计算或估计算法的运算量。90年代之前的数值线性代数教科书中，计算运算量时通常只计算乘除运算的次数，这是因为当初的计算机作乘除运算要比加减运算慢得缘故。进入90年代以后，由于计算机的运算速度大幅度的提高，加减运算与乘除运算已相差甚微，因此现在是将一个算法的所有运算次数的总和作为运算量的。其次，假定某一算法共需作次加、减、乘、除运算，则通常是略去其低阶项而说该算法的运算量为.这里需要指出的是，虽然运算量在一定程度上反映了算法的快慢速度，但又不能完全依据运算量来判定一个算法的快慢，这是因为现代计算机的运算速度远远高于数据的传输速度，而这使得一个算法实际运行的快慢在很大程度上依赖于该算法软件实现后数据传输量的大小。而对于迭代法，除了对每步所需的运算量进行分析外，还需要对其收敛速度进行分析。假定某一迭代法产生的序列满足其中，则称该算法是线性收敛的，而且越小越好；若满足则称该算法是平方收敛的（有时亦称二次收敛的），其中是一个不依赖于的正数。显然，平方收敛算法要比线性收敛的算法快得多。