计算方法 函数逼近与FFT 曲线拟合的最小二乘法ch03d r.ppt

第三章函数逼近与FFT 本节内容 曲线拟合 曲线拟合 最小二乘 最小二乘求解 最小二乘求解 最小二乘求解 最小二乘求解 举例 举例 多项式拟合 举例 正交多项式拟合 正交多项式拟合 正交多项式的构造 几点注记 举例 非线性最小二乘 作业 * * 计算方法 —— 曲线拟合的最小二乘法 曲线拟合 曲线拟合基本概念 最小二乘算法 最小二乘拟合多项式 能否找到一个简单易算的 p(x) ，使得 f(x) ? p(x) 已知 f(x) 在某些点的函数值： ym xm y1 x1 … y0 f(x) … x0 x 但是 m 通常很大 yi 本身是测量值，不准确，即 yi ? f (xi) 这时不要求 p(xi) = yi , 而只要 p(xi) ? yi 总体上尽可能小 使 最小 使 最小 p(xi) ? yi 总体上尽可能小 使 最小 常见做法 太复杂 ? 不可导，求解困难 ? 最小二乘法：目前最好的多项式曲线拟合算法 曲线拟合的最小二乘问题 这个问题实质上是最佳平方逼近问题的离散形式。可以将求连续函数的最佳平方逼近函数的方法直接用于求解该问题。 已知函数值表 ( xi , yi )，在函数空间 ? 中求 S*(x) ，使得 其中 ?i 是点 xi 处的权。 对任意 S(x) ? ? = span{?0, ?1, ?, ?n}，可设 S(x) = a0?0 + a1?1 + · · · + an?n(x) 则求 S*(x) 等价于求下面的多元函数的最小值点 k = 0, 1, …, n 最小值点 ( k = 0, 1, … , n ) 这里的内积是离散带权内积，即 ， 法方程 G 法方程 法方程存在唯一解 det(G) ? 0 Haar条件 ?0, ?1, ?, ?n 的任意线性组合在点集 x0, x1, ?, xm 上至多只有 n 个不同的零点，则称 ?0, ?1, ?, ?n 在点集 x0, x1, ?, xm 上满足 Haar 条件 ?0, ?1, ?, ?n 线性无关 m ? n 若 ?0, ?1, ?, ?n ? C[a, b] 在点集 x0, x1, ?, xm 上满足 Haar 条件，则法方程的解存在唯一 设法方程的解为： a0* , a1*, ?, an* , 则 S*(x) = a0* ?0 + a1* ?1 + · · · + an* ?n(x) 结论 S*(x) 是 f(x) 在 ? 中的 最小二乘解 例：给定函数值表，求 f(x) 的最小二乘拟合函数 S*(x) 0.24 2.52 0.56 2.77 1.00 2.99 0.27 1.73 0.10 2.01 -0.29 2.23 -0.45 1.24 -0.26 0.65 0.23 0.24 -1.10 0.95 yi xi 解： 在坐标平面上描出上表中的数据点，根据点的分布情况，选取基函数 得法方程 解得 所以 最小二乘问题中，如何选择数学模型很重要，即如何选取函数空间 ? = span{?0, ?1, ?, ?n} ，通常需要根据物理意义，或所给数据的分布情况来选取合适的数学模型。 ?＝Hn= span{1, x, ..., xn}, 即 ?i = xi, 则相应的法方程为 此时 为 f(x) 的 n 次最小二乘拟合多项式 多项式最小二乘曲线拟合 例：求下面数据表的二次最小二乘拟合多项式 得法方程 2.7183 1.00 2.1170 0.75 1.2840 0.25 1.0000 0 1.6487 0.50 f (xi ) xi 解： 设二次拟合多项式为 解得 所以此组数据的二次最小二乘拟合多项式为 (1) 若题目中没有给出各点的权值 ?i ，默认为 ?i = 1 (2) 该方法不适合 n 较大时的情形 （病态问题） 带权正交（离散情形） 给定点集 以及各点的权系数 ，如果函数族 满足 则称 关于点集 带权 正交 若 ?0, ?1, ?, ?n 是多项式，则可得正交多项式族 用正交多项式做最小二乘 设多项式 p0, p1, ?, pn 关于点集 x0, x1, ?, xm 带权 ?0, ?1, ?, ?m 正交，则 f(x) 在 Hn 中的最小二乘拟合多项式为 其中 k