知识卡片
正定矩阵求逆可递归缩成块乘法
对称正定矩阵分块后,借舒尔补把求逆拆为两个半阶求逆和常数次半阶矩阵乘法。若乘法时间满足定理的正则条件,递归成本为O(M(n)),从而求逆渐近上不难于乘法。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第28章 矩阵运算 · 查看原书依据
Thus, to invert an n×n symmetric positive-definite matrix, invert two n/2×n/2 matrices in steps 2 and 5; perform four multiplications of n/2 × n/2 matrices in steps 3, 4, 6, and 7; plus incur an additional cost of O(n2)
参考来源
- 位置:《算法导论(第4版)》第28章《矩阵运算》(OEBPS/chapter028.xhtml,文本字符[25000,30000))。
- 结论依据:定理28.2 对称正定情形,`OEBPS/images/Art_P936.jpg` 给舒尔补 S=D−CB⁻¹Cᵀ,`Art_P937.jpg` 给分块逆,`Art_P938.jpg`(式28.15)给递推;在 M(n)=Ω(n²) 和定理正则条件下 I(n)=O(M(n))。
- 公式图核读:I(n)≤2I(n/2)+4M(n/2)+O(n²)=2I(n/2)+O(M(n))=O(M(n))。
- 原始内容:Thus, to invert an n × n symmetric positive-definite matrix, invert two n /2× n /2 matrices in steps 2 and 5; perform four multiplications of n /2 × n /2 matrices in steps 3, 4, 6, and 7; plus incur an additional cost of O ( n 2 )