当前课程知识点：计算方法 > 第1章 计算方法概论 > 1.2 算法与效率 > 1.2 算法与效率
今天我们学习第二节
算法与效率
上一节曾说过
计算方法的目标是
要构造一个面向计算机
计算复杂性好
又有可靠精度的算法
那么什么是算法
算法
按照原理来分
可以分为确定性算法
与非确定性算法
按照功能来分
可以分为数值算法与非数值算法
进行科学计算
我们就需要构造确定型的数值算法
从给定的已知量出发
按照规定的运算顺序
经过有限次的四则运算与逻辑运算
最后求出未知量的数值解
这样构成的完整的计算步骤
这样构成的完整的计算步骤
称为算法
注意算法不是一个数学公式
它要具备以下两个要素
第一规定的运算顺序
第二
有限次四则运算
本课程我们采用
Matlab语言来描述算法
下面我们给出几个例子
例1
给出多项式求值的一个算法
那么这里我们首先来
看一下如何来计算x的i次幂
通过递推公式
ti=xti-1
来实现
其次
我们从低 次项开始
我们从低次项开始
逐项累加
通过递推公式
ui=ui-1+ai×ti
来实现
将上述递推公式
用MATLAB语言描述
我们就给出如下算法
首先令t等于1
u等于a0
然后执行循环体
t等于x乘t
u等于u+ai乘t
循环N次即可算得多项式的值
再看一个例子,给出三个矩阵
A
B
C
求ABC的乘积
这里我们按照矩阵
乘法的结合律
给出如下两个算法
算法一矩阵A与B相乘
然后再和矩阵C相乘
算法二矩阵B和C相乘
然后在左乘矩阵A
然后在左乘矩阵A
两个算法
虽然只是括号的位置有所不同
但是却给出了两种不同的计算顺序
因此是两个不同的算法
从上述例子可以看出
一个数学问题可以给出不同的算法
那么如何评价算法呢
一个重要的指标就是计算量
所谓计算量
就是一个算法所包含的
四则运算的总次数
由于计算机做加减法运算
所用的时间比作乘除法运算
所用的时间要少得很多
因此我们往往忽略加减法运算
而只统计乘除法的运算次数
这样我们又可以把计算量
简化为一个算法所包含的
乘除法运算的总次数
单位是flop
flop表示浮点运算
我们将计算机完成一次
浮点加法或减法
乘法和除法称作一次浮点运算
计算量是衡量一个
算法好坏的重要标志之一
下面我们通过几个例子
来统计算法的计算量
刚才我们已经给出了这个例子
当然是求值的算法
那么这里呢
我们要给出多项式求值的
我们要给出多项式求值的
一个高效算法
在例1中
我们给出了下述算法
统计一下它的计算量
这个算法包含有一个循环体
循环体里还有两个语句
每个语句包含一次乘法
循环N次
因此这个算法的计算量就是
2n次浮点运算
我们把它记为算法1
再介绍一个算法
首先我们将多项式分解为
n-1个括号相互嵌套的这种形式
每一个括号对应一个一次式
我们可以用递推式
Pi=Pi+1乘以x+ai来表示
也就是把这个多项式转化为
n-1个1次式的
n-1个一次式
和的这种形式
那么这个递推式
我们用Matlab语言来描述
就得到了下面的算法2
这个算法包含一个循环体
循环体里面只有一个语句
这个语句呢
含有一次乘法循环n次
含有一次乘法
循环n次
因此算法2的计算量
就是N次乘法
N次浮点运算
刚才算法1的计算量2n次浮点运算
那么和算法1相比
很显然是算法2更好
这个算法2
我们又把它称为是秦九韶算法
秦九韶算法
它是我国南宋的数学家
秦九韶首先提出来的
这个算法的主要作用就是
简化多项式的计算
我们再看一个例子矩阵乘积
A乘与B的计算量的分析
这里矩阵A是一个m乘n的矩阵
矩阵B是一个n乘s的矩阵
我们要统计矩阵C的计算量
那么矩阵C它一共有多少个元素呢
一共是m乘s个元素
它的任意一个元素
Cij的计算公式
如上
由公式可知
计算Cij需要做N次乘法
它一共有m乘s个元素
因此计算矩阵C的计算量
就是n乘m乘s
下面我们再来看
三个矩阵乘积的计算量的统计
我们这里给出两个算法
算法1矩阵A与B相乘
然后再和矩阵C相乘
算法二矩阵B和C相乘
然后在左乘矩阵A
那么
根据刚才第一个例子的分析
算法1
它的计算量可以表述为
s乘m乘l
再加上l乘m乘n
其中加法中的第一项
是A乘B的计算量
第二项是
A乘B在与C相乘的计算量
我们把这个计算量记为N1
类似的我们也可以
给出算法2的计算量N2
先求B和C相乘的计算量
是l乘s乘n
然后再与矩阵A相乘
加上s乘m乘n
我们把这个计算量记为N2
那么这两个计算量
相等不相等呢
我们说一般是不相等的
下面给出具体的
矩阵A B C
A是100x10矩阵
B是10x1矩阵
C是1x100矩阵
那么
我们分别按照算法1和算法2来统计
它们的计算量
分别是
N1=11000次浮点运算
N2=101000浮点运算
显然算法1的计算量要比算法2少
本节我们介绍了算法与效率
构造一个面向计算机
计算复杂性好
有可靠精度的算法
所谓计算复杂性
指的是时间复杂性与空间复杂性
时间复杂性指的就是计算效率
一个算法
它的计算时间短
它的效率就高
空间复杂性指的是存储空间
计算效率是衡量一个算法好坏的
重要标准之一
-1.1 引言
--1.1 引言
-1.2 算法与效率
-1.3 计算机数系与浮点运算
-1.4 误差与有效数字
-1.5 四则运算与函数求值的误差
-1.6 问题的性态与条件数
-1.7 算法数值稳定性
-第1章 作业
--第一章 作业
-2.1 引言 2.2 线性空间
-2.3 内积空间与元素的夹角
-2.4 赋范线性空间
-2.5 向量范数与向量序列极限
-2.6 矩阵范数
--2.6 矩阵范数
-第二章 作业
--第二章 作业
-3.1 引言
--3.1 引言
-3.3 不动点迭代法
--3.2 二分法
-3.4 不动点迭代法的收敛条件
-3.5 牛顿迭代法及其变形
-3.6 迭代法收敛阶
-3.7 重根的计算与加速收敛
-3.8 数值实验
--3.8 数值实验
-第3章 作业
--第3章 作业
-4.1 引言
--4.1 引言
-4.2 Lagrange插值
-4.3 Lagrange插值余项
-4.4 Newton差商插值
-4.5 Hermite插值
-4.6 分段多项式插值
-4.7 三次样条插值
-4.8 数值实验
--4.8 数值实验
-第4章 作业
--第4章 作业
-5.1 函数逼近与曲线拟合基本概念
-5.2 连续函数的最佳平方逼近
-5.3 曲线拟合的最小二乘法
-第5章 作业
--第5章 作业
-6.1 引言 6.2 高斯消元法
-6.3 矩阵分解与应用
-6.4 误差分析 6.5 数值实验
-第6章 作业
--第6章 作业
-7.1 引言 7.2 线性方程组的迭代法（上）
-7.2 线性方程组的迭代法
-7.3 非线性方程组的迭代法
-7.4 数值实验
--7.4 数值实验
-第7章 作业
--第7章 作业
-8.1 引言
--8.1 引言
-8.2 幂法与反幂法
-8.3 矩阵的正交分解
-8.4 QR方法
--8.4 QR方法
-8.5 Jacobi方法
-第8章 作业
--第8章 作业
-9.1 引言
-9.2 牛顿-柯特斯公式
-9.3 复合牛顿-柯特斯公式
-9.4 龙贝格算法
-9.5 高斯型求积公式
-9.6 数值微分
--9.6 数值微分
-10.1 引言
--10.1 引言
-10.2 梯形公式和改进的欧拉方法
-10.3 单步法的误差与稳定性收敛性
-10.4 高阶单步方法
-10.5 线性多步法
-10.6 多步法的误差与稳定性
-10.7 一阶微分方程组与高阶微分方程
-第10章 作业
--第10章 作业
