##线性方程组
矩阵、线性方程组的特性、范数不再赘述，请参考线性代数 或《科学计算导论》2.1、2.2、2.3
矩阵的条件数
矩阵的条件数刻画了矩阵对于非零矢量最大的伸展和压缩能力
矩阵的条件数越大，说明矩阵越接近奇异
直接解法 -《科学计算导论》2.4.1-2.4.8、2.5.1《数值方法与计算机实现》2.1、2.5.1、2.5.2
高斯消去法
LU 分解法
Gauss—Jordan
Cholesky
由于这部分知识在线性代数中已经学过，就不再过多介绍。
注意：
在高斯消元中，对角线上的元素aii会作为除数，如果aii很小或者为0则需要重新选取主元。
线性方程组解的精度 -《科学计算导论》11.5.1-11.5.3《数值方法与计算机实现》2.3
残差向量r = b -Ax
当A 为良态时，小的相对残差意味着解的相对误差也小
A 如果病态，稳定的算法可以得到小的残差，但解的精度不一定高
###迭代求解 不动点迭代 JACOBI A = D + (L + U) GAUSS-SEIDEL A = (D + L) + U
不动点迭代
雅克比法
高斯赛德法
##非线性方程
存在性和唯一性
如果f (x) 是闭区间[a，b] 上的连续函数，且有f(a)f(b)<0，则一维非线性方程f(x)=0 在区间[a，b] 内一定有的解
残差与条件数
只有在问题良态的条件下，残差小才意味着解是精确的
###非线性方程求解-《科学计算导论》5.1-5.4、5.5.1-5.5.5《数值方法与计算机实现》4.1、4.2、4.4
如果满足下式（C 为大于零的常数），称迭代法的收敛速度为r
若r = 1 且C < 1，收敛是线性的（Linear）
若r > 1，收敛是超线性的（Super-Linear）
若r = 2，收敛是平方的（Quadratic）
二分法
在区间内二分查找，较为简单，不过多描述
二分法的r = 1，C = 0.5
二分法的收敛速度是线性的
不动点法
f(x) = g (x) - x
xk+1 = g (xk)
如果|g'(x*)| > 1，不动点迭代式发散的
如果|g'(x*)| = C<1，不动点收敛的速度是线性的
如果|g'(x*)| = 0，不动点收敛的速度至少是超线性的
牛顿法
泰勒展开后截取前两项
f(xk + h)≈f(xk)+ f'(xk)h
r = 2，牛顿法是平方收敛的
割线法
割线法是一种准牛顿法
割线法的收敛是超线性的：r = 1.618
反插法
割线法利用前两次的迭代值决定一条直线，用这条直线与x 轴的交点作为一下次的迭代值
r = 1.839
二分法是比较安全的方法，但收敛速度是线性的，效率比较低
牛顿法、割线法和反插法是超线性收敛的，效率比较高；但是要求初值和真解比较接近，否则有可能不收敛，因此安全性不够好
在一个较小的有根区间外采用安全的二分法，在区间内采用高效的
迭代方法
典型例子：二分法+反插法
##优化-《科学计算导论》6.1-6.4、6.5.1-6.5.4
全局最小与局部最小
概念略
寻找，甚至验证全局最小值都很困难
一般优化算法都是寻求局部最小值
最优解的存在性和唯一性
如果f 在有界闭集S上连续，则f 在S 上存在全局最小值
如果S 不是闭的或无界，则f 在S 上可能没有全局或局部最小值
强制函数
如果连续函数f 在无界闭集S上是强制的，则f 在S 上存在全局最小值
凸集与凸函数
概念略
如果优化问题中的目标函数f 和约束集合S 都是凸的，就称为凸优化问题
凸函数f 在凸集S上的任意局部最小值，都是f在S上的全局最小值
严格凸函数f 在凸集S上的局部最小值，是f在S上的唯一全局最小值
如果f 在有界闭集S上严格凸，则f在S上存在唯一的全局最小值
如果f 在无界闭集S上严格凸，则f在S上存在唯一全局最小值的充要条件是f 在S上是强制的
####无约束优化
一维求导不再赘述
海森矩阵
对f 的临界点x*，观察海森矩阵在x* 的性质
如果Hf (x) 正定，则x* 是f 的最小值点
如果Hf (x) 负定，则x* 是f 的最大值点
如果Hf (x) 不定，则x* 是f 的鞍点
如果Hf (x) 奇异，则问题是病态的
拉格朗日函数
令
得到临界点(x*,λ*)
####一维优化
黄金分割搜索
与二分搜索相似
收敛速度是线性的：C = 0.618
逐次抛物插值
取两个端点和近似极值点，利用这三个点进行二次多项式的插值
取插值的二次多项式的最小值点作为函数极值点新的近似
一般情况下，当初始点接近极值点时能够收敛
超线性收敛：r = 1.324
牛顿法
将泰勒展开截断到二阶，有
迭代公式为：
当初始点与极值点足够接近时，牛顿法是平方收敛的
保护法
与非线性方程的迭代解法一样，一维优化的迭代解法中有
收敛速度慢但安全可靠的黄金分割搜索
收敛速度快但风险大的逐次抛物插值和牛顿法
因此在实际应用中，经常采用混合方案
###多维优化
最速下降法
最速下降迭代公式为：xk+1 = xk -αk ▽f (xk)
其中αk为
最速下降法的收敛速度是线性的
初值的选择很重要
牛顿法
迭代公式
牛顿法是平方收敛的，要比最速下降法的收敛速度快得多
但只有初始点距离问题最优解很近时，牛顿法才是收敛的
牛顿法并不需要搜索参数
如果Hf (x) 不正定，得到的方向不一定是函数的下降方向，需要另行处理