【精品】数值代数期末论文

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