多元函数误差分析

基本概念：绝对误差 $\varepsilon(x)$ 和相对误差 $\varepsilon_r(x) = \frac{\varepsilon(x)}{x*}$

对于 $z=f(x_0,x_1,...x_n)$，有

$\varepsilon(z) \approx \sum_{k=1}^{n}|\frac{\partial f}{\partial x_{k}}| \varepsilon(x_{k})$

对于特例：

$\begin{aligned} \varepsilon(x_1+x_2) &=\varepsilon(x_1)+\varepsilon(x_2) \\ \varepsilon(x_1 \cdot x_2) & \approx|x_1| \varepsilon(x_2)+|x_2| \varepsilon(x_1) \\ \varepsilon(x_1 / x_2) & \approx \frac{|x_1| \varepsilon(x_2)+|x_2| \varepsilon(x_1)}{x_2^2} \end{aligned}$

比如 $z=xy$ 误差为 $|x|y'+x'|y|$。

应用：对于除法的情况，避免绝对值小的量当分母。

安利秦九韶算法来计算多项式。
在不同数据下误差小的算法就叫 稳定的算法。

例题：稳定的算法

看一个例子：利用递推式计算 $I_n$ 的估计值 $S_n$。

$I_n = e^{-1} \int_0^1 x^n*e^x dx \quad (n = 0, 1, ...,20)$

对积分值可以放缩：由于 $1 \leq e^x \leq e \quad(0<x<1)$，有

$\frac{e^{-1}}{n+1} \leq e^{-1} \int_0^1 x^n*e^x dx \leq \frac{1}{n+1}$

• 方法一：利用分部积分求得递推式

$\begin{cases} I_0 &= 1-e^{-1} \\ I_n &= 1-n I_{n-1},(n=1,2, \cdots) \end{cases}$

如果推出递推式用迭代法从小往大，$n>=20$ 的时候误差值就会变得非常大，甚至超出了预估值的范围（$S_{20} = -30.19$）.。
理由是初值有误差，每次迭代都会放大误差。那么能不能把放大误差变成缩小误差呢？

——把递推式中的 *n 换为 /n，从后往前推。

• 方法二：先算 $S_{30}$ 再往前推，最后误差极小，这时候这就是一个稳定的算法。

由 $I_n$ 的估计式，令 $S_n = \frac{1}{31}$。 反解上面的递推式，得 $I_{n-1} = \frac{1}{n}(1-S_n)$。

然后反过来跑递推，得到的 $S_1$ 能保证 $10^{-14}$ 的精确度。

数值方法

前人：$n \geq 5$ 时无显式求根公式

基本思想：迭代法逼近

• 第一步：对 $f(x)=0$ 的根进行隔离
• 第二步：利用迭代法计算一定精度的根近似值
• 从给定的一个出发值 $x_0$，产生一个序列 $x_0, x_1,...$

详见迭代法解线性方程组

二分法

二分夹逼，简单无脑，要求单调。

定理 误差满足 $|x_n-x^*|<\frac{|b-a|}{2^{n+1}}$

不动点迭代

偏理论的方法，略。

另外提到了收敛阶数 $r$：

$\lim\limits_{n\to\infty}\frac{|x_{n+1}-x^*|}{|x_n-x^*|^r} = a$

按 $r$ 大小分为线性收敛、超收敛、平方收敛等等。

迭代误差：

• 线性收敛：每次迭代误差放大 k 倍
• 超收敛 ($r>1$) 每次迭代误差是上一次误差的 $r$ 次方的 $k$ 倍数，在这个含义下，如果第一次误差 $1\%$，$r=2$，那么迭代一次后误差为 $0.01\% \times k$

牛顿迭代法（正确性根据引理，从略）

基本思想：泰勒公式将非线性函数线性化
设函数 $f(x)$ 在有根空间 $[a,b]$ 二次连续可微，泰勒后只取线性部分。

用切线方程的根近似原 $f(x)$ 的根，然后多次牛顿迭代近似

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

牛顿迭代法的几何意义：

上一次得到根 $x_1$，再在 $x_1$ 的地方做泰勒近似（做切线），在 $x$ 轴截到 $x_2$... 用上一个根迭代下一个根，nb 所以单变量牛顿迭代法也被称为切线法

一个例题，实际使用估计还得工具箱

有缺陷的牛顿迭代法

f=inline('x*exp(x)-1');
f1=inline('(x+1)*exp(x)');
x0=0.5;er=1;k=0;
while er>0.00001
    x=x0-f(x0)/f1(x0);
    er=abs(x-x0)
    x0=x; k=k+1
end

缺陷：

1. 被 0 除错误，根使得原函数和导函数都为 0 的情况，称为二重根
   可以考虑加一个 eps？
