【数值分析】线性方程组的迭代方法，jacobi，高斯赛德尔GS，SOR

本文主要是介绍【数值分析】线性方程组的迭代方法，jacobi，高斯赛德尔GS，SOR，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性方程组的迭代解法

2024年1月1日
#analysis

文章目录

线性方程组的迭代解法
- 基本迭代法
- - - Jacobi迭代
    - 高斯-赛德尔（GS）迭代
    - SOR迭代
- 迭代的收敛性分析和误差估计
- 下链

基本迭代法

Jacobi迭代

$A = D - L - U$
$Dx^{(k+1)}=(L+U)x^{(k)}+b$
$B_j =D^{-1}(L+U)=I-D^{-1}A$
matlab实现

%% 迭代法例子
A = [2 -1 0;-1 3 -1;0 -1 2];
b = [1 8 -5]';
[x,i] = jacobi(A,b,1e-5,10000)%% Jacobi迭代
% 输入矩阵A，向量b，精度，最大迭代次数
% 输出解向量x，迭代次数i
function [x,i] = jacobi(A,b,eps,max_iter)D = diag(diag(A));L = D-tril(A);U = D-triu(A);x = zeros(size(b)); %!for i = 1:max_iterx = D\(b+L*x+U*x);err = norm(b-A*x)/norm(b); %!if err<epsbreak;endend
end

高斯-赛德尔（GS）迭代

$A = D - L - U$
$D-L)x^{(k+1)}=Ux^{(k)}+b$
$B_{gs} =(D-L)^{-1}U=I-(D-L)^{-1}A$
matlab实现

%% 迭代法例子
A = [2 -1 0;-1 3 -1;0 -1 2];
b = [1 8 -5]';
[x,i] = GS(A,b,1e-5,10000)%% GS迭代
% 输入矩阵A，向量b，精度，最大迭代次数
% 输出解向量x，迭代次数i
function [x,i] = GS(A,b,eps,max_iter)D = diag(diag(A));L = D-tril(A);U = D-triu(A);x = zeros(size(b)); %!for i = 1:max_iterx = (D-L)\(b+U*x);err = norm(b-A*x)/norm(b); %!if err<epsbreak;endend
end

SOR迭代

$A = D - L - U$
$x^{(k+1)}=x^{(k)}+ \omega D^{-1}(Lx^{(k+1)}+Ux^{(k)}-Dx^{(k)}+b)$
$x^{(k+1)}= (D- \omega L)^{-1}[(1- \omega )D+ \omega U]x^{(k)} + \omega (D- \omega L)^{-1}b$
$B_{SOR} = (D- \omega L)^{-1}[(1- \omega )D+ \omega U]$
matlab实现

%% 迭代法例子
A = [2 -1 0;-1 3 -1;0 -1 2];
b = [1 8 -5]';
[x,i] = SOR(A,b,1e-5,10000,1.1)%% SOR迭代
% 输入矩阵A，向量b，精度，最大迭代次数
% 输出解向量x，迭代次数i
function [x,i] = SOR(A,b,eps,max_iter,w)D = diag(diag(A));L = D-tril(A);U = D-triu(A);x = zeros(size(b)); %!for i = 1:max_iterx = (D-w*L)\(((1-w)*D+w*U)*x + w*b);err = norm(b-A*x)/norm(b); %!if err<epsbreak;endend
end

迭代的收敛性分析和误差估计

排列矩阵 每行每列仅有唯一非零元的方阵。
可约矩阵 ${A}$ 是 ${n}$ 阶矩阵， ${n\ge2}$ ，如果存在 ${n}$ 阶排列矩阵 ${P}$ ，使得
$P^ \mathrm TAP= \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}$
其中 ${A_{11}}$ 和 ${A_{22}}$ 分别为 ${r}$ 阶和 ${n-r}$ 阶方阵， ${1\le r\le n-1}$ ，则称 ${A}$ 为可约矩阵，否则为不可约矩阵。
对角占优矩阵 ${A}$ 是 ${n}$ 阶矩阵，满足
$a_{ii} |\ge \sum_{j=1,j\ne i}^{ n}|a_{ij}| \,\,,\,\, i=1,2,\cdots,n$
即对角元素大于等于该行其他元素的和，如果 ${A}$ 中至少有一行使不等式严格成立，则称A为弱对角占优矩阵，如果每一行都使不等式严格成立，则称 ${A}$ 为严格行对角占优矩阵。

一些定理

如果 ${n}$ 阶矩阵 ${A}$ 是严格对角占优矩阵或不可约弱对角占优矩阵，则 ${A}$ 是非奇异矩阵
${n}$ 阶矩阵 ${A}$ 的 ${k}$ 次幂 ${A^k\to0}$ 的充要条件为谱半径 ${\rho (A)<1}$
任一矩阵 ${A}$ 的谱半径均不大于 ${A }$ 的任一与某一向量范数相容的矩阵范数，即 ${\rho(A)\le ||A||}$
对于迭代格式
$x^{(k+1)}=Bx^{(k)}+g$
给定任意的初值 ${x^{(0)}}$ ，有下列收敛结果和误差估计0
1. 迭代格式收敛的充要条件为谱半径 ${\rho(B)<1}$
2. 如果 ${||B||<1}$ ，则有估计
  $\begin{align*} ||x^{(k)}-x ^{*} ||\le& \frac{||B||^k}{1-||B||}||x^{(1)}-x^{(0)}|| \\ \\ ||x^{(k)}-x ^{*} ||\le& \frac{||B||}{1-||B||}||x^{(k)}-x^{(k-1)}|| \end{align*}$
若 ${A}$ 是严格对角占优矩阵或不可约弱对角占优矩阵，则Jacobi迭代和GS迭代都收敛
若 ${A}$ 对称正定，则Jacobi迭代收敛的充要条件为 ${2D-A}$ 也是对称正定矩阵
SOR迭代收敛的必要条件为 $\omega <2}$
系数矩阵 ${A}$ 对称正定，则 ${0<\omega <2}$ 时SOR迭代收敛