误差分析、最值、谱半径、范数

《应用数值分析》
《应用数值分析》

目录

1. 基本概念

1.2 误差分析

1.2.1 绝对误差/相对误差

  • 绝对误差准确值近似值之差,
  • 相对误差
  • 绝对误差界
  • 相对误差界

1.2.2 有效数字

  • 定义:设 $x$ 的近似值 $x^*$ 表示成规格化形式:

如果有 ,则称 $x^*$ 有 $n$ 位有效数字

  • 有效数字的位数与小数点无关
  • 有效数字位数相对误差有下列关系:

(1) 如果 $x^*$ 有 $n$ 位有效数字,则

(2) 如果下式成立,则 $x^*$ 至少有 $n$ 位有效数字:

1.2.3 截断误差/舍入误差/初始数据误差

  • 截断误差:或称方法误差,指在构造数值计算方法时,用有限过程代替无限过程,其计算结果所存在的误差。
  • 舍入误差:或称计算误差,进行舍入操作所引起的误差
  • 初始数据误差:或称输入数据误差,可能是物理数据测量不准确、初始数据只能取近似值引起的。为简明起见,把这些误差归入舍入误差范围处理

1.3 病态问题与条件数/数值稳定性

1.3.1 病态问题与条件数

条件数

  • 条件数记为 $C$ 或 $Cond$
  • 误差 $e(x^*)$ 的条件数:
  • 相对误差 $e_r(x^*)$ 的条件数:

病态/良态

  • 对于一个数值问题,当输入数据(初始数据)有微小扰动时,计算结果对之很敏感,即条件数很大,就称这个问题是病态的
  • 当初始数据有微小扰动时,计算结果对之不敏感,即条件数不大,就称这个问题是良态的

1.3.2 算法数值稳定性

  • 一个算法在执行过程中,某阶段所产生的小误差在随后的阶段中不会被积累或放大,就称这个算法过程是数值稳定
  • 否则,称这个算法过程是数值不稳定
  • 不稳定有时也叫病态

所谓严重降低计算精确度,确切地说,设由且仅由 $\varepsilon$ 引起的、$n$ 步运算之后的误差为 $e_n$:

  • 如果 ($c$ 是与 $n$ 无关的常数),即误差是线性增长的,从而可通过 $\varepsilon$ 来控制 $e_n$,故算法是稳定
  • 如果 ($k > 1$ 的常数),即误差是指数增长的,或者如果 ,从而无论 $\left| \varepsilon \right|$ 多么小,均难以通过 $\varepsilon$ 来控制 $e_n$,故算法是不稳定

1.4 数值算法设计与实现

对于数值算法设计来说,主要强调以下两方面:

  • 尽量简化计算步骤,减少运算次数
  • 尽量减少舍入误差的影响,避免有效数字的损失,保证算法的数值稳定性
  • 秦九韶算法:$n$ 次加法,$n$ 次乘法

1.5 数学分析中的几个重要概念

1.5.1 $Taylor$ 公式

  • 设 $f$ 在含有点 $x_0$ 的某个开区间 $( a,b )$ 内具有 $n+1$ 阶导数,则 $\forall x \in (a,b) $,有:

其中,$\xi$ 在 $x_0$ 与 $x$ 之间,前 $n+1$ 项称为 $n$ 次 $Taylor$ 多项式,最后一项称为 $n$ 次 $Taylor$ 多项式的余项(即截断误差)。为了方便作误差估计,有时还假定 $f$ 的 $n+1$ 阶导数连续

1.5.2 大 $O$ 记号

定义

大 $O$ 记号是为表示近似值而允许我们用 “$=$” 号替代 “$\approx$” 的方便符号。

设变量 $X, Y$(其中 $X \neq 0$),如果在变化过程的某一时刻以后,有:

($M$ 为大于 $0$ 的常数)便记成 $Y=O(X)$

