迭代法

迭代法第一章绪论内容提要§1.1计算方法的任务与特点§1.2误差知识§1.3选用算法时应遵循的原则§1.1计算方法的任务与特点提出实际问题辨析其中的主要矛盾和次要矛盾，并在合理假设的条件下，运用各种数学理论、工具和方法，建立起问题中不同量之间的联系，即得到数学模型。建立数学模型模型的适定性:数学模型解的存在性（模型内部没有蕴含矛盾）、惟一性（模型是完备的)以及对相关数据的连续依赖性统称为模型的适定性.科学与工程计算过程：提出数值问题数值问题是指有限个输入数据（问题的自变量、原始数据）与有限个输出数据（待求解数据）之间函数关系的一个明确无歧义的描述。这正是数值分析所研究的对象。数值问题举例是用一阶常微分方程初值问题表示的数学模型，要求无穷多个输出，因而它不是数值问题。但当我们要求出有限个点处函数值的近似值时，便成为一数值问题。02010yyxyxdxdy)(],[设计高效可靠的算法计算方法的任务之一就是提供求得数值问题近似解的方法—算法。算法：指把对数学问题的解法归结为只有加、减、乘、除等基本运算，并确定运算次序的完整而准确的描述。算法分类:分类方法1：若算法包含有一个进程则称其为串行算法，否则为并行算法。分类方法2：从算法执行所花费的时间角度来讲，若算术运算占绝大多数时间则称其为数值型算法，否则为非数值型算法。本课程介绍数值型串行算法。（其它类型算法参阅数据结构、并行算法等课程。）算法的可靠性：算法的可靠性包括算法的收敛性、稳定性、误差估计等几个方面。这些是数值分析研究的第二个任务。一个算法在保证可靠的大前提下再评价其优劣才是有价值的。算法的优劣评价：可靠算法的优劣，应该考虑其时间复杂度（计算机运行时间）、空间复杂度（占据计算机存储空间的多少）以及逻辑复杂度（影响程序开发的周期以及维护）。这是数值分析研究的第三个任务。算法应用状态计算方法研究对象以及解决问题方法的广泛适用性，著名流行软件如Maple、Matlab、Mathematica等已将其绝大多数内容设计成函数，简单调用之后便可以得到运行结果。但由于实际问题的具体特征、复杂性，以及算法自身的适用范围决定了应用中必须选择、设计适合于自己特定问题的算法，因而掌握数值方法的思想和内容是至关重要的。科学与工程计算过程小结•提出实际问题•建立数学模型•提出数值问题•设计可靠、高效的算法•程序设计、上机实践计算结果•计算结果的可视化在具体问题的求解过程中，上述步骤形成一个循环。科学计算（数值模拟）已经被公认为与理论分析、实验分析并列的科学研究三大基本手段之一。鉴于实际问题的复杂性，通常将其具体地分解为一系列子问题进行研究，本课程主要涉及如下几个方面问题的求解算法：函数的插值和曲线拟合数值积分和数值微分线性方程组求解、非线性方程（组）求解代数特征值问题常微分方程数值解法本课程主要内容本课程的学习方法尽管本课程所讲算法是很有限的，但许多初学者可能仍会觉得公式多，理论分析复杂。在此，我们提出如下的几点学习方法，仅供初学者参考。1、认识对每个算法进行理论分析是基本任务，主动适应公式多和讲究理论分析的特点。2、注重各章节所研究算法的提出，搞清楚问题的基本提法、逐步深入的层次及提法的正确性。3、理解每个算法建立的数学背景、数学原理和基本线索，而且对一些最基本的算法要非常熟悉。4、从各种算法的理论分析中学习推理证明方法，提高推理证明能力。5、认真进行数值计算的训练。§1.2误差知识内容提要：1.误差的来源及其分类2.误差的度量3.误差的传播一、误差来源及其分类1)模型误差（描述误差）反映实际问题有关量之间的计算公式（数学模型）通常是近似的。2）观测误差数学模型中包含的某些参数是通过观测得到的。221rmmGF在计算方法中不研究这两类误差，总是假定数学模型是正确合理的反映了客观实际问题。3）截断误差（方法误差）数值方法精确解与待求解模型的理论分析解之间的差异。这是由于我们需要将无穷过程截断为有限过程，而使得算法必须在有限步内执行结束而导致的。neeee,!n1!21!111,!21!111n例如：4）舍入误差在实现数值方法的过程中，由于计算机表示浮点数采用的是有限字长，因而仅能够区分有限个信息，准确表示某些数，不能准确表示所有实数，这样在计算机中表示的原始输入数据、中间计算数据、以及最终输出结果必然产生误差，称此类误差为舍入误差。如利用计算机计算e的近似值en时，实际上得不到en的精确值，只能得到en的近似e*；这样e*作为e的近似包含有舍入误差和截断误差两部分：)()(nn**eeeeee二、误差的度量1)绝对误差2)相对误差3)有效数字4)度量间的关系1.绝对误差绝对误差定义：准确值减近似值)(**xexx在不引起混淆时，简记)(*xe为*e。],[****xxx，**xx。如果存在正数)(**x，使得有绝对误差***xxe，则称*为x*近似x的一个绝对误差限。Remark:通常计算中所要求的误差，是指估计一个尽可能小的绝对误差限。•绝对误差限：2.相对误差•Remark:绝对误差限虽然能够刻划对同一真值不同近似的好坏，但它不能刻划对不同真值近似程度的好坏。定义设x*是对准确值x（0）的一个近似，称*****)()(xxexxxxer为x*近似x的相对误差。不引起混淆时，简记)(*xer为*re.相对误差限：数值*re的上界，记为)(*xr。相对误差限也可以通过*rx**来计算。Remark1:当要求计算相对误差，是指估计一个尽可能小的相对误差限。Remark2:相对误差及相对误差限是无量纲的，但绝对误差以及绝对误差限是有量纲的。3.有效数字为了规定一种近似数的表示法，使得用它表示的近似数自身就直接指示出其误差的大小。为此需要引出有效数字和有效数的概念。定义：设x的近似值x*有如下标准形式p1nn21m*xxxxx.010x，其中m为整数，},,,,{}{9210xi且0x1，np.如果有nm21*10e*xx，则称x*为x的具有n位有效数字的近似数，或称x*准确到nm10位，其中数字n21xxx,,,分别被称为x*的第一、二、…、n个有效数字。有效数：当x*准确到末位，即n=p，则称x*为有效数。举例：x=π,x1*=3.141,x2*=3.14231*11021005.000059.0xx41*210210005.000040.0xx3位有效数字，非有效数4位有效数字，有效数Remark1:有效数的误差限是末位数单位的一半，可见有效数本身就体现了误差界。Remark2:对真值进行四舍五入得到有效数。Remark3:准确数字有无穷多位有效数字。Remark4:从实验仪器所读的近似数（最后一为是估计位）不是有效数，估计最后一位是为了确保对最后一位进行四舍五入得到有效数。–例从最小刻度为厘米的标尺读得的数据123.4cm是为了得到有效数123.cm,读得数据156.7cm是为了得到有效数157.cm。4.误差度量间的联系绝对误差与相对误差nmxe10)(21*定理：10若x*具有n位有效数字，则相对误差n1110x21*re；20若相对误差n1110)1x(21*re，则x*至少具有n位有效数字。绝对误差与有效数字相对误差与有效数字)(/)(***xexxer定理证明nm1021****rxxeen11nm11-m10x21101021xo1o2)1(1010)1x(2111-mn11xxee**r*nm1021证毕,10)1(1011*11mmxxxnmxe1021)(*Remark1、该定理实质上给出了一种求相对误差限的方法。2、仅从并不能保证x*一定具有n位有效数字。如设其近似值a=0.484，其相对误差为：我们并不能由此断定a有两位有效数字，因为nrxe11*10214900.00229sinA21104210125.0012397.0484.0484.04900.0201021005.00600.0484.04900.0aA例题为使5x的近似值x*的相对误差不超过1%，问查开方表时至少要取几位有效数字？设近似数x*保留n位有效数字可满足题设要求.解：对于5x，有x1=2.依据定理1o有n1n11*r104110x21e令01.01041n1，解得2.4n.取n=3位有效数字。#三、数值运算的误差估计概念：近似数参加运算后所得之值一般也是近似值，含有误差，将这一现象称为误差传播。误差传播的表现：–算法本身可能有截断误差；–初始数据在计算机内的浮点表示一般有舍入误差；–每次运算一般又会产生新的舍入误差，并传播以前各步已经引入的误差；–误差有正有负，误差积累的过程一般包含有误差增长和误差相消的过程，并非简单的单调增长；–运算次数非常之多，不可能人为地跟踪每一步运算。初值误差传播：假设每一步都是准确计算，即不考虑截断误差和由运算进一步引入的舍入误差，仅介绍初始数据的误差传播规律。–研究方法：泰勒（Taylor）方法–n元函数复习泰勒公式))(())((!11)()(***11*1*nnnxxpfxxpfpfpf记点),,,(**2*1nxxx为p*,点),,,(21nxxx为p，n元泰勒公式：21112221122211112111121)xx)(p(f)xx)(xx)(p(f)xx)(xx)(p(f)xx)(xx)(p(f)xx)(xx)(p(f)xx)(p(f!*nn*nn**nn*n*nn**n****nn**n**泰勒公式分析初值误差传播设n元可微函数),,,(n21xxxfy中的自变量x1、x2、…、xn是相互独立的。用自变量的近似值进行准确计算，得y*=),,,(***n21xxxf。当*1x、*2x、…、*nx很好地近似了相应真值时，利用多元函数一阶Taylor公式求得y*的绝对误差：n1i*ii*n*1'i**))(,,()(xxxxfyyyen1i*i*n*1'i)(),,(xexxf相对误差：n1i*i*i*n*1'i**i***)(),,()()(xxexxfyxyyeyern1i*i*n*1'i**i)(),,(xexxfyxr进而得到如下绝对误差限和相对误差限传播关系：n1i*i*n*1'i*)(),,()(xxxfyn1i*i*n*1'i**i*)(),,()(xxxfyxyrr二元函数算术运算误差传播规律)()()(*2*1*2*1xxxx)()()(*2*1*1*2*2*1xxxxxx)0()()()(*22*2*2*1*1*2*2*1xxxxxxxx绝对误差限相对误差限)}(),({max)(*2*1*2*1xxxxrrr)(**021xx)()()(*2*1*2*1xxxxrrr)(**021xx)()()(*2*1*2*1xxxxrrr)(**021xx§1.3选用算法应遵循的原则简化计算步骤以减少运算次数。842842284488163*3*3*3*33*3*3*33*3*33*33例1例2秦九韶算法01223344axaxaxaxa01234)))(((axaxaxaxa)10(98765432110000001kkk例尽量避免相近的数相减例x=52.127x*=52.129四位有效数字y=52.123y*=52.121四位有效数字A=x-y=0.004A*=x