大数据计算方法 课件 chap1-绪论

1大数据计算方法Chap1：绪论主要内容1.绪论

(误差分析/Matlab基础/浮点算术体系)2.数据分析方法概述(数据分析的基本概念与模型的评价方法)3.线性方程组求解与矩阵分解(LU/Cholesky分解/QR分解与最小二乘)4.大型稀疏线性方程组求解(稀疏矩阵/直接解法/CG/GMRES算法)5.矩阵的特征值与奇异值(QR算法/Krylov子空间迭代法/SVD算法)6.优化问题与凸优化

(优化问题基础/凸优化/举例:几何优化)7.数据分析中的凸优化(最大间隔分类/正则化回归/压缩感知)8.非线性方程与无约束优化(牛顿法/简单方法/基于求导的方法)9.约束优化问题解法与对偶原理

(等式约束/不等式约束/对偶原理)10.基于矩阵分解的数据挖掘(PCA及应用/随机化算法/非负矩阵分解)大数据计算方法2主要借助Matlab学习(也涉及Python)Matlab的替代引言Matlab与数值计算软件浮点算术体系与误差分析Outline3引言概览“十大算法”问题、以及求解步骤误差分析基本概念回顾41950年之前算法线性插值牛顿法高斯消去法工具手算数学手册数据表格数值计算的历史51950年代之后现代计算机的发明催生了大量

新的数值计算方法/算法数值计算的历史6数值计算：主要研究求解连续数学问题的算法（其中包含、但不局限于计算误差的研究）Evolutionofnumericalcomputingfromothersciencesandengineeringdisciplines数值计算是求解很多实际工程问题的重要工具数值计算8PageRank算法对1010x1010、甚至更大的矩阵计算其特征向量——世界上最大规模的矩阵计算航空公司使用优化算法来确定机票

价格、航班调度和航油供应更多现实世界的例子数值计算9汽车公司通过对汽车碰撞的计算机模拟来发现潜在的安全隐患金融公司通过统计仿真工具来预测股票价格常微分方程(Ordinarydifferentialequation,ODE)电路的瞬态分析(transientanalysis)数值计算问题举例10

...代数方程偏微分方程(Partialdifferentialequation,PDE)热分析(thermalanalysis)：求温度分布数值计算问题举例11比重比热容热导率热源的功率密度热流(单位面积热通量)温度发热功率密度(傅里叶热传导定律)线性回归(Linearregression)也称为响应面建模(responsesurfacemodeling)数值计算问题举例12求解超定线性方程组来得到参数a和b(方程数目比变量多)带正则项/约束的线性回归(regularization)数值计算问题举例13最小二乘误差L1-范数正则项原始图片上采样

恢复出的图片分类问题(Classification)最大间隔分类-支撑向量机(SVM)方法数值计算问题举例14求解凸二次规划得到W和CL2-范数(最大间隔)WenjianYu1515JackDongarra获2021年图灵奖主要源于其在数值算法和库方面的开创性贡献，正是他的研究使高性能计算软件在四十多年里与硬件的指数级改进保持同步。Toptenalgorithmsofthecentury1.1946LosAlamos国家实验室的J.vonNeumann,S.Ulam和N.Metropolis发展出来的Metropolis算法

（属于MonteCarlo方法；拒绝采样/MCMC,生成给定概率分布随机点)2.1947RAND公司的G.Dantzig创造的解线性规划的单纯型算法(simplexmethod)3.1950UCLA与美国国家标准局数值分析所的M.Hestenes,E.Stiefel和C.

Lanczos开创的Krylov子空间迭代法(CG算法，Lanczos过程)4.1950’s矩阵分解方法,由OakRidge国家实验室的A.Householder引入数值线性代数中(矩阵计算研究中掀起革命)“Wetriedtoassemblethe10algorithmswiththegreatestinfluenceonthedevelopmentandpracticeofscienceandengineeringinthe20thcentury”Editors16通用性,统一,reuse,舍入误差分析,updating,软件开发Toptenalgorithmsofthecentury5.1957IBM的J.

Backus领导的小组开发的Fortran优化编译器6.1959-61

伦敦FerrantiLtd.的J.G.F.Francis发明的QR算法，稳定地计算中、小规模矩阵的所有特征值7.1962伦敦ElliottBrothers,

Ltd.的TonyHoare提出快速排序算法(Quicksort)8.1965IBMWatson研究中心的J.Cooley与Princeton大学及AT&TBell实验室的J.Tukey共同提出了的FFT算法9.1977BrighamYoung大学的H.

