知识卡片

普通读书笔记卡 · 3683.a.5

一次分解可解多个右端方程

理解等级:中级

LUP 分解把带换行的高斯消元写成 PA=LU:P 是行置换矩阵,L、U 分别是下三角与上三角矩阵。它只依赖系数矩阵 A。求解 Ax=b 时先解下三角方程 Ly=Pb,再解上三角方程 Ux=y。

前代和回代各求一个未知量时,要与已知分量做长度至多 n 的内积;全程约有 1+2+⋯+(n−1) 次乘加,故各为 Θ(n²)。多个方程若只更换右端 b,可复用同一分解;每个新右端只需两次三角求解,k 个右端累计 Θ(kn²),一次性的分解成本另计。

这张卡片看不懂?

已有反馈 · 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