Chap3 线性代数方程组 ¶

系数矩阵类型 ¶

低阶稠密矩阵
大型稀疏矩阵 ( 矩阵中 0 元素较多 )
三对角矩阵 ( 非 0 元素集中于主对角线及相邻两对角线上 )

数值解法 ¶

无法显示

直接法
- 经过有限步算数运算，可求得方程组的精确解的方法（若在计算过程）

直接法 ¶

高斯消去法 ¶

无法显示

病态方程组判别 ¶

行列式的值
矩阵求逆
- 缩放系数矩阵，使每一行最大元素为 1，缩放后的逆矩阵元素值大于 1 数倍则为病态
- 将逆矩阵与原矩阵相乘，结果不接近单位阵则为病态
- 求逆矩阵的逆矩阵，与原系数矩阵对比，不相等则为病态
系数微小改变再求解

解求精技术 ¶

使用扩展精度
选主元列主元消去法或者全主元消去法
缩放缩放之后的系数用来确定是否需要交换主元，但实际消去和回代中仍使用原系数值

消去法 ¶

顺序消去法条件苛刻，且数值不稳定
全主元消去法工作量偏大，需要比较的元素及行列交换工作较多，算法复杂
高斯约当消去法形式上简单，且无回代求解，但计算量大

从算法优化的角度考虑，列主元消去法较好

function X=Gauss(A,B)
%采用高斯消去法
n=length(B);
for i=1:n-1
    %寻找该列绝对值最大的元素
    max=abs(A(i,i));
    mark=i;
    for j=i+1:n
        if (abs(A(i,j)) > max)
            max=abs(A(i,j));
            mark=j;
        end
    end
    %交换行
    l=A(i,:);
    A(i,:)=A(mark,:);
    A(mark,:)=l;
    c=B(i);
    B(i)=B(mark);
    B(mark)=c;
    %顺序消元
    %消去
    for j=i+1:n %对第j行进行操作
        factor=A(j,i)/A(i,i);
        for k=i+1:n %对第k个进行操作
            A(j,k)=A(j,k)-factor*A(i,k);
        end
        B(j)=B(j)-factor*B(i);
    end
end

%回代
X(n)=B(n)/A(n,n)
for i=n-1:-1:1
    sum=B(i);
    for j=i+1:n
        sum=sum-A(i,j)*X(j);
    end
    X(i)=sum/A(i,i);
end
end

三角分解 (LU 分解 ) ¶

LU 分解矩阵求逆可减少计算量

Doolittle 分解 ¶

L 为单位下三角矩阵，U 为上三角矩阵

Crout 分解 ¶

L 为下三角矩阵，U 为单位上三角矩阵

三角分解和高斯消去的比较 ¶

计算量相当
三角分解不必计算中间结果，不需要提前知道右端项
解相同系数矩阵方程相当方便

Cholesky 分解 ¶

对称正定矩阵的平方根法

由 Doolittle 分解，A 有唯一分解 $A=LU$
LDR 分解：(L、R 分别为下、上三角矩阵，D 为对角矩阵 )
三角分解：$A=LDL^T$
优势：存储量小，计算量小，数值稳定
缺点：存在开方运算，可能会出现根号下复数

带状方程组 ¶

高斯消去或 LU 分解效率低
元素满足对角占优条件，可以证明 A 非奇异，且各阶顺序主子式都采用三对角方程组的追赶法 (Thomas 算法 )

Thomas 算法 ¶

分解计算公式：$A=LU$
求解方程组 $Ly=f$ 的递推算式

求解方程组 $Ux=y$ 的递推算式

function X=Thomas(A,B)
%采用三对角方程组的追赶法
n=length(B);
%crout分解
L=eye(n);
U=zeros(n);
for i=1:n
    %计算U矩阵的第i行
    U(i,i:n)=A(i,i:n)-L(i, 1:i-1)*U(1:i-1,i:n);        
    %计算L矩阵的第i+1列到第n列
    for j=i+1:n
        L(j,i)=(A(j,i)-L(j,1:i-1)*U(1:i-1,i))/U(i,i);
    end
end
%求解方程组Ly=f
Y=zeros(1,n);
Y(1)=B(1)/A(1,1);
for i=2:n
    Y(i)=(B(i)-A(i,i-1)*Y(i-1))/(A(i,i)-A(i,i-1)*U(i,i-1));
end 
%求解方程组Ux=y
X(n)=Y(n);
for i=n-1:-1:1
    X(i)=Y(i)-X(i+1)*U(i,i+1);
end
end

误差分析、条件数 ¶

向量范数 ¶

满足条件：正定，齐次，三角不等式 + "2"范数(欧几里得范数) $$ ||x||2=(\sum\limits^{n}x_i $$ + "1"范数 $$ ||x||})^{½1=\sum\limits|x_i| $$ + "∞"范数(极大值范数或一致向量范数) $$ ||x||}^{n∞=\mathop{\max $$ + "p"范数 $$ ||x||}\leq{n}}^{}}{|x_i|p=(\sum\limits^{n}|x_i| $$})^{1/p

矩阵范数 ¶

满足条件：正定，齐次，三角不等式，矩阵乘法不等式 ( 相容性条件 ) + "2"范数(谱范数) $$ ||A||2=[\lambdaA^TA] $$ + "1"范数(列和范数) $$ ||A||1=\max\limits| $$ + "∞"范数(行和范数) $$ ||A||}\leq{n}}\sum\limits_{i=1}^{n}|a_{ij∞=\max| $$}\leq{n}}\sum_{j=1}^n|a_{ij