数值计算基本概念_822007367

《数值计算基本概念_822007367》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据与算法2012-2013年秋季学期陈健生jschenthu@tsinghua.edu.cn清华大学电子工程系1Previously…基本概念◦数据、算法、数学建模、时间/空间复杂度、关系、抽象数据类型；非数值（有限离散）数据与算法◦线性表：顺序表、链表、循环链表；插入、删除；◦线性表特例：栈、队列、字符串；递归及消除、模式串匹配(KMP)；◦非线性结构之一：树、二叉树、二叉搜索树(BST)、AVL树；树遍历、Huffman树、BST的查找/插入/删除、AVL树的构造；◦非线性结构之二：图(邻接矩阵、邻

2、接表)；图遍历(BFS、DFS)，最小生成树，最短路径；◦非数值数据应用：查找(线性、折半、散列、索引)、排序（冒泡、插入、选择、快速、归并）.2《《科数学值计方算法导与数值计算基本概念论计》算1.1机1.2实误差1.3现良态》稳定性1.3.11.3.2浮点数…3•数值计算问题•近似与误差•计算机运算4非数值计算问题◦查找、排序、模式匹配、最短路径、最小生成树...◦问题变量通常是离散的；一定规模的问题解空间通常是数有限的；值◦精确解如存在，是有可能达到的；求解过程通常是稳定的，对输入的依赖性较小；计◦算法

3、的性能通常用时间/空间复杂度衡量.算数值计算问题问◦方程求解、插值、拟合、最优化...题◦问题变量和解空间通常是连续的；◦一般不可能通过有限步运算得到精确解，而仅能满足于符合精度要求的解(可能有无限多个)；◦求解过程的稳定程度，决定了其对输入的依赖性；◦算法的性能通常用收敛性、稳定性以及解的精确度衡量.5非数值计算问题的特性◦?问题、??问题、???问题、??−ℎ???问题.数值数值计算问题的特性计◦数值计算问题的解存在、唯一、且连续依赖于问题的参算数，则称该问题是适定的(well-posed)；否则称

4、问题是不适定的(ill-posed)；问◦适定问题中参数微小变动，不会导致解的急剧的不均匀题的变化；但参数的微小扰动，解可能产生高度敏感的响应(虽连续)，称问题是病态的(ill-conditioned)；◦适定问题有机会用稳定算法求解；而不适定的问题求解需补充额外假设,称为规范化(regularization).6数值计算问题的特性◦参数不同，数值问题的特性可能发生改变：?+?=1数求解线性方程组??+??=1值◦?=?=1时，方程解不唯一，问题不适定；计◦?=?≠1时，方程解不存在，问题不适定；算◦?≠?

5、时，方程解存在唯一，且是参数的连续函数：问?−1?−1?=?=题?−??−?◦当?≈?时，方程解对参数敏感，问题病态：?=2,?=1.999→?=−999?=+1000?=2,?=2.001→?=+1001?=−10007数值计算问题的求解◦适定/不适定，良态(well-conditioned)/病态，均是问题的的属性，与选择的算法无关；数◦适定的良态问题，所选择算法得到结果的敏感性也不值应超过问题本身(“donotharm”)；计◦数值计算的输入与计算过程都不可避免存在近似：数学模型简化或忽略了次要方面

6、；测量的精度受到设备、手段算和具体操作的影响；前级的计算结果存在近似；计算中公式的简化或省略导致数值的截断和离散化的近似；数问值的表示精度有限造成近似.题例：用球表面积公式?=4??2计算地球表面面积.地球看成球体，是一种理想化的近似；半径?≈6370??存在测量上的近似；圆周率?的值只能截取到某一位；计算过程存在数据的舍入.8•数值计算问题•近似与误差•计算机运算9误差(error)◦测量，或计算结果与真值之间的偏差；◦数值计算中各种近似综合作用反映为计算结果的误差；计算过程中误差可能传递、积累

7、或者是对消；近◦绝对误差=近似值–真值；似精确度：近似某个量时有效数字的位数；与精度：表示数的数字个数；误◦相对误差=绝对误差/真值(真值≠0)差◦近似值=真值×(1+相对误差)；◦真值一般未知，通常只能估计误差范围，相对误差只能相对于近似值；数据误差误差截断误差计算误差舍入误差10有效数字◦除了误差之外，实际中也常用有效数字的位数来反映近似数的准确程度；近∗∗1−?◦用?来近似?，若?−?≤×10，则称该近似精2似确到小数点之后第?位，并称从小数点之后?第位起直到最左边的非零数字之间的一切数字为有效数

8、字，有与效数字的位数称为有效位数；误?=3.1415926535897932…差?∗=3.14?−?∗≈0.001526≤0.5×10−2有效位数=3?∗=3.1416?−?∗≈0.00000735≤0.5×10−4有效位数=5?∗=3.1415?−?∗≈0.0000927≤0.5×10−3有效位数=411有效数字vs相对误差◦若近似值?∗的有效位数为?，则其相对误差满足：1近相对误差≤×10−?