2. 死循环：对于特殊函数(如 $\arctan x$）无法使用
   多次迭代无进展的话跳出，换个算法

牛顿迭代法改进：弦截法

$x_{n+1} = x_n - \frac{(x_n - x_{n-1})f(x_n)}{f(x_n) - f(x_{n-1})}$

不使用切线，而是使用上两次迭代的点的线（也就是割线、弦），依旧是看其与 $x$ 轴的交点。

看看两个解之间的距离是不是逐渐变小且函数值是不是逐渐变小来判断是否收敛、是否适用于牛顿迭代法

范数简介

向量范数

向量范数公理化的定义：如果一种映射 $f: R^n \to R$ 的结果，映射出来的 $\| x \|$ 满足正定性、齐次性、三角不等式，则被称为范数。

范数是对长度的推广，三角不等式需要根据柯西不等式证明得到。

• 1-范数：${\|x\|}_1 = \sum\limits_{i=1}^n|x_i|$
• 2-范数：$\|x\|_2 = \left(\sum\limits_{i=1}^n|x_i|^2\right)^{1/2}$
• 无穷范数：$\|x\|_\infty = \max\limits_{1 \leq i \leq n}|x_i|$

一般向量而言，无穷范数 < 1-范数 < $n*$无穷范数。

性质：向量空间的任何范数均等价

1-范数、无穷范数随便选，算起来都简单

矩阵范数

公理化定义依旧是：正定性、齐次性、三角不等式。

对于向量的 1-、2-、无穷范数，是对向量的每一个元素进行处理、加和，矩阵中引申到矩阵的每一个元素进行处理、加和，最后将和进行开 n 次根。

$\begin{aligned} \| A \|_{m_1} &= \sum_{j=1}^n\sum_{i=1}^m|a_{ij}| \\ \| A \|_{m_2} &= \left( \sum_{j=1}^n\sum_{i=1}^m|a_{ij}|^2 \right) ^ \frac{1}{2} \\ \| A \|_{m_\infty} &= \max_{i,j}{|a_{ij}|} \quad 1 \leq i \leq m,1 \leq j \leq n \\ \| A \|_F &= \left( \sum_{j=1}^n\sum_{i=1}^n a_{ij}^2 \right) ^ \frac{1}{2} \end{aligned}$

注意 F-范数 只适用于实矩阵。

这种定义不好用，所以有了另一种矩阵范数：矩阵算子范数。

矩阵算子范数

逐渐晕掉

对于矩阵 $A \in R^{n \times n}$，其算子范数的定义为

$\| A \| = \max_{x \neq 0} \frac{\| Ax \|}{\|x\|}$

其定义是基于向量范数的。对于二阶有：

$\| A \|_2 = \max_{x \neq 0} \frac{\| Ax \|_2}{\|x\|_2}$

或

$\| A \|_2 = \max_{\|x\|=1} \| Ax \| _2$

算子的英文是 Operator。

矩阵范数的相容性

如果三种矩阵范数满足： $\|AB\|_c \leq \|A\|_a \cdot \|B\|_b$ 则称这三种矩阵范数相容。

如果 $\|AB\| \leq \|A\| \cdot \|B\|$ 则称这种矩阵范数是自相容范数。

$\| A \|_{m_\infty}$ 是不相容范数。

定理：

$\| A \|_2 = \max_{x \neq 0} \frac{\| Ax \|_2}{\|x\|_2} =\sqrt{\lambda_{max}(A^TA)}$

不仅如此，若 $A$ 为对称矩阵，$\sqrt{\lambda_{max}(A^TA)} = \lambda(A)$。之所以这么定义，是为了把任意矩阵 $A$ 变成对称矩阵 $A^TA$，而对称矩阵一定有实特征值，从而保证了范数的非负性。

这个公式告诉我们，2-算子范数不仅好用（相容），而且好算23333
目前其他的算子范数不好算。

定理：矩阵所有特征值小于等于矩阵的任意范数。而二范数又等于最大的特征值，则有：

$\| A \|_2 \leq \| A \|_c$

矩阵的条件数

$Ax=b$，右端有一点扰动量 $\delta b$，引起了方程解的扰动 $\delta x$：

$A(x+\delta x) = b + \delta b$

$A\delta x = \delta b, \delta x = A^{-1}\delta b$，由矩阵的相容性（假设我们只使用相容的矩阵范数）有

$\left\| \delta x \right\| = \left\| A^{-1} \right\| \left\| \delta b \right\|$

又由 $Ax=b$，有 $\left\| b \right\| = \left\| A \right\| \left\| x \right\|$

以上两式整理得：

$\frac{\left\| \delta x \right\|}{\left\| x \right\|} = \left( \left\| A \right\| \cdot \left\| A^{-1} \right\| \right) \frac{\left\| \delta b \right\|}{\left\| b \right\|}$

$\|A\| \cdot \|A^{-1}\|$ 越大，即使 $\delta b$ 小，$\delta x$ 也会很大

因此，定义条件数：

$Cond(A) = \|A\| \cdot \|A^{-1}\|$

条件数很大时，$Ax=b$ 是病态问题；条件数很小时（几百、几千、几万），$Ax=b$ 是良态问题。

15 阶希尔伯特矩阵的条件数为 $10^{10^{16}}$，因此，与希尔伯特矩阵的数值计算是十分困难的。

MATLAB 对范数的支持

norm 求范数，cond 求条件数。

非线性方程组

牛顿法，就是最优化嘛。由于我学过最优化，这部分就略了。