crout分解法(1)

数值分析 1 CroutCrout 分解法解线性方程组的算法及程序设计分解法解线性方程组的算法及程序设计 摘要 在自然科学和工程技术中很多问题的解决常常归结为解线性方程组 而方程组的系 数矩阵大致分为两种 一种是低阶稠密矩阵 阶数不超过 150 另一种是大型稀疏矩阵 矩阵 阶数高且零元素较多 解低阶稠密矩阵和某些特殊形式的大型稀疏矩阵宜应用直接法 例如 高 斯消元法 矩阵三角分解法 对于一般形式的系数矩阵 Crout 分解法是一种有效的方法 本文就 Grout 分解法给出其计算公式的推导过程及算法程序 正文 一 Crout 方法解线性方程组的算法 给定线性方程组 Ax b 其中系数矩阵 A aij n n 为可逆的 x x1 x2 xn T b b1 b2 bn T 为常数项列向量 Crout 分解后 A LU L 和 U 的结构为 1 公式推导 由 A LU 及矩阵乘积和相等概念 有 ai1 li1 li2 lii 0 0 li1 i 1 2 n 0 0 0 1 a1j l11 0 0 0 0 l11 u1j j 1 2 n 0 0 1 1 2 1 jj j j u u u 得 li1 ai1 u1j a1j l11 i j 1 2 n 和相等 即可求得A利用矩阵的乘法与 1 1 1 L 2 112 321 333231 2221 11 ij u ij l u uu U llll lll ll l n n nnnnn 数值分析 2 当 i j 时 aij l11 li2 lii 0 0 0 0 1 1 2 1 jj j j u u u i k kjiku l 1 当 ij 时 aij l11 li2 lii 0 0 0 0 1 1 2 1 jj j j u u u ij j k kjik lul 1 1 得 lij aij j 2 3 i i 2 3 n 1 1 j k kjiku l uij aij lii i 2 3 n j i 1 i 2 n 1 1 i k kjiku l 2 具体算法如下 对 A 作 LU 分解 由 A LU 及矩阵的乘法原理可得 lij aij j 1 2 i i 1 2 n 1 1 j k kiiku l uij aij lii j i 1 i 2 n i 1 2 n 1 1 i k kiiku l 解两个三角型方程组 由 A LU 及 Ax b 可得 L Ux b 令 Y y 1 y 2 y n T Ux 则 L Y b 于是求解 Ax b 就被化为求解下三角型方程组 L Y b 及单位上三角型方程组 Ux Y a 先解下三角型方程 LY b 由 l11y1 b1 l21y1 l22y2 b2l11 ln1y1 ln2y2 lnnyn bn 数值分析 3 所以y1 b1 l11 yi bi lii i 2 3 n k i k iky l 1 1 b 再解单位上三角型方程组 Ux Y 由 UX Y 得 x1 u12x2 u1nxn y1 x2 u2nxn y2 xn 1 un 1nxn yn 1 xn yn 利用回代解法可得方程组 AX b 的解为 xn yn xi yi i n 1 2 1 n ik xu 1 kik 二 Crout 方法解线性方程组的程序 1 程序代码 include stdio h include math h 头文件 define N 20 自定义 N 20 int main 主函数 int i j k int size float a N N l N N u N N float b N x N y N 定义变量 printf t t tCrout 分解法解方程组 n printf 请输入方阵 A 的 n scanf d printf n printf 请输入方程组的系数 n for i 0 i size i for j 0 j size j scanf f 输入方程组系数矩阵 a printf n 请输入方程组的 y n for i 0 i size i scanf f 输入结果矩阵 b printf n 方阵 A 为 n for i 0 i size i for j 0 j size j printf f a i j 输出 a printf n printf n 方程组 y 为 n 数值分析 4 for i 0 i size i printf f b i 输出 b printf n for i 0 i size i u i i 1 定初始值 令 u i i 1 for i 0 i size i for j i 1 j size j l i j 0 定初始值 令 l i j 0 for j 0 j size j for i j 1 i size i u i j 0 定初始值 令 u i j 0 l 0 0 a 0 0 for i 1 i size i l i 0 a i 0 计算第一行的 l u 0 i a 0 i l 0 0 计算第一列的 u for i 1 i size 1 i for j 1 j i j 计算第 2 行到第 size 1 行的 l l i j a i j for k 0 k j k l i j l i j l i k u k j printf n for j i 1 j size j 计算第 2 行到第 size 行的 u u i j a i j for k 0 k i 1 k u i j u i j l i k u k j u i j u i j l i i printf n 数值分析 5 for j 1 j size j 计算第 size 行的 l l size 1 j a size 1 j for k 0 k j 1 k l size 1 j l size 1 j l size 1 k u k j printf n printf 输出矩阵 L i j n for i 0 i size i for j 0 j size j printf f l i j printf 输出下三角矩阵 l printf n printf 输出矩阵 U i j n for i 0 i size i for j 0 j size j printf f u i j printf 输出单位上三角矩阵 u printf n y 0 b 0 l 0 0 给 y 0 初始值 for i 1 i size i 计算 y i 的值 y i b i for k 0 k i 1 k y i y i l i k y k 计算公式 y i y i l i i print