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

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

线性方程组的迭代解法

2024年1月1日
#analysis


文章目录

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


基本迭代法

Jacobi迭代

A = D − L − U A=D-L-U A=DLU
D x ( k + 1 ) = ( L + U ) x ( k ) + b Dx^{(k+1)}=(L+U)x^{(k)}+b Dx(k+1)=(L+U)x(k)+b
B j = D − 1 ( L + U ) = I − D − 1 A B_j =D^{-1}(L+U)=I-D^{-1}A Bj=D1(L+U)=ID1A
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 A=D-L-U A=DLU
( D − L ) x ( k + 1 ) = U x ( k ) + b (D-L)x^{(k+1)}=Ux^{(k)}+b (DL)x(k+1)=Ux(k)+b
B g s = ( D − L ) − 1 U = I − ( D − L ) − 1 A B_{gs} =(D-L)^{-1}U=I-(D-L)^{-1}A Bgs=(DL)1U=I(DL)1A
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 A=D-L-U A=DLU
x ( k + 1 ) = x ( k ) + ω D − 1 ( L x ( k + 1 ) + U x ( k ) − D x ( k ) + b ) x^{(k+1)}=x^{(k)}+ \omega D^{-1}(Lx^{(k+1)}+Ux^{(k)}-Dx^{(k)}+b) x(k+1)=x(k)+ωD1(Lx(k+1)+Ux(k)Dx(k)+b)
x ( k + 1 ) = ( D − ω L ) − 1 [ ( 1 − ω ) D + ω U ] x ( k ) + ω ( D − ω L ) − 1 b x^{(k+1)}= (D- \omega L)^{-1}[(1- \omega )D+ \omega U]x^{(k)} + \omega (D- \omega L)^{-1}b x(k+1)=(DωL)1[(1ω)D+ωU]x(k)+ω(DωL)1b
B S O R = ( D − ω L ) − 1 [ ( 1 − ω ) D + ω U ] B_{SOR} = (D- \omega L)^{-1}[(1- \omega )D+ \omega U] BSOR=(DωL)1[(1ω)D+ω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 {A} A n {n} n 阶矩阵, n ≥ 2 {n\ge2} n2 ,如果存在 n {n} n 阶排列矩阵 P {P} P ,使得
P T A P = [ A 11 A 12 0 A 22 ] P^ \mathrm TAP= \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix} PTAP=[A110A12A22]
其中 A 11 {A_{11}} A11 A 22 {A_{22}} A22 分别为 r {r} r 阶和 n − r {n-r} nr 阶方阵, 1 ≤ r ≤ n − 1 {1\le r\le n-1} 1rn1 ,则称 A {A} A 为可约矩阵,否则为不可约矩阵。
对角占优矩阵 A {A} A n {n} n 阶矩阵,满足
∣ a i i ∣ ≥ ∑ j = 1 , j ≠ i n ∣ a i j ∣ , i = 1 , 2 , ⋯ , n | a_{ii} |\ge \sum_{j=1,j\ne i}^{ n}|a_{ij}| \,\,,\,\, i=1,2,\cdots,n aiij=1,j=inaij,i=1,2,,n
即对角元素大于等于该行其他元素的和,如果 A {A} A 中至少有一行使不等式严格成立,则称A为弱对角占优矩阵,如果每一行都使不等式严格成立,则称 A {A} A 为严格行对角占优矩阵。

一些定理

  • 如果 n {n} n 阶矩阵 A {A} A 是严格对角占优矩阵或不可约弱对角占优矩阵,则 A {A} A 是非奇异矩阵
  • n {n} n 阶矩阵 A {A} A k {k} k 次幂 A k → 0 {A^k\to0} Ak0 的充要条件为谱半径 ρ ( A ) < 1 {\rho (A)<1} ρ(A)<1
  • 任一矩阵 A {A} A 的谱半径均不大于 A {A } A 的任一与某一向量范数相容的矩阵范数,即 ρ ( A ) ≤ ∣ ∣ A ∣ ∣ {\rho(A)\le ||A||} ρ(A)∣∣A∣∣
  • 对于迭代格式
    x ( k + 1 ) = B x ( k ) + g x^{(k+1)}=Bx^{(k)}+g x(k+1)=Bx(k)+g
    给定任意的初值 x ( 0 ) {x^{(0)}} x(0) ,有下列收敛结果和误差估计0
    1. 迭代格式收敛的充要条件为谱半径 ρ ( B ) < 1 {\rho(B)<1} ρ(B)<1
    2. 如果 ∣ ∣ B ∣ ∣ < 1 {||B||<1} ∣∣B∣∣<1 ,则有估计
      ∣ ∣ x ( k ) − x ∗ ∣ ∣ ≤ ∣ ∣ B ∣ ∣ k 1 − ∣ ∣ B ∣ ∣ ∣ ∣ x ( 1 ) − x ( 0 ) ∣ ∣ ∣ ∣ x ( k ) − x ∗ ∣ ∣ ≤ ∣ ∣ B ∣ ∣ 1 − ∣ ∣ B ∣ ∣ ∣ ∣ x ( k ) − x ( k − 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*} ∣∣x(k)x∣∣∣∣x(k)x∣∣1∣∣B∣∣∣∣Bk∣∣x(1)x(0)∣∣1∣∣B∣∣∣∣B∣∣∣∣x(k)x(k1)∣∣
  • A {A} A 是严格对角占优矩阵或不可约弱对角占优矩阵,则Jacobi迭代和GS迭代都收敛
  • A {A} A 对称正定,则Jacobi迭代收敛的充要条件为 2 D − A {2D-A} 2DA 也是对称正定矩阵
  • SOR迭代收敛的必要条件为 1 < ω < 2 {1< \omega <2} 1<ω<2
  • 系数矩阵 A {A} A 对称正定,则 0 < ω < 2 {0<\omega <2} 0<ω<2 时SOR迭代收敛

例题看同济《现代数值计算》习题6.6。


下链


这篇关于【数值分析】线性方程组的迭代方法,jacobi,高斯赛德尔GS,SOR的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/561717

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

golang中reflect包的常用方法

《golang中reflect包的常用方法》Go反射reflect包提供类型和值方法,用于获取类型信息、访问字段、调用方法等,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值... 目录reflect包方法总结类型 (Type) 方法值 (Value) 方法reflect包方法总结

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin