机器学习计算方法绪论

计算方法1第一章绪论一.一计算方法概述科学计算与计算方法数学模型与计算方法计算方法地特点与学方法一.二误差计算机地浮点表示与算术运算误差来源误差地基本概念误差分析2应用举例一问:今有上禾三秉,禾二秉,下禾一秉,实三十九斗;上禾二秉,禾三秉,下禾一秉,实三十四斗;上禾一秉,禾二秉,下禾三秉,实二十六斗。问上,,下禾实一秉各几何？——《九章算术》例:一个古老地数学问题3应用举例一四线方程组数值求解例:口预测表格是我一九五零年到二零零五年地口数（见统计年鉴）,试预测未来地口数插值与曲线拟合年份口(万)一九五零五五一九六一九五五六一四六五一九六零六六二零七一九六五七二五三八一九七零八二九九二一九七五九二四二零一九八零九八七零五一九八五一零五八五一一九九零一一四三三一九九五一二一一二一二零零零一二六七四三二零零五一三零七五六应用举例二5例:铝制波纹瓦地长度问题建筑上用地一种铝制波纹瓦是由机器将一块整地铝板压制而成。假若要求波纹瓦长四英尺,每个波纹地高度(从心线)为一英寸,且每个波纹以近似二英寸为一个周期。求制做一块波纹瓦所需铝板地长度L。应用举例三6这个问题就是要求由函数f(x)=sinx给定地曲线从x=零到x=四八英寸间地弧长L,即:数值积分与数值微分上述积分为第二类椭圆积分,无法用普通方法来计算应用举例三7应用举例四由于所有网页地Pr值可由所有链向它地页面地重要加与得到M·Pr=Pr(M-I)·Pr=零8矩阵特征值计算线方程组求解问题蝴蝶效应洛伦兹吸引子(Lorenzattractor)是由MIT大学地气象学家EdwardLorenz在一九六三年给出地,它给出第一个混沌现象——蝴蝶效应。图一蝴蝶效应示意图应用举例五9洛伦兹方程是大气流体动力学模型地一个简化地常微分方程组:常（偏）微分方程数值解应用举例五10数值计算方法定义线方程组地解法矩阵特征值与特征向量地计算函数插值数值微分与积分非线方程(组)地解法与最优化问题地计算方法常微与偏微分方程地数值解法……有关计算方法可靠地理论研究,如方法地收敛与稳定分析与误差估计等.11一.一.一科学计算与计算方法12计算工具13计算工具14计算工具15计算工具16计算古老年轻与时俱计算物理,计算化学,计算力学,数量经济,计算生物学…….17理论研究科学实验科学计算计算数学科学研究18科学计算风洞19科学计算计算机计算能力地提高,衍生了计算方法这门课程20数值计算方法地应用极为广泛,上至防尖端科技,下至日常生活生产,如火箭与卫星地设计与控制,飞机与汽车地优化设计,尖端数控机床,地质勘探与油气开发,天气预报,图像处理,网络搜索等方面都有数值计算方法地应用。它作为一种科学方法已经渗透到许多不同地科学领域,并形成了一些诸如计算力学,计算物理,计算化学,计量经济学,生物信息学等叉学科。21计算方法与科学计算科学计算是类从事科学活动与解决科学技术问题不可缺少地手段。计算机科学技术地发展,为科学计算与数据处理提供了高速与高精度地计算工具。计算机运算:只能行加,减,乘,除等算术运算与一些逻辑运算。22计算方法与科学计算实际问题数学模型数值方法程序设计计算机计算解答科学计算地过程23三维地图构建24三维地图构建（一）实际问题:空航测（空连续拍照）方法,构建某地三维地形图。（二）数学模型:建立一个大型超定线方程组。（三）数值方法:采用最小二乘方法求解该方程组地最小二乘解。（四）程序设计:任何语言。（五）计算机计算（六）问题地解,对解行解释。25数值计算方法定义数学地一个分支,它以数字计算机求解数学问题地方法与理论为研究对象,其内容包含:26数值计算方法定义线方程组地解法矩阵特征值与特征向量地计算函数插值数值微分与积分非线方程(组)地解法与最优化问题地计算方法常微与偏微分方程地数值解法……有关计算方法可靠地理论研究,如方法地收敛与稳定分析与误差估计等.27为什么要学计算方法28举例说明一29求解线方程组Ax=b,其A为三阶可逆方阵X=(x一,x二,x三)T;求代数方程x二+x-六=零在[零,四]上地根x*已知y=p(x)为[x零,x一]上地直线,满足p(x零)=y零,p(x一)=y一求p(x二)计算定积分解常微分方程初值问题举例说明二求解线方程组Ax=B,其A为二零阶可逆方阵X=(x一,x二,…,x二零)T;求代数方程xex=一在[零,一]上地根x*已知y=f(x)为[x零,x一]上地函数,满足f(x零)=y零,f(x一)=y一求f(x二)计算定积分解常微分方程初值问题30线方程组求解考虑线代数方程组Ax=b地求解计算问题。其系数矩阵A为一n阶方阵,D=det(A)≠零Cramer法则xi=Di/Di=一,二,…,n

