第三章_课件3.doc

3 最佳平方逼近 前面讨论的最佳一致逼近是在最大模（逐点）意义下的最佳逼近问题 本节主要讨论平均意义下的最佳逼近问题，即 最佳平方逼近 主要分两种情形：1. 连续意义下在空间中讨论2. 离散意义下在维欧氏空间中讨论，只要求提供的样本值 一、连续情形的最佳平方逼近问题（在中） 整体逼近误差的度量（范数）：为此引入内积空间： 上满足可积的函数的全体，且 . 将上述作为度量 由逼近空间的不同分为两种连续情形的最佳平方逼近问题逼近空间1：代数多项式空间逼近空间2：三角多项式空间 以下主要讨论代数多项式空间l 问题的提法对，求，使得 ， （*1）称为的最佳平方逼近多项式，为子空间对函数的最佳逼近.l 问题的适定性 一般最佳逼近问题的存在性，已经讨论（见书2节）下面讨论唯一性定理 对，在中存在的唯一最佳平方逼近多项式.证明 用反证法.设在中有两个不同的最佳逼近多项式，令， 记 则有即也是的最佳逼近多项式 . , 与假设矛盾，证毕. l 问题的收敛性 一般最佳逼近问题的收敛性，都可由最佳逼近问题的提法以及Weierstrass定理可得：最佳逼近问题是收敛的.l 算法1. 内积空间中最佳逼近多项式的特征性质定理8 ， 是的最佳逼近多项式 误差函数与中的任意多项式正交，即. 证明 “必要性”， 用反证法。设，使.令， ，则 .即不是的最佳逼近多项式，矛盾，从而必要性得证.“充分性”若，有，则.为的最佳逼近多项式. 充分性得证. 其几何意义见下图,从图中可见, 在中的正交投影便是的最佳逼近多项式. 2. 最佳逼近多项式的法方程组设的维子空间 =span,其中 是的线性无关多项式系.对，设其最佳逼近多项式可表示为: 由 即 （*2） 其中称(*2)式为最佳逼近多项式的法方程组（或正规方程组）.记 阶对称矩阵 由的线性无关性，可证明正定，即上述法方程组的解存在且唯一 .例 设，求在上的一次最佳平方逼近多项式.解 设所求的最佳一次逼近多项式为，经计算可得：.代入法方程组 即 在上的一次最佳平方逼近多项式为：.缺陷：该算法是利用中的幂函数基，求最佳平方逼近多项式.当较大时，由法方程组（*3）的系数矩阵是高度病态的，求解时，舍入误差很大. 为避免上述缺陷，利用正交多项式基函数，可保证计算的可靠性.3. 正交多项式(1)定义 定义在上的函数系称为的带权正交基(称为上的带权的次正交多项式)，若它满足： 恰为次多项式，即 ； ，特别，若，则称为上的标准（正规）正交基.易知：对，有 . (2) 几类特殊的带权正交多项式 (a). 勒让德（legendre）多项式设-1，1上，令，由正交化可得勒让德多项式，具体表达式是 实用中，由于求高阶导数较麻烦，因而常按以下递推公式计算 称为勒让德多项式. 称为-1，1上的正规正交基.由上述递推式可知：当为偶数时，为偶函数；当为奇数时，为奇函数.(b). Chebyshev多项式 . 由Chebyshev多项式的性质3知，是-1，1上带权的次正交多项式.上述定义的也称为第一类Chebyshev多项式.(c).其它正交多项式 .第二类Chebyshev多项式.它是-1，1上带权的次正交多项式.拉盖尔（Laguerre）多项式.它是上带权的次正交多项式.埃尔米特(Hermite)多项式.它是上带权的次正交多项式.4. 利用正交多项式作基函数建立法方程组将法方程组（*2）中的用 代替，有 若两两正交（这时称该多项式系为空间的正交基），则矩阵成为对角矩阵，可直接得解.此时，最佳逼近多项式为： 称上式为的广义富氏展开，相应的系数称为广义富氏系数.5. 近似Chebyshev逼近利用带权的Chebyshev正交多项式，及可给出的次最佳平方逼近多项式： (*4) 其中： ：上满足可积的函数的全体，.称(*4)式为按Chebyshev多项式展开的部分和.可以证明,，当时，一致收敛于（称为的Chebyshev级数）， 又Chebyshev多项式展开式的系数随着的增大，迅速趋向于零 当充分大时： .而在-1，1上具有个交错点，则由Chebyshev定理知，可作为的近似Chebyshev逼近多项式.例 求的三次Chebyshev最佳平方逼近多项式.解 由 (*4)式， ，其中： 即得 再利用在幂函数下的表示式可得： l 三角多项式最佳平方逼近被逼近函数：周期函数逼近空间：三角多项式空间设是以为周期的函数，定义相应的内积和范数为：， 选取上的逼近函数空间，其中.函数系构成三角多项式空间的一组正交基，即.则由前面的讨论知，空间关于的最佳平方逼近多项式唯一存在，且可表示成，其中 ， .即三角多项式最佳平方逼近恰好是的富氏级数的部分和，而为富氏系数.由富氏级数的收敛性定理知：若在上平方可积，则平方收敛到，即 .二、离散情形的最佳平方逼近问题（在欧氏空间中） 即数据拟合的最小二乘法 整体逼近误差的度量（范数）：为此引入一特殊内积空间：n维欧氏空间： ，. 这时的内积就是向量的点积将上述作为度量 由逼近空间的不同分为两种离散情形的最佳平方逼近问题逼近空间1：代数多项式空间逼近空间2：三角多项式空间 逼近空间：代数多项式空间l 问题的提法对给定的个样本点，记问题：求，使得 ,或： 其中 称为关于数据的最小二乘逼近（拟合）多项式 .l 问题的适定性 其存在性与唯一性，在讨论（构造）算法时得证。l 算法关键：将最小二乘逼近问题转化为求多元函数的极小值问题令 则问题转化为求 求使得多元函数达到极小值 必要条件即得最小二乘逼近多项式的法方程组 上述方程是关于的线性方程组，其矩阵形式为 （&1）由于点互异，上述法方程组的解是存在且唯一的。（可证明（&1）的系数矩阵为对称正定阵。对称性显然。下证其正定性，有(*)其中 等号当且仅当成立，即次多项式有个零点，而，则 ，即当且仅当时，(*)式等号成立。 的正定性得证。 ） 利用（&1）解出 最小二乘拟合多项式： .例 某物质的溶解度和温度的关系经测定满足下面数据表，试建立该问题的数学模型.810121620304060100y0.881.221.642.723.967.6611.9621.5643.16将的数据点描在坐标平面上，如下图所示.可推测与近似成抛物线关系，即，其中是待定常数.问题：求 ，使得其中为所求的最小二乘逼近（拟合）函数.待定常数由法方程组(&1)确定.即. 溶解度和温度近似满足关系：，注 1.这里是通过对多元函数求极小值点，得极小解 .实用中，也可将偏差带权平方和视为待定参数的多元函数，.2.上述变量依赖于单个变量的数据拟合问题，可推广依赖于多个变量的情形.此时，相应的数据拟合问题可描述为：已知一组测量数据，及权系数，要求用数据拟合的最小二乘法确定变量与变量的关系式，即求多元函数.同两个变量的数据拟合的最小二乘法类似，我们可分二步实现多个变量的最小二乘数据拟合. 逼近空间：三角多项式空间 即数据拟合的三角多项式最小二乘逼近问题. 首先引入在维复向量空间中，内积为 (*1)其中是的共轭复数.逼近空间： 其中 l 问题的提出设是以为周期的复函数，给定在个等距样本点的值.记,求复向量，使得 ， (*2) 其中.l 算法与代数多项式的最小二乘逼近问题完全类似，极小问题(*2)的解可通过求解相应的法方程组 得到.其中内积由(*1)式定义，而复向量，可验证复向量系构成了空间下的正交向量系, 即 . 则法方程组的系数矩阵为对角矩阵，此时，法方程组退化为 最小二乘逼近问题的解 。特别，当时，的最佳平方逼近就是它自己，即：，则有， (*3) 此时，称为的次插值三角多项式.下面将(*3)式和离散富里叶变换（DFT）建立联系.定义：给定复数序列, 称序列 (*4)为序列的离散富氏变换 .利用定义及. 称上式为(*4)式的逆变换.注：离散富氏变换是利用计算机进行富氏分析的主要方法.下面我们讨论它的计算问题.l 快速富氏变换讨论 (*5)其中 称序列和为问题(*5)的系数序列和解（离散频谱）序列.求解的运算量：当很大时，运算量相当大因而引入快速富氏变换（FFT）1. FFT的基本思想 基本思想：将运算规模为的DFT问题(*5)递归地化为2个运算规模为的DFT问题。 利用重要事实：， 对偶下标有： 因为 同理，利用重要事实：， 及 对奇下标有： ， 令 ， ， 其中DFT系数. (*6)则将运算规模为的DFT问题递归化为两个规模为的DFT问题.重复此过程，对，做步，可得到个规模为1的DFT问题，相应的DFT系数就是所要求的DFT问题(*5)的解序列，这就是FFT算法的基本思想.DFT计算的工作量： （推导过程：分别记和为利用FFT算法求解运算规模为的DFT问题所需的乘法和加减法次数.由(*6)式，可得： 又 .同理， FFT算法的运算量为） 从而大大节省了计算DFT所需的工作量 。2. FFT算法的实现将系数分别存放在系数和所占用的存贮单元中，（系数在求得后不再使用）则新产生的两个规模为的DFT问题的系数序列将分别存放在规模为的DFT问题的系数序列所占用的连续存贮单元的前半段和后半段.实际编程时，只需引入一个辅助变量及一个数组，即可实现FFT算法，具体描述如下：第一步，初始化数组，及整型变量（表示当前所需计算的DFT问题的运算规模）.第二步，若，则转到第三步；否则，1 令整型变量,2 DoFor ；EndforUntil 3 令 ，并转入第二步第三步，将数组按二进制意义下的逆序输出，就是问题(*5)的解序列.注意，在第三步中，用到了由第二步所得到的个规模为1的DFT系数序列就是所要计算的DFT解序列在二进制意义下的逆序这一事实.下面我们通过一具体实例说明这一重要事实的正确性.以为例说明上述FFT算法的实现过程.将下标值用二进制数表示.此时，对任给，有.即， .是存放FFT执行过程中的DFT系数序列的数组，则上述FFT算法可由以下4步完成.步1 ;步2 因为，所以仅作一次For ；Endfor用二进制形式可等价表示为For ；Endfor而由前面推导的递推公式， 其中 。知：上述系数序列和存放的分别是序列和而和应占据和的存储位置。注意：及 因此，所求得的2个规模为4的DFT问题的系数序列和的存储位置与实际解序列的存储位置恰好构成二进制意义下的逆序关系。 步3 ，对，做循环对，即对 做：；这4个规模为2的DFT系数序列，,实际占用的是所需求解的DFT解序列，应存放的存贮单元.步4 ，对，做循环即对，