多个线性方程组求解:LU 分解 vs 高斯消元法
已知有形如 Ax=b1, Ax=b2, ..., Ax=bm 的 m 个线性方程组。在求解这 m 个线性方程组的过程中,可以采用下面两种方法之一:
(1) 对每个线性方程组使用高斯消元法求解; (2) 先将矩阵 A 进行 LU 分解,再将求解。
请问:上面哪种解法更好? 说明理由。(只考虑乘除法的运算次数,且乘除法看作相同的运算)
第二种解法更好。
理由如下:
在第一种解法中,对每个线性方程组使用高斯消元法求解,需要进行 m 次高斯消元运算。每次高斯消元运算的乘除法运算次数为 O(n^3),因此总的乘除法运算次数为 O(mn^3)。
而在第二种解法中,先将矩阵 A 进行 LU 分解,需要进行一次 LU 分解运算,其乘除法运算次数为 O(n^3/3)。然后对于每个线性方程组,只需要进行一次前代和一次回代运算,其乘除法运算次数均为 O(n^2)。因此总的乘除法运算次数为 O((m+1)n^3/3)。
可以看出,当 m 比较大时,第二种解法更加高效。因此,对于多个线性方程组求解,推荐使用 LU 分解方法。
原文地址: https://www.cveoy.top/t/topic/mS0b 著作权归作者所有。请勿转载和采集!