性质

  • 当 $X$ 变化到某一时刻后,$\left| O(X) \right|$ 总是不会超过 $M\left| (X) \right|$
  • 大 $O$ 记号具有单向相等性,等式的右端只是左端的粗略化

运算法则

  • $O(X) \pm O(X) = O(X)$
  • $mO(X) = O(X)$,$m$ 为不等于 $0$ 的常数
  • $O(X) \cdot O(X) = O(X^2)$
  • $O(O(X)) = O(X)$

1.5.3 上确界与下确界

最大值/最小值

设 $S$ 是一个非空的实数集$S \subset \mathbf{R}$($\mathbf{R} \equiv \mathbf{R}^1 = (-\infty,+\infty)$ 是实数的全体),

  • 如果有 $M \in \mathbf{R}$,使得:$x \leqslant M, \forall x \in S$,则称集 $S$ 上有界,$M$ 是 $S$ 的一个上界
  • 如果有 $m \in \mathbf{R}$,使得:$x \geqslant m, \forall x \in S$,则称集 $S$ 下有界, $m$ 是 $S$ 的一个下界
  • 如果 $S$ 上、下有界,则称 $S$ 为有界集
  • 当上界 $M \in S$,则称 $M$ 是 $S$ 的最大值,记为 $M = \max S$$M = \max \limits_{x \in S} x$
  • 当下界 $m \in S$,则称 $m$ 是 $S$ 的最小值,记为 $m = \min S$$m = \min \limits_{x \in S} x$

最小上界公理

  • 任何有上界的非空实数集都有一个最小上界

上确界/下确界

设 $S \subset \mathbf{R}$,

  • 如果 $\mu \in \mathbf{R}$ 是 $S$ 的最小上界,则称 $\mu$ 是 $S$ 的上确界(supremum),记作 $\mu = \sup S$$\mu = \sup \limits_{x \in S} x$
  • 如果 $\nu \in \mathbf{R}$ 是 $S$ 的最大下界,则称 $\nu$ 是 $S$ 的下确界(infimum),记作 $\nu = \inf S$$\nu = \inf \limits_{x \in S} x$
  • 当 $S$ 上无界时,规定 $\sup S = + \infty$
  • 当 $S$ 下无界时,规定 $\inf S = - \infty$
  • 若 $S \subset \mathbf{R}$ 上有界,则必存在上确界,但不一定存在最大值;如果 $S$ 存在最大值,则最大值就是上确界
  • 若 $S \subset \mathbf{R}$ 下有界,则必存在下确界,但不一定存在最小值;如果 $S$ 存在最小值,则最小值就是下确界

1.5.4 函数序列的一致收敛性

设数列 $\left \{ x_n \right \}$,如果存在常数 $a$,对任意给定的正数 $\varepsilon$(无论它多小),总存在正整数 $N$,使得当 $n > N$ 时,有

则称 $a$ 为数列 $\left \{ x_n \right \}$ 的极限,记为 $\lim \limits_{n \to \infty} x_n = a$,或称为数列 $\left \{ x_n \right \}$ 收敛于 $a$

1.6 几种重要矩阵及相关性质

1.6.1 对称正定矩阵

定义

设 $\pmb{A} = (a_{ij}) \in \mathbf{R^{n \times n}}$

(1) 如果 $\pmb{A}^T = \pmb{A}$,即 $a^{ij} = a^{ji}$,则称 $\pmb{A}$ 为对称矩阵

(2) 如果对称矩阵 $\pmb{A}$ 满足对于 $\forall x \neq 0, x \in \mathbf{R}^{n \times n}$,有

则称 $\pmb{A}$ 为对称正定矩阵

性质

