知识卡片

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

正定矩阵求逆可递归缩成块乘法

理解等级:高级

对称正定矩阵分块后,借舒尔补把求逆拆为两个半阶求逆和常数次半阶矩阵乘法。若乘法时间满足定理的正则条件,递归成本为O(M(n)),从而求逆渐近上不难于乘法。

这张卡片看不懂?

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