2020-03-29

第二章线性方程组的直接解法

2.1 引言

很多数学模型的计算最终都归结为求解线性方程组。

$线性方程组的解法\begin{cases}直接解法（经过有限次计算，求得精确解。过程中无舍入误差） \\ 迭代解法（变形为等价方程组，构造迭代公式，对给定初值迭代得到近似解） \end{cases}$

2.2 Gauss 消去法

Gauss 消去法的基本思想

利用初等行变换，将线性方程组的增广矩阵转化为上三角矩阵，再通过回代求得方程组的解。

例子解线性方程组：
$\begin{cases} x_1 +2x_2 +3x_3 &=1\\ 2x_1 +7x_2 +5x_3 &=6\\ x_1 +4x_2 +9x_3 &=-3 \end{cases}$

解
第一步，初等行变换：
$\begin{cases} x_1 +2x_2 +3x_3 &=1\\ 3x_2 -x_3 &=4\\ 2x_2 +6x_3 &=-4 \end{cases}$

第二步，化为上三角矩阵：
$\begin{cases} x_1 +2x_2 +3x_3 &=1\\ 3x_2 -x_3 &=4\\ \frac{20}{3}x_3 &= -\frac{20}{3} \end{cases}$

第三步，回代求得： $x^*=(2,1,-1)^T$

Gauss 消去法的计算公式

看前述例子。

Gauss 消去法的条件

能用 Gauss 消去法求解线性方程组 $Ax=b$ 的充要条件是系数阵 $A$ 的各阶顺序主子式不为零。

Gauss 消去法的计算量约为 $\frac{n^3}{3}$ 。

2.3 Gauss 主元素法

Gauss 消去法中，若存在 $\mid a^{(i)}_{ii} \mid \ll 1$ ，则会导致舍入误差扩散。

例子采用三位有效数字计算，求解线性方程组：
$\begin{cases} 0.50x_1 +1.1x_2 +3.1x_3 &=6.0\\ 2.0x_1 +4.5x_2 +0.36x_3 &=0.020\\ 5.0x_1 +0.96x_2 +6.5x_3 &=0.96 \end{cases}$

解方程组的精确解为: $x^*=(-2.6,1,2)^T$ 。

解法一 顺序消去法
$\left(\begin{array}{lcr|r} 0.50 & 1.1 & 3.1 & 6.0\\ 2.0 & 4.5 & 0.36 & 0.020\\ 5.0 & 0.96 & 6.5 & 0.96 \end{array}\right) \xrightarrow[l_{31}=10]{l_{21}=4} \left(\begin{array}{lcr|r} 0.50 & 1.1 & 3.1 & 6.0\\ 0 & 0.100 & -12.0 & -24.0\\ 0 & -10.0 & -24.5 & -59.0 \end{array}\right) \xrightarrow{l_{32}=-100} \left(\begin{array}{lcr|r} 0.50 & 1.1 & 3.10 & 6.0\\ 0 & 0.100 & -12.0 & -24.0\\ 0 & 0 & -1220 & -2460 \end{array} \right)$
回代求得: $x=(-5.80,2.40,2.02)^T$ 。

解法二 列主元消去法
$\left( \begin{array}{lcr|r} 0.50 &1.1 &3.1 &6.0\\ 2.0 &4.5 &0.36 &0.020\\ 5.0^* &0.96 &6.5 &0.96 \end{array} \right) \xrightarrow{} \left( \begin{array}{lcr|r} 5.0 &0.96 &6.5 &0.96\\ 2.0 &4.5 &0.36 &0.020\\ 0.50 &1.1 &3.1 &6.0 \end{array} \right) \xrightarrow{} \left( \begin{array}{lcr|r} 5.00 &0.960 &6.50 &0.960\\ 0 &4.12 &-2.24 &-0.364\\ 0 &0 &2.99 &5.99 \end{array} \right)$
回代求得： $x=(-2.60,1,2)^T$ 。

由上可知，通过“选主元”可以避免“零主元”或“小主元”的出现。具体可分为：

列主元消去法
全主元消去法

2.4 Gauss-Jordan 消去法

