数值分析课件chap1绪论

1、数值分析数值分析 Numerical Analysis 谢谢 波波 X X 华南理工大学理学院华南理工大学理学院教材教材n应用数值分析应用数值分析 郑咸义等郑咸义等 编著编著 （华南理工大学出版社）（华南理工大学出版社）参考书目参考书目 Numerical Analysis:Mathematics of Scientific Computing (Third Edition) David Kincaid & Ward Cheney（机械工业出版社（机械工业出版社) Numerical Analysis (Seventh Edition) Richard L. Burden &

2、J. Douglas Faires （高等教育出版社）（高等教育出版社）科学计算科学计算 Scientific Computingl 现代许多科学、工程、经济或人文中的复杂问题现代许多科学、工程、经济或人文中的复杂问题. .需要使用数学、统计与计算器的技术，借助计算机高需要使用数学、统计与计算器的技术，借助计算机高速计算的能力来解决。速计算的能力来解决。u 科学计算是一门工具性、方法性、整合性的新学科，科学计算是一门工具性、方法性、整合性的新学科，是各种科学与工程计算领域（如：气象、地震、核能是各种科学与工程计算领域（如：气象、地震、核能技术、石油探勘、航天工程、技术、石油探勘、航天工程、 密

3、码解译等）中不可密码解译等）中不可缺少的工具。缺少的工具。数学模型数学模型构造算法构造算法编制程序编制程序上机运行上机运行输出结果输出结果实际问题实际问题数学化数学化离散化离散化程序化程序化u 科学计算已成为当今科学研究的三种基本手段之科学计算已成为当今科学研究的三种基本手段之一，是数学将触角伸向其他学科的桥梁。一，是数学将触角伸向其他学科的桥梁。科学计算科学计算应用举例应用举例问：今有问：今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二

4、十六斗。上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？问上、中、下禾实一秉各几何？ 九章算术九章算术3239xyz 2334xyz 2326xyz例：一个古老的数学问题例：一个古老的数学问题应用举例应用举例1112111212222211nnnnnnnnaaaxbaaaxbaaaxb 线性方程组数值求解线性方程组数值求解 教材第五、六章教材第五、六章Axb 应用举例应用举例例：人口预测例：人口预测表格中是我国表格中是我国19501950年到年到20052005年的人口数（见年的人口数（见中国统计年鉴），试预测未来的人口数中国统计年鉴），试预测未来的人口数插值与曲线拟合插

5、值与曲线拟合 教材第二、三章教材第二、三章年份年份人口人口(万万)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120001267432005130756应用举例应用举例矩阵特征值计算矩阵特征值计算 教材第八章教材第八章例：例：Google 搜索引擎搜索引擎1998 年创立，目前市值近年创立，目前市值近2000亿亿G: Google Matrix, “the worlds largest matrix computation” x: PageRank vect

6、or “The $25,000,000,000 Eigenvector” SIAM Review，2006Gx = x, eTx =1数值分析研究的对象数值分析研究的对象n 数值分析数值分析又叫数值计算方法、计算方法、数又叫数值计算方法、计算方法、数值方法等，其值方法等，其研究对象研究对象是各种数学问题的数值方是各种数学问题的数值方法的设计、分析及其有关的数学理论和具体实现法的设计、分析及其有关的数学理论和具体实现的一门学科，它是一个数学分支的一门学科，它是一个数学分支, , 是科学与工程是科学与工程计算（计算（科学计算科学计算）的理论支持）的理论支持。 n 数值分析是数学，计算机科学与其他学

7、科数值分析是数学，计算机科学与其他学科交叉的产物交叉的产物。数值分析的任务数值分析的任务u 设计求解各种实际问题的设计求解各种实际问题的高效可靠高效可靠的的数值算法数值算法l 有效：有效：易于在计算机上实现易于在计算机上实现l 可靠可靠：收敛性稳定性等有理论保证：收敛性稳定性等有理论保证l 高效高效：尽可能地节省计算时间和存储空间：尽可能地节省计算时间和存储空间u 对求得的结果进行理论分析对求得的结果进行理论分析u数值算法在计算机上的实现数值算法在计算机上的实现数值分析的特点数值分析的特点u 数值算法数值算法u 课程课程目的目的u 学习一些常用的数值方法，掌握数值方法学习一些常用的数值方法，掌

