Phân tích LU và chỉ số nhân của ánh xạ hợp thành
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| nullity/ˈnʌlɪti/ | số không |
| forward substitution/ˈfɔːwəd ˌsʌbstɪˈtjuːʃn/ | thay thế tiến |
| back substitution/bæk ˌsʌbstɪˈtjuːʃn/ | Solving an upper-triangular system from the last equation upward. |
Factor once, solve many
- With $A = LU$, each new right side costs two triangular solves instead of a full elimination. But the solves must go in the right order.
- GRE linear algebra tests LU solving and the nullity 零度 of composed maps.
LU and pivoting
- $L$ lower triangular (often unit diagonal), $U$ upper triangular. Invertible is not enough for $A = LU$: a zero leading pivot needs a row swap, $PA = LU$.
- With $PA = LU$, permute $b$ too.
Some invertible matrices need a row exchange before an LU factorisation exists.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
True. A zero leading pivot, as in $\begin{pmatrix}0&1\\1&0\end{pmatrix}$, needs a permutation: $PA = LU$.
Forward, then back
- Forward substitution 前代 solves $Ly = b$ top to bottom; back substitution 回代 then solves $Ux = y$ bottom to top.
$L = \begin{pmatrix} 1&0&0\\2&1&0\\-1&3&1 \end{pmatrix}$, $U = \begin{pmatrix} 2&1&-1\\0&3&2\\0&0&4 \end{pmatrix}$, $b = (-1,-1,12)$. Forward: $y = (-1, 1, 8)$. Back: $x_3 = 2$, $x_2 = (1 - 4)/3 = -1$, $x_1 = (-1 + 1 + 2)/2 = 1$. So $x = (1, -1, 2)$.
- Cost: factorisation $\sim n^3$; each triangular solve $\sim n^2$.
Forward or back substitution?
Match each step of an LU solve to its phase.
$L = \begin{pmatrix} 1&0\\3&1 \end{pmatrix}$, $U = \begin{pmatrix} 2&1\\0&1 \end{pmatrix}$, $b = (2, 7)$. Solve $LUx = b$; give $x_1$.
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
y = (2, 1); x₂ = 1, x₁ = (2 − 1)/2.
Put the steps for solving $PAx = Pb$ with $PA = LU$ in order.
Độ khó 3/5 · 200 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Forward, then back.
Nullity of a composition
- For $B: V \to W$, $A: W \to Z$: $\ker B \subseteq \ker(AB)$, and the extra vectors are those $B$ sends into $\ker A$.
- $\dim\ker(AB) = \dim\ker B + \dim(\operatorname{im} B \cap \ker A)$.
Bounding the intersection
- Subspaces of dimensions $r, s$ in an $m$-dimensional space meet in dimension between $\max(0, r + s - m)$ and $\min(r, s)$.
- On $\mathbb R^6$ with nullity $A = 2$, nullity $B = 3$: rank $B = 3$, intersection 0 to 2, so nullity $AB$ is 3 to 5.
On $\mathbb R^5$, nullity $B = 2$ and nullity $A = 1$. What is the largest possible nullity of $AB$?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
rank B = 3; the intersection is at most 1.
Same maps: what is the smallest possible nullity of $AB$?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
nullity(AB) = nullity B + dim(im B ∩ ker A). Here im B has dimension 3 and ker A dimension 1 in ℝ⁵, so the intersection can be as small as max(0, 3 + 1 − 5) = 0. The smallest nullity is 2 + 0 = 2.
Recap
- Solve $Ly = Pb$, then $Ux = y$.
- Nullity$(AB)$ = nullity $B$ + $\dim(\operatorname{im} B \cap \ker A)$ — not a plain sum.
- Bound intersections with $\max(0, r + s - m) \le \dim \le \min(r, s)$.
- back substitution: Solving an upper-triangular system from the last equation upward.