6.1 引言 6.2 高斯消元法在线视频

各位同学

大家好

我是来自北京科学大学数理学院的

卫宏儒老师

我给大家介绍的是计算方法

这门课里面的

线性方程组的直接解法

我

将从下面几个方面作一介绍

第一部分是这章的引言部分

第二部分高斯消元法

第三部分

矩阵的分解与应用

第四部分是矩阵分析

最后

我们讲一下数值实验

首先

我们看一下关于线性方程组

直接解法的一些背景

那么在科学与工程计算技术里面

很多问题都可以归结为

求解大型方程组的问题

那么还有很多非线性问题可以通过

局部线性化而转化成线性问题

那么这样的话

我们可以得到

利用直接解法来

解决他的求解问题

第一个主要内容掌握消元法

还有我们的列主元消元法

按比例消元法以及它的计算量

第二部分

我们得到了根据消元法

所获得的LU分解

包括追赶法

还有平方根法以及

改进的平方根法

第三部分来介绍一下

关于矩阵的条件数

方程组的误差估计

迭代求精法

它的一些应用问题

好了

我们先看一下引言

那么解方程组问题

其实是个古老问题

我们知道什么叫线性方程组

有n个变量

n个方程所组成的这样方程组

称为n阶线性方程组

那么它的系数矩阵

由a11到a12，a1n以及

ann

这样的元素组成

把它记成矩阵A

还有我们的常数项

b1，b2...我们记成矩阵b

这样的话我们把线性方程组可以写成

矩阵形式

Ax=b

那么

对这个方程组已经有方法可以解决

我们就有方法可以解决了

它的方法就是大家所熟悉的

克莱姆法则

克莱姆法则很重要

而且十分重要

它给我们解决了

这类方程组的求解问题

也说把它的解值给我们了

但是

在实际问题里面

这样方程组的计算量相当大

也说解决他的n个变量的求解问题

十分困难

我们举个例子看一下

按照这个方程组的克莱姆法则求解的话

我们有n+1个n阶行列式

同时我们会得到这样一个

n-1乘以n的阶乘次乘法

同时

还有相关的一些除法问题

那么这些计算量加在一起

它的计算量应该相当大

我们举个例子比如说

这个方程组如果是二十个变量的话

那么他的求解的这个

时间大概到三百多年

大家想一想

这是不可能的事情

所以说这个计算量相当大也就说

克莱姆法则

虽然很好

但是

解决这种线性方程的求解问题

它不可用

它不可用

因此我们有必要来研究一下

方程组的其他的数值解法

那么从宏观来讲

这样的解法有两种

一个叫直接解法

第二个叫迭代解法

我们这一章的主要解决直接解法

那么什么叫直接解法

直接解法

就是在忽略舍入误差的

假设条件下

通过有限次运算

我们得到方程组的解

把这个办法

叫直接解法

那么直接接法的典型代表

就是高斯消元法

下面看一下第二部分

高斯消元法

所以说高斯消元法

解决大型方程组的求解问题

而给了一个数值办法

我们的目标是把这个方程组

经过消元

转化成能够很方便的

求解的

这个方程组叫三角形方程组

那么对三角形方程组来讲

他的求解十分简单

我们有这样一个形式

这样的三角形方程组它有两种

一个那叫上三角形方程组

就我们看到的这个形式的

那么还有一种情况

是叫下三角形方程组

那么对这两种方程组的求解

很简单

我们直接利用回代法求解就可以

也就是说

不管是上三角行方程组

还是下三角形方程组

我们都可以利用回代法求解

所以说

我们要解决这个

大型方程组的求解问题

首先的目标想办法把它能变成

上三角方程组

或者下三角方程组就可以了

比如我们看一个简单例子

回代法像这个例题

告诉我们我们要求解它的解

实际上很简单

我们可以通过先求x3

再求x2，再求x1

可以得到它的解

这是我们说的

一个

上三角方程组

那么这下三角方程组

我们这三个变量

x1,x2,x3也可以

