求线性方程组的解

wuchangjian2021-11-05 13:29:25编程学习

求线性方程组的解

  • 直接法
    • 高斯顺序消去法
      • 过程
      • 运算次数
      • 优缺点
      • 代码实现
  • 迭代法

直接法

高斯顺序消去法

过程

高斯顺序消去法的过程如下:

  1. 高斯消去过程
    k = 1 , 2 , . . . , n − 1 k = 1, 2, ..., n-1 k=1,2,...,n1,如果 A [ k ] [ k ] ≠ 0 A[k][k] \neq 0 A[k][k]=0,
    则对 i = k + 1 , k + 2 , . . . , n i = k+1, k+2, ..., n i=k+1,k+2,...,n,计算 l i k = A [ i ] [ k ] A [ k ] [ k ] l_{ik} = \frac{A[i][k]}{A[k][k]} lik=A[k][k]A[i][k]
    之后对 j = k , k + 1 , . . . , n j = k, k+1, ..., n j=k,k+1,...,n,计算 A [ i ] [ j ] = A [ i ] [ j ] − l i k × A [ k ] [ j ] A[i][j] = A[i][j] - l_{ik} \times A[k][j] A[i][j]=A[i][j]lik×A[k][j]以及 B [ i ] = B [ i ] − B [ k ] × l i k B[i] = B[i] - B[k] \times l_{ik} B[i]=B[i]B[k]×lik
  2. 回代过程
    • 计算 X [ n ] = B [ n ] A [ n ] [ n ] X[n] = \frac{B[n]}{A[n][n]} X[n]=A[n][n]B[n]
    • k = n − 1 , . . . , 1 k = n-1,..., 1 k=n1,...,1,计算 X [ k ] = 1 A [ k ] [ k ] × ( B [ k ] − ∑ j = k + 1 n A [ k ] [ j ] × X [ j ] ) X[k] = \frac{1}{A[k][k]} \times (B[k] - \sum_{j=k+1}^{n}A[k][j] \times X[j]) X[k]=A[k][k]1×(B[k]j=k+1nA[k][j]×X[j])

运算次数

消元过程所需乘除运算次数为
1 3 n 3 + 1 2 n 2 − 5 6 n \frac{1}{3}n^{3}+\frac{1}{2}n^{2}-\frac{5}{6}n 31n3+21n265n

回代过程所需乘除运算次数为
1 2 n ( n + 1 ) \frac{1}{2}n(n+1) 21n(n+1)
因此,高斯顺序消元法总的乘除运算次数
1 3 n 3 + n 2 − 1 3 n \frac{1}{3}n^{3}+n^{2}-\frac{1}{3}n 31n3+n231n

优缺点

优点:相较于Cramer法则,二者计算次数有天壤之别,其速度比Cramer法则快很多
缺点:高斯顺序消元过程能进行下去的充要条件是系数矩阵 A A A k k k阶顺序主子式 Δ k ≠ 0 ( k = 1 , 2 , . . . , n − 1 ) \Delta_{k} \neq 0(k=1, 2, ..., n-1) Δk=0(k=1,2,...,n1),即
Δ k = ∣ a 11 ⋯ a 1 k ⋮ ⋮ a k 1 ⋯ a k k ∣ ≠ 0. \Delta_{k} = \left | \begin{matrix} a_{11} & \cdots & a_{1k}\\ \vdots & & \vdots\\ a_{k1} & \cdots & a_{kk} \end{matrix} \right | \neq 0. Δk=a11ak1a1kakk=0.
但是,当 ∣ a k k ( k ) ∣ ≈ 0 \left | a_{kk}^{(k)} \right | \approx 0 akk(k)0 ∣ a k k ( k ) ∣ \left | a_{kk}^{(k)} \right | akk(k)相对于 ∣ a i k ( k ) ∣ ( i = k + 1 , k + 2 , ⋯   , n ) \left | a_{ik}^{(k)} \right |(i = k+1, k+2,\cdots, n) aik(k)(i=k+1,k+2,,n)比较小时,消元过程在计算机计算时产生的舍入误差将可能导致计算结果误差较大( a k k ( k ) a_{kk}^{(k)} akk(k)是第k次消元前,系数矩阵 A A A k k k k k k列的元素, a i k ( k ) a_{ik}^{(k)} aik(k)同理)。

代码实现

// 求AX = B的解
// A ---- n × n矩阵
// 消元过程
for (int k = 0; k < n - 1; k++)
{
    if (A[k][k])
    {
        for (int i = k + 1; i < n; i++)
        {
            double lik = A[i][k] / A[k][k];
            for (int j = k; j < n; j++)
            {
                A[i][j] = A[i][j] - lik * A[k][j];
            }
            B[i] = B[i] - lik * B[k];
        }
    }
}

// 回代过程
X[n - 1] = B[n - 1] / A[n - 1][n - 1];
for (int k = n - 2; k >= 0; k--)
{
    double sum = 0.0;
    for (int j = k + 1; j < n; j++)
    {
        sum += A[k][j] * X[j];
    }
    X[k] = (B[k] - sum) / A[k][k];
}

迭代法

相关文章

小Q学姐过圣诞节

    #include <algorithm> #include &l...

seq命令

-s指定输出的分隔符,默认为\n,即默认为回车换行-W指定为...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。