对称矩阵对称正定矩阵有如下性质:

  • 若 $\pmb{A}$ 对称,则 $\pmb{A}$ 的特征值皆为实数,且有 $n$ 个线性无关的特征向量
  • $\pmb{A} \in \mathbf{R}^{n \times n}$ 对称正定的充要条件是 $\pmb{A}$ 的所有顺序主子式
  • $\pmb{A}$ 对称正定的充要条件是 $\pmb{A}$ 的所有特征值 $\lambda^i > 0 \quad (i=1,2,\cdots,n)$
  • $\pmb{A}$ 对称正定,则 $\pmb{A}$ 非奇异,且 $\pmb{A}^{-1}$ 也对称正定
  • $\pmb{A}$ 对称正定,则 $\pmb{A}$ 的对角元素 $a_{ij} > 0$

1.6.2 正交矩阵/相似矩阵

正交矩阵定义

设 $\pmb{A} = (a_{ij}) \in \mathbf{R^{n \times n}}$ 且成立 $\pmb{A}^T \pmb{A} = I$,则称 $\pmb{A}$ 为正交矩阵

定义式 $\pmb{A}^T \pmb{A} = I$ 可以写成:

其中,

称为 $Kronecker$(克罗内克尔)符号。

正交矩阵性质

正交矩阵有如下性质:

  • 单位矩阵正交矩阵
  • 若 $\pmb{A}$ 是正交矩阵,则 $\pmb{A}^T$、$\pmb{A}^{-1}$ 也是正交矩阵
  • 若 $\pmb{A}$ 是正交矩阵,则 $\pmb{A}$ 非奇异,且 $(\det \pmb{A})^2 = 1$,即 $\det \pmb{A}$ 等于 $1$ 或 $-1$
  • $\pmb{A},\pmb{B}$ 同阶且为正交矩阵,则 $\pmb{A}\pmb{B}$ 与 $\pmb{B}\pmb{A}$ 为正交矩阵

相似矩阵定义

设 $\pmb{A}$ 与 $\pmb{B}$ 为 $n$ 阶方阵,如果有非奇异的 $n$ 阶方阵 $\pmb{S}$,使得

则称 $\pmb{A}$ 与 $\pmb{B}$ 相似,记作 $\pmb{A} \sim \pmb{B}$

相似矩阵性质

矩阵相似关系有如下三个性质:

  • 反身性:$\pmb{A} \sim \pmb{A}$
  • 对称性:$\pmb{A} \sim \pmb{B} \Rightarrow \pmb{B} \sim \pmb{A}$
  • 传递性:$\pmb{A} \sim \pmb{B}, \pmb{B} \sim \pmb{C} \Rightarrow \pmb{A} \sim \pmb{C}$

应用中,常常不是判断两个矩阵是否相似,而是对给定的矩阵 $\pmb{B}$,寻找合适的可逆矩阵 $\pmb{S}$ 按 $\pmb{A} = \pmb{S}^{-1}\pmb{B}\pmb{S}$ 来产生一个矩阵 $\pmb{A}$。

  • 矩阵的相似变换:对一个矩阵两边分别乘以某可逆矩阵及其逆
  • 矩阵的正交表换:对给定矩阵利用正交矩阵作相似变换

1.6.3 初等矩阵与初等变换

初等矩阵

下面三种形式的 $n$ 阶矩阵称为初等矩阵

  • $\pmb{E}(i,j)$
  • $\pmb{E}(i(\alpha))$
  • $\pmb{E}(i,j(\alpha))$

初等矩阵性质

  • $\pmb{E}(i,j)^{-1}=\pmb{E}(i,j)$
  • $\pmb{E}(i(\alpha))^{-1}=\pmb{E}(i(\frac{1}{\alpha}))$
  • $\pmb{E}(i,j(\alpha))^{-1}=\pmb{E}(i,j(-\alpha))$

1.6.4 矩阵特征值/矩阵谱半径

矩阵特征值定义

设 $\pmb{A}=(a_{ij}) \in \mathbf{R}^{n \times n}$。若存在一个数 $\lambda$(实数或复数)和非零向量 $\pmb{x}=(x_1,x_2,\cdots,x_n)^T \in \mathbf{R}^n$,使得:

