在Statlect上搜索概率和统计术语
统计列克特
指数 > 矩阵代数

LU分解

通过 博士

如果满足以下条件,则称方阵具有LU分解(或LU分解) 它可以写为下三角(L)和上三角的乘积 三角(U)矩阵。

并非所有平方矩阵都有LU分解,因此可能有必要 在获得矩阵分解之前对矩阵的行进行置换。

目录

定义

我们从定义开始。

定义 A $ Kimes K $ 矩阵 A 当且仅当存在一个 下三角 $ Kimes K $ 矩阵 $ L $ 上三角 $ Kimes K $ 矩阵 美元 这样 [eq1]

下面是LU分解的一些简单示例。

2元2元 矩阵[eq2]具有 以下LU 分解:[eq3]

3美金3美金 矩阵 [eq4]能够 被写 如 [eq5]

存在与独特

我们从关于存在的负面结果开始。

主张 并非所有平方矩阵都有LU分解。

证明

只需提供一个 反例。拿 2元2元 可逆矩阵 [eq6]假设 A 具有LU分解 [eq7]与 因素[eq8][eq9]计算 的 产品[eq10]现在, [eq11] 暗示[eq12]哪一个 反过来意味着至少一个 $ L_ {11} $$ U_ {11} $ 必须为零。结果,以下至少一项 $ L $美元 是不可逆的(因为 三角矩阵是 仅当对角线项为非零时才可求逆)。这是在 与事实相矛盾 A 是可逆的,因此, $ L $美元 必须是可逆的(请参阅有关 产品的可逆性)。 因此,我们通过矛盾证明了 A 不能进行LU分解。

第二个负面结果涉及唯一性。

主张 如果矩阵具有LU分解,则它不是唯一的。

证明

假设一个 $ Kimes K $ 矩阵 A 有一个LU 分解[eq13]采取 任何 $ Kimes K $ 对角矩阵 $ D $ 其对角线项均为非零。然后, $ D $ 是可逆的 $ D ^ {-1} $ 也是对角线,我们可以 写[eq14]A 对角矩阵 $ D $ 是下三角形,并且 的 两个下三角矩阵的乘积是下三角 。因此 $ LD $ 是较低的三角形。倒数 $ D ^ {-1} $, 对角线是上三角形。由于两个上三角的乘积 矩阵是上三角,我们有 $ D ^ {-1} U $ 是上三角形。因此,通过改变矩阵 $ D $, 我们能够得到无穷大的因式分解 A 变成下三角矩阵 $ LD $ 和上三角矩阵 $ D ^ {-1} U $.

存在的充分条件

现在,我们为LU的存在提供了一些充分的条件 矩阵分解。

主张A 成为 $ Kimes K $ 矩阵。如果 A 可以减少到 行梯队 形成 通过 高斯型 淘汰 无需交换两行,然后 A 具有LU分解。

证明

高斯消除允许减少 A 到矩阵 美元 通过基本操作以梯队形式排列。如果 n 执行基本操作,然后我们可以 写[eq15]哪里 [eq16] 基本矩阵。的 矩阵 美元 是上三角的,因为 a 行梯形形式的方阵是上三角。由于没有排 互换是必要的,任何矩阵 $ E_ {i} $ 用于将一行的倍数添加到其下一行。通过写下任何 这样的矩阵的实例,可以看出所有矩阵 $ E_ {i} $ 是较低的三角形,并且其主要对角线上的所有条目都不为零, 这样它们是可逆的。由于下三角形的乘积和倒数 矩阵是较低的三角形,我们可以 写[eq17]哪里 矩阵 [eq18]是 下三角。

PA = LU:如何始终获得具有排列的LU分解

我们已经证明并非所有平方矩阵都具有LU分解。然而, 我们总是可以置换矩阵的行(即重复交换它们) 从而获得LU分解,如以下命题所示。

主张A 成为 $ Kimes K $ 矩阵。然后,存在一个 置换矩阵 $ P $ 这样 $ PA $ 有一个LU 分解:[eq19]哪里 $ L $ 是下三角形 $ Kimes K $ 矩阵和 美元 是上三角形 $ Kimes K $ 矩阵。

证明