Gauss-Jordan 消去法的基本思想
将对角线元素上方和下方的元素通过消元运算转化为 0，并且将对角线元素转化为 1。即将增广矩阵的系数矩阵转化为单位矩阵。其省去了回代过程，也称为无回代的 Gauss 消去法。计算量约 $\frac{n^3}{2}$ ，大于 Gauss 消去法。
方阵的求逆
Gauss-Jordan 消去法是初等行变换求逆矩阵的一种规范化算法。
例子求：
$\left(\begin{array}{lcr} 1 &-1 &0 \\ 2 &2 &3 \\ -1 &2 &1 \end{array} \right)$

解 Gauss-Jordan 消去法：
$\left(\begin{array}{lcr|lcr} 1 &-1 &0 &1 &0 &0\\ 2 &2 &3 &0 &1 &0\\ -1 &2 &1 &0 &0 &1 \end{array}\right) \xrightarrow{r_1{\leftrightarrow} r_2} \left(\begin{array}{lcr|lcr} 2 &2 &3 &0 &1 &0\\1 &-1 &0 &1 &0 &0\\-1 &2 &1 &0 &0 &1 \end{array}\right) \xrightarrow{第一次消元} \left(\begin{array}{lcr|lcr} 1 &1 &3/2 &0 &1/2 &0\\0 &-2 &-3/2 &1 &-1/2 &0\\ 0 &3 &5/2 &0 &1/2 &1 \end{array}\right) \xrightarrow{r_2 \leftrightarrow r_3} \left(\begin{array}{lcr|lcr} 1 &1 &3/2 &0 &1/2 &0\\ 0 &3 &5/2 &0 &1/2 &1\\ 0 &-2 &-3/2 &1 &-1/2 &0 \end{array}\right) \xrightarrow{第二次消元} \left(\begin{array}{lcr|lcr} 1 &0 &2/3 &0 &1/3 &-1/3\\ 0 &1 &5/6 &0 &1/6 &1/3\\ 0 &0 &1/6 &1 &-1/6 &2/3 \end{array}\right) \xrightarrow{第三次消元} \left(\begin{array}{lcr|lcr} 1 &0 &0 &-4 &1 &-3\\ 0 &1 &0 &-5 &1 &-3\\ 0 &0 &1 &6 &-1 &4 \end{array}\right)$
即：
$\left(\begin{array}{lcr} 1 &-1 &0\\ 2 &2 &3\\ -1 &2 &1 \end{array}\right)^{-1} = \left(\begin{array}{lcr} -4 &1 &-3\\ -5 &1 &-3\\ 6 &-1 &4 \end{array}\right)$

2.5 矩阵的 LU 分解

矩阵 LU 分解的定义
对 n 阶方阵 $A$ ，若存在 n 阶下三角矩阵 $L$ 和 n 阶上三角矩阵 $U$ ，使得 $A=LU$ ，则称 $LU$ 为矩阵 $A$ 的三角分解，简称 $LU$ 分解。
为使三角分解唯一，需对分解式规范化，常见的三角分解有：
Doolittle 分解：限定 $L$ 为单位下三角矩阵。
Crout 分解：限定 $U$ 为单位上三角矩阵。
Doolittle 分解

$\left(\begin{array}{lccr} a_{11} &a_{12} &\cdots &a_{1n}\\ \ _{21} &a_{22} &\cdots &a_{2n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n1} &a_{n2} &\cdots &a_{nn} \end{array}\right)= \left(\begin{array}{lccr} 1 \\ l_{21} &1\\ \vdots &\vdots &\ddots \\l_{n1} &l_{n2} &\cdots &1 \end{array}\right)\left(\begin{array}{lccr} u_{11} &u_{12} &\cdots &u_{1n}\\ \ &u_{22} &\cdots &u_{2n}\\ \ &\ &\ddots &\vdots\\ \ &\ &\ &u_{nn} \end{array}\right)$

