C++ 中的乔莱斯基分解

引言

Cholesky 分解 是一种主要用于线性代数的数值技术，用于将厄米正定矩阵分解为下三角矩阵及其共轭转置的乘积。该方法在求解线性方程组、计算行列式和执行数值模拟方面特别有效。

在 C++ 中，实现 Cholesky 分解涉及将矩阵分解为下三角分量，从而简化后续的计算和优化。该算法通过更新下三角矩阵的元素来迭代计算 Cholesky 因式分解。

在 C++ 中使用 Cholesky 分解通常涉及设计类或函数来高效地执行矩阵运算，包括矩阵乘法、转置和求解线性系统。此外，在实现过程中，错误处理和内存管理是需要考虑的关键方面。

程序

输出

Original Matrix A:
4 12 -16 
12 37 -43 
-16 -43 98 
Cholesky Decomposition L:
2 0 0 
6 1 0 
-8 5 3

说明

• 矩阵表示

矩阵表示为双精度浮点数的二维向量 (std::vector<std::vector<double>>)。这允许轻松操作矩阵元素。

• Cholesky 分解函数 (choleskyDecomposition)

该函数以矩阵作为输入，并返回下三角 Cholesky 因子矩阵。

它初始化一个空矩阵 L 来存储 Cholesky 因子。

它遍历矩阵的每一行和每一列，计算 Cholesky 因子矩阵 L 的元素。

在每次迭代中，它根据 Cholesky 分解算法计算 L 的元素。

该算法通过对原始矩阵的元素和 L 中先前计算的元素进行求和来计算下三角矩阵 L 的每个元素。

如果当前元素位于对角线上，则使用原始矩阵中相应元素与 L 中先前计算元素的平方和之差的平方根来计算它。

如果当前元素不在对角线上，则使用 L 中先前计算的元素来计算它。

• 显示矩阵函数 (displayMatrix)

此函数用于将矩阵的内容显示到控制台。

它遍历矩阵的每一行，并打印由空格分隔的每个元素。

• 主函数

它定义了一个示例矩阵 A。

它显示原始矩阵 A。

它调用 choleskyDecomposition 函数对矩阵 A 执行 Cholesky 分解。

它显示 Cholesky 因子矩阵 L。

复杂度分析

时间复杂度

• Cholesky 分解算法中的主要操作涉及遍历矩阵行和列的嵌套循环。
• 外层循环运行 n 次，其中 n 是矩阵的行数或列数。
• 对于外层循环的每次迭代，内层循环最多运行 i 次，其中 i 是当前行/列的索引。
• 在内层循环中，存在涉及矩阵乘法和加法的计算，这些通常是常数时间操作。
• 因此，Cholesky 分解算法的总体时间复杂度约为 O(n3)，其中 n 是矩阵的大小。

空间复杂度

• Cholesky 分解算法的空间复杂度主要取决于存储 Cholesky 因子矩阵 L 所需的空间。
• Cholesky 因子矩阵 L 是一个大小为 n×n 的下三角矩阵。
• 由于仅存储矩阵的下三角部分，因此空间复杂度约为 O(n2)。
• 此外，还需要一些辅助空间用于循环计数器和临时存储等变量，但与 Cholesky 因子矩阵所需的空间相比，这些可以忽略不计。
• 因此，Cholesky 分解算法的总体空间复杂度约为 O(n2)。

块状 Cholesky 分解

块状 Cholesky 分解 将矩阵划分为较小的块，并在每个块上执行 Cholesky 分解，从而利用缓存局部性和减少内存访问次数。

这种方法涉及将原始矩阵划分为方形子矩阵（块），并在每个块上独立执行 Cholesky 分解。

通过分解较小的块，算法可以更好地利用处理器缓存并优化内存访问。分解完块后，将块的下三角部分连接起来形成 Cholesky 因子矩阵。

程序

输出

Original Matrix A:
25 15 -5 
15 18 0 
-5 0 11 
Cholesky Decomposition L:
5 15 -5 
3 3 0 
20 120 -nan 

说明

• choleskyBlock 函数

它对矩阵的一个块执行 Cholesky 分解。

它遍历块的行和列，根据 Cholesky 分解算法更新每个元素。

使用内层循环更新元素，这些循环处理乘法和减法运算。

• choleskyBlocked 函数

将矩阵划分为较小的块，并在每个块上执行 Cholesky 分解。

以块大小为步长遍历矩阵，并为每个块调用 choleskyBlock 函数。

处理最后一个块，该块的大小可能小于指定的块大小。

• displayMatrix 函数

将矩阵的内容显示到控制台。

遍历矩阵的每一行，并打印由空格分隔的每个元素。

• 主函数

定义了一个示例矩阵 A。

为块状 Cholesky 分解指定块大小。

显示原始矩阵 A。

调用 choleskyBlocked 函数对矩阵 A 执行块状 Cholesky 分解。

显示生成的 Cholesky 因子矩阵。

复杂度分析

时间复杂度

• 该算法中的主要操作涉及遍历矩阵元素并在嵌套循环中执行算术运算。
• choleskyBlocked 函数中的外层循环运行 O(n/blockSize) 次，其中 n 是矩阵的大小，blockSize 是指定的块大小。
• 在每个块内，choleskyBlock 函数执行 Cholesky 分解，其中涉及额外的嵌套循环。每个块的迭代次数取决于块大小，并且相对恒定。
• 总的来说，块状 Cholesky 分解算法的时间复杂度约为 O(n2/blockSize)。

空间复杂度

• 空间复杂度主要取决于输入矩阵和 Cholesky 因子矩阵的存储。
• 由于输入矩阵 A 和 Cholesky 因子矩阵都表示为双精度浮点数的二维向量，因此它们的总空间复杂度为 O(n2)，其中 n 是矩阵的大小。
• 此外，函数内的循环计数器和临时变量也需要一些辅助空间，但与矩阵的大小相比，这些可以忽略不计。
• 因此，块状 Cholesky 分解算法的总体空间复杂度约为 O(n2)。