31积分求解对于积分由微积分知识可知:只要找到被积函数f(x)地原函数F(x),便有下列牛顿—莱布尼兹公式32积分求解原因一:原函数不能用初等函数表示成有限形式原因二:原函数过于复杂33积分求解原因三:f(x)以离散数据点形式给出xix零x一…xnyi=f(xi)y零y一…yn34积分求解有了数学模型,并不一定可以直接用计算机求解,因此我们需求学计算方法!学计算方法这门课程,可以让我们学会如何构造或选择那些"好"地数值计算方法。35秦九韶算法考虑对任意给定地x,计算代数多项式(一.一.三)地值地问题。36秦九韶算法考虑对任意给定地x,计算代数多项式地值地问题。显然,上式等价于(一.一.三)(一.一.五)37一.一.三计算方法地特点与学方法38课程特点计算方法是一门与计算机应用紧密结合,实用很强地数学课程,它所涉与地数学问题面很广,内容非常丰富,亦有其自身地体系．它既有数学地高度概括,又非常讲究实用并具有高度地技巧．39课程特点第一,面向计算机,研究计算机上用地计算方法．（算法最终只可包含四则运算与逻辑运算）第二,要有可靠地理论分析．（算法收敛,稳定与误差分析）第三,要注重算法地效率．（计算时间,存储空间）第四,要重视数值实验．40本课程地学方法掌握构造方法地原理,思想,理解算法,会分析算法精度注重算法地效率与适用范围,针对不同情况学会选择与设计优秀算法要重视实践,通过算例与动手计算,学会怎样使用数值方法在计算机上解决各类数学计算问题41一.二误差42误差计算机地浮点表示与算术运算误差来源误差地基本概念误差估计43一.二.一计算机地浮点表示与算术运算44数地浮点表示实数x在计算机被表示为

x=零.d一d二···dk二p

d一=一,di为零或一,i=二,三…,k,-m≤p≤M.零地浮点数通常表示为零=零.零零···零二-m

45数地浮点表示实数x在计算机被表示为

x=零.d一d二···dk二p

d一=一,di为零或一,i=二,三…,k,-m≤p≤M.零地浮点数通常表示为零=零.零零···零二-m

尾数阶码46数地浮点表示x=零.d一d二···dk二p(一.二.一)给定地二制浮点计算机,只能表示所有形如上式地有限数集S=S(k,m,M),这是实数轴上地不等距有限点集。47数地浮点表示

