知识卡片
带主元置换仍保持三次方耗时
LUP每轮额外扫描当前列并交换行,核心舒尔补更新仍由三重循环主导,因此总耗时Θ(n³),与无置换LU同阶。
选择主元改善可计算性和稳定性,渐近成本不升阶。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第28章 矩阵运算 · 查看原书依据
Because of its triply nested loop structure, LUP-DECOMPOSITION has a running time of Θ(n3), which is the same as that of LU-DECOMPOSITION. Thus, pivoting costs at most a constant factor in time. Exercises 28.1-1 Solve the equation by using forward substitution.
参考来源
- 位置:《算法导论(第4版)》第28章《矩阵运算》(OEBPS/chapter028.xhtml,文本字符[20000,25000))。
- 结论依据:原文给出主元策略、求解成本或块矩阵复杂度归约,并明确前提条件。
- 原始内容:Because of its triply nested loop structure, LUP-D ECOMPOSITION has a running time of Θ( n 3 ), which is the same as that of LU-D ECOMPOSITION . Thus, pivoting costs at most a constant factor in time. Exercises 28.1-1 Solve the equation by using forward substitution.