则称 $\lambda$ 为 $\pmb{A}$ 的特征值,$\pmb{x}$ 为 $\pmb{A}$ 对应 $\lambda$ 的特征向量

矩阵特征值求解

应用中主要对给定的 $\pmb{A}$ 求其特征值 $\lambda$,为此将定义式改写为齐次方程 $(\lambda\pmb{I} - \pmb{A})\pmb{x}=0$,即

  • $\pmb{p}(\lambda)$ 称为 $\pmb{A}$ 的特征多项式
  • $\pmb{p}(\lambda)=0$ 称为相应的特征方程
  • 在复数域内有 $n$ 个根即为 $n$ 个特征值
  • 求 $\pmb{A}$ 的特征值即为求 $\pmb{A}$ 的特征方程的根

矩阵谱半径定义

设 $\pmb{A} \in \mathbf{R}^{n \times n}$,$\pmb{A}$ 的特征值 $\lambda_1,\lambda_2,\cdots,\lambda_n$,则有:

  • $\pmb{A}$ 的全体特征值 $\left \{ \lambda_1,\lambda_2,\cdots,\lambda_n \right \}$ 称为 $\pmb{A}$ 的谱
  • 这些特征值的模的最大值 $\max\limits_{1\leqslant i\leqslant n}\left| \lambda_i \right|$ 称为 $\pmb{A}$ 的谱半径,记为 $\rho(A)$,即

矩阵特征值性质

  • 若 $\pmb{A} \in \mathbf{R}^{n \times n}$ 是对称矩阵,则 $\pmb{A}$ 的特征值均为实数,且有 $n$ 个线性无关的特征向量
  • $\pmb{A} \in \mathbf{R}^{n \times n}$ 对称正定的充要条件是 $\pmb{A}$ 的所有特征值 $\lambda_i > 0$,$(i=1,2,\cdots,n)$
  • 若 $\lambda_1,\lambda_2,\cdots,\lambda_m$ 是矩阵 $\pmb{A}$ 的单重特征值,$\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_m$ 依次是相应的特征向量,则 $\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_m$ 线性无关
  • 相似矩阵相同的特征多项式,因而也有相同的特征值

1.7 线性空间概要

1.7.1 线性空间

  • $\pmb{R}^n$:$n$ 维实向量的全体
  • $\pmb{R}^{n \times m}$:$n$ 行 $m$ 列实矩阵的全体
  • $C[a,b]$:定义在区间 $[a,b]$ 上连续实值函数的全体
  • $P_n[a,b]$:定义在区间 $[a,b]$ 上次数 $\leqslant n$ 的实系数多项式全体
  • $C^n[a,b]$:定义在区间 $[a,b]$ 上的具有连续 $n$ 阶导数的实值函数全体

线性相关

对数域 $K$ 上的线性空间 $X$,有 $u_1, u_2, \cdots, u_n \in X$,若存在不全为零的数 $\alpha_1, \alpha_2, \cdots, \alpha_n \in K$,使得下列等式成立:

则称 $u_1, u_2, \cdots, u_n$ 是线性相关的,否则,等式只对 $\alpha_1 = \alpha_2 = \cdots = \alpha_n = 0$ 才能成立,则称 $u_1, u_2, \cdots, u_n$ 是线性无关的。

基、维数、坐标

称 $S$ 是由线性空间 $X$ 中的 $n$ 个线性无关元素 $u_1, u_2, \cdots, u_n \in X$生成的,即 $\forall s \in S$,都有:

  • $S = Span \left \{ u_1, u_2, \cdots, u_n \right \}$
  • 称 $u_1, u_2, \cdots, u_n$ 是 $S$ 的一组
  • 称 $S$ 是 $n$ 维的
  • 系数 $\alpha_1, \alpha_2, \cdots, \alpha_n$ 称为 $S$ 在基 $u_1, u_2, \cdots, u_n$ 下的坐标,并记为 $(\alpha_1, \alpha_2, \cdots, \alpha_n)$

