第1讲(2014-9-10)

数值分析王云诚办公室：文理大楼1207电话：8249346E-mail:[e-mail]2014年9月10日关于教学参考书的建议1．科学和工程计算基础。施妙根、顾丽珍编。清华大学出版社，1999。2．数值分析（第五版）。李庆扬、王能超、易大义编，清华大学出版社，2008。3．科学计算导论（第二版）。MichaelT.Heath著。清华大学出版社，2005。课程成绩判定平时成绩：40%（考勤）期末成绩：60%（开卷）第一章绪论§1数值分析的几个基本问题一、用数学方法解决科学与工程问题的步骤实际问题建立数学模型求解数学模型的计算方法（本课程针对基本模型）编程，并上机计算求出问题的结果。二、研究对象用计算机求解数学模型的计算方法：符号运算数值运算本课程研究：数值计算方法三、研究内容(1)数值代数:线性方程组的解法，求矩阵的特征值与特征向量。(2)函数逼近：插值法，数值微分和数值积分，数据拟合。(3)方程求解：非线性方程（组）、常微分方程数值解法。四、研究数值计算方法的意义（1）很多数学模型不能用公式求解（2）手工求解计算量巨大（3）新的数学模型不断被提出五、算法设计的基本思想基本思想一：连续问题离散化计算机只能计算离散点的函数值，对于连续取值的问题，必须通过离散化方法解决。【例1】计算函数在一个区间上的定积分。只能利用区间上有限个点（逐步增多）处的函数值，计算处定积分的近似值。【例2】求常微分方程定解问题的解。理论上它的解是一个区间上的函数，但用计算机只能求出离散点处方程的近似解。基本思想二：迭代法大多数数学模型的解，不能通过一次计算得到，而需要采用逐步逼近的方式，求出其满足一定精度要求的近似解。【例3】求非线性方程0)(xf的根，一般方法是构造一个近似解序列，使序列收敛到方程的解。【例4】大规模线性方程组，一般方法是构造一个近似解向量序列，使序列收敛到方程的解。基本思想三：局部近似（1）以直代曲【例5】求非线性方程()0fx的根*x。牛顿法：在当前近似根kx处作曲线()yfx的切线，该切线与x轴的交点作为1kx，由此产生的点列kx在一定条件下可收敛到方程的根*x。（2）化整为“零”后近似【例6】计算定积分()dbafxx的值。基本思路：——将曲边梯形分割为若干小曲边梯形；——将曲边梯形用矩形或者梯形近似；——以小矩阵面积的和近似曲边梯形的面积。事实上，“以直代曲”的思路”，可以推广到“以简代繁”。譬如，计算定积分值的“以直线代曲线”，可以“以抛物线代曲线”。六、算法应具备的特性（1）算法应是计算机可执行的；（2）算法要有理论分析作支持：包括收敛性，收敛速度，数值稳定性，误差分析等；（3）算法要有好的计算复杂性：时间复杂性，空间复杂性；xy0y=f(x)0ax1x2x1ixix1nxnxb（4）算法要有数值实验验证。§2数值计算的误差采用数值计算方法，一般只能得到问题的近似解。研究算法产生误差的原因，以及得到的近似解与问题的精确解之间的“近似程度”是必要的。一、误差的分类1．截断误差截断误差也叫做公式误差。在科学计算中，计算一个数学问题，常采用近似公式。近似公式带来的误差称为截断误差。【例7】计算!7!5!3sin753xxxxx)()!12()1(1212xRnxnnn用多项式)!12()1(!7!5!312753nxxxxxnn近似xsin带来的误差)(12xRn叫做截断误差。【例8】计算baxxfd)(也要用近似公式，两者之间的误差叫做近似公式的截断误差。2．舍入误差计算机存储实数时，只能保存有限位，通常采用“四舍五入”近似，这一误差叫做舍入误差。舍入误差很难分析，因此，在误差分析方面，本课程主要研究算法的截断误差。二、误差的概念1．绝对误差定义：设x为准确值（真值），*x为x的一个近似值，称xxxE**)(为近似值*x的绝对误差，简称误差。绝对误差可能是正的，也可能是负的。由于准确值x通常是不知道的，所以绝对误差)(*xE实际上也无法准确度量。通常根据算法估计)(*xE的一个上界)(*x，叫做近似值*x的误差界（或误差限），即)()(***xxxxE.误差限不依赖于准确值x，并且不是唯一的。通常误差限要尽可能小，它取决于误差分析的技术水平。2．相对误差定义：当0x时，称xxExEr)()(**为近似值*x的相对误差。在实际计算中，由于准确值x是未知的，通常取****)()(xxExEr，作为*x相对误差，并取****)()(xxxr作为*x的相对误差限。问题：相对误差限的上述两种定义，何时“基本相等”？结论：当****)()(xxExEr的绝对值较小时。这是因为0))((1))(())(())(())(()()(**2*****2*******xxExxExExxxExxxxxExxExxE因此，***)()(xxExxE。【例9】已知71828182.2e，其近似值为71828.2*e，求*e的绝对误差限和相对误差限*r。解：因为00000182.0*eeE，所以61083.100000183.000000182.0E从而可取*e的绝对误差限为：61083.1。又766**108.61067.071828.21083.1eeE所以可取*e的相对误差限*r为：7*108.6r。3．有效数字如果一个实数的精确值有无限多位，或位数很多，计算机一般按“四舍五入”取其近似值（单精度8位，双精度16位）。例如：按“四舍五入”的规则，14159265.3取3位近似值得*233.14,13.14102取5位近似值，得*453.1416,13.1416102由于上述两个近似值是按“四舍五入”得到的，它们的绝对误差的绝对值都不超过近似值末位数字的半个单位。除了绝对误差和相对误差，还可以用“有效数字”描述近似数的“近似程度”。定义：如果*x的误差绝对值不超过某一个数字的半个单位，且该数字到*x的第一位非零数字共有n位，则称用*x近似x时具有n位有效数字。注意：这一定义中，近似值*x不一定是有限位小数。如何判别有效数字的位数？情形一：如果*x是四舍五入后得到的近似值，并且*x从左面第一位非零数字到最后一位数字共有n位，则*x具有n位有效数字。例如：取14.3*作为的近似值，*有3位有效数字；取1416.3*作为的近似值，*有5位有效数字。情形二：将*x表达为nkx21*.010其中k是某个整数，n,,1为9~0中的数字，并且01。根据定义，当且仅当)1021(10)1021(10*)1(nknkxx时，*x恰有n位有效数字；仅右面的不等式成立时，*x至少具有n位有效数字。例如：用722*作为1415926.3的近似值，有几位有效数字？因为*22100.3142857，4*31110(10)10(10)22所以*有3位有效数字。如果一个准确值有1n位（首位不等于0），当末位按“四舍五入”处理后，得到的n位近似值一定有n位有效数字。下面的定理反映了相对误差与有效数字的关系。定理设*x是x的近似值，则*x的有效数字与*x的相对误差之间有如下关系：（1）若*x具有n位有效数字，则*x的相对误差*re满足*11102nre（2）若*x的相对误差*re满足*1102nre则*x至少有n位有效数字。证明设*x表示为*12100.knx其中n,,1为9~0中的数字，并且01。则1*1010kkx（1）当*x具有n位有效数字时，按定义，有)1021(10*nkxx从而**1*1102nrxxex（2）当*x的相对误差*re满足*1102nre时，有**1102110(10)2nknxxx因此，*x至少有n位有效数字。这个定理说明，近似值的有效数字位数越多，即n越大，相对误差就越小；反之，相对误差越小，则有效数字的位数就可能越多。三、数值运算的误差当自变量有误差时，一般地，其函数值也有误差。误差——可能是截断误差——也可能是舍入误差1．一元函数的误差设*x是准确值x的近似值，则函数)(xf的近似值为)(*xf。由于))(()()(**xxfxfxf，介于x与*x之间，所以)()()()(**xxfxfxf从而)()())((**xfxf2.多元函数的误差对于多元函数),,,(21nxxxf，设自变量的近似值分别为**2*1,,,nxxx，则),,,(),,,(),,,((21**2*1**2*1nnnxxxfxxxfxxxfE)(|)(|*),,,(*1),,,(1**2*1**2*1nxxxnxxxxexfxexfnn于是误差限),,,((**2*1nxxxfnkkxxxkxxfn1*),,()(|**2*1特别)()()(*2*1*2*1xxxx)()()(*1*2*2*1*2*1xxxxxx2*2*1*2*2*1*2*1)()()/(xxxxxxx