第七章课件-数值分析与算法(第3版)-喻文健-清华大学出版社

数值计算方法课件
Introduction
数值分析 能够做什么？
数值计算方法课件
•
研究使用计算机求解各种数学问题的 数值方法（近似方法），对求得的解的 精度进行评估，以及如何在计算机上实 现求解等
数值计算方法课件
计算机解决实际问题的步骤
建立数学模型 选择数值方法 编写程序 上机计算
数值计算方法课件
lim||
k
xk x* 数值计算方法课件
||0
➢ 矩阵范数 ( matrix norms ) 定义3:对任意 A,B,R称m|n| ·|| 为Rmn空间的矩阵范数, 指|| ·||满足(1)-(3)：
(1 )|A || |0 ;|A || |0 A 0
(2) ||A||||||A|| 对任意 C
David Kincaid & Ward Cheney（机械工业出版社)
➢ Numerical Analysis (Seventh Edition)
数值分析 （第七版 影印版）
Richard L. Burden & J. Douglas Faires （高等教育出版社）
数值计算方法课件
数值计算方法课件
10n1 10n1
10n
0
1
102
0
10 1101 0
2。与计算机不能分离：上机实习（掌握一 门语言：C语言，会用Matlab）
数值计算方法课件
1.2 误差 ( Error )
§1 误差的背景介绍 ( Introduction ) 1. 来源与分类 ( Source & Classification ) 模型误差 ( Modeling Error ): 从实际问题中抽象出数 学模型

趣味益智游戏
一人带着一只狼、一只羊和一箱蔬菜要过河,但只 有一条小船.乘船时，每次只能带狼、羊和蔬菜中的一 种.当有人在场时，狼、羊、蔬菜都相安无事.一旦人 不在,狼会吃羊,羊会吃菜.请设计一个方案,安全地将狼、 羊和蔬菜带过河.
过河游戏
如何发电子邮件？
假如你的朋友不会发电子邮件，你能教会他么？ 发邮件的方法很多，下面就是其中一种的操作步骤：
第四步, 用5除35,得到余数0.因为余数为0， 所以5能整除35.因此，35不是质数.
变式: “判断53是否质数”的算法如下：
第1步,用2除53得余数为1,余数不为0,所以2不能整除53;
第2步,用3除53得余数为2,余数不为0,所以3不能整除53;
……
第52步,用52除53得余数为1,余数不为0,故52不能整除53;
第二步, 给定区间［a,b］,满足f(a) ·f(b)＜0．
第三步,
取中间点
m
a
2
b．
第四步, 若f(a) ·f(m) < 0,则含零点的区间为
［a,m］；否则，含零点的区间b］.
第五步,判断f(m)是否等于０或者［a,b］的长 度是否小于d，若是，则m是方程的近似解;否 则，返回第三步．
|a-b| 1
0.5 0.25 0.125 0.062 5 0.031 25 0.015 625 0.007 812 5 0.003 906 25
y=x2-2
1 1.25 1.5
1.375
2
于是，开区间（1.4140625,1.41796875）中 的实数都是当精确度为0.005时的原方程的近 似解.
判断“整数n(n>2)是否是质数”的算法 自然语言描述
第一步 给定大于2的整数n. 第二步 令i=2. 第三步 用i除n，得到余数r. 第四步 判断“r=0”是否成立.若是，则n不是质

LOOP UNTIL i>100
PRINT S
结束
END
循环体
否
条件
是
DO
循环体
LOOP UNTIL 条件
2021/7/26
22
一、辗转相除法（欧几里得算法）
1、定义：
所谓辗转相除法，就是对于给定的两个 数，用较大的数除以较小的数。若余数不为 零，则将余数和较小的数构成新的一对数， 继续上面的除法，直到大数被小数除尽，则 这时较小的数就是原来两个数的最大公约数。
二、程序框图
用程序框、流程线及文字说明来表示算 法的图形称为程序框图，它使算法步骤显得 直观、清晰、简明.
○
终端框 输入、 处理框 (起止框) 输出框 (执行框) 判断框 流程线 连接点
2021/7/26
7
程序框图又称流程图，是一种用规定的图形，指向线及 文字说明来准确、直观地表示算法的图形。
程序框
（2）、现代数学中的更相减损术：
第一步：任意给定两个正整数；判断他们是否都是偶数。 若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小 的数比较，并以大数减小数。继续这个操作，直到所得的 减数和差相等为止，则这个等数就是所求的最大公约数。
2021/7/26
26
2、定义：
语句
一般格式
1.输入 语句
INPUT “提示内容”;变量
2.输出 PRINT “提示内容”;表达式 语句
3.赋值 语句
变量＝表达式
2021/7/26
主要功能
说明
可对程序中 的变量赋值
（1）提示内容和它后面 的“；”可以省略
（2）一个语句可以给多个变 量赋值，中间用“，”分隔