利用回代法求解

这个是两个简单例题

也就告诉我们

如果是一个上三角形方程组

或者下三角形方程组

我们可以直接利用回代法来求解

这是给我们两个例子

那么下面我们看一下如何去把一个

n个变量

n个方程的方程组

变成这样一个

上三角形或下三角形方程组

我们这个办法

叫做消元法

那么消元法怎么去做

我们通过下面过程讲一下

第一步

我们假设这个方程组的变量

它的n个变量

然后n个系数里面的a11

如果不等于0

如果a11

不等于零

我们第一个方程

乘以a11分之a21

它的相反数加到第二方程

我们就可以把a21元素变成0

同样的

我们可以给第一个方程

乘一下a11分之a31

它的相反数加到第三方程

我们可以把a31

这个元素变成零

以此类推

我们得到一般式子

第一步我们可以说

确定一个元素就是如上

等于负的如上分之

ai1加到后面

n-1个方程

那么就可以把

第一列的a21,a31到an1

全部变成零

这是我们第一步消元

那么通过第一步消元之后

我们这个方程组

变成它的等价方程组

第一个方程不变

第二方程到最后一个方程

他的系数包括常数项都发生了变化

所以说我们做个标记

那么就说把原系数

给它右上角写个零对吧

然后

第二方程到最后方程我们给它

右上角都标个1

这是经过第一次消元后

我们所得到的

这个方程组

好了

通过第一步完成之后

我们下面接着做第二步消元

第二步消元

我们仍然假设有一个要求

就是a22

右上角1那个元素

要不等于零

如果说如上这个元素不等于零

我们类似于刚才的办法

给第二个方程乘一下a22(1)分之的

a32的那个相反数加

加到第三个方程

以此类推

我们可以把a22(1)

下面的所有元素

统统变成零

这是我们的第二步消元、

那么完成第二步消元之后

我们同理就可以进行第三步消元

那么我们经过了n-1次消元之后

这个方程组就会变成

一个上三角形方程组

上三角形方程组变成之后

就是我们刚才所讲的两个例题

那个例子一样

我们可以利用回代法

求解这个方程组的解

这是我们经过最后变形所得到的

一个上三角形方程组

那么我们给出它的

一般的这样一个公式

就是

我们有这么三个表达式

利用这个方法

我们完成了消元

通过n-1步消元之后

原方程组就变成它的同解方程组

我们后面利用回代法来求解

这是我们说的这样一个消元过程

那么通过消元之后

我们完成了

第一步后面

我们就利用回代法来求解方程组就可以了

所以说

整个高斯消元法的过程里面

还有两个过程

一个

消元，第二

回代

我们看个简单例题

那么这个例题

它里面有三个变量

我们利用这个变量可以去

刚才的消元过程应用下

我们可以求解它的解

这是我们的高斯消元法

那么在高斯消元法里面

我们刚才发现一个问题

在每次消元里面

我们需要主对角线元素

不为零才能够进行消元

那么我们下面看一下

这个问题如何解决如果说

这个主对消元法为零了

那么消元法就失效了

另外一个情况

如果在消元过程中

aii如果很小

那么在消元过程中

也很有可能会出现一些问题

我们看下第三个问题主元消元法

那么考虑到刚才两个因素一个

就是因为这个aii消元过程中

他为零

第二个呢如果说

消元的对象

他比较小

我们在计算过程中

就很难进行

也就是说消元法失效

那么借助这个思路

我们下面引出来

叫主元消元法

那么刚才看到这个例子

如果说主元比较小

在此情况下我们在计算过程中

计算机要做计算的话

它首先要规格化

把所有系数包括常数项

规格化之后

再进行运算

包括运算过程中

有对接这样一对接的话

我们这样

元素比较小

情况下

它的解就达到了

1跟0一个关系问题

跟原来解差的太多了

失真

因此为了解决这个问题

我们下面介绍一下

主元消元法的的基本思想

主元消元法里面有两个很重要的

一个叫列主元选法