例子用 Doolittle 方法求解方程组 $Ax=B_1,Ax=B_2$ ，其中：
$A=\left(\begin{array}{lccr} 1 &2 &3 &4\\ 1 &4 &9 &16\\ 1 &8 &27 &64\\ 1 &16 &81 &256 \end{array}\right), B_1=\left(\begin{array}{c} 4 \\ 10\\ 28\\ 82\end{array}\right), B_2=\left(\begin{array}{c} 2 \\ 12\\ 56\\240\end{array}\right)$
解：
$\left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &4 &9 &16 &10 &12\\ 1 &8 &27 &64 &28 &56\\ 1 &16 &81 &256 &82 &240 \end{array}\right) \xrightarrow{计算U的第一行 L的第一列元素} \left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &4 &9 &16 &10 &12\\ 1 &8 &27 &64 &28 &56\\ 1 &16 &81 &256 &82 &240 \end{array}\right)\xrightarrow{计算U的第二行 L的第二列元素} \left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &2 &6 &12 &6 &10\\ 1 &3 &27 &64 &28 &56\\ 1 &7 &81 &256 &82 &240 \end{array}\right) \xrightarrow{计算U的第三行 L的第三列元素} \left(\begin{array}{lccr|lr} 1 &2 &3 &4 &4 &2\\ 1 &2 &6 &12 &6 &10\\ 1 &3 &6 &24 &6 &24\\ 1 &7 &6 &24 &0 &24 \end{array}\right)$
即：
$L=\left(\begin{array}{lccr}1 &0 &0 &0\\ 1 &1 &0 &0\\ 1 &3 &1 &0\\1 &7 &6 &1 \end{array}\right), U=\left(\begin{array}{lccr} 1 &2 &3 &4\\ 0 &2 &6 &12\\ 0 &0 &6 &24\\0 &0 &0 &24 \end{array}\right)$
由： $Ax=LUx=b，\begin{cases}Ux=y\\Ly=b\end{cases}$ ，
回代求得： $x_1=(1,0,1,0)^T,x_2=(0,-1,0,1)^T$ 。

Crout 分解
$\left(\begin{array}{lccr} a_{11} &a_{12} &\cdots &a_{1n}\\ a_{21} &a_{22} &\cdots &a_{2n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n1} &a_{n2} &\cdots &a_{nn} \end{array}\right)= \left(\begin{array}{lccr} l_{11} \\ l_{21} &l_{22}\\ \vdots &\vdots &\ddots \\l_{n1} &l_{n2} &\cdots &l_{nn} \end{array}\right) \left(\begin{array}{lccr} 1 &u_{12} &\cdots &u_{1n}\\ \ &1 &\cdots &u_{2n}\\ \ &\ &\ddots &\vdots\\ \ &\ &\ &1 \end{array}\right)$
例子用 Crout 方法求解方程组：
$\left(\begin{array}{lccr} 2 &4 &2 &6\\ 4 &9 &6 &15\\ 2 &6 &9 &18\\ 6 &15 &18 &40 \end{array}\right) \left(\begin{array}{c} x_1\\ x_2\\ x_3\\ x_4 \end{array}\right)= \left(\begin{array}{c} 9\\23\\22\\47 \end{array}\right)$
解： $L=\left(\begin{array}{lccr}2\\ 4 &1\\ 2 &2 &3\\ 6 &3 &6 &1 \end{array}\right), U=\left(\begin{array}{lccr}1 &2 &1 &3\\ \ &1 &2 &3\\ \ &\ &1 &2\\ \ &\ &\ &1 \end{array}\right)$
回代求得： $x=(0.5,2,3,-1)^T$ 。

2.6 平方根法

若方程组 $Ax=b$ 的系数矩阵 $A$ 是对称正定矩阵，则三角分解还可以简化。