曲线拟合的最小二乘法
多项式插值
(拉格朗日, 牛顿) 分段多项式插值 样条函数插值
Wenjian Yu 2
函数逼近问题的例子
1.4
sqrt(1+t2)

1.3 1.2 1.1 1 0 0.2 0.6 t cos(t) /2-4/ 0.4 0.8 1
傅里叶变换, 信号的频谱分析
3 2.5 2 1.5 1 0.5 -3 -2 -1 0 t 1 2 3
Wenjian Yu 68
样条插值及其他

B-样条函数
有k-1阶连续导数的分段k次多项式为k次样条函数 可写成基函数的线性组合,
基函数为B-样条函数 1次样条函数为分段线性函数 1 B-样条基函数应用广泛(计算机图形 学, 几何建模, 数值求解微分方程)

Matlab
yi
= interp1(x,y,xi,method) „nearest’, „linear‟, „spline‟, „pchip‟ interp2, interp3, pchip, spline, “Spline toolbox”

定义6.6
DFT
Wenjian Yu
40
插值与多项式插值

解存在、唯一吗?
Th6.6
(Vandermonde阵)
Wenjian Yu
41
Lagrange插值法

不便于计算、以及理论分析
“两点式”直线公式:
Wenjian Yu
42
Lagrange插值法

Lagrange 插值函数
(一个常用的技巧)
数值分析与算法 (6)
Numerical Analysis & Algorithms

似算法的收敛性和数值稳定性； 要有好的计算复杂性，节省时间及存储量； 有数值实验，证明算法有效。
算法基本结构：顺序，分支，循环
算法描述：程序或流程图
常采用的处理方法：
构造性方法 离散化方法 递推化方法 迭代法 近似替代方法 以直代曲法 化整为零的处理方法 外推法
数学基础：
微积分的若干定理： 罗尔定理和微分中值定理； 介值定理及推论； 泰勒公式（一元、二元）； 积分中值定理；
设y=f(x)为一元函数，自变量准确值x*，对应函数准确 值y*=f(x*)，x误差为e(x)，误差限为ε(x)，函数近似值 误差e(y)，误差限为ε(y)。则（可由Taylor公式推得）
( y) | f '(x) | (x)
r
(
y)
|
xf |f
'(x) (x) |
|
r
(
x)
对于多元函数 z f (x1, x2 ,, xn )
定义1.1 设x*为某一数据的准确值，x为x*的一个近 似值，称e(x)=x-x*(近似值－准确值)为近似值x的绝对 误差，简称误差。
e(x) 可正可负，当e(x) >0时近似值偏大，叫强近似值；当e(x) <0时近似值偏小，叫弱近似值。
由于x*通常无法确定，只能估计其绝对误差值 不超过某整数ε(x)，即
设准确值
z* f (x1*, x2*,, xn* )
由多元函数Taylor公式，可得误差估计：
n
(z)
k 1
f xk
(xk )
相对误差限为：
r (z)
n k 1
xk
f xk
r (xk )
z
2. 算术运算的误差估计：

0
x
y
2 4 6
8 6 4 2

