数值计算方法课件

4
1.1 算法 一、算法的概念
当我们用数值计算方法求解一个比较复杂的数学问题 时，常常要事先拟定一个计算方案，规划一下计算的步骤。 所谓算法，就是指在求解数学问题时，对求解方案和计算 步骤的完整而明确的描述。
描述一个算法可以采用许多方法，最常用的一个方法 是程序流程图。算法也可以用人的自然语言来描述。如果 用计算机能接受的语言来描述算法，就称为程序设计。
10
3) 舍入误差 在计算过程中，当我们表示一个数时，常常只能取有
限位。超出的尾数将会舍去，从而造成误差，这种误差称 为舍入误差。
舍入误差时我们数值计算中重点研究的对象，将贯穿 整个课程之中。
11
二、 误差的概念
1） 误差： 某个量的真值与近似值的差的绝对值，称为近似值
的误差，又称绝对误差，用e表示。
5
二、算法的质量标准 求解一个数学问题，可以采用不同的算法，比如：
线性方程组，可用克莱姆法则，高斯消元法等多种方法 求解。但是每一种方法的优劣不同，评价一个算法的好 坏有以下几个标准：
1） 算法的计算量（时间复杂性） 例1：用克莱姆法则求解一个n阶线性方程组时，需要计 算（n+1）个n阶行列式的值。需要做 n2 n! 次乘法。设 n=20,若采用10亿/秒的计算机，要花费三十万年的时间 进行计算。若用高斯消元法来求解，采用一个普通的 586微机，在几分钟之内就可得结果。
12
3）有效数字 我们还可以用有效数字的概念来说明一个近似值的准
确程度。 我们先介绍“四舍五入”的概念，四舍五入是数值计
算时，取近似值的一种方法。若被舍去部分的头一位大 于等于5时，就在所取数的末位加1；小于5时，就舍去。
用四舍五入方法得到的近似值，称为有效数字。 有效数字的末位到第一位非零数字的个数，称为该有 效数字的位数。 有效数字可用来表示一个近似值的准确程度，一个近 似值的有效位数越多，这个近似值就越逼近真值。
以上我们介绍了算法的一些基本概念。下面讨论数 值计算中的另一个重要问题——误差。
8
1.2 误差
在研究算法时，要进行误差分析，能估计误差的算 法才是有实用价值的算法。 一、 误差的来源：
引起计算误差的原因是多方面的。 1）模型误差
当解决一个工程实际问题时，常常需要用一定的数 学表达式来描述，即建立一个数学模型。建立数学模型 时，通常要根据实际需要做一些简化，忽略一些次要因 素，是模型不致过分复杂，又能满足精度要求。这样建 立起来的数学模型是客观现象的近似描述。这种近似必 然产生误差。
7
2） 算法的空间复杂性 当使用计算机求解一个数学问题时，计算程序要占
用许多工作单元（内存）。当计算一个大型的数学问题 时，内存的消耗量是很大的。因此，算法占用内存数量 的多少，是衡量算法优劣的另一个标准。
3） 算法逻辑结构的复杂性 设计算法时应该考虑的另一个因素是逻辑结构问题，
虽然计算机能自动执行极其复杂的计算程序，但是计算 程序的每个细节都需要编程人员制定，因此算法的逻辑 结构应尽量简单，才能使程序的编制、维修和使用比较 方便。
模型：人们为了一定的目的，对客观事物的某一部分进 行简化、抽象和提炼出来的替代物，它集中反映了客观 事物中人们需要研究的那部分特征。
数学模型：将模型的特征、内存规律用数学的语言和符 号来描述的数学表述或数学结构。例如：人口增长模型
求解问题的方法和步骤： • 形成问题－明确待研究问题的特征、背景、用途 • 提出假设－抓住主要矛盾、忽略次要因素 • 建立模型－量化关键因素、建立数学结构和模型 • 算法求解－选择合适的算法对模型问题进行求解 • 算法分析－对算法的误差和灵敏度、稳定性进行分析 • 修正模型－对模型进行检验和修正 • 算法应用－应用成果解决实际问题
2) 新的数学,混沌理论(迭代法求非线性方程的根). 与过去相比，现代数值计算方法有两个显著特点： 1） 数值计算的方法和理论都结合数字计算机的特点来 研究。在进行算法研究时，注意算法与计算速度，计算内存 消耗的关系 2）在研究算法时，注重算法误差分析，注意数值解的收 敛性和数值计算的稳定性问题。
3
天神梵天要这庙的僧侣，把这些金片全部由一根针移 到另外一根指定的针上，一次只能移一片，不管在什么 情况下，金片环的大小次序不能变更，小金片环永远只 能放在大金片环上面。
只要有一天这六十四片的金环能从指定的针上完全转 移到另外指定的针上，世界末日就来到。
经过计算机的运算，移动的次数需18,446,744,073, 709,551,615，一秒移动一次，大约需要5849亿年。
9
2） 方法误差 在计算过程中，由数学方法产生的误差，称为方法
误差。
例如，在计算指数函数的值时，常用到如下幂级数展开
式：
ex 1 x x2 xn
2!
n!
这是一个无穷级数。计算时，只能取有限项。
Sn (x)
1
x
x2 2!
xn n!
用有限项逼近无穷级数，会产生一个误差，这个误差 是由数学方法产生的，所以是一种方法误差。
计算量的大小事衡量一个算法优劣的重要标准。
6
例2：天竺国，梵塔 据说在东方的古国──印度土地上，有一座印度教的
神庙，这庙有一块黄铜板，板上插著三根细细的、镶上 宝石的细针，细针像菜叶般粗，而高就像成人由手腕到 肘关节的长。
当印度教的主神梵天在创造地球这个世界时，就在其 中的一根针上从下到上放了半径由大到小的六十四片圆 金片环，这就是有名的「梵塔」或称「汉内塔」 （Towers of Hanoi）。
数值计算方法
1
主要内容
算法和误差 非线性方程 线性方程组 特征值 插值和拟合 微学问题的常用方法，随着计算机技术 的飞速发展，数值计算方法在现代科学研究中的作用越来越 广泛。数值计算的算法的研究越来越受到人们的重视。
1) 数值计算是应用数学一个重要分支,比如:微分方程, 现代物理.
e x x x—真值，x—近似值，
2） 误差限 在许多情况下，我们不知道某个量的真实值是多少，
因此也不知道它的近似值的误差。但是我们能估计出 误差不会超过某个确定的数值。这个数值就称为近似 值的误差限。
我们能用误差限定量的衡量一个近似值的误差。
如果某近似值的误差限是ε，我们就说，在允许误 差ε的条件下，近似值是准确的。