数值分析
Numerical Analysis
华中科技大学计算机科学与技术学院
HUST
College of Computer Science & Technology
Spring,2003
Version 2.0
主讲教师许贵平
xugpjq@263.net
什么是数值分析?
Numerical Analysis is concerned with
the design and analysis of algorithms for solving
mathematical problems that arise in many fields,
especially science and engineering.
----Michael T,Heath
Numerical analysis is the study of
algorithms for the problems of continuous
mathematics,
----Lloyd N,Trefethen
什么是数值分析?
“数值分析”就是研究在计算机上解决数学问题的理论和数值方法
数值算法的构造
算法的理论分析数值分析的学科别名
计算方法
科学与工程计算科学计算的重要性
科学计算是工程实践的重要工具
科学计算是继理论与实验后另一科学研究手段科学计算的国家战略与发展 1
1983年一个由美国著名数学家拉克斯(P,Lax)为首的不同学科的专家委员会向美国政府提出的报告之中 强调“科学计算是关系到国家安全 经济发展和科技进步的关键性环节 是事关国家 的 事,
1984年美国政府 科学计算经 的,
个国家 计算中 分别在 斯 学
学 学? ￠￡?￥?§性currency1的计算机 'NSFNSF--net,?
80年?中?fi国fl –科学与工程计算国家· 重
科学计算的国家战略与发展 2
1987年?美国NSF?“科学与工程计算”,”?工程”,全…
性科学”‰为? · 的`′
1990年美国国家研究委员会发ˉ美国数学 90年?的计? 的报告 ˙ 由计算¨发的数学 的和·
1991年ˇ美国— ˙的 提出,§性currency1计算与 HPCC
计?” 是为 和提§美国在计算和“?的 进`′
中的` 的?发展的关键技 是a 展的 –
计算
1995年美国为的性currency1 安全性 ao性和
要 实 的,战略计算 ASCI 计?”
战略计算
是?为美国克 — 在1995年8 1111?,美国决
的“”全 验?武器条约”
不意味着?竞赛的结束 恰恰相反是?武器计? ￥?的开始 要 过逼?的 –和–拟计算来取?传 的反复 验的工程处理方法 主要依赖于 进的数值计算和–拟currency1力
年 美国的DOE/FNS共同联合组织召开 关于,进科学计算”的全国会˙ 会˙强调科学–拟的重要性 希望应用科学–拟来攻克复杂的科学与工程难题
1995年8 22 即美国—?决 后的11天 currency1源部DOE
就采购世界上?快的一台计算机 运算 过万亿次 交付
实验室 96年年121 安装
Some past developments in scientific computing
----Lloyd N,Trefethen
Before 1940
Newton's method
Gaussian elimination
Gauss quadrature (求积法
Least-squares fitting
Adams and Runge-Kutta formulas
Richardson extrapolation
1940--1970
floating point arithmetic
Fortran
finite differences
finite elements
simplex algorithm 单纯形算法
Monte Carlo
FFT
orthogonal linear algebra
1970--1998
quasi-Newton iterations multigrid
adaptivity Matlab
stiff ODE solvers interior point methods
software libraries spectral methods
sparse and iterative linear algebra
The future development in scientific computing
----Lloyd N,Trefethen
1998--2048
linear algebra in flops
multipole methods
breakthroughs in preconditioners,spectral methods,time
stepping for PDE
* speech and graphics everywhere
* fully intelligent,adaptive numerics
* loss of determinism
* seamless interoperability
* massively parallel computing made possible by ideas related
to the human brain
* new programming methods made possible by ideas related to
natural selection
2
()ON
ε+
数值分析课的主要内容
插值和函数逼近
数值微分和数值积分
常微分方程和偏微分方程数值解法
数值?数,解线性和非线性方程的直接法和间接法
数?征值问题的数值解法数值分析的学科?点实用性 理论性 实践性
1 向计算机 根据计算机的?点提供a 的 效算法
只提供 减 乘 除和逻辑运算
串 机和 机
2 ao的理论分析 算法的收敛性 稳 性 误差分析
3 好的计算复杂性 ￥间和空间复杂性
4 分的数值实验构造数值算法的
近?
近?
解:
1 计算 理数e的近 值.
2
1,..,..
2! !
n
x
xx
ex
n
=++ + + +∵
11
11,.,.
2! !
e
n
∴=++ + + +
是一个 过程,计算机 法实,一,只currency1
算出?的和,‰为?近 值
11
11,.
2! !
e
n
≈++ + +
由Taylor,由,的误差:
3
(1)!(1)!
e
R
n
nn
<<
++
2
1
1..,(01)
1! 2! ! ( 1)!
nx
xn
xx x e
ex
nn
θ
θ
+
=+ + + + + < <
+
∵
不currency1用
次运算 解的问题,为用
次运算
解的问题
---的问题 为?的问题
2 计算 积分
011
1
( ) [ ( ),.,]
2
b
nn
a
ba
fxdx y y y y
n
≈+++
∫
()
b
a
Ifxdx=
∫
I为 的
的 积,个 的问题,法在计算机上计算.
一,aˇ 计算:
1..nn?分[a,b],a,b],
01
...,( ),0,1,...,
ni i
ax x x by fxi n=<<<= = =
2.用n个￠ 的 积之和近? 的
积
---复杂的计算￡结为?过程的￥次重复,
于用§环结构来实,(currency1?法)
3 计算￥?
1
110
(),..
nn
nnn
Px ax a x ax a
=+ +++
构造 算法:
12
1210
() ( ),.
nn
nnn n
Px ax a x a x ax a
=+ + ++∵
'
0
,
n
ua=
110nn n
uaxa uxa
=+=+
12
12 10
( ),..
nn
nn
Px ux a x ax a
∴= + +++
2
12 10
().
n
n
ux a x ax a
=+ +++
2
210
...
n
ux ax a
=+++
……
0
1
=
=+
n
kk nk
ua
uuxa
(1.3) ()
nn
Px u?=
是fi国“?数学家 提出的,fi为算法,
(国flfi为 Horner 算法)
学,计算方法” –意?点
1.要?·算法的 理和
2.要?·算法的处理技?,步?和计算
3.重?误差分析,理解收敛性,稳 性分析的理论
4.?一 的理论分析”?与计算…
5.上机实践
1.2 误差的 理论
2 误差是不a‰ 的,?要 `误差,′要
误差.要重?误差分析,分析误差的来源,误差的传?ˉ 误差‰出?计
1 用计算机进 实˙问题的数值计算￥,¨
¨ 的是问题的近 解,在误差误差来源
用计算机解决科学与工程计算问题的过程:
实˙问题 数学–?
数值分析 程?ˇ计上机计算
—,
近
中主要会,ˇ?个方 的误差
1.–?误差 3,误差
2,误差 4,?误差
–?误差,误差
!数学–?是 实˙问题的— 和近,?在误差
——–?误差 /* Modeling Error */
国经济学家 Malthus的? –?
00
(1)
()
dp
p
dt
pt p
α
=
=
中 为” 系数0.029α =
2
00
(2)
()
dp
pp
dt
pt p
αβ
=?
=
中 为 会 系数0β >
! 过? 实验 到–?中 数的值,的误差
—— 误差 /* Measurement Error */
4
2
1,..,..
2! !
n
x
xx
ex
n
=+ + + + +
2
() 1,.
2! !
n
x
n
xx
eSx x
n
≈=++++
￥ 误差为
1
() () (0 1)
(1)!
n
xx
nn
x
Rx e Sx e
n
θ
θ
+
=? = <<
+
误差
! 近 解——方法误差( 误差/* Truncation Error */ )
误差由于计算机的,只currency1 数进 运算,过的 数?一?,”,?误差”.
3.1415926...,2 1.41421356...π ==
在计算机上运算￥,只currency1取
a取￠数点后4 数,?误差是
1
3.1416 0.0000074...,0.3333 0.000033...
3
π?=?=?
￠结,–?误差,误差不是数值分析 论的内容,计算方法主要研究 误差和?误差在计算过程中的传?和 计算结 的,ˇ提§计算的?,
!机器 ——?误差 /* Roundoff Error */
dxe
x
∫
1
0
2
近 计算,
家一
<<
∫
dxe
2
x
1
0
1
1 / e
解法之一 flfl‰‰Taylor展开后?积分
2
x
e
"
"
×+×?×+?=
+?+?=
∫∫
9
1
!4
1
7
1
!3
1
5
1
!2
1
3
1
1
)
!4!3!2
1(
1
0
864
2
1
0
dx
xxx
xdxe
2
x
S
4
R
4
/* Remainder */
,
1
0
4
∫
≈
Sdxe
2
x
取
"+×?×=
11
1
!5
1
9
1
!4
1
4
R
fi为 误差 /* Truncation Error */
0050
9
1
!4
1
4
.R <×<
743002401033301
42
1
10
1
3
1
1
4
....S =?+?≈?+?=
0010200050,,=×<
|?误差/* Roundoff Error */ |
006000100050
1
0
2
...dxe
-x
=+<
∫
的—o误差计算
= 0.747… …
由 部分
/* excluded terms */
¨?
由 部分
/* included terms */
¨?
误差,误差
1 误差是? 的,a?a
x
x 1.1 ' 是? 值是?的一个近 值
() | *|xxxε =?
是 误差
() | *|xxxεε=? ≤
** **
[
*
,]εεεεε∈=?≤≤ +? + ±xx x xxxxx或或
x
*
=?ex x是 误差x
! 误差 /* absolute error */
()xε x
ε
ε
x
0.5 10,
p
ε =×
2 的 ￠ 的? 的 难ˇ计算 值不过 aˇ?计出?的一个上界
fi 为为的 误差 的 误差 /* accuracy */
3 a取 p为 合条?的?￠ 数误差,误差
1.8 用一的? 的,来
的,出的
* 1235xmm=
是? 实˙ x一个近 值,由的?,
个近 值的误差不会 过0.5mm(即 误差 为
1/2mm),
1
|* |1235
2
xx x mm?=? ≤
1234.5 1235.5x≤≤
即
[]
1234.5,1235.5x∈
1235 0.5xmm=±
效数
1.2 a近 值x*的 误差 为 一 上的半个?,且该 直到x*的第一 非?数 共 n,fi近
值x* n 效数,说 x*? 到该
1.10 ˇ 那么
3.1415926...x π==
0
11
1,x *=3,(x)=0.14159 0.5 10ε ≤×""
X
1
*
的 效数 为1 3,X
1
*
到个,
-4 -5
22
2,x *=3.1416,(x)=0.00000734 0.5 10 (>0.5 10 )ε ≤× ×"
X
2
*
的 效数 为5,者说X
2
*
到0.0001.
! 效数 /* significant digits */
效数
1.11 用四?法 取x=4.26972的近 值取? 2 X
1
*
=4.3 效数 为2,￥
*-1
1
|x -x|<=0.5 10×
取? 4 X
2
*
=4.270 效数 为4,￥
3
2
|x -x|<=0.5 10×
用科学计数法 记
12
* 0.,..,.,10
m
ln
xaaaa=± ×
中a
1
a
2
… a
n
是0到9的自然数,
1
* 10 (1 n)
2
ml
xx l
=× ≤≤
x* l 效数 a
1
a
2
… a
l
1
0a ≠
– 数 末尾的0不a随意省
–
1.aˇ 过误差? 效数 数
2.aˇ 过 效数 的 数来?误差,
(1.2)
效数 … …
1.12 (1)ax*=3587.64是x的具 六 数 的近
值,那么?的误差 是￥少? (2)ax*=0.0023156是 x 的具 5 效数 的近 值,?的误差 是￥少?
*4
(1) 0.358764 10,( 4,6)=×==xml∵
解:
*2
(2) 0.23156 10,( 2,5)
= × =? =?xml∵
1.13 ax=1000 x
1
*
=999.9与x
2
*
=1000.1的 效数 的 数解:
|x
1
*
-x|= | x
2
*
-x|=0.1<0.5 10
0
分别 3和4 效数
46 2
11
|* | 10 10
22
∴?≤× =×xx
25 7
11
|* | 10 10
22
∴?≤× =×xx
相 误差
*
r
exx
e
xx
==
为近 值x*的相 误差
– 1?|e
r
|较￠￥
2?相 误差 值的上界 fi为相 误差 记‰
中 是x*的误差
|* |
||
|*| |*|
rr
xx
e
xx
ε
ε
=≤=
!相 误差 /* relative error */
==
*
**
r
exx
e
xx
r
ε
/* relative accuracy */
ε
…
1.14
10
(2.997925 0.000001) 10 /ccms=±×光速
10
* 2.997925 10 /ms=×
误差 =0.000001 10
10
cm/s
相 误差
0.000001
0.0000003.
| *| 2.997925
r
c
ε
ε == ≈
– 误差与相 误差的区别
1,误差是? 相 误差?
2,于同一个?的两个不同近 值 aˇ 过? 误差来判 谁? 于两个不同?的近 值 只 过
相 误差来比较 程
相 误差与 效数 的联系一
理1.1 ˇ近 值
12
* 0.,.,10
m
n
xaaa=± × n 效数,
a
1
0,?相 误差 为
1
1
1
10
2
n
a
+
×
”,x* n 效数
m-n
1
|x*-x| 10
2
∴≤×
≥
mm-1
1 2n 1
| x*|= 0.aa,..a 10a10
1
1
11
1
10
|* | 1
2
10
|*| 10 2
mn
n
m
xx
xa a
+
×
∴≤=×
×
" 效数?相 误差
–
该 理指出由近 值的 效数 a 出?相 误差,
相 误差与 效数 的联系二
理1.2 ˇ近 值x*= 0.a
1
a
2
..a
n
×10
m
的相 误差 为
1
1
1
1
10,0.
2( 1)
n
a
a
+
×≠
+
n 效数,
”:
1
12 1 2
| * | 0.,.,10,,.,10
=×=×
mm
n
xaaa aa∵
ˇx* n 效数,
"相 误差? 效数
1
=10
2
×
mn
1
1
(1)10
≤+×
m
a
|* |
|* | |*|
|*|
∴?=?
xx
xx x
x
11
1
1
1
10 ( 1) 10
2( 1)
+?
≤××+×
+
nm
a
a
理1.11与与与1.2 1 的应用
22
11
10 10
22 4
=×=×
×
1.15 用x*=2.72来? e的具 效数 的近 值.
x*的相 误差?
解,x*=0.272 10
1
a
1
=2
由 理1.1,
1.16 要使 的近 值的相 误差 ￠于0.1% 要取? 效数?
解,ˇ应取n 效数 由 理1.1
1
20 4.4..,a =4,=∴∵
从 应取4 效数 即为4.427 查?
20
13
1
10 0.1% 10
8
n
r
ε
+?
∴≤× < =
4n∴≥
4
10 8
n?+
<
31
1
1
10
2
+
≤×
r
a
ε
1.2.4 算 运算的误差一误差的传? 初始数据的误差 算 运算的结 何
1,x+y的近 值为x
*
+ y
*
'x
*
y
*
分别是x y的近 值 且
||xx
*
--x|x| (x) |y
*
--y|y| (y)
x
*
+y
*
- x+y = x
*
--xx + y
*
--yy
| x
*
+y
*
- x+y | =| x
*
--xx + y
*
--yy |
||xx
*
--x| +| yx| +| y
*
--y| y|
(x)+ (y)
ˇx
*
+y
*
的误差 (x+y)= (x)+ (y)
2,类 x
*
--yy
*
- xx---yy = x
*
--xx - y
*
--yy
(x--y)= y)= (x)+ (y)
和的误差?于误差的和 和的误差?于误差 的和
1.2.4 算 运算的误差二
3,xy的近 值为x
*
y
*
(()) (())
ηη
η
*
**
2
*
00yy
xyyx
x
y
y
≠≠
+
≈
其中
|x
*
y
*
--xyxyxy| = | x| = | x
*
y
*
--xyxy
*
++xyxy
*
--xyxy|
= |y
*
x
*
--xx +x y
*
--yy |
|y
*
|·||xx
*
--x| +|x|x| +|x|·|y
*
--y| y|
|y
*
|·||xx
*
--x| +|xx| +|x
*
--xxx---xx
*
|·|y
*
--y| y|
|y
*
|·||xx
*
--x| +|xx| +|x
*
|·|y
*
--y|+|xy|+|x
*
--x|x|·|y
*
--y| y|
|y
*
| (x)+|x
*
| (y)+ (x) (y)
a (y) |y
*
| (x) |x
*
|
((xyxy)= |y
*
| (x)+|x
*
| (y)+ (x) (y)
((xyxy) |x
*
| (y) ++|y|y
*
| (x)
4,
函数的误差?计 /*Error Estimation for Functions*/
问题 于 y= f (x) a用 x*取? x fl y,什么
分析 e(y) = f (x*)? f (x) e(x) = x*? x 由
Mean Value
Theorem
= f ’(ξ )(x*? x)
x* 与x 非常接近￥ a认为f ’(ξ ) ≈ f ’(x*)
|e(y)| ≈ | f ’(x*)|·|e(x)| (y)| ≈ | f ’(x*)|· (x)
即 x*,的误差经过f ‰用后被放 /缩￠ | f ’(x*)|倍故fi| f ’(x*)|为放? /* amplification factor */
条?数/* absolute condition number */.
****
** *
() () () () ()
|()|| || || |
() ()
r
ey fx fx fx fx x x x
ey
yfx xxfxx
== =
*
'*
*
|()|| () ||()|
()
rr
x
ey fx ex
fx
≈
相 误差条?数
/* relative condition number*/
￥元函数的误差?计
￥元函数 a 分别是
()
12
,,,"
n
fxx x
** *
12
,,,"
n
xx x
12
,,,"
n
xx x
(())
(())
** *
12
*
1
,,,
()
n
n
k
k
k
fxx x
ey y y e x
x
=
=?≈
∑
"
的近 值
(())
(())
** *
**
12
**
1
*
*
*
(
,,,
(),
),(),
n
n
k
r k
k
k
kk
kkkrk
r
k
ex
fxx x
xyy
ey e x
yxy
xx
xxex
x
=
=≈
=? =
∑
"
其中积与商的相 误差?计应用刚才的 容? 出出算 运算的相 误差?计算
1
12 1 2
(,),yfxx xx==?
**
12
12 2 1 1 2
** **
12 12
() () (),
rrr
xx
exx x ex x ex
xx xx
≈? +?
∵
2
1
12
2
(,),
x
yfxx
x
==
1
12
2
() () ()
rrr
x
eexex
x
≈?
12 1 2
()()()
rrr
exx ex ex∴?≈ +
和与差的相 误差?计一
**
12
12 1 2
** **
12 12
() () ()
rrr
xx
ex x ex ex
xx xx
+≈ +
++
–1 ax
1
*
与x
2
*
同号
** * *
12 1 2
0,1 1
**** ** **
1212 1212
xx x x
xxxx xx xx
≤≤+=
++ + +
且
() () ()
** **
12 1 2
12 12
xx x x
rrr
xx xx
εεε+≈ +
++
()max{(),()}
12 1 2
ex x ex ex
rrr
+∴ ≤
()max{(),()}
12 1 2
xx x x
rrr
εεε∴ +≈
()|max{|()|,()|}
12 1 2
ex x ex ex+≤|
和与差的相 误差?计二
**
12
12 1 2
** **
12 12
() () ()
rrr
xx
ex x ex ex
xx xx
+≈ +
++
–2 a|x
1
*
|>>|x
2
*
|
**
12
** **
12 12
10
xx
xx xx
≈≈
++
∵ 而
12 1
()()
rr
ex x ex≈∴ +
和与差的相 误差?计
–3 ax
1
*
与x
2
*
异号 且x
1
*
+x
2
*
0 相 误差条?数很
**
12
1,1
** **
12 12
xx
xx xx
>> >>
++
∵
**
12
() () ()
** **
12 1 2
12 12
xx
xx x x
rrr
xx xx
εεε+≈ +
++
类计算问题fi为坏条?的 病 的?初始数据的微￠
误差 致计算结 较 的误差 计算过程不稳? 要‰
两相近的数相减
计算 四 效数
11
662 663
1
6
11
2.278 10
662 663
662 663
= ≈×
×
解法一解法二
11
662 663
0.0015106- 0.0015081 =0.0000025=2.5 10
-6
￥元函数误差?计 的应用
1.18 分析函数数的相 误差传?的
( )
(())
** *
*
,,,
*
12
()
**
1
fx x x
x
n
yy n
k
ey e x
rr
x
k
k
=≈
∑
=
"
xy
u
zw
=
** * *
** * ** *
** * ** *
*2 * * * *2 *
() () ()
() ( )
() ( )
rrr
rr
yx xy
eu ex ey
zw u zw u
xy z xy w
ez ew
zwu zw u
≈? +?
| ( )| | ( )| | ( )| | ( )| | ( )|
rr r r r
eu ex ey ez ew ≤ + + +∵
() () () ( )
rrrr
ex ey ez ew=+
() () () ( )
rrrr
x y zwεεεε≤+++
() () () () ( )
rrrrr
uxy zwεεεεε∴=+++
一元函数误差?计 的应用
1.19 ˇ函数y=x
10
,问xx= =3.141592…取? 效数
才currency1使y的相 误差 不 过0.5×10
-6
*
*9
| ( ) | 10( ) | ( ) |
*
x
ey x ex
rr
y
≈?
*
'*
*
|()|| () ||()|
()
r r
x
ey fx ex
fx
≈
解 ˇ 取n 效数 后 x* ≈ x
() 10 () () 0.1 ()
rrr r
yxx yεεε ε∴≈?≈?
1
16
10 0.1 0.5 10
23
n?+?
≤×
×
8
10 3
n?+
≤
8n?≥
*10
()
10 | ( ) | 10 | ( ) |
*10
()
x
ex ex
rr
x
=? = 10 ( )x
r
ε≤
4?点–意事? /* Remarks */
1,‰ 相近二数相减
a
1
= 0.12345 a
2
= 0.12346 各 5 效数
a
2
a
1
= 0.00001 只剩 1 效数
#?种经验性‰ 方法;
xεx
ε
xεx
++
=?+
(()) ;1lnlnln
+=?+
x
ε
xεx
| x | << 1 ￥;
2
sin2cos1
2
x
x =?
+++=?,..
6
1
2
1
11
2
xxxe
x
4 –意事?2
2,‰ 除数的 值远￠于被除数的 值
(()) (())
ηη
η
**
2
*
xyyx
x
y
y
+
≈
￥￥,?误差会
xy>>
2.718
2718.2
0.001
=?分母y‰微￠ 0.0001,
2.7182
2471.1
0.0011
=
计算结 y的扰动很敏感 y 常是近 值 ˇ计算结
不ao 另fl 很￠的数‰除数 ￥还会造 计算机的溢出
停机
3,‰ 数吃￠数
用 计算 的根
010)110(
992
=++? xx
解为 110
2
9
1
== x,x
$ 算法1 利用 根
a
acbb
x
2
4
2
±?
=
在计算机内 10
9
为0.1×10
10
1?为0.1×10
1
法￥
两 数的指数 向 指数 齐?fl浮点部分相
即1 的指数部分须 为10
10
1 = 0.0000000001 × 10
10
取 ￥就 为
10
9
+1=0.10000000×10
10
+0.00000000 ×10
10
=0.10000000 ×10
10
数吃￠数
0
2
4
,10
2
4
2
2
9
2
1
=
==
+?
=?
a
acbb
x
a
acbb
x
4 –意事?3
$算法2 解出
利用
9
2
1
10
2
4)(
=
=
a
acbbsignb
x
1
10
10
9
9
1
221
==
=?=
xa
c
x
a
c
xx
–
和￥从￠到 相 a使和的误差减￠
从￠到 ˇˉ从 到￠的顺?分别计算
1 + 2 + 3 + … + 40 + 10
9
4,计算步? 减少运算次数 进 减少误差积累
5,选用稳 的算法 ˇ便误差的传?
16
algorithm 1,
16
x xxx x=
#$%$&
评价算法的准 计算复杂性 算法的? 算法的稳 性
HW,p.13
#1,3,5,10,12
16 2222
algorithm 2,((( ) ) )xx=
Numerical Analysis
华中科技大学计算机科学与技术学院
HUST
College of Computer Science & Technology
Spring,2003
Version 2.0
主讲教师许贵平
xugpjq@263.net
什么是数值分析?
Numerical Analysis is concerned with
the design and analysis of algorithms for solving
mathematical problems that arise in many fields,
especially science and engineering.
----Michael T,Heath
Numerical analysis is the study of
algorithms for the problems of continuous
mathematics,
----Lloyd N,Trefethen
什么是数值分析?
“数值分析”就是研究在计算机上解决数学问题的理论和数值方法
数值算法的构造
算法的理论分析数值分析的学科别名
计算方法
科学与工程计算科学计算的重要性
科学计算是工程实践的重要工具
科学计算是继理论与实验后另一科学研究手段科学计算的国家战略与发展 1
1983年一个由美国著名数学家拉克斯(P,Lax)为首的不同学科的专家委员会向美国政府提出的报告之中 强调“科学计算是关系到国家安全 经济发展和科技进步的关键性环节 是事关国家 的 事,
1984年美国政府 科学计算经 的,
个国家 计算中 分别在 斯 学
学 学? ￠￡?￥?§性currency1的计算机 'NSFNSF--net,?
80年?中?fi国fl –科学与工程计算国家· 重
科学计算的国家战略与发展 2
1987年?美国NSF?“科学与工程计算”,”?工程”,全…
性科学”‰为? · 的`′
1990年美国国家研究委员会发ˉ美国数学 90年?的计? 的报告 ˙ 由计算¨发的数学 的和·
1991年ˇ美国— ˙的 提出,§性currency1计算与 HPCC
计?” 是为 和提§美国在计算和“?的 进`′
中的` 的?发展的关键技 是a 展的 –
计算
1995年美国为的性currency1 安全性 ao性和
要 实 的,战略计算 ASCI 计?”
战略计算
是?为美国克 — 在1995年8 1111?,美国决
的“”全 验?武器条约”
不意味着?竞赛的结束 恰恰相反是?武器计? ￥?的开始 要 过逼?的 –和–拟计算来取?传 的反复 验的工程处理方法 主要依赖于 进的数值计算和–拟currency1力
年 美国的DOE/FNS共同联合组织召开 关于,进科学计算”的全国会˙ 会˙强调科学–拟的重要性 希望应用科学–拟来攻克复杂的科学与工程难题
1995年8 22 即美国—?决 后的11天 currency1源部DOE
就采购世界上?快的一台计算机 运算 过万亿次 交付
实验室 96年年121 安装
Some past developments in scientific computing
----Lloyd N,Trefethen
Before 1940
Newton's method
Gaussian elimination
Gauss quadrature (求积法
Least-squares fitting
Adams and Runge-Kutta formulas
Richardson extrapolation
1940--1970
floating point arithmetic
Fortran
finite differences
finite elements
simplex algorithm 单纯形算法
Monte Carlo
FFT
orthogonal linear algebra
1970--1998
quasi-Newton iterations multigrid
adaptivity Matlab
stiff ODE solvers interior point methods
software libraries spectral methods
sparse and iterative linear algebra
The future development in scientific computing
----Lloyd N,Trefethen
1998--2048
linear algebra in flops
multipole methods
breakthroughs in preconditioners,spectral methods,time
stepping for PDE
* speech and graphics everywhere
* fully intelligent,adaptive numerics
* loss of determinism
* seamless interoperability
* massively parallel computing made possible by ideas related
to the human brain
* new programming methods made possible by ideas related to
natural selection
2
()ON
ε+
数值分析课的主要内容
插值和函数逼近
数值微分和数值积分
常微分方程和偏微分方程数值解法
数值?数,解线性和非线性方程的直接法和间接法
数?征值问题的数值解法数值分析的学科?点实用性 理论性 实践性
1 向计算机 根据计算机的?点提供a 的 效算法
只提供 减 乘 除和逻辑运算
串 机和 机
2 ao的理论分析 算法的收敛性 稳 性 误差分析
3 好的计算复杂性 ￥间和空间复杂性
4 分的数值实验构造数值算法的
近?
近?
解:
1 计算 理数e的近 值.
2
1,..,..
2! !
n
x
xx
ex
n
=++ + + +∵
11
11,.,.
2! !
e
n
∴=++ + + +
是一个 过程,计算机 法实,一,只currency1
算出?的和,‰为?近 值
11
11,.
2! !
e
n
≈++ + +
由Taylor,由,的误差:
3
(1)!(1)!
e
R
n
nn
<<
++
2
1
1..,(01)
1! 2! ! ( 1)!
nx
xn
xx x e
ex
nn
θ
θ
+
=+ + + + + < <
+
∵
不currency1用
次运算 解的问题,为用
次运算
解的问题
---的问题 为?的问题
2 计算 积分
011
1
( ) [ ( ),.,]
2
b
nn
a
ba
fxdx y y y y
n
≈+++
∫
()
b
a
Ifxdx=
∫
I为 的
的 积,个 的问题,法在计算机上计算.
一,aˇ 计算:
1..nn?分[a,b],a,b],
01
...,( ),0,1,...,
ni i
ax x x by fxi n=<<<= = =
2.用n个￠ 的 积之和近? 的
积
---复杂的计算￡结为?过程的￥次重复,
于用§环结构来实,(currency1?法)
3 计算￥?
1
110
(),..
nn
nnn
Px ax a x ax a
=+ +++
构造 算法:
12
1210
() ( ),.
nn
nnn n
Px ax a x a x ax a
=+ + ++∵
'
0
,
n
ua=
110nn n
uaxa uxa
=+=+
12
12 10
( ),..
nn
nn
Px ux a x ax a
∴= + +++
2
12 10
().
n
n
ux a x ax a
=+ +++
2
210
...
n
ux ax a
=+++
……
0
1
=
=+
n
kk nk
ua
uuxa
(1.3) ()
nn
Px u?=
是fi国“?数学家 提出的,fi为算法,
(国flfi为 Horner 算法)
学,计算方法” –意?点
1.要?·算法的 理和
2.要?·算法的处理技?,步?和计算
3.重?误差分析,理解收敛性,稳 性分析的理论
4.?一 的理论分析”?与计算…
5.上机实践
1.2 误差的 理论
2 误差是不a‰ 的,?要 `误差,′要
误差.要重?误差分析,分析误差的来源,误差的传?ˉ 误差‰出?计
1 用计算机进 实˙问题的数值计算￥,¨
¨ 的是问题的近 解,在误差误差来源
用计算机解决科学与工程计算问题的过程:
实˙问题 数学–?
数值分析 程?ˇ计上机计算
—,
近
中主要会,ˇ?个方 的误差
1.–?误差 3,误差
2,误差 4,?误差
–?误差,误差
!数学–?是 实˙问题的— 和近,?在误差
——–?误差 /* Modeling Error */
国经济学家 Malthus的? –?
00
(1)
()
dp
p
dt
pt p
α
=
=
中 为” 系数0.029α =
2
00
(2)
()
dp
pp
dt
pt p
αβ
=?
=
中 为 会 系数0β >
! 过? 实验 到–?中 数的值,的误差
—— 误差 /* Measurement Error */
4
2
1,..,..
2! !
n
x
xx
ex
n
=+ + + + +
2
() 1,.
2! !
n
x
n
xx
eSx x
n
≈=++++
￥ 误差为
1
() () (0 1)
(1)!
n
xx
nn
x
Rx e Sx e
n
θ
θ
+
=? = <<
+
误差
! 近 解——方法误差( 误差/* Truncation Error */ )
误差由于计算机的,只currency1 数进 运算,过的 数?一?,”,?误差”.
3.1415926...,2 1.41421356...π ==
在计算机上运算￥,只currency1取
a取￠数点后4 数,?误差是
1
3.1416 0.0000074...,0.3333 0.000033...
3
π?=?=?
￠结,–?误差,误差不是数值分析 论的内容,计算方法主要研究 误差和?误差在计算过程中的传?和 计算结 的,ˇ提§计算的?,
!机器 ——?误差 /* Roundoff Error */
dxe
x
∫
1
0
2
近 计算,
家一
<<
∫
dxe
2
x
1
0
1
1 / e
解法之一 flfl‰‰Taylor展开后?积分
2
x
e
"
"
×+×?×+?=
+?+?=
∫∫
9
1
!4
1
7
1
!3
1
5
1
!2
1
3
1
1
)
!4!3!2
1(
1
0
864
2
1
0
dx
xxx
xdxe
2
x
S
4
R
4
/* Remainder */
,
1
0
4
∫
≈
Sdxe
2
x
取
"+×?×=
11
1
!5
1
9
1
!4
1
4
R
fi为 误差 /* Truncation Error */
0050
9
1
!4
1
4
.R <×<
743002401033301
42
1
10
1
3
1
1
4
....S =?+?≈?+?=
0010200050,,=×<
|?误差/* Roundoff Error */ |
006000100050
1
0
2
...dxe
-x
=+<
∫
的—o误差计算
= 0.747… …
由 部分
/* excluded terms */
¨?
由 部分
/* included terms */
¨?
误差,误差
1 误差是? 的,a?a
x
x 1.1 ' 是? 值是?的一个近 值
() | *|xxxε =?
是 误差
() | *|xxxεε=? ≤
** **
[
*
,]εεεεε∈=?≤≤ +? + ±xx x xxxxx或或
x
*
=?ex x是 误差x
! 误差 /* absolute error */
()xε x
ε
ε
x
0.5 10,
p
ε =×
2 的 ￠ 的? 的 难ˇ计算 值不过 aˇ?计出?的一个上界
fi 为为的 误差 的 误差 /* accuracy */
3 a取 p为 合条?的?￠ 数误差,误差
1.8 用一的? 的,来
的,出的
* 1235xmm=
是? 实˙ x一个近 值,由的?,
个近 值的误差不会 过0.5mm(即 误差 为
1/2mm),
1
|* |1235
2
xx x mm?=? ≤
1234.5 1235.5x≤≤
即
[]
1234.5,1235.5x∈
1235 0.5xmm=±
效数
1.2 a近 值x*的 误差 为 一 上的半个?,且该 直到x*的第一 非?数 共 n,fi近
值x* n 效数,说 x*? 到该
1.10 ˇ 那么
3.1415926...x π==
0
11
1,x *=3,(x)=0.14159 0.5 10ε ≤×""
X
1
*
的 效数 为1 3,X
1
*
到个,
-4 -5
22
2,x *=3.1416,(x)=0.00000734 0.5 10 (>0.5 10 )ε ≤× ×"
X
2
*
的 效数 为5,者说X
2
*
到0.0001.
! 效数 /* significant digits */
效数
1.11 用四?法 取x=4.26972的近 值取? 2 X
1
*
=4.3 效数 为2,￥
*-1
1
|x -x|<=0.5 10×
取? 4 X
2
*
=4.270 效数 为4,￥
3
2
|x -x|<=0.5 10×
用科学计数法 记
12
* 0.,..,.,10
m
ln
xaaaa=± ×
中a
1
a
2
… a
n
是0到9的自然数,
1
* 10 (1 n)
2
ml
xx l
=× ≤≤
x* l 效数 a
1
a
2
… a
l
1
0a ≠
– 数 末尾的0不a随意省
–
1.aˇ 过误差? 效数 数
2.aˇ 过 效数 的 数来?误差,
(1.2)
效数 … …
1.12 (1)ax*=3587.64是x的具 六 数 的近
值,那么?的误差 是￥少? (2)ax*=0.0023156是 x 的具 5 效数 的近 值,?的误差 是￥少?
*4
(1) 0.358764 10,( 4,6)=×==xml∵
解:
*2
(2) 0.23156 10,( 2,5)
= × =? =?xml∵
1.13 ax=1000 x
1
*
=999.9与x
2
*
=1000.1的 效数 的 数解:
|x
1
*
-x|= | x
2
*
-x|=0.1<0.5 10
0
分别 3和4 效数
46 2
11
|* | 10 10
22
∴?≤× =×xx
25 7
11
|* | 10 10
22
∴?≤× =×xx
相 误差
*
r
exx
e
xx
==
为近 值x*的相 误差
– 1?|e
r
|较￠￥
2?相 误差 值的上界 fi为相 误差 记‰
中 是x*的误差
|* |
||
|*| |*|
rr
xx
e
xx
ε
ε
=≤=
!相 误差 /* relative error */
==
*
**
r
exx
e
xx
r
ε
/* relative accuracy */
ε
…
1.14
10
(2.997925 0.000001) 10 /ccms=±×光速
10
* 2.997925 10 /ms=×
误差 =0.000001 10
10
cm/s
相 误差
0.000001
0.0000003.
| *| 2.997925
r
c
ε
ε == ≈
– 误差与相 误差的区别
1,误差是? 相 误差?
2,于同一个?的两个不同近 值 aˇ 过? 误差来判 谁? 于两个不同?的近 值 只 过
相 误差来比较 程
相 误差与 效数 的联系一
理1.1 ˇ近 值
12
* 0.,.,10
m
n
xaaa=± × n 效数,
a
1
0,?相 误差 为
1
1
1
10
2
n
a
+
×
”,x* n 效数
m-n
1
|x*-x| 10
2
∴≤×
≥
mm-1
1 2n 1
| x*|= 0.aa,..a 10a10
1
1
11
1
10
|* | 1
2
10
|*| 10 2
mn
n
m
xx
xa a
+
×
∴≤=×
×
" 效数?相 误差
–
该 理指出由近 值的 效数 a 出?相 误差,
相 误差与 效数 的联系二
理1.2 ˇ近 值x*= 0.a
1
a
2
..a
n
×10
m
的相 误差 为
1
1
1
1
10,0.
2( 1)
n
a
a
+
×≠
+
n 效数,
”:
1
12 1 2
| * | 0.,.,10,,.,10
=×=×
mm
n
xaaa aa∵
ˇx* n 效数,
"相 误差? 效数
1
=10
2
×
mn
1
1
(1)10
≤+×
m
a
|* |
|* | |*|
|*|
∴?=?
xx
xx x
x
11
1
1
1
10 ( 1) 10
2( 1)
+?
≤××+×
+
nm
a
a
理1.11与与与1.2 1 的应用
22
11
10 10
22 4
=×=×
×
1.15 用x*=2.72来? e的具 效数 的近 值.
x*的相 误差?
解,x*=0.272 10
1
a
1
=2
由 理1.1,
1.16 要使 的近 值的相 误差 ￠于0.1% 要取? 效数?
解,ˇ应取n 效数 由 理1.1
1
20 4.4..,a =4,=∴∵
从 应取4 效数 即为4.427 查?
20
13
1
10 0.1% 10
8
n
r
ε
+?
∴≤× < =
4n∴≥
4
10 8
n?+
<
31
1
1
10
2
+
≤×
r
a
ε
1.2.4 算 运算的误差一误差的传? 初始数据的误差 算 运算的结 何
1,x+y的近 值为x
*
+ y
*
'x
*
y
*
分别是x y的近 值 且
||xx
*
--x|x| (x) |y
*
--y|y| (y)
x
*
+y
*
- x+y = x
*
--xx + y
*
--yy
| x
*
+y
*
- x+y | =| x
*
--xx + y
*
--yy |
||xx
*
--x| +| yx| +| y
*
--y| y|
(x)+ (y)
ˇx
*
+y
*
的误差 (x+y)= (x)+ (y)
2,类 x
*
--yy
*
- xx---yy = x
*
--xx - y
*
--yy
(x--y)= y)= (x)+ (y)
和的误差?于误差的和 和的误差?于误差 的和
1.2.4 算 运算的误差二
3,xy的近 值为x
*
y
*
(()) (())
ηη
η
*
**
2
*
00yy
xyyx
x
y
y
≠≠
+
≈
其中
|x
*
y
*
--xyxyxy| = | x| = | x
*
y
*
--xyxy
*
++xyxy
*
--xyxy|
= |y
*
x
*
--xx +x y
*
--yy |
|y
*
|·||xx
*
--x| +|x|x| +|x|·|y
*
--y| y|
|y
*
|·||xx
*
--x| +|xx| +|x
*
--xxx---xx
*
|·|y
*
--y| y|
|y
*
|·||xx
*
--x| +|xx| +|x
*
|·|y
*
--y|+|xy|+|x
*
--x|x|·|y
*
--y| y|
|y
*
| (x)+|x
*
| (y)+ (x) (y)
a (y) |y
*
| (x) |x
*
|
((xyxy)= |y
*
| (x)+|x
*
| (y)+ (x) (y)
((xyxy) |x
*
| (y) ++|y|y
*
| (x)
4,
函数的误差?计 /*Error Estimation for Functions*/
问题 于 y= f (x) a用 x*取? x fl y,什么
分析 e(y) = f (x*)? f (x) e(x) = x*? x 由
Mean Value
Theorem
= f ’(ξ )(x*? x)
x* 与x 非常接近￥ a认为f ’(ξ ) ≈ f ’(x*)
|e(y)| ≈ | f ’(x*)|·|e(x)| (y)| ≈ | f ’(x*)|· (x)
即 x*,的误差经过f ‰用后被放 /缩￠ | f ’(x*)|倍故fi| f ’(x*)|为放? /* amplification factor */
条?数/* absolute condition number */.
****
** *
() () () () ()
|()|| || || |
() ()
r
ey fx fx fx fx x x x
ey
yfx xxfxx
== =
*
'*
*
|()|| () ||()|
()
rr
x
ey fx ex
fx
≈
相 误差条?数
/* relative condition number*/
￥元函数的误差?计
￥元函数 a 分别是
()
12
,,,"
n
fxx x
** *
12
,,,"
n
xx x
12
,,,"
n
xx x
(())
(())
** *
12
*
1
,,,
()
n
n
k
k
k
fxx x
ey y y e x
x
=
=?≈
∑
"
的近 值
(())
(())
** *
**
12
**
1
*
*
*
(
,,,
(),
),(),
n
n
k
r k
k
k
kk
kkkrk
r
k
ex
fxx x
xyy
ey e x
yxy
xx
xxex
x
=
=≈
=? =
∑
"
其中积与商的相 误差?计应用刚才的 容? 出出算 运算的相 误差?计算
1
12 1 2
(,),yfxx xx==?
**
12
12 2 1 1 2
** **
12 12
() () (),
rrr
xx
exx x ex x ex
xx xx
≈? +?
∵
2
1
12
2
(,),
x
yfxx
x
==
1
12
2
() () ()
rrr
x
eexex
x
≈?
12 1 2
()()()
rrr
exx ex ex∴?≈ +
和与差的相 误差?计一
**
12
12 1 2
** **
12 12
() () ()
rrr
xx
ex x ex ex
xx xx
+≈ +
++
–1 ax
1
*
与x
2
*
同号
** * *
12 1 2
0,1 1
**** ** **
1212 1212
xx x x
xxxx xx xx
≤≤+=
++ + +
且
() () ()
** **
12 1 2
12 12
xx x x
rrr
xx xx
εεε+≈ +
++
()max{(),()}
12 1 2
ex x ex ex
rrr
+∴ ≤
()max{(),()}
12 1 2
xx x x
rrr
εεε∴ +≈
()|max{|()|,()|}
12 1 2
ex x ex ex+≤|
和与差的相 误差?计二
**
12
12 1 2
** **
12 12
() () ()
rrr
xx
ex x ex ex
xx xx
+≈ +
++
–2 a|x
1
*
|>>|x
2
*
|
**
12
** **
12 12
10
xx
xx xx
≈≈
++
∵ 而
12 1
()()
rr
ex x ex≈∴ +
和与差的相 误差?计
–3 ax
1
*
与x
2
*
异号 且x
1
*
+x
2
*
0 相 误差条?数很
**
12
1,1
** **
12 12
xx
xx xx
>> >>
++
∵
**
12
() () ()
** **
12 1 2
12 12
xx
xx x x
rrr
xx xx
εεε+≈ +
++
类计算问题fi为坏条?的 病 的?初始数据的微￠
误差 致计算结 较 的误差 计算过程不稳? 要‰
两相近的数相减
计算 四 效数
11
662 663
1
6
11
2.278 10
662 663
662 663
= ≈×
×
解法一解法二
11
662 663
0.0015106- 0.0015081 =0.0000025=2.5 10
-6
￥元函数误差?计 的应用
1.18 分析函数数的相 误差传?的
( )
(())
** *
*
,,,
*
12
()
**
1
fx x x
x
n
yy n
k
ey e x
rr
x
k
k
=≈
∑
=
"
xy
u
zw
=
** * *
** * ** *
** * ** *
*2 * * * *2 *
() () ()
() ( )
() ( )
rrr
rr
yx xy
eu ex ey
zw u zw u
xy z xy w
ez ew
zwu zw u
≈? +?
| ( )| | ( )| | ( )| | ( )| | ( )|
rr r r r
eu ex ey ez ew ≤ + + +∵
() () () ( )
rrrr
ex ey ez ew=+
() () () ( )
rrrr
x y zwεεεε≤+++
() () () () ( )
rrrrr
uxy zwεεεεε∴=+++
一元函数误差?计 的应用
1.19 ˇ函数y=x
10
,问xx= =3.141592…取? 效数
才currency1使y的相 误差 不 过0.5×10
-6
*
*9
| ( ) | 10( ) | ( ) |
*
x
ey x ex
rr
y
≈?
*
'*
*
|()|| () ||()|
()
r r
x
ey fx ex
fx
≈
解 ˇ 取n 效数 后 x* ≈ x
() 10 () () 0.1 ()
rrr r
yxx yεεε ε∴≈?≈?
1
16
10 0.1 0.5 10
23
n?+?
≤×
×
8
10 3
n?+
≤
8n?≥
*10
()
10 | ( ) | 10 | ( ) |
*10
()
x
ex ex
rr
x
=? = 10 ( )x
r
ε≤
4?点–意事? /* Remarks */
1,‰ 相近二数相减
a
1
= 0.12345 a
2
= 0.12346 各 5 效数
a
2
a
1
= 0.00001 只剩 1 效数
#?种经验性‰ 方法;
xεx
ε
xεx
++
=?+
(()) ;1lnlnln
+=?+
x
ε
xεx
| x | << 1 ￥;
2
sin2cos1
2
x
x =?
+++=?,..
6
1
2
1
11
2
xxxe
x
4 –意事?2
2,‰ 除数的 值远￠于被除数的 值
(()) (())
ηη
η
**
2
*
xyyx
x
y
y
+
≈
￥￥,?误差会
xy>>
2.718
2718.2
0.001
=?分母y‰微￠ 0.0001,
2.7182
2471.1
0.0011
=
计算结 y的扰动很敏感 y 常是近 值 ˇ计算结
不ao 另fl 很￠的数‰除数 ￥还会造 计算机的溢出
停机
3,‰ 数吃￠数
用 计算 的根
010)110(
992
=++? xx
解为 110
2
9
1
== x,x
$ 算法1 利用 根
a
acbb
x
2
4
2
±?
=
在计算机内 10
9
为0.1×10
10
1?为0.1×10
1
法￥
两 数的指数 向 指数 齐?fl浮点部分相
即1 的指数部分须 为10
10
1 = 0.0000000001 × 10
10
取 ￥就 为
10
9
+1=0.10000000×10
10
+0.00000000 ×10
10
=0.10000000 ×10
10
数吃￠数
0
2
4
,10
2
4
2
2
9
2
1
=
==
+?
=?
a
acbb
x
a
acbb
x
4 –意事?3
$算法2 解出
利用
9
2
1
10
2
4)(
=
=
a
acbbsignb
x
1
10
10
9
9
1
221
==
=?=
xa
c
x
a
c
xx
–
和￥从￠到 相 a使和的误差减￠
从￠到 ˇˉ从 到￠的顺?分别计算
1 + 2 + 3 + … + 40 + 10
9
4,计算步? 减少运算次数 进 减少误差积累
5,选用稳 的算法 ˇ便误差的传?
16
algorithm 1,
16
x xxx x=
#$%$&
评价算法的准 计算复杂性 算法的? 算法的稳 性
HW,p.13
#1,3,5,10,12
16 2222
algorithm 2,((( ) ) )xx=