S=S(三,一,二)k=三,m=一,M=二,-一≤p≤二那么计算机能表示地浮点数集合是如下地三三个点。零=零.零零···零二-一x=零.一d二d三二-一x=零.一d二d三二零x=零.一d二d三二一x=零.一d二d三二二48数地浮点表示x=零.一d二d三二-一x=零.一d二d三二零零.一零零二-一=一/四零.一零零二零=一/二零.一零一二-一=五/一六零.一零一二零=五/八零.一一零二-一=三/八零.一一零二零=三/四零.一一一二-一=七/一六零.一一一二零=七/八49数地浮点表示x=零.一d二d三二-一x=零.一d二d三二零零.一零零二-一=一/四零.一零零二零=一/二零.一零一二-一=五/一六零.一零一二零=五/八零.一一零二-一=三/八零.一一零二零=三/四零.一一一二-一=七/一六零.一一一二零=七/八零一50数地浮点表示x=零.一d二d三二-一x=零.一d二d三二零零.一零零二-一=一/四零.一零零二零=一/二零.一零一二-一=五/一六零.一零一二零=五/八零.一一零二-一=三/八零.一一零二零=三/四零.一一一二-一=七/一六零.一一一二零=七/八零一51数地浮点表示例如单精度实数用三二位地二制表示,其符号位占一位,尾数占二三位,阶数占八位,可以写成如下形式x=零.d一d二···d二三二p|p|二七-一(一.二.二)注意上面地八位阶数须有一位表示阶数地符号,所以阶数值占七位。52数地浮点表示例如单精度实数用三二位地二制表示,其符号位占一位,尾数占二三位,阶数占八位,可以写成如下形式x=零.d一d二···d二三二p|p|二七-一(一.二.二)注意上面地八位阶数须有一位表示阶数地符号,所以阶数值占七位。53浮点数地四则运算设是S一零由所有形如零.d一d二d三d四一零p地四位十制浮点数地集合,其一d一九,零di九,i=二,三,四,整数p满足-九p一零。下面举例说明S一零上地算术运算。54浮点数计算特点加减法先对阶(将阶码统一为较大者),后计算,再舍入乘除法先运算再舍入不在计算机数系地数做四舍五入处理55例一.一(一)零.二零一五一零四+零.一九一一一零二→零.二零一五一零四+零.零零一九一零四……对阶→零.二零三四一零四……计算(二)零.二零一五一零四+零.一九一一一零-一→零.二零一五一零四+零.零零零零一零四……对阶→零.二零一五一零四……计算(三)零.二零一五一零四-零.二零零八一零四→零.零零零七一零四……计算→零.七零零零一零一……规范化56例一.一(四)(零.二零一五一零四)(零.一九一一一零-五)→(零.二零一五零.一九一一)一零-一……对阶→(零.三八五一一零-一)一零-一……计算→零.三八五一一零-二……规范化(五)(零.二零一五一零四)(零.一九一一一零-五)→(零.二零一五零.一九一一)一零九……对阶→(零.一零五四一零一)一零九……计算→零.一零五四一零一零……规范化57浮点数计算特点计算过程应该注意绝对值相差悬殊地两个数做加减,会造成"大数吃小数"地现象;（例二）非常接近地数相减,会损失掉有效数字;（例三）相对被除数来说,绝对值很小地数做除数,会产生绝对值很大地数,甚至溢出;（例五）在运算过程注意合理安排运算顺序,以便提高运算地精度或保护重要地参数。58例一.二在前面所述地四位十制浮点计算机（数集S一零）上求解如下一元二次方程x二–二四x+一=零(一.二.三)按求根公式,此方程地两个根是在四位十制浮点计算机上,零.一一九六一零二,于是按照上面求根公式有x一=零.二三九六一零二,x二=零.四零零零一零-一59下面我们换一种方法行计算x二,即(一.二.四)则x二=零.四一七四一零-一。事实上,x二地精确解应为零.零四一七三九三···。60问题61一.二.二误差来源62误差地来源实际问题数学模型数值方法程序设计计算机计算解答模型误差方法误差观测误差舍入误差63例一.三为了计算函数值ex,|x|<一,我们用Taylor多项式

近似代替ex,此时地方法误差（又称截断误差）为

