数据与算法课程讲义（吴及）基本数值算法1-概念

《数据与算法课程讲义（吴及）基本数值算法1-概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012-2013春季学期数据与算法课程讲义基础数值算法吴及wuji_ee@tsinghua.edu.cn清华大学电子工程系2012年11月内容提要数值问题误差分析计算机运算数据与算法吴及2(20230253)电子工程系内容提要数值问题误差分析计算机运算数据与算法吴及3(20230253)电子工程系研究范围数值分析/科学计算设计和分析数值型的算法，用于解决科学和工程领域的数学问题数值分析研究问题线性方程组非线性方程拟合与插值最优化问题数据与算法吴及4(20230253)电子工程系典型案例电路分析电路模型：基尔霍夫定律KCL和KVL是电磁场的简化模型

2、，是离散化的电磁场分析算法：线性方程组求解高斯消去法，LU分解……数据与算法吴及5(20230253)电子工程系典型案例线性拟合:通过实验中的多次观测值来求解线性系数数学模型：超定方程??=?,其中?为?×?,?>?算法：最小二乘拟合数据与算法吴及6(20230253)电子工程系数值问题(vs非数值)问题的特性面对的是连续量，变量取值是连续的符合一定精度要求的近似解可能有无穷多个满足于得到符合精度要求的近似解解的特性存在性，唯一性，最优性，精确性算法的特性性能和效率(时间/空间复杂度)数据与算法吴及7(20230253)电子工程系数值问题的特性一个数值

3、问题是适定的(well-posed)，如果解满足：解存在解是唯一的连续地依赖于问题数据不满足条件的问题，被称为不适定的(ill-posed)问题数据的微小变化，会引起解的急剧的，不连续的变化适定的问题，解可能对于输入数据也很敏感；这样的问题被称为病态的(ill-conditioned)数据与算法吴及8(20230253)电子工程系则。现在设，，则病态问题?+??=1求解线性方程组??+?=0当?=1时，问题无解当?≠1时，问题的解为:1−??=，?=1−?21−?2当?≈1时，问题的解就对?非常敏感?=0.999，?=500.25；?=0.998，?=250.

4、25；数据与算法吴及9(20230253)电子工程系数值问题的特性病态是问题的特性，与所选择的算法没有关系但对于适定和良态(well-conditioned)的问题，需要选择合适的算法才能得到正确的解由于数值分析面对的问题都是连续量，因此每一个环节都会产生误差数学模型：抓住主要因素，而忽视次要因素输入数据：来自于观测或者以前的计算算法实现：计算过程经常会遇到“近似”因此数值分析满足于得到具有一定精度的近似解数据与算法吴及10(20230253)电子工程系内容提要数值问题误差分析计算机运算数据与算法吴及11(20230253)电子工程系误差数值计算的误差指数学

5、问题的真解和数值方法得到的近似解之间的偏差输入数据可能不精确的，或者不能精确地被表示计算过程是不精确的，每一运算环节都可能产生误差，并且在整个计算过程中发生误差的传递、积累和对消所有的近似源最后都会反映到问题的求解结果中，从而导致计算结果和真值之间的偏差因此，误差分析是数值算法的关键问题之一数据与算法吴及12(20230253)电子工程系绝对误差与相对误差绝对误差=近似值−真值相对误差=绝对误差真值近似值=真值×1+相对误差由于真值是未知的，因此我们需要估计误差或者给出误差的界同样原因，实际计算中采用近似值代替真值来求相对误差相对误差≈估计误差近似值数据与算法吴

6、及13(20230253)电子工程系误差分析典型问题：求函数?的值?：输入真值??：期望得到的正确值?：输入的近似值?：实际计算得到的近似值总误差：??−??=??−??+??−??计算误差传播误差算法影响计算误差，但对传播误差没有影响，数据与算法吴及14(20230253)电子工程系误差分析误差=计算误差+传播误差计算误差=截断误差+舍入误差截断误差：对于实际输入数据，理论上的真实结果与用给定算法经过精确计算得到的结果之间的差异，一般由无穷级数的截断，有限差分代替导数，或者收敛之前终止迭代等近似造成舍入误差：用给定算法经过精确计算得到的结果，与用同样算法经有限

7、精度运算得到结果之间的差异，是由实数的不精确表示以及对它们的操作引起的数据与算法吴及15(20230253)电子工程系误差分析求解地球表面积，可以利用公式?=4??2?=4×3.14×63702=509645864=5.09×108??2把地球建模为一个球体模型误差取地球半径?=6370??测量误差圆周率取3.14来计算截断误差计算得到的结果保留到小数点后两位舍入误差数据与算法吴及16(20230253)电子工程系舍入误