第一章 绪 论
主要内容： 主要内容： 一些概念； 一些概念； 数值计算中的误差 数值算法的复杂度与稳定性； 数值算法的复杂度与稳定性； 数值算法设计的若干原则； 数值算法设计的若干原则；
1.计算方法中一些概念 1.计算方法中一些概念
数值问题 数值解 算法
数值问题、 数值问题、数值解 、算法
由一组已知数据（输入数据），求出一组结果 由一组已知数据（输入数据），求出一组结果 ）， 数据（输出数据）， ），使得这两组数据之间满足 数据（输出数据），使得这两组数据之间满足 预先制定的某种关系的问题，称为数值问题。 预先制定的某种关系的问题，称为数值问题。 数值问题 经过计算机的计算求出的解， 经过计算机的计算求出的解，或由数值计算公 数值解。 式得出的解称为数值解 一般数值解是近似值。 式得出的解称为数值解。一般数值解是近似值。 由给定的已知量， 由给定的已知量，经过有限次的四则运算及规 定的运算顺序，求出所关心的未知量的数值解， 定的运算顺序，求出所关心的未知量的数值解， 这样所构成的整个计算步骤，称为数值算法 这样所构成的整个计算步骤，称为数值算法 简称算法 算法）。 （简称算法）。
2. 数值计算中的误差
用计算机进行实际问题的数值计算时， 用计算机进行实际问题的数值计算时， 往往求得是问题的近似解，都存在误差。 往往求得是问题的近似解，都存在误差。 误差是不可避免的，即要允许误差， 误差是不可避免的，即要允许误差，又 要控制误差。 要控制误差。
3. 数值计算中的误差
模型误差、参数误差、 来源及种类 --- 模型误差、参数误差、 截断误差、舍入误差 截断误差、舍入误差。 1. 模型误差(描述误差) Modeling Error 模型误差(描述误差) 模型误差是在建立数学模型时， 模型误差是在建立数学模型时，由于忽略了一些 次要因素而产生的误差。 次要因素而产生的误差。 参数误差( 2. 参数误差(观测误差) Measurement Error 通过测量或实验而得到模型中参数的值而产生 的误差
∂f ( x* , y * ) ∂f ( x* , y * ) e( f ( x, y )) ≈ e( x ) + e( y ) ∂x ∂y x ∂f ( x* , y * ) y ∂f ( x* , y * ) er ( f ) ≈ er ( x) + er ( y ) f f ∂x ∂y
基本的误差估计
数值计算中的误差
有效数字 significant digits 准确到小数点后第 --- 用 x * 表示 x 时准确到小数点后第 m 位： 则该位直到第一位非零的数总共n 则该位直到第一位非零的数总共n位， n为有效 数字。 数字。 ---用科学记数法 用科学记数法， ---用科学记数法，记 x* = ±0.a1a2 a3 ⋅ ⋅ ⋅ an × 10 k , (a1 ≠ 0) 如果 x − x* ≤ 1 ×10k − n
--- 相对误差为
1 Er ( x) ≤ × 10− ( n −1)，且 x1 ≠ 0（最左一位） 2( x1 + 1)
的近似数 x
*
位有效数字。 至少具有 n 位有效数字
例：要使 20 的近似值相对误差限小 要取几位有效数字？ 于0.1%, 则 20 要取几位有效数字？
假设取 n位有效数字。 位有效数字。
4. 数值计算中应注意的几个问题
１．避免两个相近的数相减； 避免两个相近的数相减；
er ( x ± y ) ≤ x er ( x) + y er ( y ) x± y
放大相对误差限， 放大相对误差限，导致计算结果有较大误 差。
（p12） p12）
4. 数值计算中应注意的几个问题
2.防止大数“吃掉”小数(p13) 防止大数“吃掉”小数(p13) 防止大数 求和时从小到大相加，可使和的误差减小。 注：求和时从小到大相加，可使和的误差减小。 3.避免绝对值很小的数做分母 3.避免绝对值很小的数做分母
∵ x* = 0.358764 ×10 4 , (k = 4, n = 6) 1 1 * 4−6 ∴ e( x) = x − x ≤ ×10 = ×10 − 2 2 2
数值计算中的误差
有效数字与相对误差的关系（ ） 有效数字与相对误差的关系（P4）
--- n 位有效数字的近似数 x * 其相对误差： 其相对误差： 1 Er ( x) ≤ ×10− ( n −1)，且 x1 ≠ 0（最左一位） 2 x1
舍入误差(计算误差) 4. 舍入误差(计算误差) Roundoff Error
舍入误差是由于计算机只能表示有限位数字， 舍入误差是由于计算机只能表示有限位数字，因而只能取 有限位数进行计算所得的误差。 有限位数进行计算所得的误差。 （举例： π = 3.141592653⋯ ）
注
模型误差, 模型误差, 观测误差不是数值分 析讨论的内容, 析讨论的内容, 计算方法主要研究 截断误差, 截断误差, 舍入误差在计算过程中 传播和对计算结果的影响( 传播和对计算结果的影响(误差分 析), 以提高计算的精度. 以提高计算的精度.
•
• 初步掌握一种科学计算软件包 （如Matlab）的使用方法。
课程主要内容
线性代数方程组数值求解的直接法； 线性代数方程组数值求解的直接法； 线性代数方程组数值求解的迭代法； 线性代数方程组数值求解的迭代法； 数值代数 非线性方程与方程组数值求解； 非线性方程与方程组数值求解； 代数插值法； 代数插值法； 曲线拟合与函数逼近； 数值逼近 曲线拟合与函数逼近； 数值积分与数值微分； 数值积分与数值微分； 常微分方程数值求解。 常微分方程数值求解。 Matlab 简介
e ( x ± y ) ≤ e( x ) + e( y ) er ( x ± y ) ≤ x er ( x) + y er ( y ) x± y
e( xy ) ≤ y e( x) + x e( y ) er ( xy ) ≤ er ( x) + er ( y )
e( x) x x e( ) ≤ + 2 e( y) y y y x er ( ) ≤ er ( x) + er ( y) y
∵ 20 = 4.4 ⋅ ⋅⋅,∴ x1 = 4 1 − n +1 ∴ er ≤ ×10 ≤ 0.1% 2× 4 ⇒n≥4
基本的误差估计（P6）
函数计算的误差估计 * * * e( f ( x )) ≈ f ' ( x )e( x ) 1. * x er ( f ) ≈ f ' ( x ) er ( x) f 2.
数值分析研究的对象
数值分析又叫数值计算方法、计算方法、数 又叫数值计算方法、计算方法、
值方法等， 研究对象是各种数学问题的数值方 值方法等，其研究对象是各种数学问题的数值方 法的设计、 法的设计、分析及其有关的数学理论和具体实现 的一门学科，它是一个数学分支 的一门学科，它是一个数学分支, 是科学与工程 计算（科学计算） 计算（科学计算）的理论支持。 。
数值计算中的误差
3.截断误差(方法误差) 3.截断误差(方法误差) Truncation Error 截断误差
截断误差是对参与计算的数学公式做简化可行处理后所产 生的误差（ 生的误差（用有限过程代替无限过程或用容易计算的方法代 替不容易计算的方法）（举例： 替不容易计算的方法）（举例：P4 ）（举例 sinx = … ）
数值分析研究的对象
科学计算的过程， 科学计算的过程，是从数学模型的提出到上机 计算得出结果的完整过程。（ 。（下图表明了其中的 计算得出结果的完整过程。（下图表明了其中的 主要步骤和 主要步骤和相互关系 ） 数 实 编 构 输 上 机 学 制 造 出 际 模 算 结 问 程 运 序 型 法 行 题 果
e( x ) x x e( ) ≤ + 2 e( y ) y y y
当
x >> y 时，
舍入误差会扩大。 舍入误差会扩大。
4. 数值计算中应注意的几个问题
4.尽量简化计算步骤，减少乘除运算的次数( 4.尽量简化计算步骤，减少乘除运算的次数(计 尽量简化计算步骤 算量) 算量) 计算量： 计算量：一个算法所需要的乘法和除法总次数称为
数值计算中的误差
• 相对误差 relative error --- 近似数 x * 关于准确数 x 的相对误差： 的相对误差： x − x* x − x* e er ( x) = 或er ( x) = x x*
--- 近似数
x
*
关于准确数 x 的相对误差限： 相对误差限
*
x−x ≤ εr er ( x) = * x
4. 数值计算中应注意的几个问题
5. 选用数值稳定性好的算法，以控制舍入 选用数值稳定性好的算法， 误差传播
在计算过程中产生的舍入误差能被控制在一定 的范围内， 的范围内，且对最后的结果影响不大的算法称 为数值稳定算法。不是数值稳定的算法称为数 数值稳定算法。不是数值稳定的算法称为数 。（P9 值不稳定算法。（P9） 值不稳定算法。（P9） 因初始数据的微小变化， 因初始数据的微小变化，导致计算结果的剧烈 病态问题。 变化问题称为病态问题 变化问题称为病态问题。病态问题也称为坏问 这类问题通常是问题本身固有的。（P8） 。（P8 题，这类问题通常是问题本身固有的。（P8）
2
1 x − x ≤ ×10 − m 2
*
则x *有n有效数字
数值计算中的误差
由准确数字通过“四舍五入” 由准确数字通过“四舍五入”得到的近似值都 为有效数字。 为有效数字。 可以通过有效数字的位数来确定误差限。 可以通过有效数字的位数来确定误差限。 例如： x*=3587.64是 例如：若 x*=3587.64是x的具有六位有效数 字的近似值，它的绝对误差限是多少？ 字的近似值，它的绝对误差限是多少？
数值分析研究的对象
数值分析是数学， 数值分析是数学，计算机科学与其他学科 交叉的产物。 交叉的产物 本门课程将着重介绍进行科学计算所 本门课程将着重介绍进行科学计算所 科学计算 必须掌握的一些最基本、 必须掌握的一些最基本、最常用的数值方 数值算法），并作相关分析。 ），并作相关分析 法（数值算法），并作相关分析