数值分析基础第1章:引论

本文的内容主要来自关治的《数值分析基础(第3版)》第1章《引论》和老师的PPT。

# 1 数值分析的研究对象

(略)

# 2 数值计算的误差

# 2.1 误差的来源与分类

误差大致分为4类:

  1. 输入数据的误差;
  2. 舍入误差:来源于计算机的数字是有限的;
  3. 截断误差:用有限的过程代替无限的过程,或用简化的问题代替不易计算的原问题;
  4. 误差在计算过程中的传播。

# 2.2 绝对误差和相对误差、有效数字

定义2.1formula是精确值,formula是一个近似值。formula称为formula绝对误差,而formula称为formula相对误差

定义2.2 因为formula通常是未知的,一般只能给出formula的上界formulaformula称为formula绝对误差界,而formula称为formula相对误差界

对于一个实数,取有限位数作为近似值,采用四舍五入的方法。这样得到的近似值,绝对误差界为最后数位的半个单位。因此引入了有效数字概念。

定义2.3formulaformula的一个近似值,formula,其中formula为整数,formulaformula。如果有formula,则称formula具有formula有效数字formula

有效数字就是寻找误差在formula以内(包括formula)的那位,计数之前数字的个数。

formula的近似值formula,则:

  1. 如果formulaformula位有效数字,则:

    formula

  2. 如果:

    formula

    formula至少有formula位有效数字。

1的证明比较简单,这里证明2,由formula可以证明。

# 2.3 求函数值和算术运算的误差估计

向前误差分析formula的浮点数表示为formula。则:

formula

因而,每次乘法相对误差加倍。这里,formula由于超出浮点数表示能力而被忽略。

向后误差分析 把计算结果的误差归结为原始数据经扰动之后的精确的计算结果的误差分析叫做后向误差分析

formula,如果参量formula有误差,则formula也会有误差。若formula的近似值为formula,相应的解为formula,则formula的绝对误差和相对误差分别为:

formula

把两个数formulaformula看成二元函数,则有:

formula

# 2.4 计算机的浮点数表示和舍入误差

在计算机上,实数系统formula是用浮点数系统formula来近似的。实数formulaformula进制浮点数系统下的表示为:

formula

其中:

  • formula:符号位,formula为负数,formula为正数;
  • formula:尾数,formula称为字长;
  • formula:指数。

二进制浮点数系统formula为:

formula

其中formula

浮点数的近似formula,有两种:

  • 截断
  • 舍入:IEEE属于这种。

定义formula为机器精度:

formula

# 3 病态问题、数值稳定性与避免误差危害

# 3.1 病态问题与条件数

敏度分析是研究formula有微小变化formula时,函数值formula会发生多大的变化:

formula

formulaformulaformula的条件数。

formula很大时,自变量的微小变化就可能引起函数值的巨大变化,则称formulaformula点是病态的;否则称formulaformula点是良态的。

一个计算问题是否病态是问题本身的固有属性。

formula

例如:Wilkinson多项式formula求根就属于病态问题,用特征值的定义求求解特征值同样是病态问题。

# 3.2 数值方法的稳定性

一个数值方法,如果初始数或计算过程某一不有微小的改变,由此引发的计算结果也只是微小的变化,则称该方法是数值稳定的,否则称为数值不稳定的。

一般来说,如果具有初始误差formula,计算formula步后的误差为formula,若方法是数值稳定的,则存在与formula无关的常数formula使得formula

  • formula,线性型的误差增长;
  • formula,指数型的误差增长。formula稳定,formula不稳定。

TODO: 给个例子。

# 3.3 避免误差危害

  • 避免相近的数相减;
  • 避免和绝对值大的数相乘;
  • 避免和绝对值小的除数相除。

数学上等价formula计算上等价:例如对于formula,采用formula,可以解决formula情况下的问题;使用formula替代formula可以避免formula时精度的损失。同时对于求解formula次多项式,可以利用分配律合并多项式,达到formula次乘法和formula次加法。

选用公式也很重要,对于无穷级数毕竟求解的情况,通常选用同号数列求和极限比交替数列求和极限收敛速度更快。

# 4 线性代数的一些基本概念

矩阵乘法的定义 定义formula的一个运算,称为矩阵乘法formula,其中formula

矩阵迹的定义formula,矩阵formula的迹是其所有对角元素之和。formula

定理formula,则formula

证明:

formula