还有个叫按比例消元法

那么列主元消元法

有几个很重要的过程

在消元里面我们就说

首先得避免这样个小的主元

刚才已经看到这个例子了

实际里进行第k步消元过程中

应该说在第k列

里面要找个元素

绝对是最大的

然后

把它进行消元

换句话说

经过这样比较之后

我们得到这样一个主元

把这样的元素叫做主元

因此由于在第k列

我们所选的元素

因此把它叫做

按列选主元或者叫部分选主元

如果在第k步消元之前

在第K个方程里面

到第n个方程中

我们把这个元素的

绝对值最大值找到之后

我们要进行交换

也说

把第k个跟第p个方程进行对换

对换之后

对换之后呢

把这个过程那叫完全选主元

我们在整个元素里面

去选主元的话

得到的完全选主元

不管是按列选主元

还是全主元也罢

不论是这两种情况下

都叫我们的选主元方法

我们通过选主元之后

再进行消元

我们简单总结一下两句话

在消元过程中那在某一列里面

选元素绝对值最大的

我们进行消元

另外一个我们在

全部元素里面选元素

绝对值最大的

进行消元

这两个都叫做选主元消元法

我们看个简单例题

这个叫利用列主元消元法解方程组

我们看到了第一列元素

有三个元素-0.002

还有1，另外一个3.996

那么这三个元素里面第一元素太小

刚才我们讲过了

如果元素很小情况下

能够进行消元

消元过程中可能会产生它的解失真

因此把第三个和第一个对调一下

因为3.996跟第一列元素比较的话

它绝对值最大

所以说我们进行兑换之后

在进行消元

把第一个跟第三个方程进行对调

按照矩阵运算来讲

就是对这个增广矩阵

第一行和第三行对调之后

我们再把

第一列里边的3.996下面的

两个元素变成零

这是我们说的第一步消元

那么经过第一步消元之后

我们第一列里边的

第二元素第三元素

变成零了

那么再进行第二步消元

那么第二步消元

就把我们第二元素

第二列第二元素第三元素

它的绝对是最大的作为消元对象

经过消元之后

我得到一个上三角形方程组

下面利用回代法来求他的解

这样的话我们得到它的解之后发现

跟这方程组它原来

的精确解相比较来讲还是比较准确

这是我们通过这个例子来讲一下

他的消元过程

当然了

我们刚才讲的叫选主元消元法

里面两个很重要的一个是

列主元消元法还有全主元消元法

还有个按比例消元法

其实最重要的

体现到他的计算量

也说

我们从高斯消元法计算上来看的话

这个计算量大概是

达到了n³的这个量级

这是我们说的高斯消元法

那么通过刚才所讲消元法包括

我们刚介绍的消元法过程里面

列主元消元法和全主元消元法来看

它的特点应该是

具体来讲全主元消元法的这个精度

它比

我们列主元消元法要高一些

因为它的全部元素里面要选主元

但是带来的问题也比较大

我们要进行行的对换

还有列的对换

不太容易

计算量要大一些

那么列主元消元法

它的计算量小

精度呢

它可能比全主元消元法要低一点

但是

他的计算量相对小一些

具有实用价值

这是方法的特点

不管是列消元法还是全主元消元法

都属于直接消元法

这是对高阶的方程组特别是

对系数矩阵是稀疏的

在计算过程中是很有用的

这是我们说的

关于他的一个特点

特别是在方程组

阶数比较高情况下

这样方程

在求解里面

我们后面还会介绍一些新的办法

叫迭代法

另外一个

高斯选主元消元法

还有一些技巧

比如说在解决方程组里面

特殊的分组里面有很重要应用

同时又有误差的影响

计算过程中

可能出现一些坏的现象

要尽量的避免

比如说求解方程组里边消元过程中

我们可能会出现这个运算元素

的对象为零对吧

我们要进行交换

这样的话可能会要按照我们

消元过程来讲的话

就要进行一个行列的互换问题

这是关于我们的消元法