LU分解与复合映射的零度
引入| English | 释义 | 拼音 |
|---|---|---|
| nullity/ˈnʌlɪti/ | 零度 | líng dù |
| forward substitution/ˈfɔːwəd ˌsʌbstɪˈtjuːʃn/ | 前代 | qián dài |
| back substitution/bæk ˌsʌbstɪˈtjuːʃn/ | 回代 | huí dài |
一台机器,多种负载
- 固定网络可能面临多个需求向量 $b$。在线性模型 $Ax=b$ 中,只需对同一矩阵进行一次分解,即可快速求解每个新的需求。
- 第二个问题询问线性映射链会丢失哪些输入。其零度(nullity)统计被映射为零的独立输入方向的数量;这不等于零元素的数量。
固定分解约定
- 为了解方程组,取一个可逆的 $n\times n$ 矩阵并写出 $PA=LU$。其中 $P$ 排列行,$L$ 是主对角线元素为 $1$ 的下三角矩阵,$U$ 是主对角线元素非零的上三角矩阵。
- 写出 $d=Pb$ 和 $y=Ux$。先解 $Ly=d$,再解 $Ux=y$。若 $P=I$,则简化为 $A=LU$;无需显式计算矩阵逆。
消元过程存储乘数
- For $A=\begin{pmatrix}2&1\\6&4\end{pmatrix}$, subtract $3$ times row 1 from row 2. This gives $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ and stores the multiplier in $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$. Multiplication checks $LU=A$.
- 对于 $b=(2,7)$,先解 $Ly=b$:得到 $y_1=2$ 和 $y_2=7-3(2)=1$。然后计算 $x_2=1$ 和 $x_1=(2-1)/2=1/2$。将结果代入 $Ax=b$ 可验证两个方程均成立。
Let $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$, $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ and $b=(2,7)$. Solve $LUx=b$; give $x_1$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Forward substitution gives $y=(2,1)$. Then $x_2=1$ and $x_1=(2-1)/2=1/2$. The product $LU=\begin{pmatrix}2&1\\6&4\end{pmatrix}$ checks the original system.
前代通过下三角部分
- 前代法 前代 利用已在上行求得的元素逐行求解。若对角元为单位元$L$,可直接使用$y_i=d_i-\sum_{j<i}l_{ij}y_j$;若非单位元,则需除以$l_{ii}\ne0$。
- 在原三行示例中,$L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}$与$d=(-1,-1,12)$成立。由此推出$y_1=-1$,$y_2=-1-2(-1)=1$及$y_3=12+(-1)-3(1)=8$。
Solve $Ly=d$ for $L=\begin{pmatrix}2&0\\3&1\end{pmatrix}$ and $d=(4,7)$. Give $y_2$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Divide by $l_{11}=2$: $y_1=2$. Then $y_2=7-3(2)=1$. Assuming $y_1=d_1$ would be wrong for this non-unit L.
回代通过上三角部分
- 回代(Back substitution)从底部开始:$x_i=(y_i-\sum_{j>i}u_{ij}x_j)/u_{ii}$。除法有效是因为每个对角线主元均不为零。
- 针对$U=\begin{pmatrix}2&1&-1\\0&3&2\\0&0&4\end{pmatrix}$与$y=(-1,1,8)$,可得$x_3=2$、$x_2=(1-4)/3=-1$与$x_1=(-1+1+2)/2=1$。因此$x=(1,-1,2)$;$Ux=y$与$Ly=b$验证了原方程组。
行交换必须同时移动右侧
- 取 $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$ 和 $b=(4,7)$。交换行:$P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ 给出 $PA=\begin{pmatrix}1&3\\0&2\end{pmatrix}=U$ 和 $L=I$。新的右侧为 $Pb=(7,4)$。
- 求解 $y=(7,4)$,然后 $x_2=2$ 和 $x_1=7-3(2)=1$。原方程给出 $2x_2=4$ 和 $x_1+3x_2=7$。使用旧的 $b$ 与 $PA$ 将解出不同的方程组。
For an invertible square matrix with $PA=LU$, put the steps for solving $Ax=b$ in order.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
$PAx=LUx=Pb$. Set $y=Ux$, solve the lower-triangular system first, then the upper-triangular system, and check $Ax=b$.
支持 $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$, $b=(4,7)$ and the row-swap matrix $P$, which pair gives $Pb$ and the solution $x$?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Swap the right side with the rows. Back substitution in $\begin{pmatrix}1&3\\0&2\end{pmatrix}x=(7,4)$ gives $x_2=2$, then $x_1=1$.
可逆性不保证无主元LU分解
- 上一个 $A$ 是可逆的,因为其行列式为 $-2$。但单位下三角 $L$ 将给出 $a_{11}=u_{11}=0$ 和 $a_{21}=l_{21}u_{11}=0$,与 $a_{21}=1$ 矛盾。因此该矩阵没有这种形式的无主元 $A=LU$。
- 在精确算术运算中,每个可逆方阵都允许通过适当的行交换获得 $PA=LU$。仅非零的首项并不能保证后续所有主元均非零。在数值计算中,交换还可以避免导致舍入误差放大的小主元。
Some invertible square matrices require a row exchange before a factorisation with unit-lower L and upper-triangular U exists.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
True. For $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$, an unpivoted unit-lower factorisation would force $a_{21}=0$. A row swap gives $PA=U$ and $L=I$.
支持 $A=\begin{pmatrix}0&1\\2&3\end{pmatrix}$ and $b=(2,8)$, exhibit $PA=LU$, solve $Ax=b$ and check the original equations. Explain why unit-lower unpivoted LU fails.
比较中间步骤、映射顺序及假设与模型回答。
对角线为零需要不同的决策
- 奇异矩阵仍可有 LU 分解:$L=I$ 和 $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ 即为一个例子。对角线为零会阻止唯一解除法法则,但这本身并不证明无解。
- 对于这个 $U$,若右侧为 $(2,0)$,则给出无穷多解 $x_1=2-t$ 和 $x_2=t$。若右侧为 $(2,1)$,则无解,因为最后一行将意味着 $0=1$。应检查一致性和自由变量,而非除以零。
支持 $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$, how many solutions do $Ux=(2,0)$ and $Ux=(2,1)$ have, in that order?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The first system leaves $x_2$ free. The second requires $0=1$. A zero pivot does not allow a unique-solution division step.
复用因子,而非旧解
- 对于一般稠密 $n\times n$ 矩阵,标准消元法需耗费 $O(n^3)$ 次算术运算。每次三角求解需耗费 $O(n^2)$,因此当复用相同的 $P,L,U$ 时,$k$ 个右侧共需耗费 $O(n^3+kn^2)$。
- 对每个右端项重新计算 $Pb$、$y$ 和 $x$。在原始行序中检查残差 $b-Ax$;精确为零验证了精确解。当 $A$ 病态时,仅数值残差小并不能保证解误差小。
求解的哪个阶段?
对于单位对角线L的可逆3x3 PA=LU分解,分别进行置换、前向求解、后向求解和验证。
Using standard dense LU, what is the total arithmetic cost for $k$ right sides of the same invertible $n\times n$ matrix, reusing its factors?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Factor once at cubic cost, then perform two quadratic-cost triangular solves for each right side. This is a general dense estimate.
追踪维数之前的空间
- 现在设 $B:V\to W$ 和 $A:W\to Z$ 为同一域上有限维空间之间的线性映射。乘积 $AB=A\circ B$ 先应用 $B$。记作 $\dim V=n$、$\dim W=m$、$\operatorname{rank}B=r$ 和 $\dim\ker A=s$。
- 由于 $Bv=0$ 蕴含 $A(Bv)=0$ 到 $\ker B\subseteq\ker(AB)$。额外丢失的方向出现在 $Bv$ 非零但位于 $\ker A$ 中的情况。交集 $\operatorname{im}B\cap\ker A$ 包含于 $W$ 中。
推导复合恒等式
- 将 $B$ 限制在 $T:\ker(AB)\to\operatorname{im}B\cap\ker A$ 上。该映射是满射:若 $w=Bv$ 且 $Aw=0$,则 $ABv=0$。其核恰好为 $\ker B$。
- 因此对 $T$ 的秩-零化度定理给出 $\dim\ker(AB)=\dim\ker B+t$,其中 $t=\dim(\operatorname{im}B\cap\ker A)$。等价地,$\operatorname{rank}(AB)=r-t$:只有被 $B$ 实际到达的方向才可能在第二个映射中丢失。
For linear maps $B:V\to W$ and $A:W\to Z$, suppose rank $B=4$ and rank $AB=2$. Give $\dim(\operatorname{im}B\cap\ker A)$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Rank $AB=r-t$, so $t=4-2=2$.
确定中间空间的交集界限
- 对于维数为 $r,s$ 的子空间 $S,K\subseteq W$,写出 $t=\dim(S\cap K)$。恒等式 $\dim(S+K)=r+s-t\le m$ 给出 $t\ge r+s-m$。同样有 $0\le t\le\min(r,s)$。
- $t$ 的下界为 $\max(0,r+s-m)$;上界为 $\min(r,s)$。加上 $\dim\ker B=n-r$ 可得零化度界限,或从 $r$ 中减去 $t$ 可得秩界限。环境维数是 $m$,不一定等于 $n$。
六维范围的两端均可能出现
- 对于$\mathbb R^6$的自同态,设零度分别为$A=2$和$B=3$。则$r=3$、$s=2$、$m=6$,因此$0\le t\le2$和$3\le\dim\ker(AB)\le5$。
- 选择$A=\operatorname{diag}(1,1,1,1,0,0)$。令$B$将其前三个基向量映射到$(e_1,e_2,e_3)$、$(e_1,e_2,e_5)$或$(e_1,e_5,e_6)$,其余三个映射为零。这些选择分别给出$t=0,1,2$及零度$3,4,5$。
开启 $\mathbb R^4$, let $A=\operatorname{diag}(1,1,0,0)$ and let $B$ have nullity $2$. Find every possible nullity of $AB$, and construct B for each value.
比较中间步骤、映射顺序及假设与模型回答。
计算原始五维界限
- 对于$A,B:\mathbb R^5\to\mathbb R^5$,其零度为$1,2$,秩为$B=3$和$0\le t\le1$。因此$AB$的最小可能零度为$2$,最大为$3$。
- 固定$A=\operatorname{diag}(1,1,1,1,0)$。取$B=\operatorname{diag}(1,1,1,0,0)$得$t=0$;取$B=\operatorname{diag}(1,1,0,0,1)$得$t=1$。因此两个界限均可实现。在第一例中,将两个零度相加总是得出错误答案。
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ and $2$, respectively. What is the largest possible nullity of $AB$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Rank $B=3$. The image of $B$ can contain the one-dimensional kernel of $A$, giving nullity $AB=2+1=3$.
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ and $2$, respectively. What is the smallest possible nullity of $AB$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
The intersection can have dimension $\max(0,3+1-5)=0$. Thus the minimum is $2+0=2$, attained by the two diagonal maps in the lesson.
不同的定义域大小可强制产生重叠
- 设$\dim V=7$、$\dim W=4$、$\dim Z=3$,零度分别为$B=4$和$A=2$。则$r=3$、$s=2$和$1\le t\le2$。故零度$AB$的范围从$5$至$6$,且$1≤\operatorname{rank}(AB)≤2$。
- 为实现界限,设定$A(w_1,w_2,w_3,w_4)=(w_1,w_2,0)$。将$V$的前三个基向量映射至$(e_1,e_2,e_3)$以得到$t=1$,或映射至$(e_1,e_3,e_4)$以得到$t=2$;其余四个映射为零。中间空间维数为$4$,而非$7$。
Let $\dim V=7$, $\dim W=4$, nullity $B=4$ and nullity $A=2$ for $B:V\to W$, $A:W\to\mathbb R^3$. What is the smallest possible nullity of $AB$?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Rank $B=3$. The intersection in the four-dimensional middle space has dimension at least $3+2-4=1$, so the minimum nullity is $4+1=5$.
Let $B:\mathbb R^6\to\mathbb R^3$ have nullity $4$, and $A:\mathbb R^3\to\mathbb R^2$ have nullity $2$. Find the sharp bounds for nullity $AB$ and give maps attaining both.
比较中间步骤、映射顺序及假设与模型回答。
反转映射顺序会改变问题
- 即使对于方阵,$AB$和$BA$也不一定具有相同的零度。取$A=\begin{pmatrix}1&0\\0&0\end{pmatrix}$和$B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$。则$AB=B$的秩为$1$,零度为$1$,而$BA=0$的零度为$2$。
- $BA$ 的恒等式使用 $\operatorname{im}A\cap\ker B$ 并加上零化度 $A$。保持实际映射顺序。对于矩形映射,$AB$ 和 $BA$ 甚至可能具有不同的定义域维数,或者某个乘积未定义。
Two square matrices always give the same nullity for AB and BA.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
False. With $A=\operatorname{diag}(1,0)$ and $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$, $AB=B$ has nullity $1$ 但是 $BA=0$ has nullity $2$.
从像中读取等号成立的情形
- 若$\operatorname{im}B\cap\ker A=\{0\}$,则$\ker(AB)=\ker B$:$A$在$B$所达到的像上是单射。可逆的$A$保证此性质,但非必要条件。若$\operatorname{im}B\subseteq\ker A$,则$AB=0$且零度为$AB=\dim V$。
- 若$B$是同构,它将$\ker(AB)$双射地映到$\ker A$,故二者维数相等。它们的核不一定是同一个子空间。一般而言,仅凭零度$A$无法得知其丢失的方向中有哪一个被$B$映射到了。
地图信息保证什么?
使用有限维相容的 B,则 A 满足零度 B=k,dim V=n,且 t=dim(im B ∩ ker A)。
Let $A=\operatorname{diag}(1,0)$ on $\mathbb R^2$ and $B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Find $\ker A$ and $\ker(AB)$. Explain why their dimensions agree but their subspaces differ.
比较中间步骤、映射顺序及假设与模型回答。
复习要点
- 配合$PA=LU$,置换右侧,求解$Ly=Pb$,再求解$Ux=y$。在使用除法前先检查非主元,并验证$Ax=b$。
- 对于$B:V\to W$后接$A:W\to Z$,将零度$B$加到像核交叠维数上。在$W$中界定该交叠,并检查所求结果是极小值、极大值还是定值。
- 零度:线性映射核的维数。
- 前向代入法:从第一行向下求解下三角方程组。
- 后向代入法:从最后一行向上求解上三角方程组。