第一章绪论-数值

数值分析NumericalAnalysis西安电子科技大学理学院数学科学系Dept.ofMathematicsSchoolofScienceXidianUniv.什么是数值分析?NumericalAnalysisisconcernedwiththedesignandanalysisofalgorithmsforsolvingmathematicalproblemsthatariseinmanyfields,especiallyscienceandengineering.----MichaelT.HeathNumericalanalysisisthestudyofalgorithmsfortheproblemsofcontinuousmathematics.----LloydN.TrefethenChapter1Introduction“数值分析”就是研究在计算机上解决数学问题的理论和数值方法•数值算法的构造:计算公式和算法步骤•算法的理论分析：误差分析、收敛性、稳定性等什么是数值分析?Chapter1Introduction提问：数值分析是做什么用的？数值分析输入复杂问题或运算计算机近似解Chapter1Introduction数值分析的学科别名•计算方法•科学与工程计算Chapter1Introduction科学计算的重要性•科学计算是工程实践的重要工具•科学计算是继理论与实验后另一科学研究手段Chapter1IntroductionChapter1Introduction科学计算的国家战略与发展(1)•1983年一个由美国著名数学家拉克斯(P.Lax)为首的不同学科的专家委员会向美国政府提出的报告之中，强调“科学计算是关系到国家安全、经济发展和科技进步的关键性环节，是事关国家命脉的大事。”•1984年美国政府大幅度地增加对科学计算经费的支持,新建成五个国家级超级计算中心（分别在普林斯顿大学、圣地亚哥、伊里诺大学、康奈尔大学、匹兹堡大学），配备当时最高性能的计算机，建立NSF-net新网络。•80年代中期我国将“大规模科学与工程计算”列入国家资助重大项目。•1987年起美国NSF把“科学与工程计算”，“生物工程”“全局性科学”作为三大优先资助的领域。•1990年美国国家研究委员会发表《振兴美国数学：90年代的计划》的报告，建议对由计算引发的数学给予特殊的鼓励和资助。•1991年以美国总统倡议的形式提出了“高性能计算与通信HPCC计划”，这是为了保持和提高美国在计算和网络的所有先进领域中的领导地位而制定的。其发展的关键技术是可扩展的大规模并行计算。•1995年美国为了确保核库存的性能安全性、可靠性和更新需要而实施的“加速战略计算创新ASCI计划”。科学计算的国家战略与发展(2)Chapter1Introduction战略计算•这是因为美国克林顿总统在1995年8月11日宣布：“美国决定谋求真正的“零当量”全面禁止试验核武器条约”。•这并不意味着核竞赛的结束，恰恰相反是核武器计划新时代的开始，要求通过逼真的建模和模拟计算来取代传统的反复试验的工程处理方法，这主要依赖于先进的数值计算和模拟能力。•1995年8月22日（即美国总统宣布决定后的11天），能源部DOE就采购世界上最快的一台计算机（速度超过万亿次运算）交付圣地亚哥实验室（96年12月安装）。•1998年7月30-31日，美国DOE/FNS共同联合组织召开了关于“先进科学计算”的全国会议，会议强调科学模拟的重要性，希望应用科学模拟来攻克复杂的科学与工程难题。Chapter1IntroductionSomepastdevelopmentsinscientificcomputing----LloydN.Trefethen•1970--1998quasi-NewtoniterationsmultigridAdaptivityMatlabstiffODEsolversinteriorpointmethodssoftwarelibrariesspectralmethodssparseanditerativelinearalgebra

•Before1940Newton'smethodGaussianeliminationGaussquadrature(求积法Least-squaresfittingAdamsandRunge-KuttaformulasRichardsonextrapolation

•1940--1970floatingpointarithmeticFortranfinitedifferencesfiniteelementssimplexalgorithm单纯形算法MonteCarloFFTorthogonallinearalgebraChapter1IntroductionThefuturedevelopmentinscientificcomputing----LloydN.Trefethen•1998—2048linearalgebrainO(N2+)flopsmultipolemethodsbreakthroughsinpreconditioners,spectralmethods,timesteppingforPDE*speechandgraphicseverywhere*fullyintelligent,adaptivenumerics*lossofdeterminism*seamlessinteroperability*massivelyparallelcomputingmadepossiblebyideasrelatedtothehumanbrain*newprogrammingmethodsmadepossiblebyideasrelatedtonaturalselectionChapter1Introduction数值分析课的主要内容Chapter1Introduction•插值和函数逼近•数值微分和数值积分•常微分方程数值解法非线性方程的迭代法•数值代数:求解线性和非线性方程组的直接法和间接法•代数特征值问题的数值解法数值分析的学科特点实用性理论性实践性1面向计算机，根据计算机的特点提供可行的有效算法；•只提供加减乘除和逻辑运算•串行机和并行机2有可靠的理论分析:算法的收敛性、稳定性和误差分析；3有好的计算复杂性:时间和空间复杂性；4有充分的数值实验证明算法的有效性。Chapter1Introduction构造数值算法的基本思想近似替代离散化递推化Chapter1Introduction学习“计算方法”需注意如下几点1.要掌握算法的原理和思想2.要掌握算法的处理技巧,步骤和计算公式3.重视误差分析,理解收敛性,稳定性分析的理论4.做一定的理论分析证明与计算练习5.上机实践Chapter1Introduction§2误差的基本理论