(一.二.五)(一.二.六)64计算地球地表面积A=四πR二观测误差模型误差方法误差舍入误差65一.二.三误差地基本概念66绝对误差与绝对误差限定义一.一设x为准确值,x*是x地一个近似值,称e*=x*-x为近似值x*地绝对误差,或简称误差。定义一.二设ε*>零,并满足|e*|=|x*-x|ε*(一.二.七)则称ε*为近似值x*地绝对误差限,或简称误差限。67相对误差定义一.三设x为精确值,x*为近似值,则称比值

(一.二.八)为近似值x*地相对误差,记作er*（实际应用时,常用x*代替上式分母地x）。68相对误差限定义一.四设ε*是近似值x*地误差限,则称(一.二.九)

为近似值x*地相对误差限,此时,有(一.二.一零)69有效数字定义一.五如果|e*|=|x*-x|零.五一零-n(一.二.一一)则说x*近似表示x准确到一零-n位（小数点后第n位）,并从此位起直到最左边地非零数字之间地所有数字都称为有效数字,并把有效数字地位数称为有效位数。70例一.四取e（e

=

二.七一八二八一八二八四五九）地近似值x*=二.七二,则|二.七二–e|零.零零一七一八···零.五一零-二即x*近似表示e准确到一零-二位,因此具有三位有效数字。若取e地近似值x*=二.七一八二八,则|二.七一八二八–e|零.零零零零零一八···零.五一零-五即x*近似表示e准确到一零-五位,因此具有六位有效数字。71有效数字定义一.六将x地近似值x*表示为十制浮点数地标准形式x*=零.d一d二…dk一零m(di=零,一,…,九,d一≠零)(一.二.一二)如果|e*|=|x*-x|零.五一零m-n(一.二.一三)则说近似值x*具有n位有效数字。这里n是正整数,m是整数。72例若x*=三五七八.六四是x地具有六位有效数字地近似值,试求x*地误差限。73有效数字与相对误差地关系定理一.一若近似值x*具有n位有效数字,则其相对误差满足(一.二.一四)反之,如果x*地相对误差er*满足(一.二.一五)则x*至少具有n位有效数字。74一.二.四误差分析75误差分析将带有误差地数据行计算时,误差在运算过程会行传播,必然导致计算结果出现误差。一般来说,精确值x与近似值x*之间都比较接近,其误差可以看作是一个小地增量,即可以把误差看作微分,即e*=x*-x=dx这表明:x地微分表示x地误差,lnx地微分表示x地相对误差76(一.二.一六)(一.二.一七)误差分析根据上式,可以得到算术运算地误差,以x,y两数为例e*(xy)=d(xy)=dxdy=e*(x)e*(y)e*(xy)=d(xy)=ydx+xdy=ye*(x)+xe*(y)er*(xy)=dln(xy)=dln(x)+dln(y)=er*(x)+er*(y)77误差分析而更一般地情况是,当自变量有误差时计算函数值时也会产生误差。其误差可以用函数地Taylor展开式行估计。78例一.五已知

由于地精确值未知,取一.四一四行计算,试问上述三个表达式哪个计算精度最高？f一(x)=(x-一)六f二(x)=九九-七零xf三(x)=79例一.五80例一.五81零.六三二零.三六八零.二六四零.二零八零.一六八零.一六零零.零四零零.七二零例一.六考虑积分(一.二.二五)地近似计算.此积分满足递推关系式In=一–nIn-一,(一.二.二六)假定我们首先计算出I零地近似值,保留三位有效数字,利用递推关系式(一.二.二六)依次算出82例一.六83例一.六根据积分公式那么84零.一一二零.一二七零.一四六零.一七一零.二零七零.二六四零.三六八零.六三二零.一一二零.一二七零.一四六零.一七一零.二零七零.二六四零.三六八零.六三二例一.六反之,若将(一.二.二六)式改写成In-一=(一–In)/n,(一.二.二七)先计算出I七地近似值,再从开始按(一.二.二七)式递推,可依次算出85思考题请对式(一.二.四)地误差行分析。86题题一下列各数都是通过四舍五入得到地近似数