骄行札或务旷恰洗大而非仆椒鸿孜襟儡和跟浪陪痕骚树认邻异镍屠丰逃臃数值分析课件第3章数值分析课件第3章
初每孟缅家邱拙货另崇屎慑芝骋磨雨鹏苯核碉断策占悲异贺碴察鸿旧岿父数值分析课件第3章数值分析课件第3章
例3-4 已知实测数据表如下,确定数学模型 y=aebx, 用最小二乘法确定a，b。
帜尸砚损讹祖邱帆迄攫让汕芽柔造兔优伐具猪购冈琅高蹄熊嫌第凸貉楚章数值分析课件第3章数值分析课件第3章
伸姜积升斯钳更相傍抒匣替讯蔽炽恋喉爱著殷都皂孵羌邹捞谎寐池骇织狱数值分析课件第3章数值分析课件第3章
i
0 1 2 3 4
拙猪囤犀缎孩甸萤捷褐番舍倪酌月迢飘沟锰乡橙波旗骨渠虎偷朋袒夹惹胳数值分析课件第3章数值分析课件第3章
新隆培润已描苍淬霖绪册防嚷拇痘掂腹坏蕉吁咳洞烷携敦玻腔同翻坎镀讨数值分析课件第3章数值分析课件第3章
宽烹呼境眺泡狞瑞怕敝斧厨寞贝砚妄特痒福踊阁监桐却挠伸井竟哇含野劲数值分析课件第3章数值分析课件第3章
囊铭徒庄裸课爹压屏滴插百盗万武廷校船卿肪没弹溃想镊茨壳峨孽信骗跨数值分析课件第3章数值分析课件第3章
i
0 1 2 3 4
xi yi yi
1.00 1.25 1.50 1.75 2.00 5.10 5.79 6.53 7.45 8.46 1.629 1.756 1.876 2.008 2.135
3.1基本概念
x0
x
x
x
x
x
x
x
f(x)
p(x)
虐座韦龄椽加腕槽晶僵壤漱键椒赏琢芭尊校榆唤著里钙治纹改瞥宁岁坛草数值分析课件第3章数值分析课件第3章
2、范数与赋范线形空间

