知识卡片
一次分解可解多个右端方程
LUP 分解把带换行的高斯消元写成 PA=LU:P 是行置换矩阵,L、U 分别是下三角与上三角矩阵。它只依赖系数矩阵 A。求解 Ax=b 时先解下三角方程 Ly=Pb,再解上三角方程 Ux=y。
前代和回代各求一个未知量时,要与已知分量做长度至多 n 的内积;全程约有 1+2+⋯+(n−1) 次乘加,故各为 Θ(n²)。多个方程若只更换右端 b,可复用同一分解;每个新右端只需两次三角求解,k 个右端累计 Θ(kn²),一次性的分解成本另计。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第28章 矩阵运算 · 查看原书依据
Since the LUP decomposition depends on A but not b, you can run LUP-SOLVE on a second set of equations of the form Ax = b′ in Θ(n2) additional time. In general, once you have the LUP decomposition of A, you can solve, in Θ(kn2) time, k versions of the
参考来源
- 位置:《算法导论(第4版)》第28章《矩阵运算》(OEBPS/chapter028.xhtml,文本字符[20000,25000))。
- 结论依据:原文说明 LUP 分解依赖 `A` 而不依赖 `b`,并给出每个新右端调用 LUP-SOLVE 的 `Θ(n²)` 成本与 `k` 个右端的 `Θ(kn²)` 总成本;`PA=LU` 是该节已定义的分解关系。
- 原始内容:Since the LUP decomposition depends on A but not b , you can run LUP-S OLVE on a second set of equations of the form Ax = b ′ in Θ( n 2 ) additional time. In general, once you have the LUP decomposition of A , you can solve, in Θ( kn 2 ) time, k versions of the