非奇异矩阵的定义 矩阵formula称为非奇异的可逆的,若存在一个矩阵formula,使得formula。其中formula称为formula的逆矩阵,如果formula的逆矩阵不存在,则称其是奇异的

注:对于有结合律且有左右逆的代数系统中,左逆一定等于右逆。此外,formula

线性方程组的可解性定理 formula可逆,则方程组formula有唯一解formula

formula非奇异formula齐次方程组formula只有formula解(平凡解)formula formula

矩阵转置的定义formula,它的转置formula可通过交换formula的行和列得到,即formula

注:formulaformulaformula

对称矩阵的定义,若formula,则称formula为对称矩阵。

注:formula一定是对称矩阵。

# 4.1 矩阵的特征值问题、相似变换化标准形

矩阵的特征值问题 对于formula,若有formula和非零向量formula,使得:

formula

则称formula为特征值formula对应的特征向量。

特征值的求解 formula,多项式formula称为formula的特征多项式,方程formula称为特征方程,若formulaformula的根,则formulaformula的特征值。

注:由于实际上,特征多项式是一个高阶多项式,所以直接使用特征多项式求解特征值是个病态问题。

谱的定义 任意formula,一定有formula个特征值。全体特征值的集合称为formula,记作formula

formula

还定义谱半径

formula

有:

  • formula
  • formula

注:展开特征多项式就能得到这个结论。

可对角化的定义formula,若存在非奇异矩阵formula,使得:

formula

为对角阵,则称formula可对角化。formula可对角化的充要条件是它有formula个线性无关的特征向量。

实对称矩阵的特征值问题formula是实对称矩阵,则formula的特征值都是实数,可以对角化。且不同特征值的特征向量相互正交。

可对角化的充分条件 矩阵formula的不同特征值对应的特征向量是线性无关的。若formulaformula个不同的特征值,则formula可对角化。

代数重数的定义formula具有重特征值,即特征方程有重根,则:

formula

亦即formula是特征方程的formula重根,formula称为特征值formula代数重数

formula

几何重数的定义formula对应的最大线性无关特征向量的个数为formula,则formula就是其次方程组formula的基础解系所包含最大线性无关解的个数,亦即特征值对应的特征子空间的维数,formula称为特征值formula几何重数

几何重数小于代数重数 formula

可对角化的充要条件formula具有重特征值,则formula可对角化的重要条件是每个特征值的几何重数和代数重数相等。

Jordan标准型 任意复方阵可以通过相似变换化为Jordan标准型J:

formula

每个formula对应一个特征值formula,它是formula个小块组成的块对角阵:

formula

# 4.2 线性空间与内积空间

# 4.2.1 线性空间

线性空间的定义formula是一个数域,formula是一个非空集合,在formula上定义两种运算:

  • 加法formula,有唯一formula(封闭性),且:
    • formula(加法交换律);
    • formula(加法结合律);
    • 有唯一零元素formula,使得formula
    • 对每个formula,有唯一的负元素formula,使得formula
  • 数乘formula,有唯一formula(封闭性),且:
    • formula(单位元);
    • formula(数乘的交换律);
    • formula(数乘对数的结合律);
    • formula(数乘对向量的结合律)。

formula为数域formula上的线性空间(或数域formula上的向量空间)。

线性子空间的定义 若线性空间formula的一个子集formula按照formula的加法和数乘也是一个线性空间,则称formulaformula线性子空间

例子:实向量formula、复向量formulaformula闭区间上的连续函数formula、实矩阵formula、复矩阵formulaformula闭区间上最高次数为formula的多项式formula都能组成线性空间。

线性无关的定义formula是一个线性空间,formula,若存在不是全零的formula,使得:

formula

则称formula线性相关的,反之,则称它是线性无关的。

例子:在formula中,formula是线性无关的,在formula中,formula是线性无关的。

基和维数的定义formula,且formula,有formula,则formula构成formula的一组,空间的维数为formula

例子:formulaformula是一组基,formulaformulaformula是线性无关的,formula

# 4.2.2 内积空间

内积的定义formula是数域formula上的线性空间,内积formula,且有:

  1. formula
  2. formula
  3. formula
  4. formula,且formula

则称formulaformulaformula内积,定义了内积的空间称为内积空间

欧氏空间上的一种内积 formula,则内积定义为:

formula

酉空间上的一种内积 formula,则内积定义为:

formula

此外也可以定义一种带权内积:formula

正交的定义 若向量formula满足formula,则称它们是正交的。两个向量的集合formulaformula,如果每个formula和每个formula正交,则称formulaformula正交。

