##拟合问题
-《科学计算导论》3.1-3.4、3.5.1《数值方法与计算机实现》6.2.1、6.2.4、2.5.3
拟合问题的一般形式
给定m 个数据点(xi，yi)，假设x 和y 满足y = f(t，x)，t 为参数向量找到最佳的参数向量t，使得代价函数：
min(t) Σ[yi-f(t,xi)]2
###超定方程与欠定方程
给定线性方程组Ax = b，其系数矩阵A 为m×n 维，我们已经讨论了m = n 时的求解问题
如果m > n：方程的数目多于未知数的数目，称为超定方程
如果m < n：方程的数目少于未知数的数目，称为欠定方程
最小二乘
若系数矩阵A 的各列线性独立，即rand (A) = n，则解是唯一的
若系数矩阵A 欠秩，即rand (A) < n，则解是不唯一的
正规方程
用Cholesky 分解法求解
复杂度：
方程变换：主要是矩阵相乘，复杂度约为(mn^2)/2
Cholesky 分解法：复杂度约为n^3/6
正规方程方法可能会导致敏感性的恶化
QR 分解
对于m×n 的矩阵A，寻找一个m×m 的正交变换阵Q，使得
通过一组Householder 变换，实现了对系数矩阵的QR 分解
详细请看求解举例，过程较为繁琐，不一一列举。
由乘法次数考察基于Householder 变换的QR 分解复杂度
对于m×n 的系数矩阵，需要引入n 个Householder 变换阵
对一个列矢量进行Householder 变换，需进行的乘法为2 (m-i)
总的乘法次数为
效率比较
当m≈n 时，两种方法相当
当m>>n 时，QR 分解的复杂度是正规方程方法的两倍
##插值
-《科学计算导论》7.1、7.2、7.3.1-7.3.3《数值方法与计算机实现》5.1、5.2.1、5.4.1
利用数学函数在已知点上的取值计算其它点上的值
插值函数在基底函数张成的集合中，是基底函数的线性组合
存在性和唯一性
如果给定m个数据点和n个基底函数，则At=y的系数矩阵A 是m×n维
m > n，插值问题一般没有解
m < n，插值问题解不唯一
m = n 且系数矩阵A 不奇异，插值问题有唯一解，插值函数可以精
确地通过给定数据点参数t求解的敏感性取决于系数矩阵A的条件数cond (A)，系数矩阵就与基底函数的选择有很大关系
单项式基底
霍纳法则
对于多项式：Pn-1 (x)
求解复杂度
加法n次
乘法：n(n+1)/2
按霍纳法则改写为
复杂度：加法n 次，乘法也是n 次
拉格朗日插值
拉格朗日基底函数
拉格朗日插值多项式
牛顿基底函数
牛顿基底函数
牛顿插值多项式
