斯坦福 CS205A 数值计算讲义

### 斯坦福 CS205A 数值计算讲义知识点概述 #### 一、数学回顾 ##### 1.1 初步：数和集合 - **基础概念**：介绍基本数学符号及其含义，如自然数、整数、有理数、实数等。 - **集合论简介**：涵盖集合的基本定义、集合的运算（并集、交集、补集等）。 ##### 1.2 向量空间 - **定义向量空间**：向量空间的定义及其重要性。 - **张成、线性独立性和基**：讨论如何通过一组向量来描述整个向量空间；线性独立的概念及其实用意义；以及基的定义及其在向量空间中的作用。 - **重点：\(R^n\)空间**：特别强调在现实世界应用中最常见的向量空间——\(R^n\)空间，并探讨其几何意义和应用背景。 ##### 1.3 线性性 - **矩阵介绍**：矩阵的定义、类型及运算规则。 - **标量、向量和矩阵**：深入探讨这些基本数学对象之间的关系及运算。 - **矩阵存储和乘法方法**：讲解不同类型的矩阵存储格式及其对应的乘法实现方式。 - **模型问题：\(A\mathbf{x}=\mathbf{b}\)**：介绍线性方程组的基本形式及其解决方法。 ##### 1.4 非线性：微分计算 - **一元微分**：微积分的基础概念及一元函数的微分。 - **多变量微分**：将微分的概念扩展到多变量函数上，包括梯度、雅可比矩阵等。 - **优化**：利用微分工具进行函数极值的寻找，包括局部最优与全局最优的概念。 ##### 1.5 练习 - 提供针对本章内容的练习题，帮助巩固所学知识。 #### 二、数值计算和误差分析 ##### 2.1 存储带小数部分的数字 - **定点表示**：介绍定点数表示法，及其在计算机内存中的存储方式。 - **浮点表示**：更详细地讨论浮点数的表示法，包括IEEE 754标准。 - **其他选择**：探讨除定点和浮点之外的数字表示方式。 ##### 2.2 理解误差 - **误差分类**：分为截断误差和舍入误差两类，讨论它们产生的原因及影响。 - **条件、稳定性和精度**：解释这些概念对于数值计算的重要性。 ##### 2.3 实际问题 - **计算向量范数**：介绍不同类型的向量范数及其计算方法。 - **大规模例子：求和**：分析在大规模数据集上的数值求和过程中的常见问题及解决策略。 ##### 2.4 练习 - 通过具体实例加深对误差分析的理解。 #### 三、线性代数 ##### 第一部分：线性系统和LU分解 - **线性系统的可解性**：探讨线性方程组解的存在性与唯一性。 - **自适应解决方案策略**：介绍根据系统特性选择合适的求解方法。 - **高斯消元**：详细介绍高斯消元法及其变种（如前向和后向替代），并分析其效率。 - **LU分解**：LU分解的原理、构造方法及其应用。 ##### 第二部分：设计和分析线性系统 - **解决方程组**：多种不同的线性方程组求解方法，如回归、最小二乘法等。 - **线性系统的特殊性质**：包括正定矩阵的乔列斯基分解、稀疏矩阵等。 - **灵敏度分析**：讨论系统对输入变化的敏感程度，包括矩阵和向量范数的概念。 ##### 第三部分：列空间和QR - **正规方程的结构**：介绍正规方程的定义及其与线性系统的联系。 - **正交性**：正交向量和正交矩阵的概念及其重要性。 - **格拉姆-施密特正交化**：一种常用的向量正交化方法。 - **厄尔霍德变换**：用于构造正交矩阵的一种方法。 - **降阶QR分解**：QR分解的一种特殊情况，适用于特定场景下的计算。 ##### 第四部分：特征向量 - **动机**：介绍特征向量在统计学、微分方程和谱嵌入等领域中的应用。 - **特征向量的性质**：包括对称矩阵和正定矩阵的特征值和特征向量的特点。 - **计算单个特征值**：介绍几种常用的计算方法，如幂迭代法、逆迭代法等。 - **寻找多个特征值**：包括缩减法、QR迭代法等高级技巧。 ##### 第五部分：奇异值分解 - **推导奇异值分解**：介绍奇异值分解的原理及其计算方法。 - **奇异值分解的应用**：包括解决线性系统、主成分分析等方面的应用。 #### 四、非线性技术 ##### 第一部分：非线性系统 - **单变量根查找**：介绍二分法、不动点迭代法、牛顿法等多种单变量方程求根方法。 - **多变量问题**：扩展至多变量方程组的求解，包括牛顿法及其变体。 ##### 第二部分：无约束优化 - **无约束优化：动机**：介绍无约束优化问题的实际应用场景。 - **最优性**：讨论最优解的定义及其判别条件。 - **一维策略**：如黄金分割搜索法。 - **多变量策略**：包括梯度下降法、牛顿法及其变体BFGS等。 ##### 第三部分：约束优化 - **动机**：解释约束优化问题的实际背景。 - **约束优化理论**：包括KKT条件等关键概念。 - **优化算法**：顺序二次规划（SQP）、障碍方法等。 - **凸规划**：介绍线性规划等凸优化问题的特点及求解方法。