正交集合的定义 formula是非零向量的集合,若formula,则称其为正交集合

定理正交是线性无关的充分条件 正交集合formula中的向量是线性无关的。

证:假设formula,假设有formula,两边同时点乘formula,有formula,由formula和正定性,我们知道formula,故formula,同理formula,集合formula中的向量线性无关。

正交基的推论 若正交集合formulaformula个向量,则它是formula的一组基。

连续函数内积的定义formula,则它们的formula内积为:

formula

权函数的定义 若定在formula上的可积函数formula满足:

  1. formula
  2. formula的任一子区间上formula不恒为零。

formulaformula上的一个权函数

利用权函数可以定义带权formula内积:

formula

Cauchy-Schwarz不等式formula是一个内积空间,对任一的formula有:

formula

等号成立当且仅当formula线性相关。

证:这里仅给出实数域上的证明,对任意formula,考虑内积formula,故判别式formula,得证。

Gram-Schmidt正交化方法formula是内积空间formula中的一个线性无关元素系列,则:

formula

生成formula中一个正交序列formulaformula的一组基。

若要求归一化,formula。则可得到QR分解。

经典的Gram-Schmidt正交化

  1. formula
    1. 计算formula
    2. 计算formula
    3. 计算formula,如果formula,停止,否则formula

改进的Gram-Schmidt正交化

  1. formula
    1. formula
    2. formula
      1. 计算formula
      2. 计算formula
    3. 计算formula,如果formula,停止,否则formula
代码
测试结果

# 4.3 范数、赋范线性空间

范数的定义formula是数域formula上的线性空间,定义formula,满足:

  1. 正定性:formula,且formula
  2. 齐次性:formula
  3. 三角不等式:formula

formulaformula范数(模),定义了范数的线性空间称为赋范线性空间

常见的范数 对于formula可定义范数结构:

  • formula-范数:formula
  • formula-范数:formula
  • formula-范数:formula
  • formula-范数:formula

内积与2-范数的关系 通过内积可定义formula-范数:

formula

formula,其夹角formula被定义为:

formula

平行时,即formulaformula时,Cauchy-Schwarz不等式取等号。

距离的定义formula是任一非空集合,formula中的任意两点formulaformula与之一一对应,且满足:

  1. 非负性:formula,且formula
  2. 对称性:formula
  3. 三角不等式:formula

formulaformula上的一个距离,定义了距离的集合formula称为一个距离空间

范数与距离的关系formula是赋范空间,则formula的距离可定义为:

formula

常见距离相似度

  1. Hamming距离:序列最小替换以相同的树木;
  2. 欧氏距离:formula
  3. 曼哈顿距离:formula
  4. 切比雪夫距离:formula
  5. 余弦距离(实际上是相似度):formula
  6. Jaccard相似系数:formula
  7. 相关系数formula

K近邻(KNN)算法 监督学习,选取最近的formula个训练数据点,预测数据分类为这formula个数据点的多数类别。

k-means聚类算法 无监督学习,确定有formula个分类后,选择formula个距离较远的初始数据点作为质心,而后每个数据点离哪个质心近,就归类为质心所属的集合,再重新计算每个集合的质心,循环往复直到质心位置变化量小。

范数等价formulaformula是线性空间formula的两个范数,若存在正的常数formulaformula,使得:

formula

则称范数formula和范数formula等价。

有限维空间中的任意两个范数等价。

# 5 几种常见矩阵的性质

# 5.1 正交矩阵和酉矩阵

正交矩阵的定义formula,若满足:

formula

则称formula正交矩阵

正交矩阵的性质 正交矩阵有如下的性质:

  1. formula不同的列向量相互正交,且各列向量的2-范数为1;
  2. formula,且formula也是正交矩阵;
  3. formula
  4. formulaformula是同阶的正交矩阵,则formulaformula都是正交矩阵。

# 5.2 对称矩阵和对称正定矩阵

对称阵的定义 如果formula,有formula,则称formula为对称阵。

对称阵的性质

  1. formula的特征值均为实数,且有formula个线性无关的特征向量;
  2. formula对应于不同特征值的特征向量必正交;
  3. 存在正交阵formula使得formula为对角阵。

性质1的证明:

formula

# 5.3 初等矩阵

# 5.4 可约矩阵

# 5.5 对角占优矩阵

2016-2020 Ziping Sun
京ICP备 17062397号