《数值分析课件：ch1绪论》由会员分享，可在线阅读，更多相关《数值分析课件：ch1绪论（54页珍藏版）》请在金锄头文库上搜索。
1、数值分析数值分析 Numerical Analysis教材教材n计算方法计算方法 郑咸义郑咸义 著著 （华南理工大学出版社）（华南理工大学出版社）参考书目参考书目 Numerical Analysis:Mathematics of Scientific Computing (Third Edition) David Kincaid & Ward Cheney（机械工业出版社（机械工业出版社) Numerical Analysis (Seventh Edition) Richard L. Burden & J. Douglas Faires （高等教育出版社）（高等教育出版社）科学计算科学计算
2、Scientific Computingl 现代许多科学、工程、经济或人文中的复杂问题现代许多科学、工程、经济或人文中的复杂问题. .需要使用数学、统计与计算器的技术，借助计算机高需要使用数学、统计与计算器的技术，借助计算机高速计算的能力来解决。速计算的能力来解决。u 科学计算是一门工具性、方法性、整合性的新学科，科学计算是一门工具性、方法性、整合性的新学科，是各种科学与工程计算领域（如：气象、地震、核能是各种科学与工程计算领域（如：气象、地震、核能技术、石油探勘、航天工程、技术、石油探勘、航天工程、 密码解译等）中不可密码解译等）中不可缺少的工具。缺少的工具。数数学学模模型型构构造造算算法法
3、编编制制程程序序上上机机运运行行输输出出结结果果实实际际问问题题数学化数学化离散化离散化程序化程序化u 科学计算已成为当今科学研究的三种基本手段之科学计算已成为当今科学研究的三种基本手段之一，是数学将触角伸向其他学科的桥梁。一，是数学将触角伸向其他学科的桥梁。科学计算科学计算应用举例应用举例问：今有问：今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？问上、中、下
4、禾实一秉各几何？ 九章算术九章算术例：一个古老的数学问题例：一个古老的数学问题应用举例应用举例线性方程组数值求解线性方程组数值求解 教材第二、三章教材第二、三章应用举例应用举例例：人口预测例：人口预测表格中是我国表格中是我国19501950年到年到20052005年的人口数（见年的人口数（见中国统计年鉴），试预测未来的人口数中国统计年鉴），试预测未来的人口数插值与曲线拟合插值与曲线拟合 教材第五、六章教材第五、六章年份年份人口人口(万万)1950551961955614651960662071965725381970829921975924201980987051985105851199011
5、433199512112120001267432005130756应用举例应用举例矩阵特征值计算矩阵特征值计算 教材第八章教材第八章例：例：Google 搜索引擎搜索引擎1998 年创立，目前市值近年创立，目前市值近2000亿亿G: Google Matrix, “the worlds largest matrix computation” x: PageRank vector “The $25,000,000,000 Eigenvector” SIAM Review，2006Gx = x, eTx =1应用举例应用举例例：材料科学和工程中的传热问题例：材料科学和工程中的传热问题应用举例应用举
6、例例：全球定位系统（例：全球定位系统（GPS）数值分析研究的对象数值分析研究的对象n 数值分析数值分析又叫数值计算方法、计算方法、数又叫数值计算方法、计算方法、数值方法等，其值方法等，其研究对象研究对象是各种数学问题的数值方是各种数学问题的数值方法的设计、分析及其有关的数学理论和具体实现法的设计、分析及其有关的数学理论和具体实现的一门学科，它是一个数学分支的一门学科，它是一个数学分支, , 是科学与工程是科学与工程计算（计算（科学计算科学计算）的理论支持）的理论支持。 n 数值分析是数学，计算机科学与其他学科数值分析是数学，计算机科学与其他学科交叉的产物交叉的产物。数值分析的任务数值分析的任务
7、u 设计求解各种实际问题的设计求解各种实际问题的高效可靠高效可靠的的数值算法数值算法l 有效：有效：易于在计算机上实现易于在计算机上实现l 可靠可靠：收敛性稳定性等有理论保证：收敛性稳定性等有理论保证l 高效高效：尽可能地节省计算时间和存储空间：尽可能地节省计算时间和存储空间u 对求得的结果进行理论分析对求得的结果进行理论分析 ( (误差分析和复杂度分析误差分析和复杂度分析) )u数值算法在计算机上的实现数值算法在计算机上的实现数值分析的特点数值分析的特点u 数值算法数值算法的绝大部分都具有近似性，但其理论的绝大部分都具有近似性，但其理论的绝大部分都具有近似性，但其理论的绝大部分都具有近似性，
8、但其理论 又具有严密的科学性。又具有严密的科学性。又具有严密的科学性。又具有严密的科学性。u与计算机的使用密切结合，具有实际试验的高与计算机的使用密切结合，具有实际试验的高与计算机的使用密切结合，具有实际试验的高与计算机的使用密切结合，具有实际试验的高 度技术性。度技术性。度技术性。度技术性。u 应用性强。应用性强。应用性强。应用性强。 课程课程目的目的u 学习一些常用的数值方法，掌握数值方法学习一些常用的数值方法，掌握数值方法的基本理论，为进一步研究和使用更复杂的的基本理论，为进一步研究和使用更复杂的数值算法奠定基础数值算法奠定基础u初步掌握一种科学计算软件包的使用方法初步掌握一种科学计算软
9、件包的使用方法（如（如MatlabMatlab）。）。课程主要内容课程主要内容u 线性代数方程组数值求解的直接法；线性代数方程组数值求解的直接法；u 线性代数方程组数值求解的迭代法；线性代数方程组数值求解的迭代法； 数值代数数值代数u 非线性方程与方程组数值求解；非线性方程与方程组数值求解；u 代数插值法；代数插值法；u 曲线拟合与函数逼近；曲线拟合与函数逼近； 数值逼近数值逼近u 数值积分与数值微分；数值积分与数值微分；u 常微分方程数值求解。常微分方程数值求解。 Matlab Matlab 简介简介所需知识所需知识l 微积分微积分l 高等代数、线性代数高等代数、线性代数l 常微分方程常微分
10、方程l Matlab Matlab 编程编程第一章第一章 绪绪 论论主要内容：主要内容：u 一些概念；一些概念；u 数值计算中的误差数值计算中的误差u 数值算法设计的若干原则数值算法设计的若干原则；u 数值算法设计的常见思想方法数值算法设计的常见思想方法 数值分析中一些概念数值分析中一些概念 F 数值问题数值问题F 数值解数值解F 算法算法 数值问题、数值解数值问题、数值解 、算法、算法 由一组已知数据（输入数据），求出一组结果由一组已知数据（输入数据），求出一组结果数据（输出数据），使得这两组数据之间满足数据（输出数据），使得这两组数据之间满足预先制定的某种关系的问题，称为预先制定的某种关系
11、的问题，称为数值问题数值问题。 经过计算机的计算求出的解，或由数值计算公经过计算机的计算求出的解，或由数值计算公式得出的解称为式得出的解称为数值解数值解。一般数值解是近似值。一般数值解是近似值。由给定的已知量，经过有限次的四则运算及规由给定的已知量，经过有限次的四则运算及规定的运算顺序，求出所关心的未知量的数值解，定的运算顺序，求出所关心的未知量的数值解，这样所构成的整个计算步骤，称为这样所构成的整个计算步骤，称为数值算法数值算法（简称（简称算法算法）。）。 数值计算中的误差数值计算中的误差q用计算机进行实际问题的数值计算时，用计算机进行实际问题的数值计算时，往往求得是问题的近似解，都存在往往
12、求得是问题的近似解，都存在误差误差q误差误差是人们用来描述数值计算中近似解是人们用来描述数值计算中近似解的精确程度，是科学计算中的一个十分的精确程度，是科学计算中的一个十分重要的概念重要的概念误差来源误差来源误差来源误差来源 从实际问题转化为数学问题，建立数学模型时，数学从实际问题转化为数学问题，建立数学模型时，数学模型与实际问题之间出现的误差称为模型误差。模型与实际问题之间出现的误差称为模型误差。 数学模型中一些根据观测得到的物理量，如：电压、温数学模型中一些根据观测得到的物理量，如：电压、温度、长度等，不可避免会带来误差，称为观测误差度、长度等，不可避免会带来误差，称为观测误差。q 模型误
13、差模型误差( (描述误差描述误差) ) Modeling ErrorModeling Errorq 参数误差参数误差( (观测误差观测误差) ) Measurement ErrorMeasurement Error 计算机在实际计算时，必须在有限的时间内得到计算计算机在实际计算时，必须在有限的时间内得到计算结果，就需要选用适当的数值计算方法求解，由此产生的结果，就需要选用适当的数值计算方法求解，由此产生的误差称为截断误差或方法误差。误差称为截断误差或方法误差。误差来源误差来源例如：例如：函数计算函数计算-计算计算 的近似值的近似值q 截断误差截断误差( (方法误差方法误差) ) Truncat
14、ion ErrorTruncation Error 产生了有限过程代替无限过程的误差，产生了有限过程代替无限过程的误差，即截断误差或方法误差。即截断误差或方法误差。截断误差是截断误差是：误差来源误差来源 n由于计算机的字长有限，参加运算的数据及其运算结果在由于计算机的字长有限，参加运算的数据及其运算结果在计算机中存放会产生误差。这种误差叫计算机中存放会产生误差。这种误差叫舍入误差舍入误差或或计算误计算误差差。n例如例如 在尾数四位的浮点计算机上用在尾数四位的浮点计算机上用0.33330.3333表示表示产生的舍入误差产生的舍入误差 q 舍入误差舍入误差( (计算误差计算误差) ) Roundo
15、ff ErrorRoundoff Error注注l 误差是不可避免的，即要允许误差，又要误差是不可避免的，即要允许误差，又要控制误差。控制误差。l 模型误差模型误差, , 观测误差不是数值分析讨论的观测误差不是数值分析讨论的内容内容, , 数值分析主要研究截断误差数值分析主要研究截断误差, , 舍入误舍入误差在计算过程中传播和对计算结果的影响差在计算过程中传播和对计算结果的影响( (误差分析误差分析), ), 以提高计算的精度以提高计算的精度. .绝对误差：绝对误差：absolute error x x 精确值精确值x*x* 近似值近似值则称则称 为为 绝对误差限绝对误差限/ /误差限误差限l
16、 若存在一个正数若存在一个正数 ，使得，使得工程上通常记为：工程上通常记为：x x = = x x* * |e| = |x* - x| l 绝对误差绝对误差 可能取正，也可能取负可能取正，也可能取负l 绝对误差绝对误差 越小越具有参考价值越小越具有参考价值l 但但 绝对误差绝对误差 却不能很好地表示近似值的精确程度却不能很好地表示近似值的精确程度误差的基本概念误差的基本概念相对误差相对误差相对误差：相对误差：relative error x x* er = x l 若存在正数若存在正数 r r，使得，使得 | |e er r| | r r， 则称则称 r r为为相对误差限相对误差限l 由于真值
17、难以求出，通常也使用下面的定义作为相对误差由于真值难以求出，通常也使用下面的定义作为相对误差x xx*x* e er r = = x*x* l 近似值的精确程度取决于近似值的精确程度取决于 相对误差相对误差 的大小的大小l 实际计算中我们所能得到的是实际计算中我们所能得到的是 误差限误差限 或或 相对误差限相对误差限有效数字有效数字 若近似值若近似值 x x* * 的误差限是某一位的半个单位，的误差限是某一位的半个单位，且该位到且该位到 x x* * 的第一位非零数字共有的第一位非零数字共有 n n 位，则称位，则称 x x* * 有有 n n 位有效数字位有效数字 等价描述等价描述用科学计数
18、法，记用科学计数法，记（其中（其中 ）,若若 ,则则x*x*至少有至少有n n 位有效数字位有效数字. .有效数字有效数字例：例： = = 3.14159265 3.14159265 ，近似值，近似值 x x1 1 = 3.1415= 3.1415，x x2 2 = 3.1416= 3.1416问：问：x x1 1, , x x2 2 分别有几位有效数字？分别有几位有效数字？例：例：写出下列各数的具有写出下列各数的具有 5 5 位有效数字的近似值位有效数字的近似值 187.9325187.9325，0.03785560.0378556，8.0000338.000033187.93，0.0378
19、56，8.00004，5注：数字末尾的注：数字末尾的 0 不可以随意添加或省略！不可以随意添加或省略！注注n由准确数字通过由准确数字通过“四舍五入四舍五入”得到的近似值都得到的近似值都为有效数字。为有效数字。n可以通过有效数字的位数来确定误差限。可以通过有效数字的位数来确定误差限。 例如：例如：若若 x*=3587.64x*=3587.64是是x x的具有六位有效数的具有六位有效数字的近似值，它的绝对误差限是多少？字的近似值，它的绝对误差限是多少？ n有效数字与相对误差的关系（有效数字与相对误差的关系（P P1616） - - n n 位有效数字的近似数位有效数字的近似数 x x * * 其相
20、对误差：其相对误差：- 相对误差为相对误差为 的近似数的近似数 x x * * 至少具有至少具有 n n 位有效数字位有效数字。 n例：要使例：要使 的近似值相对误差限小的近似值相对误差限小于于0.1%, 0.1%, 则则 要取几位有效数字？要取几位有效数字？假设取假设取 n n位有效数字。位有效数字。基本的误差估计（基本的误差估计（P6P6）n函数计算的误差估计函数计算的误差估计 1. 1. 2. 2.基本的误差估计基本的误差估计n n n q 避免相近的数相减避免相近的数相减 当当x x与与y y相近，相近， 就可能很大，从而导致计就可能很大，从而导致计算结果的有效数字位数的减少算结果的有
21、效数字位数的减少。 设计算法时应遵循的一些原则设计算法时应遵循的一些原则用具有舍入功能的八位计算器计算用具有舍入功能的八位计算器计算（1）（2）(1)(1)式的准确值为式的准确值为0.000000033921910.00000003392191 , , q例如例如 设计算法时应遵循的一些原则设计算法时应遵循的一些原则例例 求实系数二次方程求实系数二次方程 的根的根 解解 考虑两种解法考虑两种解法。 算法算法 1 1：算法算法 2 2：其中其中signsign表示取数的符号，即表示取数的符号，即对算法对算法1 1，若，若 4ac 4ac ，分子有一个相近数相减，会大分子有一个相近数相减，会大量损
22、失有效数字，从而有一个较大误差。量损失有效数字，从而有一个较大误差。设计算法时应遵循的一些原则设计算法时应遵循的一些原则l 几种经验性避免误差危害的方法几种经验性避免误差危害的方法：当当 | x | 1 时：时：设计算法时应遵循的一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则q 避免大数吃小数（避免大数吃小数（P1P14 4） 由于计算机的字长有限，又要作对阶处理，在由于计算机的字长有限，又要作对阶处理，在数值运算中，如果数据的数量级相差很大，如不注数值运算中，如果数据的数量级相差很大，如不注意运算次序，就可能出现大数意运算次序，就可能出现大数“吃掉吃掉
23、”小数的现象。小数的现象。求和时求和时 从小到大从小到大 相加，可使结果的误差减小相加，可使结果的误差减小设计算法时应遵循的一些原则设计算法时应遵循的一些原则q 避免小分母避免小分母可知，当可知，当y y 接近于接近于0 0时，时， 也可能很大也可能很大。 计算量：计算量：一个算法所需要的乘法和除法总次一个算法所需要的乘法和除法总次数称为数称为计算量计算量。计算量的单位为。计算量的单位为flopflop，表示完，表示完成一次浮点数乘或除法所需要的时间。算法的成一次浮点数乘或除法所需要的时间。算法的计算量可以衡量算法的优劣，因为它体现着算计算量可以衡量算法的优劣，因为它体现着算法的计算效率，通常
24、算法的计算量越小，则算法的计算效率，通常算法的计算量越小，则算法的计算效率越高，因而该算法也越好。法的计算效率越高，因而该算法也越好。 由于计算机做加减法要比乘除法快得多，故由于计算机做加减法要比乘除法快得多，故算法的计算量可以不考虑加减法的时间。算法的计算量可以不考虑加减法的时间。 q 简化计算简化计算, ,减少乘除法运算次数减少乘除法运算次数 （P1P13 3）设计算法时应遵循的一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则例如例如：计算计算 的值。的值。 若将若将 x x 的值逐个相乘，要做的值逐个相乘，要做3030次乘法，若按次乘法，若按计算，只
25、要计算，只要8 8次运算就可以了次运算就可以了。更一般的情况更一般的情况 计算多项式计算多项式 的值。输入数据为的值。输入数据为a ai i和和x x，输出数据为，输出数据为 p p( (x x) ) 的的值。值。若按如下嵌套形式从里向外一层层地计算若按如下嵌套形式从里向外一层层地计算算法算法（秦九韶法（秦九韶法或或 Horner算法算法） 此为此为秦九韶（宋代数学家）法秦九韶（宋代数学家）法。只需要做。只需要做n n次乘次乘法和法和n n次加法。次加法。设计算法时应遵循的一些原则设计算法时应遵循的一些原则q 选用选用数值稳定数值稳定的算法，控制舍入误差的传播的算法，控制舍入误差的传播在计算过
26、程中产生的舍入误差能被控制在一定在计算过程中产生的舍入误差能被控制在一定的范围内，且对最后的结果影响不大的算法称为的范围内，且对最后的结果影响不大的算法称为数值稳定算法。数值稳定算法。不是数值稳定的算法称为不是数值稳定的算法称为数值不数值不稳定算法。稳定算法。（P11P11）因初始数据的微小变化，导致计算结果的剧烈因初始数据的微小变化，导致计算结果的剧烈变化问题称为变化问题称为病态问题病态问题。病态问题也称为坏问题，。病态问题也称为坏问题，这类问题通常是问题本身固有的。（这类问题通常是问题本身固有的。（P12P12）例：例：计算计算公式一：公式一：记为记为则初始误差则初始误差 ? ! !考察第
27、考察第n步的误差步的误差(unstable algorithm), 我们有责任改变。我们有责任改变。 造成这种情况的是造成这种情况的是不稳定的算法不稳定的算法 迅速积累迅速积累, ,可见初始的小扰动可见初始的小扰动误差呈递增误差呈递增. . 公式公式方法：先估计一个方法：先估计一个IN , ,再反推要求的再反推要求的 In ( n N )。考察反推一步的误差：考察反推一步的误差：以此类推，对以此类推，对 n N 有：有： 这样的算法称为这样的算法称为稳定的算法稳定的算法(stable algorithm). 在我们今后的讨论中在我们今后的讨论中, 误差误差将不可回避将不可回避, 算法的算法的稳定性稳定性会是一个非常重要的话题。会是一个非常重要的话题。取取设计算法时设计算法时常见的思想方法常见的思想方法l 迭代法迭代法l 以直代曲以直代曲l 化整为零化整为零l 外推法外推法