Ferguson和R.Forcade提出的整数关系侦察算法(实验数学,简化量子场理论的计算)10.1987Yale大学的L.Greengard和V.

Rokhlin发明了快速多极算法(fastmultipolealgorithm,多体问题,线性复杂度)大多数都属于或涉及数值计算的范畴!17Newton/quasi-Newton法(QZ/关于Schur,SVD)PagerankJPEGKalmanfilterN.Higham,ThePrincetonCompaniontoAppliedMathematics,PrincetonUniversityPress,2015数值模拟的步骤建立数学模型（需要相关学科背景）研究数值求解方程或最优化的算法通过计算机程序(软件)实现算法在计算机上运行程序(软件),进行数值实验数值计算的问题与步骤数值计算（科学计算、计算模拟、数值模拟）没有解析解的问题：虽有解析表达式(解)，但无法(难以)计算:模拟通常难以达到的实验条件(时间、金钱成本)天体物理研究汽车碰撞实验，芯片流片(制造)前的性能仿真除了解方程的问题，还有更多的优化问题18sin(x)

数值计算的问题数值模拟的步骤（续）将计算结果用较直观的方式输出，如图形可视化方法解释和验证计算结果。若需要，重复上面的某些步骤上述各步骤相互间紧密地关联，影响着最终的计算结果和效率（问题的实际应用背景也左右着方法的选择）重视计算中的扰动原始数据、参数的扰动计算过程中的扰动扰动可能遵循一定的规律19它们对结果如何影响？(UncertaintyQuantification)(Round-offErrorAnalysis)近似造成误差模型误差：建模时的近似数据误差：测量等原因造成误差、前一步计算的结果截断误差(方法误差)：数学上的近似舍入误差：实数用有限位来表示(数值计算中总存在)误差计算地球的表面积：

20模型误差数据误差数据误差舍入误差截断误差与舍入误差统称“计算误差”

误差

数据误差引起的

f(x)=sinx,x=121

步长h

(截断误差、舍入误差)大体上

问题敏感性与算法稳定性

病态问题?22(相对条件数)Matlab与数值软件准备知识黄金分割比斐波那契数分形蕨幻方数值软件23MATLAB简介(1)MATrixLABoratory(矩阵实验室),

集成可视化快速原型编程工具,数值/矩阵计算功能强(先进算法)大量专题工具箱(Toolbox),为专业应用提供便利Matlab(作为编程语言)C,C++,Fortran第四代编程语言第三代编程语言

编译方式解释器，或JIT加速器(v6.5后)编译器

申明变量？不需要需要

开发时间较快较慢

运行时间较慢较快

开发环境集成环境(编辑器、调试器、命令历史、变量空间、profiler、编译器)--24MATLAB2020b的函数手册>>helpsvdsketchMATLAB简介(2)命令窗口，将Matlab作为计算器使用变量空间命令历史其他窗口25MATLAB简介(3)程序编辑窗口注释语句%帮助窗口26找不到Matlab软件怎么办？尝试GNUOctave

0.6180…，可能是世界上最有趣的数？Matlab功能表示、显示数的格式数值、符号(解析)求解多项式方程符号变量转为数值函数句柄与函数的绘制脚本程序与绘图功能一个较复杂的函数程序(截断n项的连分数)黄金分割比(1)27

黄金分割比(2)>>phi=(1+sqrt(5))/2>>formatlong

28求解多项式方程用降次排列的系数表示多项式，再用roots命令数值求解用SymbolicMathToolbox解析求解命令solve命解方程:解析(符号)求解运算长无法求解复杂方程符号变量转化为数值vpa,double,single

命令注意：抑制输出符“;”

黄金分割比(3)>>p=[1-1-1];>>r=roots(p)

>>vpa(phi,50)>>phi=double(phi)29>>symsx;r=solve(x-1==1/x)>>phi=r(2)

黄金分割比(4)

>>f=@(x)x-1-1./x>>phi=fzero(f,1)>>holdon>>plot(phi,0,'o')

30>>fplot(f,[0,4])脚本程序与绘图功能Matlab程序.m文件有两种:脚本(script),函数(function)一个脚本程序实现绘制黄金矩形的功能程序内容为：黄金分割比(5)>>editgoldrect.m%GOLDRECTGoldenRectangle…plot(x,y,'b',u,v,'b--')text(phi/2,1.05,'\phi')…axisequalaxisoffset(gcf,'color','white')注释、plot,text,axis,set命令getcurrentfigure%遵循真实尺寸%删除坐标轴31

黄金分割比(6)(类似于C语言中的system)

