数值代数夏银华中国科学技术大学

Size: px

Start display at page:

Download "数值代数夏银华中国科学技术大学"

毛荃鲍
5 years ago
Views:

1 数值代数夏银华中国科学技术大学

2 课程介绍时间, 地点周二 :6,7 节, 周四 :1,2 节,(1-15 周 ) 地点 :3A211 教材 D. Kincaid and W. Cheney, Numerical Analysis:Mathematics of Scientific Computing, American Mathematical Soc., 2002 参考教材 L.N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, 1997 课程内容误差条件数 (Chap. 2), 非线性方程求解 (Chap. 3), 线性方程组直接与迭代求解 (Chap. 4,5)

3 总评成绩书面作业 :20%, 程序作业 :20%, 期末考试 :60% 作业要求课程介绍请按时提交作业, 迟交及抄袭 ( 双方或多方 ) 均没有成绩, 特殊原因迟交请附上证明书面作业每周二上课前提交程序作业 ( 截止给定提交日期晚上 23:00) 请统一提交到 CourseNLA@gmail.com 邮件标题 : 学号 + 姓名 ( 如 PB 张三 ) 邮件内容 : 空邮件附件 : 只允许有一个附件, 程序报告 (pdf 或 word 文档 ) 和程序源文件请放到同一个压缩包内程序报告 : 标题 + 作者 + 问题 + 算法 + 程序说明 ( 编译及使用说明 )+ 数值图表 + 数值结果说明

4 计算数学 1 连续模型 : 微分方程 2 离散模型 : 有限维空间逼近无限维空间 3 线性 / 非线性方程组求解 4 数值解

5 误差类型舍入误差 (round-off error): 由于计算机只能表示有限位数的数字截断误差 (Truncation error): 由于数值算法对数学运算或数量的近似其它误差 : 模型误差, 数据 / 参数输入误差, 人为误差...

6 舍入误差有效数字 (significant digits): 能够被相信的数字舍入误差 : ( 计算机中 ) 被忽略的有效数字精度 : 近似值 ˆx 与真值 x 间的差距 ( 准确 ) 绝对误差 :ɛ = ˆx x ( 准确 ) 相对误差 :α = ˆx x x

7 ( 计算机 ) 数字表示数字系统十进制 :1, = 二进制 : = = 整数表示首位 (first bit) 是正负号, 剩余位存储数字例如在 16 位计算机中, = , 最大能表示的数

Computers (0/1): base-2 1101 2 = 1 x 2 3 + 1 x 2 2 + 0 x 2 1 + 1 x 2 0 =13 10 ( 计算机 ) 数字表示 Integer Representation (signed magnitude method): First bit is the sign (0,1), remaining bits used to store

8 Computers (0/1): base = 1 x x x x 2 0 =13 10 ( 计算机 ) 数字表示 Integer Representation (signed magnitude method): First bit is the sign (0,1), remaining bits used to store the number For a 16-bits computer: 浮点数 (floating number) 表示 Example: = x = mb e Largest range of numbers: 2, 15-1 largest number => -32,768 to (from 0 to ) m: 小数部分 (Mantissa/Significand) b: Floating 基 (Base) Number Representation e: 指数 (Exponent) m Mantissa/Significan = fractional part Sign Signed Exponent x = m b e Mantissa 例如 : ( 规范化小数 b 1 m < b 0 ) 十进位 : = 二进位 : = = Numerical Fluid Mechanics PFJL Lec b e Base Exponent

9 例 : ( 计算机 ) 数字表示考虑二进制 7 位浮点计算机 7 位 = 1 位符号 +3 位指数部分 (1 位符号两位数字 )+ 三位小数部分, 问计算机能表示的最大最小正数是?

10 例 : ( 计算机 ) 数字表示考虑二进制 7 位浮点计算机 7 位 = 1 位符号 +3 位指数部分 (1 位符号两位数字 )+ 三位小数部分, 问计算机能表示的最大最小正数是?

11 ( 计算机 ) 数字表示局限性有限的范围 ( 最大数和最小数 ) 有限的精度 ( 舍入误差 ) 有限的距离 ( 数字间的距离 x 随数字本身增长 ) 若 t = 计算机中数字的小数部分的有效数字的位数, 机器误差 :M ɛ = b 1 t, 相对误差 : x x Mɛ 2 绝对误差 : x Mɛ 2 x

12 ( 计算机 ) 算术运算加减法 : x 1 ± x 2 = m 1 b e 1 ± m 2 b e 2 假设 e 1 > e 2, x 1 ± x 2 = (m 1 ± m 2 b e 2 e 1 )b e 1 = mb e1 绝对误差 : ɛ ɛ 1 + ɛ 2 m ˆm 相对误差 : α = m ( 无界! 当 m 0)

13 ( 计算机 ) 算术运算乘除法 : x 1 x 2 = m 1 m 2 b e 1+e 2 指数相加小数相乘正则化并舍入 m = m 1 m 2 < 1 相对误差 : α α 1 + α 2 x 1 /x 2 = (m 1 /m 2 )b e 1 e 2 指数相加小数相除正则化并舍入相对误差 : α α 1 α 2

14 误差控制问题大规模加减法 ( 循环 ) 大数小数相加减相近的数相减级数求和时湮灭 ( 如 : 向量内积 )

15 多项式求值 Horner s 递归求和公式多项式 : p(x) = a 0 x 3 + a 1 x 2 + a 2 x + a 3 = ((a 0 x + a 1 )x + a 2 )x + a 3

16 多项式求值 Horner s 递归求和公式多项式 : p(x) = a 0 x 3 + a 1 x 2 + a 2 x + a 3 = ((a 0 x + a 1 )x + a 2 )x + a 3 一般多项式 p(x) = a 0 x n + a 1 x n a n 1 x + a n

17 多项式求值 Horner s 递归求和公式多项式 : p(x) = a 0 x 3 + a 1 x 2 + a 2 x + a 3 = ((a 0 x + a 1 )x + a 2 )x + a 3 一般多项式 p(x) = a 0 x n + a 1 x n a n 1 x + a n 递归公式 b 0 = a 0, b i = a i + b i 1 x, i = 1,, n p(x) = b n

18 误差控制例 : 求积分 :y n = 1 x n 0 x+5dx, n = 0, 1

19 误差控制例 : 求积分 :y n = 1 x n 0 x+5dx, n = 0, 1 递推关系 :y n = 1 n 5y n 1

20 误差控制例 : 求积分 :y n = 1 0 递推关系 :y n = 1 n 5y n 1 三数位循环 : x n x+5dx, n = 0, 1 y 0 = ln 6 ln y 1 = 1 5y y 2 = 0.5 5y y 3 = y (> y 2!) y 4 = y (< 0!!)

21 误差传播绝对误差考虑 y = f (x 1, x 2, x 3,..., x n ), 如果 ɛ i 是 x i 的绝对误差, y 的绝对误差?

22 误差传播绝对误差考虑 y = f (x 1, x 2, x 3,..., x n ), 如果 ɛ i 是 x i 的绝对误差, y 的绝对误差? 单变量 : y = f (x) 回忆 Taylor 展开 f (x + ɛ x ) = f (x) + f (x)ɛ x + ɛ2 x 2! f (x) + + ɛn x n! f (n) (x) + R n, 其中 R n = ɛn+1 x (n+1)! f (ξ i ), 因此 ɛ y = ɛ x f, 当 ɛ x 1

23 误差传播绝对误差考虑 y = f (x 1, x 2, x 3,..., x n ), 如果 ɛ i 是 x i 的绝对误差, y 的绝对误差? 单变量 : y = f (x) 回忆 Taylor 展开 f (x + ɛ x ) = f (x) + f (x)ɛ x + ɛ2 x 2! f (x) + + ɛn x n! f (n) (x) + R n, 其中 R n = 多变量 : 当 ɛ i 1,ɛ y n ɛn+1 x (n+1)! f (ξ i ), 因此 ɛ y = ɛ x f, 当 ɛ x 1 f (x 1,x 2,x 3,...,x n) i=1 x i ɛ i.

24 误差传播相对误差乘法 : y = x 1 x 2, ɛ y y 2 i=1 ɛ x x i.

25 误差传播相对误差乘法 : y = x 1 x 2, ɛ y y 2 i=1 更一般的情形 : y = x m 1 1 x m 2 2 x mn n, ɛ y y n i=1 ɛ x x i. m i ɛ i x i.

26 误差传播条件数 (condition number) 数学问题的条件 (condition): 问题对于输入值的敏感程度数值算法不稳定 (unstable): 如果输入值的误差被数值算法放大考虑 x and f (x), 相对条件数 ( the relative condition number ) : f (x) 和 x 相对误差的比值

27 误差传播条件数 (condition number) 数学问题的条件 (condition): 问题对于输入值的敏感程度数值算法不稳定 (unstable): 如果输入值的误差被数值算法放大考虑 x and f (x), 相对条件数 ( the relative condition number ) : f (x) 和 x 相对误差的比值 κ = α f α x = f (x(1+α x )) f (x) f (x) α x xf (x) f (x).

28 误差传播条件数 (condition number) 数学问题的条件 (condition): 问题对于输入值的敏感程度数值算法不稳定 (unstable): 如果输入值的误差被数值算法放大考虑 x and f (x), 相对条件数 ( the relative condition number ) : f (x) 和 x 相对误差的比值 κ = α f α x = f (x(1+α x )) f (x) f (x) α x xf (x) f (x). 当 κ 1, 则称问题是病态的 (ill-conditioned)

29 误差传播例 : f (x) = x x + 200; x = 100,

30 误差传播例 : f (x) = x x + 200; x = 100, κ f = = , 问题是良态的 (well-conditioned)

31 误差传播例 : f (x) = x x + 200; x = 100, κ f = = , 问题是良态的 (well-conditioned) f (x) = x x, x = 100 κ f = 1.0

32 误差传播算法条件数 (condition number) f (x) = x x, 假设四位十进制计算机

33 误差传播算法条件数 (condition number) f (x) = x x, 假设四位十进制计算机 ˆf ( ) = = ( ) = 0,

34 误差传播算法条件数 (condition number) f (x) = x x, 假设四位十进制计算机 ˆf ( ) = = ( ) = 0, α f = 1 α x = ˆx x x t κ A = α f α x 2000.

35 误差传播算法条件数 (condition number) κ A 称为算法条件数由于数位表示的原因,κ A 可能会大于问题本身的条件数 κ f

36 误差传播算法条件数 (condition number) κ A 称为算法条件数由于数位表示的原因,κ A 可能会大于问题本身的条件数 κ f 解决办法 : 提高计算精度重写算法 f (x) = 1 x x, ˆf ( ) = = κ A 0 1.

Microsoft PowerPoint - STU_EC_Ch02.ppt

Microsoft PowerPoint - STU_EC_Ch02.ppt 樹德科技大學資訊工程系 Chapter 2: Number Systems Operations and Codes Shi-Huang Chen Sept. 2010 1 Chapter Outline 2.1 Decimal Numbers 2.2 Binary Numbers 2.3 Decimal-to-Binary Conversion 2.4 Binary Arithmetic 2.5

数值代数 夏银华 中国科学技术大学

数值代数夏银华中国科学技术大学