英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
数值算法
“算法”一词来源于公元前790年至公元前840年的Per-sian数学家（Abu Ja#39;far Muhammad ibn Musa）Al-Khwarizmi的名字。他写了一本书，Hisab al-jabr w#39;al-muqabala，也命名为“代数”学科。
数值分析是研究用实数定义的表达式算法的学科。平方根是这样一个表达的例子；我们今天在计算器或计算机程序中评估，就像一样简单。正是数值分析使得这成为可能，我们将研究如何做到这一点。但是在这样做的时候，我们将会看到，同样的做法广泛地应用于包含不能命名的功能，甚至改变了数学中的基本问题的本质，比如说确定不可能为4以上的秩序表达式。
在数值分析中有两个不同的阶段：
算法的展开和算法的分析。
这些原则上是独立的活动，但在现实中, 算法的发展通常是由对算法的分析, 或由一个简单的算法来计算相同的东西或类似的东西。
在一定程度上使用实数的算法有三个特征：
bull;算法的准确性（或一致性），
bull;算法的稳定性，
bull;有限精度算术（a.k.a.round-off error）的效果。
这些中的第一个只是意味着该算法在适当的限制下将所需的量近似为任何所需的准确度。第二个意思是算法的行为与算法的参数是连续的。在最基本的层面上，第三个主题还没有得到很好的理解，因为没有一个完善的有限精度算术的数学模型。相反，我们被迫对有限精度算术的行为使用粗略的上限，这往往会导致对其在实际计算中的效果过于悲观的预测。
我们将会看到，为了提高一个稳定的算法的准确性或有效性，我们经常会考虑到算法是不稳定的，因此算法最小化（如果有的话）。数值分析的这些各个方面往往相互交织在一起，最终我们想要一个可以严格分析的算法，以确保在使用计算机算术时有效。
算法的效率是一个比较复杂的概念，但通常是选择一个算法的另一个算法的底线。它可以与上述所有特征相关，以及算法在计算工作或其执行过程中所需的内存参考方面的复杂性。
数值分析的另一个中心主题是适应性。这意味着计算算法将自身适应于要解决的问题的数据，以提高效率和/或稳定性。一些适应性算法在自动获取有关更有效解决方案所需问题的信息方面非常显着。
我们从古代开始解释这些基本情况下的数值分析的这些组成部分。我们不会总是解决不同的问题，但我们希望这些不同的组成部分是明显的。
1.1找到根源
人们一直在计算数千年的根源。有证据表明，使用基础60算术的巴比伦人能够在近4000年前大概近似。
(1.1)
在Heron1的时代，建立了一种计算平方根的方法[26]，我们现在认为是牛顿-拉夫逊 -辛普森方法（见2.2.1节），并采取反复迭代的形式，其中向后箭头larr;表示算法分配。
(1.2)
也就是说，一旦完成了箭头右侧的表达式的计算，就将一个新的值分配给变量x。一旦分配完成，右侧的计算可以用新的x重做。
算法（1.2）是所谓的固定点迭代的示例，其中希望找到固定点，即迭代退出的x。固定点因此是一个点x，更准确地说，x是函数的x=f(x)的函数，比如说，x=0。
(1.3)
如果我们在(1.3)中重新排列条件，我们就会得到，或者。因此，在(1.3)中，一个解的点是的解，所以.
(1.4)
为了描述这些算法的实际实现，我们选择在系统八度中实现的脚本语法。作为一种编程语言，这有一些局限性，但其使用非常广泛。除了八度音域的公共领域实施之外，还提供了一个名为Matlab的商业解释器（它的八度音阶）。 然而，这里呈现的所有计算都是以八度计完成的。
我们可以在两个步骤中实现（1.2）八度，如下。首先，我们通过代码定义函数（1.4）
function x=heron(x,y)
x=.5*(x y/x);
要使用此功能，您需要从一些初始猜测开始，比如说x = 1，它简单地写成
x=1
（使用和不使用分号编写表达式可以控制解释器是否打印结果）但是，您只需简单地迭代：
x=heron(x,y)
直到x（或您关心的部分）退出。这样做的结果在表1.1中给出。
我们可以通过一个简单的代码检查准确性
function x=errheron(x,y)
for i=1:5
x=heron(x,y);
errheron=x-sqrt(y)
end
在表1.1中，我们在y = 2的情况下显示这些计算的结果。该算法似乎在解决方案中“归入”。 我们会看到，每一步的准确度都翻了一番。
1.1.1相对绝对误差
我们可以要求算法的准确性基于答案的大小。 例如，我们可能希望根x的近似x相对于x的大小是小的
(1.5)
表1.1使用Heron算法的实验结果使用从x = 1开始的算法（1.2）应用于近似。粗体表示前导错误数字。 请注意，正确数字的数量在每一步都基本上加倍。
其中delta;满足一些固定公差，例如这样的要求符合我们将要采用的流程操作模式（见（1.31）和第18.1节）。
我们可以通过简单的代码检查相对精度
function x=relerrher(x,y)
for i=1:6
x=heron(x,y);
errheron=(x/sqrt(y))-1
end
我们以练习1.2的方式比较上述代码重新生成的结果与表1.1中给出的绝对误差。
1.1.2缩放苍鹭的算法
在我们分析Heron算法（1.2）如何工作之前，让我们用预分频来增强它。首先，我们可以假设我们寻求的平方根的数字y在于区间。 如果或，则对于某个整数k，我们使转换得到。
(1.6)
当然也是。 通过以这种方式缩放y，我们限制了算法必须处理的输入范围。
因此，无论初始误差有多大，相对误差都会在每次迭代时减小一个小于1 2的因子。 不幸的是，这种类型的全局收敛属性不适用于许多算法。
在表1.1中，我们显示了接近的绝对误差，在练习1.2中，探讨了接近和的相对误差。事实证明，间隔的最大误差发生在间隔的末尾（练习1.3）。因此，在缩放（1.6）之前，对于苍鹭的五次迭代，很有效地计算到16位小数。
缩放提供了一个简单的自适应示例，用于生成根的算法。没有缩放，全球表现（第1.2.2节）将是相当的不同。
1.2分析HERON的算法
顾名思义，数值分析的一个主要目标是分析Heron迭代（1.2）等算法的行为。在这方面可以提出两个问题。首先，我们可能对算法的本地行为感兴趣，假设我们在所需根附近有合理的开始。我们将看到，这可以完全相当完整，无论是在Heron迭代的情况下，还是通常用于这种类型的算法（在第2章中）。 其次，我们可能会想到算法的全局行为，也就是说，它将如何以任意的起点进行响应。使用苍鹭算法，我们可以给出一个相当完整的答案，但一般来说它更复杂。 我们的观点是，全球行为真的是一个不同的主题，例如动态系统的研究。 我们将看到缩放技术（第1.1.2节）为将本地分析转化为融合理论提供了基础。
1.2.1局部误差分析
由于苍鹭的迭代（1.2）本质上是递归的，所以自然地期望错误也可以递归地表达。我们可以为Heron的迭代（1.2）编写代数表达式，将错误在一次迭代链接到下一个错误。因此定义并让。
(1.7)
然后通过（1.7）和（1.3），
(1.8)
如果我们对相对误差感兴趣，
(1.9)
则（1.8）变为
(1.10)
所以我们看到了
the error at each step is proportional to
the square of the error at the previous step;
对于相对误差，比例常数很快就会趋于1。在 (2.20)，我们将看到相同的结果可以通过一般的技术得到。
1.2.2全局误差分析
另外，（1.10）意味着有限类型的全局收敛属性，至少对于。在这种情况下，（1.10）给出
(1.11)
因此，无论初始误差有多大，相对误差都会在每次迭代时减小一个小于1 2的因子。不幸的是，这种类型的全局收敛属性不适用于许多算法。我们可以说明当时，Heron算法的情况可能出错。
因此，无论初始误差有多大，相对误差都会在每次迭代时减小一个小于1 2的因子。不幸的是，这种类型的全局收敛属性不适用于许多算法。我们可以说明当时，Heron算法的情况可能出错。
假设为了简单起见，y = 1，所以也是x = 1，所以相对误差是，因此（1.10）意味着
(1.12)
，，即使因此，对于Heron算法，收敛性并不全面。
如果我们从开始接近零，会发生什么？ 我们在infin;附近获得。从那时起，迭代满足，所以迭代最终是收敛的。但是，根据的小，将误差降低到固定误差容差以下所需的迭代次数可以任意增加。同样的道理，我们不能限制任意大所需的迭代次数。幸运的是，我们将看到，为了避免这种潜在的不良行为，可以选择好的起始值，以避免这种潜在的不良行为。
1.3从何开始
使用任何迭代算法，我们必须在某处开始迭代，这个选择本身就是一个有趣的问题。 就像第1.1.2节中描述的初始缩放一样，这可以显着地影响整体算法的性能。
对于苍鹭算法，有各种可能性。 最简单的只是取，在这种情况下
(1.13)
这给了
(1.14)
我们可以使用（1.14）作为的公式作为x的函数（通过定义的函数）; 那么我们看到了
(1.15)
通过比较（1.14）中最右边的两个术语。 请注意，上的最大出现在间隔的末尾，
(1.16)
因此，简单的起始值x0 = 1是非常有效的。不过，让我们看看能否做得更好。
1.3.1另一个开始
开始迭代的另一个想法是给出我们总是具有yisin;[]（第1.1.2节）这个事实的近似函数。 由于这意味着y接近1，所以我们可以写入y = 1 t（即t = y -1），我们有
(1.17)
因此，我们得到近似值作为可能的起始猜测：
(1.18)
但是，如果我们从开始，这与相同。所以我们还没有找到任何新的东西。
1.3.2最好的开始
我们基于对平方根的线性近似的第一次尝试（1.18）没有产生一个新的概念，因为它给出与在一次迭代之后的恒定猜测开始相同的结果。 近似值（1.18）对应于y = 1时的图的切线，但这可能不是对间隔函数的最佳逼近。 所以让我们问一个问题，线性多项式在间隔 []上的最佳逼近是什么？这个问题是我们将在第12章中讨论的问题的缩影。
因此，无论初始误差有多大，相对误差都会在每次迭代时减小一个小于1 2的因子。不幸的是，这种类型的全局收敛属性不适用于许多算法。同样的道理，我们不能限制任意大x_0所需的迭代次数。幸运的是，我们将看到，为了避免这种潜在的不良行为，可以选择好的起始值，以避免这种潜在的不良行为。
一般线性多项式为形式
(1.19)
如果我们把，则相对误差是
(1.20)
<p
全文共7739字，剩余内容已隐藏，支付完成后下载完整资料</p
资料编号：[143918]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