◦ 使用数值求解非线性方程的命令fzero求
◦ 注意：ezplot自动避开奇异点
plot, fzero命令
◦ 图形窗口(figure)的编辑、拷贝
>> phi = fzero (f, 1)
>> hold on
>> plot (phi, 0, ‘o')
26

脚本程序与绘图功能
◦ Matlab程序.m文件有两种: 脚本(script), 函数(function)
变量空间
命令历史
命令窗口，将Matlab作
为计算器使用
20

程序编辑窗口
帮助窗口
注释语句%
多个文件
21

如何“上手”？
◦ 安装Matlab软件，版本R2009a/b或更新的
◦ 获取NCM程序包，并设置路径
(网络学堂-”教学资源”第1项)
>> ncmgui
◦ 阅读课本第1章
◦ 多动手实验
◦ 熟悉“命令历史”键： “”, “” ，以及help, doc命令
及其化简分式，并计算它的值及近似的误差
23




=
1+ 5
2
Matlab默认采用双精度浮点数，但有多种显示格式
format命令, 或通过File-Preferences菜单设置
黄金矩形
>> phi = (1+sqrt(5)) / 2
>> format long
◦ 裁去正方形后，小矩形形状比例不变
◦ 根据这一点求
◦ 解方程:
−1 1
in Science & Engineering”(IEEE

第二类椭圆积分, 无法解析求出 !
Wenjian Yu
4
数值积分基本思想

f (x)
积分系数 积分节点
希望用较少的计算量得到较准确的结果
Wenjian Yu
...
5
插值型求积公式

梯形公式
中矩形公式
Wenjian Yu
6
积分余项与代数精度

反映了计算的截断误差 插值余项的积分
衡量求积公式准确度的另一个指标
高斯积分有2n+1次代数精度
Wenjian Yu
38
高斯求积公式

Th7.7
Wenjian Yu
比自适应积分 算法使用方便
39
高斯-勒让德公式

高斯-勒让德积分表
0 1 2
3
4
5
Wenjian Yu
40
高斯-勒让德公式

Wenjian Yu
41
数值微分
Wenjian Yu
42
数值微分

利用Taylor展开推出:
要尽量寻求稳 定的求积公式
Wenjian Yu
10
牛顿-柯特斯公式
Wenjian Yu
11
Newton-Cotes公式

就是n阶牛顿-柯特斯公式
n=1, 1/2, 1/2 Cotes系数表 n=2, 1/6, 2/3, 1/6
• 一系列求积公式 • 便于使用
n=4, 7/90, 16/45, 2/15, 16/45, 7/90
p
3
5
9
Wenjian Yu
45
数值微分的应用

二阶中心 差分
例如n=2

解决具体问题的能力 借助教学演示网站、Matlab软件, 提升学习兴趣!
Wenjian Yu 7
数值计算的背景与概况
Wenjian Yu
8
数值分析、科学计算、数值计算
数值计算，也称为科学计算，已成为当今科学研究的三种 基本手段之一。它是计算数学、计算机科学和其他工程学 科相结合的产物，并随着计算机的普及和各门类科学技术 的迅速发展日益受到人们的重视。

是数学规划/最优化算法的基础，部分内容也是大 数据分析、机器学习中一些复杂算法的基础
Wenjian Yu 18
误差分析基础
Wenjian Yu
19
误差分析基础
§1.2.1误差的来源 §1.2.2误差及其分类

误差与有效数字 数据传递误差与计算误差 截断误差与舍入误差
§1.2.3问题的敏感性与数据传递误差 §1.2.4算法的稳定性
• 设计数值方法(算法)的关键：将问题简化(估计带来的 误差)，然后求解简化后的问题
Wenjian Yu 14
数值软件/程序包

数值计算的软件与程序包
解决常见问题，促进各个科学和工程领域的科研 了解基本原理，学习算法设计和实现技巧
成为聪明的软件/程序包使用者

存在形式和资源
商业软件/免费软件，互联网上共享的程序包 Fortran,
数 值 分 析 (1)
Numerical Analysis
课程简介
计算方法 数值分析与算法 科学计算导论（scientific computing） 数值计算基础（numerical computing） 课程目标

介绍广泛应用于科学与工程领域的各种数值计

则 x* 至少有n 位有效数字，且精确到10mn.
有效数字的位数 n = 近似数科学记数法的幂指 数－绝对误差限科学记数法的幂指数.
当差为负整数时，表示没有效数字! 把误差限表
示为0.5×10mn, 当指数 m n 是最小的整数时,
有效数字的位数精确地是 n.
例3 下列近似值的绝对误差限都是0.005，
e x x 其中 x 为精确值，x* 为 x 的近似值。|e|的上界
记为e , 称为绝对误差限 (accuracy),工程上常记为
x = x* ± e .
例如： 1 ex2 dx 0.743 0.006 0
注:理论上讲,e 是唯一确定的, 可能取正, 也可能取负.
e > 0 不唯一，当然 e 越小越具有参考价值。
§1.2 误差知识与算法知识
1.2.1 误差的来源与分类
在工程技术的计算中，估计计算结 果的精确度是十分重要的工作，而影响 精确度的是各种各样的误差。误差的来 源是复杂的，但主要有以下四种：
➢ 从实际问题中抽象出数学模型
—— 模型误差 ( Modeling Error )
➢ 通过测量得到模型中参数的值
例:近似计算 1 ex2 dx = 0.747… … 0
解法之01一e大：x2 d家将x 一1e1/起x0e12(作1猜13T？axy212l!or01展215xe4!开x312后!dx3!6x再71积x4!48分1!119
)
dx
取
1
e
x
2
dx
0
S4
,
S4
R4 ( Remainder )
x * f (x*) f (x*)
er (x)
| er (x) |

计算机专业基础课程: 计算方法
使用教材:数值分析 华南理工大学出版社 韩国强 林伟健等编著
数值分析
林伟健
制作
华南理工大学计算机学院
本课程介绍的内容：使用计算机来 解决某些数学问题的近似方法。
《数 值 分 析》目录
第 1 章 误差 第 2 章 代数插值与数值微分 第 3 章 数据拟合 第 4 章 数值积分 第 5 章 解线性代数方程组的直接法 第 6 章 解线性代数方程组的迭代法 第 7 章 非线性方程和非线性方程组的数值解 第 8 章 矩阵特征值和特征向量的数值解法 第 9 章 常微分方程初值问题的数值解法
2
从而得到
p n 3
而
3.1415 0.31415101 p 1
近似值 3.1415 的误差限为该值小数点后
第三位的半个单位，由有效数字的定义得知，
具有4位有效数字。 顺便指出，准确值我们通常称它具有无穷多位有效
数字。
4. 有效数字与误差限的关系
设准确值 x 的近似值为 x* ，且将 x* 表示为
x 0.1 2 m 10 p（p为整数，1,2,,m
3.1416 1 104
2 3.14159
1 105
2
2
这个数经过四舍五入之后所得到的近似值，它的误差
限是它末位的半个单位。
可以证明：对任何数经过四舍五入之后所得到的 近似值，它的误差限都是它末位的半个单位。
定义1-3 若近似值x*的误差限为该值的某一位的半个单位，
例如， 0.045678 0.0457 3 位 具有3 位有效数字 又如， 8.0005 8.00 3 位 具有3位有效数字
例1-2 若 的近似值为 3.141，5 则 有多少位有效数字?

(5)输入与输出性:每一个算法都要根据输入的初始数据或给定的
初始值才能正确执行它的后续步骤.利用算法解决问题时,一定有
一个或多个结果输出,以达到求解问题的目的.
-10-
§1 算法的基本思想
首页
课前篇 自主预习
课堂篇 探究学习
探究一
探究二
探究三
思维辨析 当堂检测
变式训练1下面的结论正确的是( ) A.一个程序的算法步骤是可逆的 B.一个算法可以无止境地运算下去 C.完成一件事情的算法有且只有一种 D.设计算法要本着简单方便的原则 解析:选项A不正确,算法只需要每一步都可以顺序进行,并且结 果唯一,不能保证可逆.选项B不正确,一个算法必须在有限步内完成, 不然就不符合算法的有限性.选项C不正确,一般情况下,一个问题的 解决办法不止一个.选项D正确,设计算法要尽量使程序运算简单, 节约时间,故选D. 答案:D
①写出的算法必须能解决一类问题,并且能够重复使用; ②要使算法尽量简单,步骤尽量少; ③要保证算法正确,且计算机能够执行.
-5-
§1 算法的基本思想
首页
课课前前篇篇 自自主主预预习习
课堂篇 探究学习
【做一做3】 给出下面一个算法:
1.给出三个数x,y,z.
2.计算M=x+y+z. 3.计算 N=13M. 4.得出每次计算结果.
-15-
§1 算法的基本思想
探究一
探究二
探究三
首页 思维辨析 当堂检测
课前篇 自主预习
课堂篇 探究学习
解法一算法步骤如下: 1.比较a与b的大小; 2.若a<b成立,则执行第3步;否则执行第4步; 3.若a<c成立,则输出a,并结束;否则输出c,并结束; 4.若b<c成立,则输出b,并结束;否则输出c,并结束. 解法二算法步骤如下: 1.记三个数中的最小数为min,将a的值记为min; 2.若b<min成立,用b的值替换min的值;否则min的值不变; 3.若c<min成立,用c的值替换min的值;否则min的值不变; 4.输出min的值.

(2) spline
Cubic spline data interpolation
.
yh=spline(x,y,xh) pp=spline(x,y)
三次样条插值, 参数含义同 interp1. 边界条件为: • 若 x 与 y 的长度相等, 则采用 “not-a-knot” (非扭结) 边界条件, 即要求插值多项式在 x1 和 xn−1 点三阶可导; • 若 y 比 x 多两个分量, 则采用第一类边界条件, 即即 y = [f ′ (x0 ), y0 , y1 , . . . , yn , f ′ (xn )], 也就是 说, y 的第一个和最后一个分量分别是 f (x) 在 x0 和 xn 处的一阶导数. MATLAB 源代码 10.4 spline 举例
10.1.3 曲线拟合工具箱 M 曲 线 拟 合 除 了 内 建 函 数 polyfit 以 外, 还 提 供 了 一 个 曲 线 拟 合 工 具 箱 (Curve Fitting Toolbox), 可以用于参数拟合, 也可以用于非参数拟合. 详细使用方法参见 M 自带的使用指南. 相关的工具箱有统计工具箱 (Statistics Toolbox) 和优化工具箱 (Optimization Toolbox). . cftool opens Curve Fitting Tool
1 2 3 4 x=0.4:0.1:0.8; y=[-0.9163,-0.6931,-0.5108,-0.3567,-0.2231]; xh=[0.54, 0.63, 0.72, 0.79]; yh=interp1(x,y,xh,’spline’)
.
pp=interp1(x,y,method,’pp’)
1 2 3 4 x=0.4:0.1:0.8; y=[-0.9163,-0.6931,-0.5108,-0.3567,-0.2231]; xh=[0.54, 0.63, 0.72, 0.79]; yh=interp1(x,y,xh)