tag: 数值分析

3.1 - 6 迭代法 基本思想 对线性方程组 \(Ax=b\) ，当 \(A\) 为低阶稠密矩阵时，选主元Gauss消去/Doolittle分解均为有效方法。 工程应用中 \(A\) 常为高阶稀疏矩阵，适用迭代法求解：利好计算机存储与性能。 通法： 将 \(Ax=b\) 改写为 \(x=B_0x+f\) 任取初始值，如 \(x^{(0)}=(0,0,0)^T\) ，将其带入得到方程组解 \(x^{(1)}=B_0x^{(0)}+f\) 依次得： \(x^{(2)}=B_0x^{(1)}+f,\ x^{(2)}=B_0x^{(1)}+f,\ \dots,\ x^{(k)}=B_0x^{(k-1)}+f,\ \dots\) 即得向量序列 \(x^{(0)},x^{(1)},\dots,x^{(k)}\) ，迭代公式 \(x^{(k)}=B_0x^{(k-1)}+f\) 迭代次数较高时，向量序列 \(x^{(k)}\) 有可能收敛至逼近精确解的值（不一定）。 根据 \(x=Bx+f\) 变形方式的不同，存在多种迭代算法。 定义1： 对于给定方程组 \(x=Bx+f\) ，用公式 \(x^{k+1}=Bx^{(k)}+f,\ (k=0,1,2,3,\dots)\) 逐步代入求近似解的方法称为迭代法（或称为一阶定常迭代法，这里 \(B\) 与 \(k\) 无关）。 如果 \(\lim\limits_{k\to\infty}x^{(k)}=x^*\) ，即向量序列收敛至精确解序列，则称此迭代法收敛，否则称发散。 由于需要研究 \(\{x^{(k)}\}\) 的收敛性，引进误差向量 \(\varepsilon^{(k+1)}=x^{(k+1)}-x^*\) 。易得到： \(\varepsilon^{(k+1)}=B\varepsilon^{(k)}\) ，递推得： \(\varepsilon^{(k)}=B\varepsilon^{(k-1)}=\dots=B^k\varepsilon^{(0)}\) 。 Jacobi迭代 通法细节： 将 \(A\) 分裂成 \(A=M-N\) ，其中 \(M\) 为可选择的非奇异矩阵，使 \(Mx=d\) 易解，一般选择为 \(A\) 的某种近似，称 \(M\) 为分裂矩阵。...

2.9-11 范数 为研究线性方程组近似解的误差估计和迭代法的收敛性，对 \(R……n\) （ \(n\) 维向量空间）中的向量（ \(R^{n\times n}\) 中的矩阵）的“大小”引进度量——向量（或矩阵）的范数。 向量的范数 定义1：设 \(x=(x_1,x_2,\dots,x_n)^T,y=(y_1,y_2,\dots,y_n)^T\in R^n (or\ C^n)\) 将实数 \((x,y)=y^Tx=\sum_{i=1}^{n}x_i\overline{y_i}\)（或复数 \((x,y)=y^Hx=\sum_{i=1}^{n}x_iy_i\) ）称为向量x,y的数量积（内积）。 将非负实数 \(\|x\|_2=(x,x)^{1\over2}=(\sum_{i=1}^{n}x_i^2)^{1\over2}\) 或 \(\|x\|_2=(x,x)^{1\over2}=(\sum_{i=1}^{n}|x_i|^2)^{1\over2}\) 称为向量 \(x\) 的欧式范数。 引理：向量的内积运算支持交换律、分配律、与实数乘时的结合律。 Cauchy-Schwarz不等式 \(|(x,y)|\le \|x\|_2\cdot\|y\|_2\) 当且仅当 \(x\) 与 \(y\) 线性相关时取等。 三角不等式 \(\|x+y\|_2\le\|x\|_2+\|y\|_2\) 定义2-向量的范数：若向量 \(x\in R^n\) （或 \(C^n\) ）的某个实值函数 \(N(x)=\|x\|\) ，满足条件： \[ \begin{aligned} & (1)\ \|x\|\ge 0\ (\|x\|=0当且仅当x=0)\quad\textbf{正定条件}\\ & (2)\ \|\alpha x\|=|\alpha|\|x\|,\ \forall\alpha\in R(或\alpha\in C)\quad\textbf{齐次性}\\ & (3)\ \|x+y\|_2\le\|x\|_2+\|y\|_2\quad\textbf{三角不等式}\\ & (3\to 4)\ \|x-y\|_2\ge\|x\|_2-\|y\|_2 \end{aligned} \] 则称 \(N(x)\) 是 \(R^n\) （或 \(C^n\) ）上的一个向量范数（或模）...

续 2.1 - 2.4 矩阵三角分解法 初等行变换 \(\Leftrightarrow\) 矩阵左乘初等矩阵 消元 \(\Leftrightarrow\) 矩阵左乘 \((n-1)\) 个初等矩阵 若 \(a_{11}^{(1)}\neq0\) ，令 \(l_{i1} = a_{i1}^{(1)}\div a_{11}^{11},\ i=2,3,\dots,n\) ，记： \(L_{1}=\begin{pmatrix} 1 \\ -l_{21} & 1 \\ -l_{31} && 1 \\ \vdots &&& \ddots \\ -l_{31} &&&& 1 \end{pmatrix}\) 则有 \(A^{(2)}=L_{1}A^{(1)}=\begin{pmatrix} a_11^{(1)} & a_{12}^{(1)} & \cdots & a_{1n}^{(1)} \\ 0 & a_{22}^{(2)} & \cdots & a_{2n}^{(2)} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & a_{n2}^{(2)} & \cdots & a_{nn}^{(2)} \end{pmatrix}\)...

1.1 - 1.2 数值分析的算法要求 结构简单，易于计算机实现 理论上保证方法的收敛性和数值稳定性 计算效率高：速度快，内存开销小 经过数值实验验证 误差的来源和分类 模型误差：将实际问题抽象为数学模型过程中产生的误差，不可避免 观测误差：观测实验得到的参数带来的误差 截断误差：近似方法产生的误差 舍入误差：计算机有限位计算产生的误差 （后两者为本课程主要研究对象） 绝对误差和相对误差 设 \(x\) 是精确值 \(x^{*}\) 的一个近似值，则 \(e=x^{*}-x\) 为近似值 \(x\) 的绝对误差，简称误差。 若 \(\varepsilon\) 满足 \(|e|\le\varepsilon\) ，则称 \(\varepsilon\) 为 \(x\) 的绝对误差限，简称误差限，有量纲。则满足 \(x-\varepsilon \le x^{*} \le x+\varepsilon\) ，简写为 \(x^{*} = x\pm\varepsilon\) 。 \(e_{r} = \displaystyle\frac{e}{x^{*}} = \frac{x^{*}-x}{x^{*}}\) 称相对误差。 \(\varepsilon_{r} = \displaystyle\frac{\varepsilon}{|x|}\) 称相对误差限， \(|e_{r}| \le \varepsilon_{r}\) ，无量纲。 （其中误差与相对误差用于理论分析，误差限与相对误差限用于实际应用。） 1.3 有效数字 定义1：设数 \(x\) 是数 \(x^{*}\) 的近似值，如果 \(x\) 的绝对误差限是它的某一数位的半个单位，并且从 \(x\) 左起第一个非零数到该数位共有 \(n\) 位，则称这 \(n\) 个数字为 \(x\) 的有效数字，也称用 \(x\) 近似 \(x*\) 时具有 \(n\) 位有效数字。...