矩阵的 LDU 分解
矩阵 $A$ 的各阶顺序主子式不等于零，则矩阵 $A$ 可以唯一分解为： $A=LDU$ 。
其中， $L$ 是单位下三角矩阵， $U$ 是单位上三角阵， $D$ 是非奇异对角阵。
Cholesky 分解
若 $A$ 为对称正定矩阵，则存在三角分解 $A=LL^T$ ，其中 $L$ 是非奇异下三角矩阵。当限定 $L$ 的对角元素为正时，分解唯一。
平方根法
利用 Cholesky 分解来求解对称正定矩阵方程组 $Ax=b$ 的方法称为平方根法。计算量约为 $\frac{n^3}{6}$ 。
$\left(\begin{array}{lccr} a_{11} &a_{12} &\cdots &a_{1n}\\ a_{21} &a_{22} &\cdots &a_{2n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n1} &a_{n2} &\cdots &a_{nn} \end{array}\right)=\left(\begin{array}{lccr} l_{11}\\l_{21} &l_{22}\\ \vdots &\vdots &\ddots\\ l_{n1} &l_{n2} &\cdots &l_{nn} \end{array}\right) \left(\begin{array}{lccr} l_{11} &l_{21} &\cdots &l_{n1}\\ \ &l_{22} &\cdots &l_{n2}\\ \ &\ &\ddots &\vdots\\ \ &\ &\ &l_{nn} \end{array}\right)$
例子用平方根法解方程组：
$\left(\begin{array}{lcr}6 &1 &0\\1&4&1\\0&1&14 \end{array}\right) \left(\begin{array}{c} x_1 \\x_2 \\x_3 \end{array}\right)=\left(\begin{array}{c} 6\\24\\322 \end{array}\right)$
解：
$A=\left(\begin{array}{lcr} 2.4495 &0 &0\\ 0.40825 &1.9579 &0\\ 0 &0.51075 &3.7066 \end{array}\right)\left(\begin{array}{lcr} 2.4495 &0.40825 &0\\ 0 &1.9579 &0.51075\\ 0 &0 &3.7066 \end{array}\right)$
回代求得： $x=(1,0,23)^T$ 。
改进的平方根法
将矩阵转换为 $LDL^T$ 分解。

2.7 追赶法

2.8 向量和矩阵的范数

通过范数这一概念可以有效地解决对向量和矩阵进行度量的问题。

向量范数
对 n 维空间内的任一向量 $x$ 对应存在一个实数 $\mid\mid x \mid\mid$ ，且满足1)非负性、2)齐次性、3)三角不等式，则称实数 $\mid\mid x \mid\mid$ 为向量 $x$ 的范数。
矩阵范数
对任一 n 阶方阵 $A$ 对应存在一个实数 $\mid\mid A \mid\mid$ ，且满足1)非负性、2)齐次性、3)三角不等式、4)乘法不等式，则称实数 $\mid\mid A \mid\mid$ 为矩阵 $A$ 的范数。
常见的矩阵范数为：
$\begin{cases}\parallel A \parallel _1 &= \underset{1\ll j \ll n}{max} \sum_{i=1}^{n} \mid a_{ij} \mid &（最大列和范数）\\ \parallel A \parallel _2 &= \sqrt{\lambda_1} &（\lambda _1 是 A^TA的最大特征值）\\ \parallel A \parallel _\infty &= \underset{1\ll i \ll n}{max} \sum_{j=1}{n} \mid a_{ij} \mid &（最大行和范数） \end{cases}$
谱半径
设 n 阶矩阵 $A$ 的特征值为 $\lambda _i(i=1,2,\cdots,n)$ ，则称 $\rho(A)=\underset{1\ll i \ll n}{max} \mid \lambda _i \mid$ 为矩阵 $A$ 的谱半径。
条件数及病态方程组
若 $A$ 和 $b$ 的微小变化只导致 $x$ 发生微小变化，则称此问题是良态的；反之则称其为病态的。
若 n 阶方阵 $A$ 非奇异，则称 $\mid\mid A \mid\mid · \mid\mid A^{-1} \mid\mid$ 为矩阵 $A$ 的条件数，记为 $cond(A)$ 。矩阵的范数选择不同，可得不同的条件数：
$cond(A)_1=\mid\mid A \mid\mid _1 \mid\mid A^{-1} \mid\mid _1$
$cond(A)_2=\mid\mid A \mid\mid _2 \mid\mid A^{-1} \mid\mid _2$
$cond(A)_\infty=\mid\mid A \mid\mid _\infty \mid\mid A^{-1} \mid\mid _\infty$
当 $cond(A)$ 接近于 1 时，称方程组是良态的；当 $cond(A)\gg 1$ 时，称方程组是病态的。

最后编辑于：2020.04.03 18:31:16

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 207,248评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,681评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 153,443评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,475评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,458评论 5赞 374
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,185评论 1赞 284
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,451评论 3赞 401
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,112评论 0赞 261
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,609评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,083评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,163评论 1赞 334
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,803评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,357评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,357评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,590评论 1赞 261
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,636评论 2赞 355
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,925评论 2赞 344