/*Introductionoferror*/§2Introductionoferror

§2Introductionoferror

1.误差的来源与分类

/*Source&Classification*/从实际问题中抽象(简化)出数学模型,模型与实际问题之间存在误差——模型误差/*ModelingError*/§2Introductionoferror

通过测量得到模型中参数的值，观测产生误差

——观测误差/*MeasurementError*/§2Introductionoferror

采用数值方法求模型的近似解，近似解与精确解之间有误差——方法误差(截断误差/*TruncationError*/)§2Introductionoferror

机器字长有限,数据在计算机中表示产生误差——舍入误差

/*RoundoffError*/§2Introductionoferror

§2Introductionoferror

大家一起猜？11/e解法之一：将作Taylor展开后再积分S4R4

/*Remainder*/取则称为截断误差/*TruncationError*/|

舍入误差

/*RoundoffError*/|=0.747……由截去部分/*excludedterms*/引起由留下部分/*includedterms*/引起§2Introductionoferror

2.传播与积累/*Spread&Accumulation*/例：蝴蝶效应——纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！NYBJ以上是一个病态问题

/*ill-posedproblem*/关于本身是病态的问题，我们还是留给数学家去头痛吧！§2Introductionoferror

例6：计算公式一：注意此公式精确成立记为则初始误差????!!!Whathappened?!§2Introductionoferror

考察第n步的误差我们有责任改变。造成这种情况的是不稳定的算法/*unstablealgorithm*/迅速积累，误差呈递增走势。可见初始的小扰动公式二：注意此公式与公式一在理论上等价。方法：先估计一个IN

,再反推要求的In(n<<N)。可取§2Introductionoferror

取Wejustgotlucky?§2Introductionoferror

考察反推一步的误差：以此类推，对n<N有：误差逐步递减,这样的算法称为稳定的算法/*stablealgorithm*/

在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。§2Introductionoferror

§3

误差与有效数字/*ErrorandSignificantDigits*/§3

ErrorandSignificantDigits

例7.用一把有毫米的刻度的米尺,来测量桌子的长度,读出的长度x*=1235mm§3

ErrorandSignificantDigits

注：e理论上讲是唯一确定的，可能取正，也可能取负。e>0不唯一，当然e越小越具有参考价值。Icantellthatthispart’sdiameteris20cm1cm.Icantellthatdistancebetweentwoplanetsis1millionlightyear±1lightyear.Ofcoursemineismoreaccurate!Theaccuracyrelatestonotonlytheabsoluteerror,butalsotothesizeoftheexactvalue.例5中：§3

ErrorandSignificantDigits

§3

ErrorandSignificantDigits

§3

ErrorandSignificantDigits

有效数字/*significantdigits*/§3

ErrorandSignificantDigits

例8例9Def1.例10问：有几位有效数字？请证明你的结论。证明：有位有效数字，精确到小数点后第位。43注：0.2300有4位有效数字，而00023只有2位有效。12300如果写成0.123105，则表示只有3位有效数字。

数字末尾的0不可随意省去！用科学计数法，记（其中）。若（即的截取按四舍五入规则），则称有n位有效数字，精确到。Def2.§3

ErrorandSignificantDigits

Def1,2例11例12§3

ErrorandSignificantDigits

有效数字与相对误差的关系

有效数字

相对误差限§3

ErrorandSignificantDigits

相对误差限有效数字§3

ErrorandSignificantDigits

例13例14§3

ErrorandSignificantDigits

§4

函数的误差估计/*ErrorEstimationforFunctions*/问题：对于y=f(x)，若用x*

取代x，将对y

产生什么影响？分析：e(y)=f(x*)f(x)e(x)=x*xMeanValueTheorem=f()(x*x)x*与x非常接近时，可认为f()

f(x*)，则有：|e(y)||f(x*)|·|e(x)|即：x*产生的误差经过f作用后被放大/缩小了|f(x*)|倍。故称|f(x*)|为放大因子

/*amplificationfactor*/

或绝对条件数

/*absoluteconditionnumber*/.§4

ErrorEstimationforFunctions相对误差条件数

/*relativeconditionnumber*/

f的条件数在某一点是小\大，则称f在该点是好条件的

/*well-conditioned*/\坏条件的

/*ill-conditioned*/。MeanValueTheorem§4

ErrorEstimationforFunctions例15:计算y=lnx。若x

20，则取x的几位有效数字可保证y的相对误差<0.1%?解：设截取

n

位有效数字后得x*

x，则估计x和y的相对误差上限满足近似关系不知道怎么办啊？x可能是20.#，也可能是19.#，取最坏情况，即a1=1。n4例：计算，取4

位有效，即,则相对误差§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions例16§4

ErrorEstimationforFunctions特例----算术运算的误差和绝对误差限分析:§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions特例----算术运算