计算科学导论

科学计算导论1.1介绍•学科名称：数值分析(numericalanalysis第1页)、数值计算、计算方法、科学计算(scientificcomputing第1页)•连续数学问题中的数值–连续问题，非离散–一些问题在理论上也没有有限步算法–一些问题迭代法比直接计算法更好–限制不仅要考虑目标，还要考虑方法、细节、条件、误差、效率、代价、稳定……特点—与数学的关系•纯数学常见问题是是否存在，表达式是什么，对于如何计算，计算是否容易则很少涉及。•计算方法解决数学问题，是数学一个分支，最接近应用的数学–应用中需要具体的“数值”，科学计算需要给出的是一个确定的计算机算法，描述了输入和输出（都是有限维数据）之间的关系。并且对得到数值的计算方法要分析（理论、误差、算法复杂性可靠性等）数值问题例用每秒运算30亿次（主频3.0G）的计算机求解时，大约需要10000年的时间22020!(201)9.710当n=20时，如果使用高斯消去法，不到一秒钟就能完成例：求解一个n阶线性方程组，如果使用克莱姆法则，需要计算n+1个n阶行列式，在不计加减运算情况下，至少需要n!(n2-1)次乘除运算。而使用高斯消去法，只需约2n3/3次乘除运算例•x=e^-x在[0,1]上的根•求f(x)积分，如f=e^(-x^2)特点--计算工具•进几十年出现的强大计算工具，如何充分发挥计算机的强大功能？•需要计算工具----计算机–数值问题的核心是（计算机）算法–算法是计算机科学中的常用词，计算机算法主要包括数值算法、非数值算法、软计算•非数值算法：搜索、排序、分类等•软计算：近来发展的不确定性算法的总称，包括随机模拟、神经网络计算、模糊逻辑等•数值算法：本课程的内容特点•需要计算工具----计算机–要面向计算机。计算机是目前的主要计算工具–要有可靠的理论依据。误差、收敛性、稳定性–算法要简练。有好的计算复杂性，包括时间复杂性、空间复杂性–要有数学试验。应用•生活中的例子•是各种科学与工程计算领域（如：气象、地震、核能技术、石油探勘、航天工程、密码解译等）中不可缺少的工具•数值计算方法已深入到各个科学研究领域，计算性交叉学科不断涌现，如计算力学、计算物理、计算化学、计算生物学、计算经济学等应用•模拟试验、计算结果可视化。可视化技术广泛应用于流体力学、有限元分析、医学、天气预报、海洋和空间探测等领域。从计算数据发掘其蕴含的规律。应用•使用计算机进行科学计算、数据处理及分析已成为人类科技活动的主要方法之一。熟练地使用计算机进行科学计算，已成为科技工作者的一项基本技能研究对象•Whatisscientificcomputing?–Designandanalysisofalgorithmsfornumericallysolvingmathematicalproblemsinscienceandengineering–借助计算机高速计算的能力，来解决现代科学中的数值计算问题解决实际问题过程实际问题数学模型数值方法程序设计上机实现教材第3页第1步•第1步，建立数学模型，要求•第1步不是科学计算的内容第二步的策略•Replacedifficultproblembyeasieronehavingsameorcloselyrelatedsolution(第3页)–infinitefinite–differentialequationalgebraicequation–nonlinearlinear–high-ordersystemlow-ordersystem–complicatedfunctionsimplefunction–generalmatrixsimplematrix策略•总的来说，就是对原始的复杂问题，找到一个（一系列）简单问题。这个（这些）简单问题易解，而且与原问题同解（一定范围内）这学期的学习内容•具体学习内容，时间进度•学习经典方法•学习解决问题的方法，基本思想和原理，为解决新问题打基础•基础知识：微积分、线性代数、计算机编程语言学习方法•参考书（考研辅导书）•预习•习题•上机，编程语言：Matlab、java•成绩：期末，平时（作业，上机，课堂）•难度教材•ScientificComputing–AnIntroductorySurvey–SecondEdition•MichaelT.Heath参考书•科学计算导论•张威（等）译•清华大学出版社1.2误差•这一节介绍关于误差的一些基本概念、方法•误差产生的原因（种类）–模型误差、测量误差、已有数据误差–截断误差（方法误差、算法误差）、舍入误差•后两种误差是这门学科关注的误差•误差分析：研究算法精确度•例1.1绝对误差和相对误差•近似值＝真值×（1+相对误差）•真值＝0时，相对误差无定义•Truevalueusuallyunknown,soweestimateorbounderrorratherthancomputeitexactly•Relativeerroroftentakenrelativetoapproximatevalue,ratherthan(unknown)truevalue相关的一些概念•例如，真值10，绝对误差0.1，则相对误差为0.01，也可以百分数表示1％•有效数字significantdigits–有效数字绝对误差相对误差关系•精度（精密度）precision表示数字使用的数字位数•精确度accuracy有效数字的位数•例误差分类：数据误差与计算误差•最后结果的误差还可以分为2个来源例1.2•数据误差•计算误差•两种误差的总和计算误差分类：截断误差和舍入误差•计算误差再分为两类–截断误差–舍入误差•截断误差：假设计算过程中没有舍入，只是由于方法产生的误差（只取有限项、有限次迭代等）。exactarithmetic—精确运算（没有算术运算方面的误差）•舍入误差：算术运算舍入造成的误差（相同算法，exactarithmetic和finite-precisionarithmetic之间的差）误差的（分析）传播向前误差向后误差向前误差向后误差•误差分析两种思路：向前分析、向后分析•向前分析误差的缺点–分析困难–过大估计误差•向后分析–整体分析–不会过大估计例1.54.1ˆ2yy，例1.6例1.6•对于x=1，计算cos(1)敏感性&病态性•输入数据会有误差•敏感性：反映误差的传播性质•例条件数•把敏感性量化度量，得到条件数•相对条件数：绝对条件数•相对条件数的定义中，如果x或f(x)为零，则采用绝对条件数的定义|Δy|/|Δx|•稳定性算法的稳定性•精确度结果的精确度1.3计算机运算•科学计算关心的误差是截断误差和舍入误差•舍入误差主要是由计算工具产生的•计算工具会产生什么误差？如何减少舍入误差？•为了了解计算机的舍入误差，需要了解计算机内部的数据表示方法，最常用的是浮点数浮点数•实数在计算机是用浮点数表示的•类似与科学计数法浮点数•人们熟知的是十进制。计算机内是二进制浮点数。为了计数方便还有八进制、十六进制•浮点数的几部分及特点浮点数•表1.1是几种典型浮点数系统的4个关键数规格化•如果不规格化，一个数有多种表示•规格化的数–D0≠0；对于二进制，D0＝1浮点数性质•只能表示有限个数•有最小正数。对于规格化的浮点数，这个数是多少？为什么称为下溢限？•有最大正数。对于规格化的浮点数，这个数是多少？为什么称为上溢限？•表示的有限个数在数轴上怎么分布的？均匀？•例1.9舍入•计算机能够精确表示的那些有限个数称为机器数。•xfl(x)。任意一个实数x不一定等于一个机器数。在计算机里用“最接近”的机器数fl(x)表示•由x到近似机器数fl(x)的转换，称为舍入。其误差称为舍入误差舍入方法•常用两种•例1.10机器精度，机器ε，机器舍入误差•虽然由于舍入方法的不同，机器数略有不同，基本含义是对机器数颗粒性的度量次规格化逐渐下溢特殊数值1.3计算机运算•前面是浮点数的有限性、粒度性。下面是浮点数的运算性质。与我们熟悉的精确算术运算也是不同的•例1.12•为什么与我们熟悉的精确算术运算不同？•除了舍入，还可能溢出，上溢或下溢（超出指数表示范围）计算机运算•用op表示正常的算术运算，用flop表示浮点数的算术运算。这两种运算有一些细微差别•一些运算规则不再有，如结合律。第23页•产生的绝对误差不确定，但是相对误差界为机器ε。•加减先对齐，极端情况“大数吃掉小数”–例1.11•乘法两个p位数相乘得到2p位数，结果必须舍入•除法也可能舍入，如1/10例12•级数是+∞，用计算机计算的序列会趋于无穷大？•实际上，在“和溢出之前”，1/N机器ε，“和不再增加”误差分析例•例1.13•第24页抵消•因为是有限精度，所以浮点运算会有舍入误差。同时，如果算法设计不当，会把计算工具的缺点放大。注意避免一些特殊的运算，如大数除以一个很小的数，或者两个相近的数相减。•两个相近的数相减会产生什么问题？有效数字严重减少。舍入时损失的是后面的有效数字，两个相近的数相减会抵消掉前面的有效数字例•一些例子说明有效数字抵消的产生与避免•当x0，计算结果震荡，抵消•例1.14–计算两地距离–计算氦原子总能量，方法：＝动能-势能例15•例1.15计算一元二次方程的根–直接用公式计算容易出现问题，应该预防•如，把方程的最大系数变为1•如，避免抵消•如果ac≈0例16•例1.16标准差–第二个公式会产生更严重的问题：抵消•标准差定义•等价的第二计算公式•如果用第二计算公式来计算，可能抵消问题严重例17•例1.17剩余量计算–直接用原来的精度（解方程的精度）计算剩余量会产生严重误差，所以计算剩余量要用更高精度作业•Exercises:1.2，1.6，1.20，1.22实验•实验：第6周开始周六，具体时间地点待定•准备：U盘，2G，保存实验程序。计算机上已有：MATLAB。U盘上尽量也有MATLAB安装程序。