8、握数值方法的基本理论，为进一步研究和使用更复杂的的基本理论，为进一步研究和使用更复杂的数值算法奠定基础数值算法奠定基础u初步掌握一种科学计算软件包的使用方法初步掌握一种科学计算软件包的使用方法（如（如MatlabMatlab）。）。课程主要内容课程主要内容u 线性代数方程组数值求解的直接法；线性代数方程组数值求解的直接法；u 线性代数方程组数值求解的迭代法；线性代数方程组数值求解的迭代法； 数值代数数值代数u 非线性方程与方程组数值求解；非线性方程与方程组数值求解；u 代数插值法；代数插值法；u 曲线拟合与函数逼近；曲线拟合与函数逼近； 数值逼近数值逼近u 数值积分与数值微分；数值积分与数值微

9、分；u 常微分方程数值求解。常微分方程数值求解。 Matlab Matlab 简介简介所需知识所需知识l 微积分微积分l 高等代数、线性代数高等代数、线性代数l 常微分方程常微分方程l Matlab Matlab 编程编程第一章第一章 绪绪 论论主要内容：主要内容：u 一些概念；一些概念；u 数值计算中的误差数值计算中的误差u 数值算法设计的若干原则数值算法设计的若干原则；u 数值算法设计的常见思想方法数值算法设计的常见思想方法 数值分析中一些概念数值分析中一些概念 F 数值问题数值问题F 数值解数值解F 算法算法 数值问题、数值解数值问题、数值解 、算法、算法 由一组已知数据（输入数据），求

10、出一组结果由一组已知数据（输入数据），求出一组结果数据（输出数据），使得这两组数据之间满足数据（输出数据），使得这两组数据之间满足预先制定的某种关系的问题，称为预先制定的某种关系的问题，称为数值问题数值问题。 经过计算机的计算求出的解，或由数值计算公经过计算机的计算求出的解，或由数值计算公式得出的解称为式得出的解称为数值解数值解。一般数值解是近似值。一般数值解是近似值。由给定的已知量，经过有限次的四则运算及规由给定的已知量，经过有限次的四则运算及规定的运算顺序，求出所关心的未知量的数值解，定的运算顺序，求出所关心的未知量的数值解，这样所构成的整个计算步骤，称为这样所构成的整个计算步骤，称为数值

11、算法数值算法（简称（简称算法算法）。）。 数值计算中的误差数值计算中的误差q用计算机进行实际问题的数值计算时，用计算机进行实际问题的数值计算时，往往求得是问题的近似解，都存在往往求得是问题的近似解，都存在误差误差q误差误差是人们用来描述数值计算中近似解是人们用来描述数值计算中近似解的精确程度，是科学计算中的一个十分的精确程度，是科学计算中的一个十分重要的概念重要的概念误差来源误差来源 从实际问题转化为数学问题，建立数学模型时，数学从实际问题转化为数学问题，建立数学模型时，数学模型与实际问题之间出现的误差称为模型误差。模型与实际问题之间出现的误差称为模型误差。 数学模型中一些根据观测得到的物理量

12、，如：电压、温数学模型中一些根据观测得到的物理量，如：电压、温度、长度等，不可避免会带来误差，称为观测误差度、长度等，不可避免会带来误差，称为观测误差。q 模型误差模型误差( (描述误差描述误差) ) Modeling ErrorModeling Errorq 参数误差参数误差( (观测误差观测误差) ) Measurement ErrorMeasurement Error 计算机在实际计算时，必须在有限的时间内得到计算计算机在实际计算时，必须在有限的时间内得到计算结果，就需要选用适当的数值计算方法求解，由此产生的结果，就需要选用适当的数值计算方法求解，由此产生的误差称为截断误差或方法误差。误