通过执行 高斯消去,我们 可以减少 A 到矩阵 美元 行梯形形式。此外,在执行过程中执行的基本操作 高斯消除可以通过使用 基本矩阵。如果 n 执行基本操作以减少 A 排梯形表格,那么我们可以 写[eq20]哪里 [eq16] 是基本矩阵。首先要注意的是 行梯形的方阵 形式是上三角。因此, 美元 是上三角形。基本矩阵 $ E_ {i} $用过的 在高斯消除中可以是1)置换矩阵 $ P_ {i} $ 用于互换两行或2)矩阵 $ L_ {i} $ 用于将一行的倍数添加到其下一行。立即进行验证 所有的矩阵 $ L_ {i} $ 是较低的三角形,并且其主要对角线上的所有条目都不为零, 这样它们是可逆的。假设第一个置换矩阵我们 遇到就位 $ j $, 这样我们 有[eq22]记得 置换矩阵是正交的,即其逆等于 转置。因此, [eq23]和 我们可以写 [eq24]要么[eq25]哪里[eq26]对于 $ i = 1,ldots,j-1 $. 正如我们在 讲座 基本矩阵矩阵 $ L_ {i} $, 用于添加 $ lpha $$ r $-th 排到 $ s $-th 可以将行写为对身份的更新 矩阵:[eq27]哪里 $ M $ 是一个矩阵,其所有条目均为零,除了 $ M_ {sr} = $ $ lpha $. 在我们的情况下,即在高斯消除算法的情况下, 有那个 $r<s$. 此外,[eq28]我们 需要分析在行和列上执行的排列 $ M $ 通过 $ P_ {j} $$ P_ {j} ^ {op} $. 如果相乘 $ P_ {j} M $ 互换 $ t $-th 和 $ u $-th 的行 $ M $, 那么我们有 $r<t<u$ 因为在高斯消除算法中,由 $ P_ {j} $ 在由执行的行添加之后 $ L_ {i} $. 如果 $s
eq t$$s
eq u$, 行交换不影响的非零元素 $ M $. 相反,如果 $ s = t $ 要么 $ s = u $, 非零元素将移至另一行( $ u $-th 或者 $ t $-th), 但仍然在 $ r $-th 柱。它也保持在主对角线以下,因为 $r<t<u$. 的列互换 $ t $-th 和 $ u $-th 的列 $ P_ {j} M $ 由...执行 $ P_ {j} ^ {op} $ 不会影响非零条目,因为后者位于 $ r $-th 列和 $r<t<u$. 因此,改造后 [eq29], 的唯一非零元素 $ M $ 保持在同一列上并可以更改行,但仍保持在主列之下 对角线。因此, $ widetilde {L} _ {i} $ 对于以下三角形 $ i = 1,ldots,j-1 $. 此外, $ widetilde {L} _ {i} $ 是可逆的,因为它是可逆矩阵的乘积。我们现在可以 继续:每次该矩阵之一 [eq30] 在里面 方程[eq25]是 一个置换矩阵,我们用它置换所有下三角 右边的矩阵(仍为三角形)。最后,我们 得到[eq32]哪里 $ J_ {1} $ 是三角形基本矩阵的索引集,并且 $ J_ {2} $ 是置换矩阵的索引集。我们可以 写[eq33]哪里[eq34][eq35]我们 有那个 $ P $ 是置换矩阵,因为置换矩阵的乘积是 置换矩阵此外, $ L $ 是下三角的,因为下三角的乘积和倒数 矩阵是较低的三角形。

强烈建议阅读上述命题的证明,因为 一个有建设性的证明:它显示了LU分解是如何计算的 使用 高斯消去 算法.

如何使LU和PA = LU分解唯一

虽然我们已经说明了如何保证LU分解的存在, 唯一性问题仍有待解决。我们已经在上面显示了 LU分解不是唯一的。但是,通过对以下其中一项添加约束 通过这两个三角形矩阵,我们也可以实现唯一性。约束我们 强加的是两个三角形矩阵之一是单位三角形(即 对角项均等于1的三角矩阵)。

主张A 成为 $ Kimes K $ 矩阵和 $ P $ a $ Kimes K $ 置换矩阵使得 $ PA $ 具有LU分解。那如果 A 是可逆的,有一个独特的 $ Kimes K $ 下三角矩阵 $ L $ 所有对角线项等于1且唯一 $ Kimes K $ 上三角矩阵 美元 这样 那[eq36]

证明

LU分解的存在 [eq37]具有 上面已经证明了。如果矩阵 $ L $ 不是单位三角形,那么我们可以 写[eq38]哪里 $ D $ 是一个对角矩阵,其对角线等于的对角线 $ L $. 注意矩阵 $ D ^ {-1} $ 定义明确,因为 A 是可逆的,这保证了 $ L $ 是可逆的,并且其主对角线上的元素非零(有关此内容,请参见 点以下)。 然后,[eq39]是 单位下三角和 [eq40]是 上三角形。因此,存在一个 因式分解[eq41]满意的 命题中陈述的特性。假设还有另一个这样的 因式分解[eq42]然后,[eq43]注意 那:1) $ L_ {1} $$ L_ {2} $ 是可逆的,因为它们的所有对角线项都不为零; 2) $ P $ 是可逆的,因为任何置换矩阵都是; 3) A 通过假设是可逆的。因此, [eq44]是 可逆的。因此,我们 有[eq45] 我们 我知道 下(上)三角矩阵的逆值较小 (上)三角,以及两个下(上)三角矩阵的乘积 较低(上方)三角形。因此, $ L_ {2} ^ {-1} L_ {1} $ 下三角和 $ U_ {2} U_ {1} ^ {-1} $ 是上三角形。这两个矩阵相等,只有在 它们是对角矩阵。都 $ L_ {1} $$ L_ {2} ^ {-1} $ 是单位三角形,因为单位三角形矩阵的逆是单位 三角(如关于三角矩阵的演讲所证明的 的条目 $ L_ {2} ^ {-1} $ 等于的对应对角线项的倒数 $ L_ {2} $)。 因此,不仅是产品 $ L_ {2} ^ {-1} L_ {1} $ 是对角线,但其所有对角线项均等于1。 话,[eq46]哪一个 暗示[eq47]此外,[eq48]哪一个 暗示[eq49]从而, $ L_ {1} $$ U_ {1} $ 是独一无二的

请注意,以上命题也适用于不需要 被置换为LU分解(即 $ P = I $)。

如何引用

请引用为:

Taboga, Marco (2017). "LU分解", 列克特ures on 矩阵 algebra. //www.junruiqiche.com/matrix-algebra/lu-decomposition.

这本书

该网站上提供的大多数学习材料现在都以传统教科书格式提供。