当前课程知识点：线性代数(1) > 第六讲 LU分解 > 6.3 消元法的计算量 > 消元法的计算量
好 我们接下来看一下
消元法的计算量
设这个系数矩阵
A是一个n阶的方阵
我们想要知道
用高斯消元法来求解线性方程
Ax等于b需要多少次
加减乘除运算
我们把一开始的系数矩阵
A叫做A1
把一开始的常数向量b叫做b1
那么我们想要做消元的过程
第一步我们希望把A1的下方的
这n-1个数都给消成0
我们这时候假设A1是不等于0的
好 我们要消元呢
首先要求乘数
我们第一第i行上的这个位置
比如ai1这个位置
我们想要去消元
我们需要求出来这个乘数
也就是ai1去除以a1等于li1
想要先把这个数求出来
那么这个数呢
要求这个数需要n-1次除法
那么因为我这个i是从2到n
一共有n-1个
所以我需要n-1次除法
求出来这个数之后
我们用这个数去乘以第一行
包括这个b1
也就是我需要来求这个乘数
li1去乘以a1j去乘以b1
然后去乘以后面这些元素
那它一共这是需要
去乘上面这个地方
是需要n-1个
再加上这个位置呢一共是n个
那我是做多少次呢
我这个是n-1行
所以我需要n-1去乘以n次的乘法
然后呢我要去做减法
我在这个第i行上减掉刚才
第一行去乘以这个li1的这个元素那么我这个减法
同样我是需要
消每一行的时候需要n次
我一共是要消n-1行
所以是n去乘以n-1次减法
那么我就变成下面的这个A2
我把A1下方这一列都消成了0
那么这时候变成一个
B变成一个n-1阶的矩阵
对它来进行消元
继续进行消元
所以我们在做消元的过程呢
一共是要做乘除法的次数
这两个乘除法的次数
它是n-k
这个k是从1到n-1的
再加上n-k乘以n-k+1
这个k从1到n-1
那么简单的计算
知道这个数是n/6
n-1 2n+5
如果n很大的话
这个数量级是约等于
三分之n的三次方的
那么在这个过程中
做加减法的次数是这个n-k
n-k+1 k从1到n-1
那这个数呢是n/3
n+1 n-1
那n很大的时候
这个数量级
和三分之n的三次方是相同的
我们又知道
就是你做完了消元之后
我们要求解这个线性方程组
还有一个回代的过程
回代的过程容易可以看到
做乘除法的次数是二分之n n+1
那么比如在最下面
你要去做一次除法
然后代到这个第n-1个方程里头
你要做两次除法
这样一直加下去二分之n n+1
那么加减法呢
因为你最下面这个第n行上
你不需要做加减法
一共是做这个二分之n
n-1次加减法
于是整个这个
高斯消元法的计算量
是乘除法的次数
是这两个数加起来
三分之n的三次方加n平方
减三分之n
n很大的时候
数量级和三分之n
的三次方是相当
那么加减法的次数呢
这两个数加起来
是三分之n的三次方
加上二分之n的平方
减掉六分之五n
n很大的时候
和三分之n的三次方是相当的
所以在做高斯消元法
它的计算量
如果两个合在一起的话
是三分之2倍的n的三次方
-课前引言
--课前引言
-1.1 引言
--1.1 引言
-1.2 n维向量空间中的点
-1.3 向量
--1.3 向量
-1.4 向量空间的定义
-1.5 向量空间的线性组合
-1.6 向量的点积、长度
-1.7 向量的夹角
-1.8 两个不等式
-第一讲 向量及其运算--1.9 课后作业
-2.1 矩阵与向量的乘积
-2.2 可逆矩阵
--2.2 可逆矩阵
-2.3 线性方程组的行图和列图
-第二讲 矩阵与线性方程组--2.4 课后作业
-3.1 Gauss消元法（上）
-3.1 Gauss消元法（下）
-3.2 消元法的矩阵表示 3.2.1 消去矩阵
-3.2 消元法的矩阵表示 3.2.2 置换阵
-3.2 消元法的矩阵表示 3.2.3 初等行(列)变换和初等矩阵
-第三讲 高斯消元法--3.3 课后作业
-4.1 矩阵
--4.1 矩阵
-4.2 矩阵的加法和数乘
-4.3 矩阵的乘法
-4.4 矩阵的乘法的性质
-4.5 矩阵的方幂
-4.6 关于矩阵乘法的引入
-4.7 分块矩阵
--4.7 分块矩阵
-4.8 矩阵的转置
-第四讲 矩阵的运算--4.9 课后作业
-5.1 可逆矩阵的定义
-5.2 矩阵可逆的性质
-5.3 初等矩阵的逆
-5.4 Gauss-Jordan消元法求A的逆
-5.5 矩阵可逆与主元个数
-5.6 下三角矩阵的逆
-5.7 分块矩阵的消元和逆
-第五讲 矩阵的逆--5.8 课后作业
-6.1 LU分解
--LU分解
-6.2 用LU分解解线性方程组
-6.3 消元法的计算量
--消元法的计算量
-6.4 LU分解的存在性和唯一性
-6.5 对称矩阵的LDL^T分解
-6.6 置换矩阵
--置换矩阵
-6.7 PA=LU分解
--PA=LU分解
-第六讲 LU分解--6.8 课后作业
-7.1 引言
--7.1 引言
-7.2 向量空间和子空间
-7.3 列空间和零空间
-7.4 阶梯形
--7.4 阶梯形
-第七讲 向量空间--7.5 课后作业
-8.1 引言
--8.1 引言
-8.2 基础解系
--8.2 基础解系
-8.3 简化行阶梯形的列变换
-第八讲 求解齐次线性方程组--8.4 课后作业
-9.1 复习
-9.2 求特解
-9.3 解的一般性讨论
-第九讲 求解非齐次线性方程组--9.4 课后作业
-10.1 引言
--引言
-10.2 n维空间的坐标系
-10.3 无关性、基与维数
-10.4 无关性、基与维数的性质
-10.5 关于秩的不等式
-第十讲 线性无关、基与维数--10.6 课后作业
-11.1 四个基本子空间的基
--11.1
-11.2 维数公式
--11.2
-11.3 例题
--11.3
-第十一讲 四个基本子空间的基和维数--11.4 课后作业
-12.1 引言
--12.1
-12.2 四个子空间的正交性
--12.2
-12.3 正交补
--12.3
-12.4 Ax=b在行空间中的唯一性
--12.4
-第十二讲 四个基本子空间的正交关系--12.5 课后作业
-13.1 引言
--13.1 引言
-13.2 点在直线和平面上的投影
-13.3 一般情形
-第十三讲 正交投影--13.4 课后作业
-14.1 复习
--14.1 复习
-14.2 最小二乘法
-14.3 最小二乘法的应用：曲线拟合
-第十四讲 最小二乘法--14.4 课后作业
-15.1 引言
--15.1 引言
-15.2 正交向量组和正交矩阵
-15.3 Gram-Schmidt正交化过程
-15.4 QR分解
-第十五讲 Gram-Schmidt正交化--15.5 课后作业
-16.1 引言
--16.1 引言
-16.2 二阶行列式的几何含义
-16.3 一般行列式的定义
-16.4 行列式和初等变换
-第十六讲 行列式的基本性质--16.5 课后作业
-17.1 行列式计算公式与展开定理
-17.2 典型例题
-第十七讲 行列式的计算--17.3 课后作业
-18.1 引言
--18.1 引言
-18.2.1 求逆矩阵公式
-18.2.2 线性方程组的公式解
-18.3 计算有向长度、面积和体积
-18.4 和QR分解的联系
-第十八讲 Cramer法则及行列式的几何意义--18.5 课后作业
-19.1 引言和定义
--default
-19.2 例
--default
-19.3 特征值的性质
--default
-第十九讲 特征值与特征向量--19.4 课后作业
-20.1 矩阵可对角化的条件
--default
-20.2 特征值的代数重数和几何重数
--default
-20.3 矩阵可对角化的应用
--default
-20.4 同时对角化
--default
-20.5 小结
--default
-第二十讲 矩阵的对角化--20.6 课后作业
-21.1 引言
--21.1 引言
-21.2 A可对角化的情形
-21.3 矩阵的指数函数
-21.4 二阶常系数线性微分方程
-21.5 微分方程的稳定性
-第二十一讲 特征值在微分方程中的应用--21.6 课后作业
-22.1 实对称矩阵的特征值与特征向量
-22.2 实对称阵正交相似于对角阵
-22.3 实对称阵特征值与主元的关系
-22.4 小结
--22.4 小结
-第二十二讲 实对称矩阵--22.5 课后作业
-总结和预告
