解线性方程组迭代法

创作时间:

作者:

@小白创作中心

解线性方程组迭代法

引用

来源

https://www.cnblogs.com/LilMonsterOvO/p/18540094

在数值分析中，迭代法是解决大规模线性方程组的重要工具。迭代法可以有效地减少计算复杂度，使得求解效率更高。本文将从前置知识开始，介绍向量和矩阵的范数，再深入探讨求解线性方程组的Jacobi和Gauss-Seidel迭代法。

一、前置知识：向量和矩阵的范数

在理解迭代法之前，我们需要掌握范数（norm）的概念。范数是衡量向量或矩阵"大小"的一种工具，它帮助我们分析和评估数值方法的收敛性。

1.1 向量范数的定义

设x是n维向量，则向量x的范数可以表示为||x||，其物理意义为向量的长度或大小。常见的向量范数包括：

1-范数（曼哈顿距离）：
$$||x||1=\sum{i=1}^{n}|x_i|$$
2-范数（欧几里得距离）：
$$||x||2={\left(\sum{i=1}^{n}|x_i|^2\right)}^{1/2}$$
∞-范数（切比雪夫距离）：
$$||x||_{\infty}=\underset{1\le i\le n}{max}|x_i|$$

1.2 范数的三大特征

范数有以下三个重要特征，这些特征与绝对值的性质类似：

正定性：
对于任意向量x，有
$$||x||\ge 0，且||x||=0\iff x=0$$
线性性（齐次性）：
对于任意标量α和向量x，有
$$||\alpha x||=|\alpha |\cdot ||x||$$
三角不等式：
对于任意向量x和y，有
$$||x+y||\le ||x||+||y||$$

这些特征与绝对值的三大特征相似：

绝对值的正定性：|a| ≥ 0且|a| = 0当且仅当a = 0。
绝对值的线性性：|αa| = |α| ⋅ |a|。
绝对值的三角不等式：|a + b| ≤ |a| + |b|。

1.3 矩阵的范数

矩阵A的范数||A||可以定义为其作用在向量x上的放大倍数，即：
$$||A||=\underset{x\neq 0}{sup}\frac{||Ax||}{||x||}$$

常用的矩阵范数包括：

1-范数：列和范数
$$||A||1=\underset{j}{max}\sum{i=1}^{m}|a_{ij}|$$
∞-范数：行和范数
$$||A||{\infty}=\underset{i}{max}\sum{j=1}^{n}|a_{ij}|$$
2-范数：谱范数（最大特征值的平方根）

1.4 正定矩阵

一个矩阵A被称为正定矩阵，如果对任意非零向量x，总有：
$${x}^{T}Ax>0$$

正定矩阵在迭代法中有重要作用，因为它们能够保证算法的收敛性。

二、解线性方程组的迭代法

在求解线性方程组Ax = b的问题中，直接求解（如高斯消元法）在处理大型稀疏矩阵时效率低下。因此，迭代法成为更好的选择。

2.1 Jacobi迭代法

Jacobi迭代法是求解线性方程组的基本方法之一。其核心思想是将Ax = b转化为：
$${x}{i}^{\left(k+1\right)}=\frac{1}{{a}{ii}}\left({b}{i}-\sum{j\neq i}{a}{ij}{x}{j}^{\left(k\right)}\right)$$

Jacobi迭代法的步骤

初始化x^{(0)}，设定初始猜测。
根据上式计算新的x_i。
检查是否满足收敛条件||x^{(k+1)} - x^{(k)}|| < \epsilon。
若未满足，重复步骤2和3。

收敛性分析

Jacobi迭代法的收敛性与矩阵A的特性相关。当A是严格对角占优或正定矩阵时，Jacobi迭代法可以保证收敛。

2.2 Gauss-Seidel迭代法

Gauss-Seidel迭代法在Jacobi迭代法的基础上进行改进，每次计算x_i时立即使用最新的迭代结果。其迭代公式为：
$${x}{i}^{\left(k+1\right)}=\frac{1}{{a}{ii}}\left({b}{i}-\sum{j<i}{a}{ij}{x}{j}^{\left(k+1\right)}-\sum{j>i}{a}{ij}{x}_{j}^{\left(k\right)}\right)$$