数据分析与算法设计11-组合数学、数值分析20161213

数据分析与算法设计 数据分析与算法设计 组合数学 数值分析组合数学 数值分析 信电学院信电学院王梁昊王梁昊副研究员副研究员 wanglianghao645840 浙江大学玉泉校区信电楼浙江大学玉泉校区信电楼505室室 主要内容主要内容 组合组合数学数学 1 生成组合对象的算法 减治法 生成组合对象的算法 减治法 4 3 数值分析数值分析 1 大整数乘法大整数乘法和矩阵和矩阵乘法 分治法 乘法 分治法 5 4 2 解线性方程组 矩阵求逆和行列式 高斯 解线性方程组 矩阵求逆和行列式 高斯消消 去去法 法 变治法 变治法 6 2 3 多项式求值 多项式求值 霍纳法则和二进制幂霍纳法则和二进制幂 变治 变治 法 法 6 5 4 截断误差和舍入误差 数值 截断误差和舍入误差 数值算法的算法的挑战 挑战 11 4 5 解 解非线性非线性方程 方程 12 4 主要内容主要内容 组合组合数学数学 1 生成组合对象的算法 减治法 生成组合对象的算法 减治法 4 3 数值分析数值分析 1 大整数乘法大整数乘法和矩阵和矩阵乘法 分治法 乘法 分治法 5 4 2 解线性方程组 矩阵求逆和行列式 高斯 解线性方程组 矩阵求逆和行列式 高斯消消 去去法 法 变治法 变治法 6 2 3 多项式求值 多项式求值 霍纳法则和二进制幂霍纳法则和二进制幂 变治 变治 法 法 6 5 4 截断误差和舍入误差 数值 截断误差和舍入误差 数值算法的算法的挑战 挑战 11 4 5 解 解非线性非线性方程 方程 12 4 5 减治法减治法 生成组合对象的算法生成组合对象的算法 生成排列生成排列 对于给定的多个元素 生成各种可能的排列 假设元素的下标为1 n 简化为下标的排列问题简化为下标的排列问题 介绍三种生成方法 1 插入法 2 Johnson Trotter 法 3 字典顺序法 5 减治法减治法 插入法生列排列 减一法减一法 生成 1 n 1 的排列 对每个排列 插 入n 得到 1 n 的排列 共有n个位置可插入 插入的顺序 从右到左 从左到右 从右到左 交替改变方向 好处 最小变化最小变化 相邻两个排列的变化 只需交换某只需交换某2个相邻元素个相邻元素 5 减治法减治法 Johnson Trotter 法生成排列 其实有的算法并不需要知道规模n 1的排列就 可以直接得到规模n的排列结果 Johnson Trotter 算法就是其中一种 利用这一算法求得的排列序 列还是相邻序列变化最小的一个序列集合 也就 是说下一个序列与上一个序列仅仅交换了两个元 素的位置 5 减治法减治法 Johnson Trotter 方法 在排列的每一分量上画一个箭头 移动元素移动元素 如果分量k 的箭头指向一个相邻的 较小元素 则该分量在排列中是移动的 5 减治法减治法 J T方法举例 例n 3 从123开始 符合最小变化要求符合最小变化要求 312 132 123 213 231 321 5 减治法减治法 字典顺序生成排列 尽管Johnson Trotter算法非常高效 但是似 乎不是那么直观 不太符合人们的思维习 惯 事实上比较自然的算法称为 字典排 序 字典排 序 lexicographic order 算法 算法 它是根 据单词在字典中的排列顺序得到的算法 5 减治法减治法 字典生成顺序举例 例n 3 在 1 2 3 中按字典顺序选择 123 132 213 231 312 321 生成子集生成子集 集合集合A的 幂集 以的 幂集 以A的所有子集为元素组成的集合 的所有子集为元素组成的集合 减 一 治技术减 一 治技术生成子集生成子集 5 减治法减治法 5 减治法减治法 位串法生成幂集位串法生成幂集 例n 3 元素为 a1 a2 a3 方法 每一个子集与一个每一个子集与一个3位二进制串位二进制串b1b2b3对应对应 ai属于 该子集时 bi 1 否则 bi 0 二进制串 000 001 010 011 100 101 110 111 对应子集 a3 a2 a2 a3 a1 a1 a3 a1 a2 a1 a2 a3 比特串的其他顺序 挤压序 最小变化 相邻比特串只变化一个比特 格雷码 主要内容主要内容 组合组合数学数学 1 生成组合对象的算法 减治法 生成组合对象的算法 减治法 4 3 数值分析数值分析 1 大整数乘法大整数乘法和矩阵和矩阵乘法 分治法 乘法 分治法 5 4 2 解线性方程组 矩阵求逆和行列式 高斯 解线性方程组 矩阵求逆和行列式 高斯消消 去去法 法 变治法 变治法 6 2 3 多项式求值 多项式求值 霍纳法则和二进制幂霍纳法则和二进制幂 变治 变治 法 法 6 5 4 截断误差和舍入误差 数值 截断误差和舍入误差 数值算法的算法的挑战 挑战 11 4 5 解 解非线性非线性方程 方程 12 4 4 分治法分治法 大整数乘法 两位数相乘的例子 1位乘法操作的次数为4 减少乘法操作的次数 公式表达 4 分治法分治法 n 位大整数乘法位大整数乘法 设A B为两个n位的大整数 直接计算需要执行n2 次1位数的乘法 A a110n 2 a2 B b110n 2 b2 直接计算 A B a110n 2 a2 b110n 2 b2 a1b110n a1b2 a2b1 10n 2 a2b2 乘法操作次数的递归公式为 M n 4M n 2 M 1 1 解得 M n O n2 4 分治法分治法 改进的乘法 A B a110n 2 a2 b110n 2 b2 a1b110n a1b2 a2b1 10n 2 a2b2 a1b110n a1 a2 b1 b2 a1b1 a2b2 10n 2 a2b2 验证 a1 a2 b1 b2 a1b1 a2b2 a1b2 a2b1 这种方法需要3次n 2位的乘法及一些加减法 4 分治法分治法 记M n 为计算两个n位整数相乘所需的1位乘法操 作次数 则有 4 分治法分治法 Strassen 矩阵乘法 矩阵乘法是线性代数中最常见的运算之一 它在 数值计算中有广泛的应用 若A和B是2个n n的 矩阵 则它们的乘积C A B同样是一个n n的 矩阵 A和B的乘积矩阵C中的元素C i j 定义为 依此定义来计算A和B的乘积矩阵C 则每计算C 的一个元素C i j 需要做n次乘法和n 1次加法 因此 求出矩阵C的n2个元素所需的计算时间为 O n3 V Strassen算法 1969 对两个2阶方阵相乘时 Strassen算法执行了7次乘法和18 次加减法 而蛮力算法需要执行8次乘法和4次加法 4 分治法分治法 4 分治法分治法 Strassen 矩阵乘法矩阵乘法 4 分治法分治法 加法运算次数加法运算次数 乘法运算次数的减少是以加法运算次数的增加为代价的 根据主定理 加法的增长次数与乘法是相同的 后续算法的效率 两个n阶实数矩阵的乘法 运行时间都属于O n 常数 越 来越小 Coopersmith and Winograd 1987 算法的效率 O n2 376 指数值的减小是以算法越来越复杂为代价的 由于乘法常量的值很大 这些算法都不太有实用的价值 学术价值在于逼近下限 学术价值在于逼近下限 n2 次乘法次乘法 4 分治法分治法 主要内容主要内容 组合组合数学数学 1 生成组合对象的算法 减治法 生成组合对象的算法 减治法 4 3 数值分析数值分析 1 大整数乘法大整数乘法和矩阵和矩阵乘法 分治法 乘法 分治法 5 4 2 解线性方程组 矩阵求逆和行列式 高斯 解线性方程组 矩阵求逆和行列式 高斯消消 去去法 法 变治法 变治法 6 2 3 多项式求值 多项式求值 霍纳法则和二进制幂霍纳法则和二进制幂 变治 变治 法 法 6 5 4 截断误差和舍入误差 数值 截断误差和舍入误差 数值算法的算法的挑战 挑战 11 4 5 解 解非线性非线性方程 方程 12 4 6 变治法变治法 6 2 Gauss消去法 科学计算中通常需要解多个变量的方程 组 这些方程组当中最简单的是线性方程组 也就是变量的次数均为1次的 求解线性方程的方法通常有利用高斯消 元的直接法以及迭代法 这里仅仅给出高斯 消元法解线性方程组的介绍 它还可以应用 于矩阵的求逆以及行列式的计算 6 变治法变治法 1 高斯消元法 一般的线性方程组是指如下形式的方程组 11 112211 21 122222 1 122 nn nn mmmnnm a xa xa xb a xa xa xb a xaxa xb 6 变治法变治法 高斯消元法 分消元过程和回代过程 消元过程 将原方程组变为上三角方程组 回代过程得到方 程组的解 6 变治法变治法 高斯消元法举例 0 54 12 321 321 321 xxx xxx xxx 2200 3330 1112 0 3330 1112 0111 5114 1112 2 23 2 1 2 1 2 3 2 13 122 rrrr rr 1 0 1 123 xxx 回代后得 6 变治法变治法 高斯消元法的伪代码 6 变治法变治法 改进 部分选主元法 6 变治法变治法 高斯消元法的效率分析 基本操作 乘法 执行次数 三重循环 6 变治法变治法 2 LU分解法 记原方程组为 A X b 若能将 A分解为下三角矩阵L与上三角矩阵U之积 A LU 则原方程组的求解转化为两个三角形方程组的求 解了 LY b 下三角方程组 UX Y 上三角方程组 6 变治法变治法 LU分解法 211100211 411210033 1111 21 21002 ALU 将A分解为 A LU 6 变治法变治法 LU分解法 0 5 2 1 322 1 12 1 21 1 yyy yy y 22 333 1 2 3 32 321 x xx xxx 与LY b UX Y对应的方程组如下 易得 y1 y2 y3 1 3 2 x1 x2 x3 1 0 1 6 变治法变治法 3 计算矩阵的逆 1112111121 2122221222 1212 100 010 001 nn nn nnnnnnnn aaaxxx aaaxxx aaaxxx 逆矩阵的定义 6 变治法变治法 计算矩阵的逆 求矩阵 A 的逆矩阵 转化为求解n个方程组 A Xj bj 其中 bj是单位矩阵 的第j列 而Xj 则是逆矩阵的第j列 100 010 001 6 变治法变治法 4 计算矩阵的行列式 n阶矩阵的行列式的计算由递归公式定义 其中 n 1时 det A a11 j为奇数 sj 1 j为偶数 sj 1 例 n 3的情形 1 1 detdet n jjj j As aA 6 变治法变治法 计算矩阵行列式 按照定义计算高阶行列式需要计算n 个项的和 可利用高斯消元法 矩阵矩阵A的行列式的行列式 消元后上三角矩阵的行列式消元后上三角矩阵的行列式 对角线上元素之乘积 对角线上元素之乘积 例如 上式中 det A 2 3 2 12 200 330 112 111 114 112 6 变治法变治法 基于矩阵行列式解方程组 克拉默法则 Cramer s rule 对n元线性方程组 当且仅当detA 0时 方程组有唯一解 其中其中Aj是把是把A的第的第j列用列列用列b替换后得到的矩阵替换后得到的矩阵 主要内容主要内容 组合组合数学数学 1 生成组合对象的算法 减治法 生成组合对象的算法 减治法 4 3 数值分析数值分析 1 大整数乘法大整数乘法和矩阵和矩阵乘法 分治法 乘法 分治法 5 4 2 解线性方程组 矩阵求逆和行列式 高斯 解线性方程组 矩阵求逆和行列式 高斯消消 去去法 法 变治法 变治法 6 2 3 多项式求值 多项式求值 霍纳法则和二进制幂霍纳法则和二进制幂 变治 变治 法 法 6 5 4 截断误差和舍入误差 数值 截断误差和舍入误差 数值算法的算法的挑战 挑战 11 4 5 解 解非线性非线性方程 方程 12 4 6 变治法变治法 6 5 Horner法则和二进制幂 6 5 1 Horner法则 南宋秦九韶算法13世纪 计算n次多项式的值的算法 6 变治法变治法 Horner法则计算实例 6 变治法变治法 6 5 2 二进制幂二进制幂 从左至右算法 6 变治法变治法 从左至右算法 总的乘法次数 6 变治法变治法 从右至左算法 主要内容主要内容 组合组合数学数学 1 生成组合对象的算法 减治法 生成组合对象的算法 减治法 4 3 数值分析数值分析 1 大整数乘法大整数乘法和矩阵和矩阵乘法 分治法 乘法 分治法 5 4 2 解线性方程组 矩阵求逆和行列式 高斯 解线性方程组 矩阵求逆和行列式 高斯消消 去去法 法 变治法 变治法 6 2 3 多项式求值 多项式求值 霍纳法则和二进制幂霍纳法则和二进制幂 变治 变治 法 法 6 5 4 截断误差和舍入误差 数值 截断误差和舍入误差 数值算法的算法的挑战 挑战 11 4 5 解 解非线性非线性方程 方程 12 4 11 4 数值算法的挑战数值算法的挑战 数值算法数值算法常常被描述为计算机科学的一个分支 它关心的 是那些求解 连续 数学问题 连续 数学问题的算法 离散数学 图 树 排列 组合等 连续 数学 解方程 方程组 求函数值 求积分等 假设建模问题已经解决了 我们在求解一个数学问题时面 对的主要障碍是什么呢 首先的障碍就是大多数数值分析问题大多数数值分析问题无法精确求解这 样一个事实 这些问题必须近似求解必须近似求解 而我们通常的 做法是用有限逼近有限逼近来代替一个无穷对象 11 算法能力的极限算法能力的极限 例 例 计算ex在给定点x的值 方法是通过泰勒序列前面若干项 的有限和来逼近无穷泰勒序列在x0 0的值 我们把它称为 第n次泰勒多项式 这种逼近所造成的误差被称为截断误差截断误差 数值分析中的一 个主要任务就是估计截断误差的数量级 一般的做法是使 用微积分工具 其中 在以0和x为端点的区间上 M max e 11 算法能力的极限算法能力的极限 例 例 函数的定积分可以用函数值的有限加权和来逼近 这被 称为组合梯形法则组合梯形法则 11 算法能力的极限算法能力的极限 其截断误差为 11 算法能力的极限算法能力的极限 另一种类型的误差被称为舍入误差舍入误差 因为一台数字计算机只能够 表示实数的有限精度 不仅所有的无理数 根据定义 为了精确 表示这种数字 需要无限位数 会出现这种误差 许多有理数也 会有这样的误差 在绝大多数情况下 实数被表示成浮点数 其中 B是数字的基数是数字的基数 一般是2或者16 或者对于简单的计算器 来说 是10 这些数字 对于i 1 2 p来说 0 di B 并且 除非该实数为0 否则的话 d1 0 合起来表示浮点数的小数部分 被换为数值部分数值部分 E是一个整数指数 它的取值范围基本上是0 点对称的 浮点表示法的精度取决于有效数字有效数字的位数p 大多数的计算机支 持两到三种精度级别 单精度单精度 一般来说相对6位到7位十进制有 效数字 双精度双精度 13到14位十进制有效数字 以及扩展精度扩展精度 19到20位十进制有效数字 12 E p d dd B 11 算法能力的极限算法能力的极限 11 算法能力的极限算法能力的极限 误差的定义误差的定义 用近似值 表示一个数 时的绝对误差绝对误差和相对误差相对误差 绝对误差 相对误差 浮点运算中的溢出现象 上溢 上溢 overflow 当一个算术操作产生了一个超出了 计算机浮点数上限的结果 就会发生一个上溢上溢 典型的 上溢上溢会发生在两个非常大的数字相乘或者除以一个非常 小的除数时 下溢 下溢 underflow 如果一个操作结果的数量级过小 以至于无法表示为一个非0的数值部分时 就会发生一个 下溢下溢 通常 下溢的数字会用0来表示 但硬件上会产生 一个特殊的信号 告诉我们发生了这样一个事件 11 算法能力的极限算法能力的极限 计算机执行的算术操作也会加重误差算术操作也会加重误差 比如两个基本相等的浮点 数相减会导致相对误差大大增加 这个现象被称为减法抵消减法抵消 例 例 考 虑 两 个 无 理 数 3 14159265 和 6 10 7 3 14159205 分 别 用 浮 点 数 0 3141593 101和 0 3141592 101来近似表示 这两个近似数的相对误差并不大 分别是 用浮点表示法 表示 所造成的相对误差为 尽管 和 都是相当精确的逼近 但2 3这个值对于相对误差来说 还是非常大的 7 0 00000034 10 3 7 7 0 00000051 10 6 103 67 7 106 102 6 103 11 算法能力的极限算法能力的极限 某些算法操作中的舍入误差在传递时会递增效应 称为不稳定性不稳定性 有些问题对于输入显示出很高的敏感度 称为坏脾气坏脾气的 病态性病态性 例 例 考虑二元线性方程组 惟一解是x 1 y 1 考虑右边值有轻微差别的方程组 惟一解是x 2 y 0 系数矩阵接近于退化矩阵 系数的微小改变都有可能产生一个要么无 解要么有无穷多解的方程组 这依赖于它等号右边的那些值 1 0010 9992 0 9991 0012 xy xy 1 0010 9992 002 0 9991 0011 998 xy xy 11 算法能力的极限算法能力的极限 例 例 求二次方程根的问题 其中系数 a b c为任意实数 a 0 当且仅当方程的 判定式 b2 4ac大于等于0时 方程有实根 而且方程 根可以用下面这个公式求出 尽管公式为数学家所关心的问题给出了一个通解 但 它远远不是算法设计师所需要的通解 2 0axbxc 2 1 2 4 2 bbac x a 11 算法能力的极限算法能力的极限 第一个主要障碍就是如何求平方根如何求平方根 即使对于大多数整数D来说 也 是一个只能近似计算的无理数 可以用牛顿法牛顿法近似计算平方根 生成一个给定的非负数D的平方根的一个近似值序列 而初始的近似 值可以选择为x0 1 D 2 在两种情况下 可以停止生成该序列的元素 要么当序列中两个连续 元素的差小于一个预定义的允许误差 0 即 要么x2n 1足够接近于D 对于D的大多数值来说 逼近序列非常快速地 收敛 具体来说 我们可证明在0 25 D0的话 计算出 来的根就会出现较大的相对误差 例 例 考虑下面这个方程 它真正的根保留11位有效数字之后 等于 和 2 4bac 25 1010 xx 1 99999 999990 x 2 0 000010000000001x 11 算法能力的极限算法能力的极限 用求根公式并取7位十进制有效数字参与所有的浮点数运算 我们 会得到 尽管用x1逼近x1 的相对误差非常小 但第二个根的相对误差是 非常大的 也就是100 2 11 0 1000000 10b 1 40 4000000 10ac 11 0 1000000 10 6 0 1000000 10 6 1 0 1000000 10 2 b x a 2 0 2 b x a 22 2 1 xx x 11 算法能力的极限算法能力的极限 为了避免可能产生较大的相对误差 我们可以改用另一种公式 这个公式是这样求得的 如果b 0的话 我们不用担心分母出现减法抵消的危险 至于x2 则可以用标准公式 来计算 也没有减法抵消的危险 当然b也必须大于0 在在b 0的情况下的情况下 结果是对称的 我们可以分别使用公式 22 2 1 2 44 4 2 24 bbacbbac bbac x a abbac 2 2 4 c bbac 2 2 4 2 bbac x a 2 12 2 42 2 4 bbacc xx a bbac 和 11 算法能力的极限算法能力的极限 主要内容主要内容 组合组合数学数学 1 生成组合对象的算法 减治法 生成组合对象的算法 减治法 4 3 数值分析数值分析 1 大整数乘法大整数乘法和矩阵和矩阵乘法 分治法 乘法 分治法 5 4 2 解线性方程组 矩阵求逆和行列式 高斯 解线性方程组 矩阵求逆和行列式 高斯消消 去去法 法 变治法 变治法 6 2 3 多项式求值 多项式求值 霍纳法则和二进制幂霍纳法则和二进制幂 变治 变治 法 法 6 5 4 截断误差和舍入误差 数值 截断误差和舍入误差 数值算法的算法的挑战 挑战 11 4 5 解 解非线性非线性方程 方程 12 4 12 4 解非线性方程的算法解非线性方程的算法 12 超越算法能力的极限超越算法能力的极限 Numerical algorithms concern with solving mathematical problems such as evaluating functions e g x ex ln x sin x solving nonlinear equations finding extrema of functions computing definite integrals Most such problems are of continuous nature and can be solved only approximately Principal Accuracy Metrics 12 超越算法能力的极限超越算法能力的极限 Absolute error of approximation of by Relative error of approximation of by undefined for 0 often quoted in Two Types of Errors 12 超越算法能力的极限超越算法能力的极限 truncation errors Taylor s polynomial approximation ex 1 x x2 2 xn n absolute error M x n 1 n 1 where M max et for 0 t x composite trapezoidal rule f x dx h 2 f a 2 1 i n 1 f xi f b h b a n absolute error b a h2 M2 12 where M2 max f x for a x b round off errors Solving Quadratic Equation 12 超越算法能力的极限超越算法能力的极限 Quadratic equation ax2 bx c 0 a 0 x1 2 b D 2a where D b2 4ac Problems computing square root use Newton s method xn 1 0 5 xn D xn subtractive cancellation use alternative formulas use double precision for D b2 4ac other problems overflow etc Notes on Solving Nonlinear Equations 12 超越算法能力的极限超越算法能力的极限 There exist no formulas with arithmetic ops and root extractions for roots of polynomials anxn an 1xn 1 a0 0 of degree n 5 Although there exist special methods for approximating roots of polynomials one can also use general methods for f x 0 Nonlinear equation f x 0 can have one many infinitely many and no roots at all Useful sketch graph of f x separate roots Three Classic Methods 12 超越算法能力的极限超越算法能力的极限 Three classic methods for solving nonlinear equation f x 0 in one unknown bisection method method of false position regula falsi Newton s method Bisection Method 12 超越算法能力的极限超越算法能力的极限 Based on Theorem If f x is continuous on a x b and f a and f b have opposite signs then f x 0 has a root on a x b binary search idea Approximations xn are middle points of shrinking segments x