1.7.2 范数/赋范线性空间

设 $X$ 是数域 $K$ 上的线性空间,若 $\forall u \in X$,存在唯一的实数 ,满足条件:

  • 正定性,其中 当且仅当 $u = 0$
  • 齐次性
  • 三角不等式

则称 为线性空间 $X$ 上的范数,并且称 $X$ 为赋范线性空间,仍记为 $X$

对于连续函数空间 $C[a,b]$,可以定义 $f \in C[a,b]$ 的如下两种范数:

  • $\infty$-范数
  • $1$ - 范数

以及稍后在内积空间中还要定义:

  • $2$ - 范数

1.7.3 内积/内积空间

内积:线性空间 $\pmb{R}^n$ 中,任意两个向量 $\pmb{x},\pmb{y}$ 的数量积,记为 $(\pmb{x},\pmb{y})$:

内积空间:设 $X$ 是数域 $K$(如实数域 $\pmb{R}$ 或复数域 $\pmb{C}$)上的线性空间,若对 $\forall u,v \in X$,有 $K$ 中一个数与之对应,记为 $(u,v)$,且满足条件:

  1. $(u,u) \geqslant 0$,其中 $(u,u) = 0 \Leftrightarrow u = 0$
  2. $(u,v) = \overline{(v,u)}$,$\overline{(v,u)}$ 为 $(v,u)$ 的共轭
  3. $(\alpha u,v)=\alpha(u,v), \alpha \in K$
  4. $(u + v, \omega) = (u,\omega) + (v,\omega),\omega \in X$

$(u,v)$ 称为 $u$ 与 $v$ 的内积定义了内积的线性空间 $X$ 称为 内积空间

正交:设 $X$ 为内积空间,若对任意的 $u,v \in X$,有:

则称 $u$ 与 $v$ 正交。

1.9 向量范数/矩阵范数

1.9.1 向量范数

设向量 $\pmb{x} \in \pmb{R}^n$,若与 $\pmb{x}$ 对应的一个实值函数 满足:

  • 正定性,其中 当且仅当 $\pmb{x}=0$
  • 齐次性
  • 三角不等式

则称 为 $\pmb{R}^n$ 上 $\pmb{x}$ 的一个向量范数

3 种常用的向量范数

  • $1$ - 范数
  • $\infty$-范数
  • $2$ - 范数

或一般地定义

  • $p$ - 范数

向量范数基本性质

  • 连续性:设 $\pmb{x} = (x_1,x_2,\cdots,x_n)^T \in \pmb{R}^n$,其范数 是 $\pmb{x}$ 的分量 $x_1,x_2,\cdots,x_n$ 的 $n$ 元连续函数
  • 等价性:设 为 $ \pmb{R}^n$ 上任意两种范数,则存在常数 $m,M>0$,使得:
  • 按范数收敛性:设向量序列 $\left\{ \pmb{x}^{(k)} \right\}$ 收敛于向量 ,即 ,则等价于:
  • 其中, 为向量的任一种范数,并称向量序列 $\left\{ \pmb{x}^{(k)} \right\}$ 按该函数收敛于向量 $\pmb{x}^*$。

1.9.2 矩阵范数

设矩阵 $\pmb{A} \in \pmb{R}^{n \times n}$,若与 $\pmb{A}$ 对应的一个实值函数 满足:

  • 正定性,其中
  • 齐次性
  • 三角不等式
  • 相容性

则称 为 $\pmb{R}^{n \times n}$ 上 $\pmb{A}$ 的一个矩阵范数

几种常用的矩阵范数

  • $F$ 范数($Frobenius$):
  • 行范数
  • 列范数
  • $2$-范数,其中 $\rho (\pmb{A}^T\pmb{A})$ 为 $\pmb{A}^T\pmb{A}$ 的谱半径

当 $\pmb{A}$ 是对称矩阵时,有:

参考文章

  1. 向量范数和矩阵范数 | 博客园