32斐波那契序列(LeonardoP.Fibonacci与他的兔子问题)f1=1,f2=2,fn=fn-1+fn-2第一个函数fibseq.m，计算出前n个斐波那契数生成全零向量函数:zeros第二个函数fibn.m，输出第n个斐波那契数recursive(递归):

递归函数形式简洁、但运行开销大!计时命令：tic,toc相邻斐波那契数之比~截断的连分数~黄金分割比斐波那契数>>f=zeros(n,1)>>tic,fibn(35),toc>>tic,f=fibseq(35);f(35),toc>>f=fibseq(40);>>f(2:40)./f(1:39)33试试fibn(60)?逐项运算符./“神奇”的通式原理平面上精心策划的点集合、无限的随机生成点的过程

,有4种变换,第1种是每次随机地应用4种变换中的一种，生成新的点无限生长程序:fern含n个点的函数:finitefernMatlab命令程序中含较复杂的绘图命令定义矩阵:‘;’while语句rand命令生成0~1之间均匀随机数用imread,image可看图片分形蕨>>fern>>finitefern(100000)>>A1=[.85.04;-.04.85];>>r=rand

>>F=imread('fern.png');>>image(F)34特殊的矩阵~magic命令《周易》中“洛书”(3阶幻方)的传说行,列,正/反对角线元素之和均相等Matlab命令验证magic(3)是幻方这些和等于多少?三阶幻方矩阵有哪几种?幻方(1)>>A=magic(3)>>sum(A)>>sum(A')'>>sum(diag(A))>>sum(diag(flipud(A)))fork=0:3rot90(A,k)rot90(A',k)end35>>det(A)>>formatrat>>X=inv(A)%逆时针转矩阵的行列式/逆矩阵三阶幻方看看矩阵的范数、

特征值更高阶幻方AlbrechtDurer的版画MelancoliaII4阶幻方有880个

(5阶~275305224个!)矩阵的秩生成幻方的算法幻方矩阵的三维表面图幻方(2)>>loaddurer>>image(X)>>colormap(map)>>axisimage>>inv(A)>>

rank(A)(丢勒)36>>norm(A)>>eig(A)>>editmagic.msurf(magic(n));axisoff;n阶幻方的最大特征值是？(.mat文件)常数:pi,i,j算术运算:+,-,*,/,^,.*,./,.^逻辑关系:==,~=,>,>=,<,<=逻辑运算:&,|,~,&&,||帮助:help,doc,lookfor,which,demo输出:disp,sprintf,;,format初等函数:sin,cos,tan,sinh,asin,exp,log,log10,sqrt

变量记录:whos,clear,save,load,ans,diary向量:[...,...],[...;...],length矩阵:[...,...;...,...],ones,zeros,eye,rand,size,diag,tril,triu绘图:plot,subplot,loglog,fplot,hold,plot3,figure,close文件:edit,type,ls,path编程:function,if,for,while,end,@退出:exit一些常用的matlab命令37数值软件/程序包数值计算的软件与程序包解决一些共同问题，促进各个科研领域的工作了解基本原理，学习算法设计和实现技巧成为聪明的软件/程序包使用者存在形式和资源免费(netlib,github,TOMS…)付费(NR,…)Fortran,C,C++,Matlab,Python,Julia,…源代码使用，或API调用;交互式集成环境的软件38数值软件/程序包矩阵计算有关程序包LAPACK,Basiclinearalgebrasubprogram(BLAS)厂家提供的BLAS;ATLAS,GotoBLAS,OpenBLAS*ScaLAPACK:Distributed-memoryvariantMAGMA:MatrixAlgebraforGPU&MulticoreArch.更高层的程序库与环境Intel公司MathKernelLibrary(inC)Eigen(aC++templatelibrary):Matlab,Octave,Python(Numpy),…392016DenseLinearAlgebraSoftwarePackagesSurvey

(J.Dongarra)87%40%22%No.1No.2(有20%需要自己写线性代数程序)“asmuchaspossiblecomputationisperformedbycallstoBLAS”“exploitLevel3BLAS”Linux:95%,Mac:32%,Win:22%(LAPACKE)浮点算术体系与误差计算机中的浮点数浮点数与舍入误差数值计算中如何减小误差40计算机中的浮点数

>>realminans=2.2251e-308>>realmaxans=1.7977e+308realmin=2-1022realmax=(2-eps)2102341[-1022,1023]

缺哪些数?(非规范数)计算机中的浮点数

浮点数系统IEEE单精度23-1261275.960

10-8IEEE双