将旋转功能添加到 Doolittle 算法

Question

到目前为止，我已经有了用于 LU 分解的代码。它接受一个输入数组，它 returns 下三角矩阵和上三角矩阵。

void LUFactorization ( int d, const double*S, double*L, double*U )
{
   for(int k = 0; k < d; ++k){
       if (
      for(int j = k; j < d; ++j){
         double sum = 0.;
         for(int p = 0; p < k; ++p) {
             sum+=L[k*d+p]*L[p*d+j];
             cout << L[k*d+p] << endl;
         }
         sum = S[k*d+j] - sum;
         L[k*d+j]=sum;           
        U[k*d+j]=sum;
      }
      for(int i = k + 1; i < d; ++i){
         double sum=0.;
         for(int p = 0; p < k; ++p) sum+=L[i*d+p]*L[p*d+k];
         L[i*d+k]=(S[i*d+k]-sum)/L[k*d+k];
      }
   }

   for(int k = 0; k < d; ++k){
      for(int j = k; j < d; ++j){
         if (k < j) L[k*d+j]=0;
         else if (k == j) L[k*d+j]=1;
      }
   }
}

有什么方法可以使它适应执行行交换？如果没有，我可以使用其他算法吗？

谢谢

Answer 1

使用主元进行 LU 分解的通常方法是存储一个置换数组 P，它被初始化为恒等置换 (P={0,1,2,...,d - 1})，然后交换 P 中的条目而不是在 S

中交换行

如果您有此排列数组，则每次访问 S 都必须使用 P[i] 而不是 i 作为行号。

请注意 P 本身就是输出的一部分，因为它表示的置换矩阵使得
P*A = L*U，所以如果你想用它来求解线性方程组，你必须在应用向后和向前替换之前在右侧应用 P

将旋转功能添加到 Doolittle 算法

Adding pivoting functionality to a Doolittle algorithm

c++

algorithm

linear-programming

factorization