《计算方法第一讲》PPT课件

数值分析,赵丽娜zhaoln,邓建中，刘之行，西安交通大学出版社，计算方法，2001年李庆扬，关冶数值分析原理，清华大学出版社，2000年李庆扬，易大义，王能超现代数值分析，高教出版社，1995年MichaelT.H.ScientificComputing:AnintroductorySurvey,清华大学出版社，2001MatlewsJ.H.NumericalMethodsUsingMatlab,电子工业出版社，2002,教材与参考书,数值分析或计算方法的历史早于计算机的产生，许多（如今仍在使用的）概念与方法由二十世纪前的伟人给出Newton(1642-1727)Euler(1707-1783)Lagrange(1736-1813)Laplace(1749-1817)Legendre(1752-1833)Hermite(1822-1901)Gauss(1777-1855)Cauchy(1789-1857)Jacobi(1804-1851)Adams(1819-1892)Chebyshev(1821-1894)Laguerre(1834-1886),第一讲数值分析的意义内容与方法,起源：寻找有效的方法获得数学问题的近似解。数学问题源于物理，天文，勘测等在仅使用纸，笔，大脑，而不是计算机进行计算时，算法效率尤为重要。如今，大规模计算成为可能，更要仔细分析控制截断误差,1.1数值分析的起源与意义,随着计算机的普及与发展，计算机性能的大幅提高，海量数据的出现，科学计算更为重要科学计算已成为现代科学技术的研究方法的第三大方法理论推导，科学试验，科学计算其他应用：符号计算、计算几何、定理的机器证明,科学计算的定义,将科学技术问题通过建立数学模型转换为数学问题；将数学问题离散化得到数值问题；使用数值计算方法求出数值问题的解；并把所得的解作为原科技问题的解。,实际问题,数学问题,可计算问题,数学建模,构造算法,计算求解,计算结果,反馈、修正、应用,解决实际问题,计算数学是科学计算的核心,计算数学-对数学模型问题研究数值求解方法，分析方法的性质数学问题通过数值计算方法化为可计算问题，然后进行计算求得结果按研究内容可分为：数值代数、数值逼近、数值微积分、微分方程数值解、最优化计算、概率统计计算、计算几何、计算力学等。,是否有了计算机，找到数学公式就可以得到正确的结果？,例1：,解为：x1=x2=x3=1,如近似为：则解为：,1.2数值问题与算法,数值问题是指输入数据（原始数据，问题中的已知量）与输出数据（结果）之间的函数关系的明确的无歧异的问题数学问题未必是数值问题，但它往往可以用数值问题来逼近,例2：求常微分方程,由题目要求，需给出y=y(x)解析式，该问题不是数值问题；若输出y=y(x)在（给定步长h）x=h,x=2h,x=nh处的近似值，则该问题转化为数值问题。,算法及其好坏,计算机的基本运算：四则运算、简单逻辑运算计算机的算法可分为串行算法和并行算法好的算法：1、面向计算机，易于编程和计算实现；2、计算复杂性好：计算时间少、占用内存少；3、计算稳定性好：能有效控制由于方法近似和舍入误差引起的误差增长，结果能达到所要求的精度；4、适用性好。,例3：计算多项式x=a时p(a)的值。,普通方法时间：n(n+1)/2次乘法；n次加法秦九韶算法,时间：n次乘法；n次加法,例：计算多项式：需10次乘法4次加法。4次乘法4次加法。这是多项式计算的秦九韶算法。3次乘法5次加法。,例4解代数方程：,直接法：用Cramer法则解，若det(A)不为0，,1.3数值计算的基本方法论,有限近似无限：有限维空间代替无限维空间；有限和代替积分或无限级数；差商近似导数；代数方程组近似微分方程组；高阶方程低阶化非线性问题线性化复杂函数用简单函数来代替（多项式泰勒展开）一般矩阵简单化,原则：复杂问题Q1简单问题Q2Q2与Q1的解在一定意义下相同。,直接方法（适用于可有限步内直接计算得到解的问题）截断近似：利用一些展开式截取其若干项来近似迭代法线性化：非线性问题局部线性化化整为零：将整体问题分割为若干小部分处理外推法：利用已算出的结果适当组合得到更精确的结果,例5：计算sinx，x0，/4,例6：求解函数方程f(x)=0.例7：求解函数方程,例9：求解常微分方程,例8：计算定积分,一个具体的例子：迭代格式为：,精确解：,例：求方程根，如z10系数210略有误差，为210.000000119，则根20变为20.847，19和18变为19.5021.94i.例：求解微分方程,某些问题的计算中，由于数据的微小变化引起解的剧烈变化，称这类问题为病态问题和坏条件问题。对于这类问题的计算，一定要采用高精度计算。但对于非病态的良态问题，如算法不当，由于计算机的近似性，有时也可能得到不可靠的结果。,例：如在尾数为4位的计算机上计算其真正值为0.05572809，但计算结果为：0.0560，但如果先进行有理化在计算，结果为：0.05574，显然，后一种计算精度高。例：如在尾数为4位的计算机上计算精确值为34.5612，计算时如先加前两项，再加后一项，结果为34.57，如先加后两项，再加前一项，结果为34.56，显然，后一种算法更好。,例：如在尾数为4位的计算机上计算按两种不同递推计算，结果为：,由此可见，舍入误差对计算有影响，影响小的算法称为数值稳定的算法。有些算法具有递推性，称之为迭代法或逐次逼近法。再计算一些复杂的函数的值，有时我们用一些简单的函数（如多项式、有理函数等）来近似之，这称为函数逼近。有时要求逼近函数与被逼近函数之间在某些点函数值及若干阶导数值相等，这种逼近称为插值；有时要求在逼近区间上的最大误差取极小，这称为最佳一致逼近；或在某些点的误差值平方和取极小，这称为最佳平方逼近。,2误差及有关概念2.1误差的来源真实值与我们所获得的值之间的差异就是误差。对实际问题的研究需要建立数学模型，这带来模型误差。求解数学问题时需要若干参量和初始值，这些数据往往通过对实际问题的观测得到，由于观测引起的误差称为观测误差（数据误差、模型参量误差）。求解数学问题时，由于算法而引起的误差称为方法误差（截断误差）。计算机计算时只能对有限位数进行计算，超过的进行舍入，由此引起的误差称为舍入误差（计算误差）。,实际问题,数学问题,可计算问题,数学建模,构造算法,计算求解,计算结果,（模型误差）,（方法误差）,（舍入误差、输入数据误差）,2.2绝对误差与相对误差设x为真正值，为近似值，称：为近似值的绝对误差（简称误差）通常我们要求绝对误差不能超过某个值，称为绝对误差限或误差限。,设x为真正值，为近似值，称：为的相对误差。如果存在r，使得，称之为相对误差限。在实际计算中，相对误差限很小时，也取：,2.3有效位数与有效数字如果的误差限为0.510-n，即则称其准确到小数后第n位，并称的第一个非零数字到第n位的全部数字为的有效数字。,例如，若x=3.1415926535，,则,准确到小数后4位，具有5位有效数字。,显然，近似值的绝对误差越小，其准确到小数后的位数越多。,注意，若x=0.200001，,则,作为x的近似只有1位有效数字，而,作为x的近似具有4位有效数字。,具有k位有效数字，则易知,若,这说明近似值的相对误差越小，其有效数字越多。,2.4数据误差的影响2.4数据误差的影响对两个数x1和x2，简单计算可得：,可见，当x1和x2同号时，反之，当x1和x2异号时，尤其,这表明，大小接近的异号数相加或大小接近的同号数相减，会严重损失有效数字！乘数绝对值很大，或除数接近零时，可能会严重扩大绝对误差，减少精度！开方会减少相对误差，提高精度。,一般地，设数学问题的解为,近似解为：则绝对误差为：相对误差为：,和起对误差的放大和缩小作用，其绝对值分别称为所求解的数学问题的绝对误差下的条件数和相对误差下的条件数。条件数很大时称该问题为病态问题或坏条件问题，它是问题固有的属性，与算法无关。但由于这类问题数据的微小变化会引起解的剧烈变化，对于这类问题的计算，一般要采用高精度计算，或改变问题的提法，降低条件数。,2.5舍入误差的影响,在计算机中，用浮点法表示的数（称为浮点数）的尾数，位数是固定的，称为字长。设计算机字长为t，任意数x十进制是按舍入原则表为浮点数则相对误差的绝对值,记称为计算机的相对精度。我们有：,则对于多数相加相对误差,类似地有在大体相同情况下，如则于是可得，多数相加时，一般先加绝对值较小的数，相对误差较小！,通常称舍入误差对计算结果影响不大的算法为稳定的算法，反之为不稳定的算法。,计算数学的特点：1、面向计算机（构造计算机能用的算法）；2、要有可靠的理论分析（