随着现代工业和科学的发展,线性方程组的应用出现在经济管理、工程计算等各个领域,许多的应用会导出一些具有特殊结构的稀疏线性方程组的计算问题[1, 2].伴随着这些方程组的出现,寻找简便而且准确的求解方法就显得十分重要而且具有现实意义.
在对角线性方程组的解法中,追赶法是一类比较常用的方法,因其计算公式简单,运算量和存储量小,在科学领域中被广泛运用,倍受广大科研技术人员关注.近年来,关于对角型线性方程组的追赶法,已经有了比较细致的研究,主要有求解三对角线性方程组、循环三对角线性方程组、五对角线性方程组、拟五对角线性方程组、对称循环五对角线性方程组和七对角线性方程组的各类追赶法,参见文献[3-9].但目前尚未见文献探讨反五对角与拟反五对角方程组的追赶法,而反五对角与拟反五对角方程组是反对角线性方程组中比较常见的一类,在力学、流体力学、工程学等领域有很重要的应用(例如神舟飞船运行轨道的某些计算问题可归结为此类线性方程组的求解问题).因此,本文将借鉴文献[6, 7]的思想,建立求解反五对角线性方程组和拟反五对角线性方程组的追赶法.
定义1 若方阵$A=(a_{ij})$的元素当$1\leq i \leq n-3$, $1\leq j \leq n-i-2$且$4\leq i \leq n$, $n-i+4\leq j \leq n$时, 均有$a_{ij}=0$, 则称此矩阵为反五对角矩阵.
引理[9] 对于任意阶数不小于3的反五对角矩阵$A$, 一般记:
若有$d_i, e_i\neq0$, 且$|c_1|\geq|d_1|+|e_1|$, $|c_2|\geq|b_2|+|d_2|+|e_2|$, $|c_{n-1}|\geq|a_{n-1}|+|b_{n-1}|+|d_{n-1}|$, $|c_n|\geq|b_n|+|a_n|$, $|c_i|\geq|a_i|+|b_i|+|d_i|+|e_i|$$(i=3, \cdots, n-2)$, 其中至少有一个不等号严格成立,则此矩阵的各阶顺序主子式不等于零,存在唯一的分解$A=LU$.若上述条件不变,其中$|c_n|>|b_n|+|a_n|$, 则称$A$为具非零元素链对角占优矩阵.
在实际问题中, 经常遇到如下形式的线性方程组
这种方程组称为反五对角线性方程组, 简记为$Ax=f$.
假设
此时, $A$为具非零元素链对角占优矩阵,可实现矩阵$LU$分解.分解形式为
利用矩阵乘法,可得
可将求解方程组$Ax=f$化为依次求解$\left\{\begin{array}{ll} Ly=f, \\ Ux=y. \\ \end{array} \right.$
算法1
第一步:解方程$Ly=f$, 即“追”过程, 算法如下:
第二步:解方程$Ux=y$, 即“赶”过程,算法如下:
其中$l_i, m_i, p_i, q_i$的计算见(2.3) 式.
上述算法1就是求解反五对角线性方程组的追赶法.
算例演示:用追赶法求解反五对角线性方程组:
有
利用以上结果, 我们可以得到关于$x_i(i=1, 2, 3, 4, 5, 6, 7)$的解:
在实际问题中,由于误差的原因,经常遇到如下形式的线性方程组
这种方程组称为拟反五对角线性方程组,简记$Ax=f$.可将系数矩阵$A$分解为3个矩阵的乘积$A=LUD$, 其中
矩阵元素的计算公式如下:
可将求解方程组$Ax=f$化为依次求解$\left\{\begin{array}{cl} Lz=f, \\ Uy=z, \\ Dx=y.\\ \end{array} \right.$
算法2
第一步:解方程$Lz=f$, 即“追”过程, 算法如下:
第二步:依次求解$Uy=z$, $Dx=y$, 即“赶”的过程, 算法如下:
其中$p_i, g_i, h_i, q_i, t_i, s_i$的值的计算见(3.3) 式.
上述算法2就是求解拟反五对角线性方程组的追赶法.
算例演示:用追赶法求解拟反五对角线性方程组:
利用以上结果, 我们最终可以得到关于$x_i(i=1, 2, 3, 4, 5, 6)$的解:
本文通过$LU$分解推导出了反五对角线性方程组的追赶法.针对拟反五对角线性方程组的特点,沿用$LU$分解和追赶法的基本思想,把拟反五对角线性方程组的系数矩阵$A$分解成3个矩阵的乘积$LUD$,与$LU$算法相比,虽然增加了一个矩阵$D$,可是简化了推导过程的复杂度.追赶法求解n阶反五对角线性方程组只需要$O(11n)$的运算量,追赶法求解$n$阶拟反五对角线性方程组的运算量仅为$O(39n)$,运算量比较小.