13、差称为截断误差或方法误差。误差来源误差来源例如：例如：函数计算函数计算-计算计算 的近似值的近似值sin x357111sin3!5!7!xxxxxq 截断误差截断误差( (方法误差方法误差) ) Truncation ErrorTruncation Error)(! 51! 31sin553xSxxxx 产生了有限过程代替无限过程的误差，产生了有限过程代替无限过程的误差，即截断误差或方法误差。即截断误差或方法误差。截断误差是截断误差是：79511( )sin( )7!9!R xxSxxx 误差来源误差来源 n由于计算机的字长有限，参加运算的数据及其运算结果在由于计算机的字长有限，参加运算的数

14、据及其运算结果在计算机中存放会产生误差。这种误差叫计算机中存放会产生误差。这种误差叫舍入误差舍入误差或或计算误计算误差差。n例如例如 在尾数四位的浮点计算机上用在尾数四位的浮点计算机上用0.33330.3333表示表示产生的舍入误差产生的舍入误差 10.33330.0000333R q 舍入误差舍入误差( (计算误差计算误差) ) Roundoff ErrorRoundoff Error注注l 误差是不可避免的，即要允许误差，又要误差是不可避免的，即要允许误差，又要控制误差。控制误差。l 模型误差模型误差, , 观测误差不是数值分析讨论观测误差不是数值分析讨论的内容的内容, , 数值分析主要研

15、究截断误差数值分析主要研究截断误差, , 舍入舍入误差在计算过程中传播和对计算结果的影响误差在计算过程中传播和对计算结果的影响( (误差分析误差分析), ), 以提高计算的精度以提高计算的精度. .绝对误差：绝对误差：absolute error *()e xxx x x 精确值精确值x x* * 近似值近似值则称则称 为为 绝对误差限绝对误差限/ /误差限误差限l 若存在一个正数若存在一个正数 ，使得，使得工程上通常记为：工程上通常记为：x x = = x x* * |e| = |x* - x| l 绝对误差绝对误差 可能取正，也可能取负可能取正，也可能取负l 绝对误差绝对误差 越小越具有参

16、考价值越小越具有参考价值l 但但 绝对误差绝对误差 却不能很好地表示近似值的精确程度却不能很好地表示近似值的精确程度误差的基本概念误差的基本概念相对误差相对误差相对误差：相对误差：relative error x x* er = x l 若存在正数若存在正数 r r，使得，使得 | |e er r| | r r， 则称则称 r r为为相对误差限相对误差限l 由于真值难以求出，通常也使用下面的定义作为相对误差由于真值难以求出，通常也使用下面的定义作为相对误差x xx x* * e er r = = x x* * l 近似值的精确程度取决于近似值的精确程度取决于 相对误差相对误差 的大小的大小l

17、实际计算中我们所能得到的是实际计算中我们所能得到的是 误差限误差限 或或 相对误差限相对误差限有效数字有效数字 若近似值若近似值 x x* * 的误差限是某一位的半个单位，的误差限是某一位的半个单位，且该位到且该位到 x x* * 的第一位非零数字共有的第一位非零数字共有 n n 位，则称位，则称 x x* * 有有 n n 位有效数字位有效数字 等价描述等价描述FF用科学计数法，记用科学计数法，记（其中（其中 ）,01 aknaa.ax10021*| 0 5 10k nxx.若若 ,则则x x* *至少有至少有n n 位有效数字位有效数字. .有效数字有效数字例：例： = = 3.14159

18、265 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.0378550.037855，8.0000338.000033187.93，0.037856，8.00004，5注：数字末尾的注：数字末尾的 0 不可以随意添加或省略！不可以随意添加或省略！注注n由准确数字通过由准确数字通过“四舍五入四舍五入”得

19、到的近似值都得到的近似值都为有效数字。为有效数字。n可以通过有效数字的位数来确定误差限。可以通过有效数字的位数来确定误差限。 例如：例如：若若 x x* *=3587.64=3587.64是是x x的具有六位有效数的具有六位有效数字的近似值，它的绝对误差限是多少？字的近似值，它的绝对误差限是多少？ 264*410211021)()6, 4( ,100.358764x*xxxenkn有效数字与相对误差的关系（有效数字与相对误差的关系（P4P4） - - n n 位有效数字的近似数位有效数字的近似数 x x * * 其相对误差：其相对误差：11(1)11002( )nrxaEa（最左一位），且 (

20、1)11( )11002(1)nrEaxa（最左一位），且 - 相对误差为相对误差为 的近似数的近似数 x x * * 至少具有至少具有 n n 位有效数字位有效数字。 n例：要使例：要使 的近似值相对误差限小的近似值相对误差限小于于0.1%, 0.1%, 则则 要取几位有效数字？要取几位有效数字？假设取假设取 n n位有效数字。位有效数字。20204%1 . 0104214,4 . 42011nexnr基本的误差估计（基本的误差估计（P6P6）n函数计算的误差估计函数计算的误差估计 1. 1. 2. 2.)()( )()()( )(*xefxxffexexfxferr)(),()(),()(

21、)(),()(),(),(*yeyyxffyxexyxffxfeyeyyxfxexyxfyxferrr基本的误差估计基本的误差估计n n n 2()( )( )()( )( )1( )( )( )()( )( )rrre xye xeye xyye xxeyxxee xe xyyyxyexyexeyxyxyq 避免相近的数相减避免相近的数相减()( )( )rrrxyexyexeyxyxy 当当x x与与y y相近，相近， 就可能很大，从而导致计就可能很大，从而导致计算结果的有效数字位数的减少算结果的有效数字位数的减少。 ()rexy设计算法时应遵循的一些原则设计算法时应遵循的一些原则arct

22、an 5430arctan 5429y arctan 5430arctan 542911arctanarctan15429543029479471y 用具有舍入功能的八位计算器计算用具有舍入功能的八位计算器计算1.5706122 1.5706121 0.0000001y83.392191110y（1）（2）(1)(1)式的准确值为式的准确值为0.00000003392191 ,0.00000003392191 , q例如例如 设计算法时应遵循的一些原则设计算法时应遵循的一些原则例例 求实系数二次方程求实系数二次方程 的根的根 02cbxax解解 考虑两种解法考虑两种解法。 算法算法 1 1：a

23、acbbx2422,11221,24)(axcxaacbbsignbx算法算法 2 2：0101)(bbbsign其中其中signsign表示取数的符号，即表示取数的符号，即对算法对算法1 1，若，若 4ac 4ac ，分子有一个相近数相减，会大分子有一个相近数相减，会大量损失有效数字，从而有一个较大误差。量损失有效数字，从而有一个较大误差。2b设计算法时应遵循的一些原则设计算法时应遵循的一些原则l 几种经验性避免误差危害的方法几种经验性避免误差危害的方法：xxxx lnlnln 1xxx 当当 | x | 1 时：时：21 cos2sin2xx 2111126xexxx. 设计算法时应遵循的

24、一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则q 避免大数吃小数（避免大数吃小数（P13P13） 由于计算机的字长有限，又要作对阶处理，在由于计算机的字长有限，又要作对阶处理，在数值运算中，如果数据的数量级相差很大，如不注数值运算中，如果数据的数量级相差很大，如不注意运算次序，就可能出现大数意运算次序，就可能出现大数“吃掉吃掉”小数的现象。小数的现象。求和时求和时 从小到大从小到大 相加，可使结果的误差减小相加，可使结果的误差减小设计算法时应遵循的一些原则设计算法时应遵循的一些原则q 避免小分母避免小分母21()()xxee xe yyyy可知，当可知，

25、当y y 接近于接近于0 0时，时， 也可能很大也可能很大。( )xey 计算量：计算量：一个算法所需要的乘法和除法总次一个算法所需要的乘法和除法总次数称为数称为计算量计算量。计算量的单位为。计算量的单位为flopflop，表示完，表示完成一次浮点数乘或除法所需要的时间。算法的成一次浮点数乘或除法所需要的时间。算法的计算量可以衡量算法的优劣，因为它体现着算计算量可以衡量算法的优劣，因为它体现着算法的计算效率，通常算法的计算量越小，则算法的计算效率，通常算法的计算量越小，则算法的计算效率越高，因而该算法也越好。法的计算效率越高，因而该算法也越好。 由于计算机做加减法要比乘除法快得多，故由于计算机

26、做加减法要比乘除法快得多，故算法的计算量可以不考虑加减法的时间。算法的计算量可以不考虑加减法的时间。 q 简化计算简化计算, ,减少乘除法运算次数减少乘除法运算次数 （P11P11）设计算法时应遵循的一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则设计算法时应遵循的一些原则例如例如：计算计算 的值。的值。31x 若将若将 x x 的值逐个相乘，要做的值逐个相乘，要做3030次乘法，若按次乘法，若按计算，只要计算，只要8 8次运算就可以了次运算就可以了。3124816xxx x x x更一般的情况更一般的情况 计算多项式计算多项式 的值。输入数据为的值。输入数据为a ai i和和x

27、x，输出数据为，输出数据为 p p( (x x) ) 的的值。值。110( )nnnnp xa xaxa若按如下嵌套形式从里向外一层层地计算若按如下嵌套形式从里向外一层层地计算1210( )()nnnp xa xaaxa xaFF算法算法（秦九韶法（秦九韶法或或 Horner算法算法）10(1,2,1,0),( )nnkkkknnuauxuap xu 此为此为秦九韶（宋代数学家）法秦九韶（宋代数学家）法。只需要做。只需要做n n次乘次乘法和法和n n次加法。次加法。设计算法时应遵循的一些原则设计算法时应遵循的一些原则q 选用选用数值稳定数值稳定的算法，控制舍入误差的传播的算法，控制舍入误差的传

28、播在计算过程中产生的舍入误差能被控制在一定在计算过程中产生的舍入误差能被控制在一定的范围内，且对最后的结果影响不大的算法称为的范围内，且对最后的结果影响不大的算法称为数值稳定算法。数值稳定算法。不是数值稳定的算法称为不是数值稳定的算法称为数值不数值不稳定算法。稳定算法。（P9P9）因初始数据的微小变化，导致计算结果的剧烈因初始数据的微小变化，导致计算结果的剧烈变化问题称为变化问题称为病态问题病态问题。病态问题也称为坏问题，。病态问题也称为坏问题，这类问题通常是问题本身固有的。（这类问题通常是问题本身固有的。（P8P8）.210110,n,dxexeIxnn 例：例：计算计算10011d1063212056 xIex.ee11.nnIn I公式一：公式一：记为记为*0,I则初始误差则初始误差 80000 5 10 .eII.391