第三章数值分析.ppt

第三章函数逼近 一 问题的提出如果要求解在 a b 区间的每一点都 很好地 逼近的话 运用插值函数有时就要失败 设为f x Taylor级数的前n 1项部分和 其截断误差为为了照顾到远离的点且误差也较小 常将阶数n取得很大 这样做费事 多占存贮单元 因此往往要求在给定精度下 求形式简单的计算公式 使其均匀地逼近 这就是函数逼近要解决的问题 二 函数逼近问题已知复杂函数 或仅知道函数在某些采样点处的函数值 在某函数集合V中 寻找的 最好 近似函数逼近问题 对集合中给定的函数 要求在另一类较简单的便于计算的函数集合 中 求函数 使得与之差在某种度量意义下最小 通常为C a b V为代数多项式 分式有理函数 三角多项式 集合V通常是依赖于一组参数的函数族 其代表元素有如下形式 若集合V是线性空间 线性无关 则可以表示为若为线性空间V的一组基 则是一个n 1维线性空间 背景 在某一函数集合中找最好的近似 赋范空间 内积空间 正交多项式最佳平方逼近曲线最小二乘拟合最佳一致逼近 工科研究生不要求 1预备知识与函数逼近问题 一 赋范线性空间1 定义设为定义于线性空间V上的实值函数 并满足 非负性 当且仅当g 0时有 齐次性 三角不等式 则称是线性空间V上的范数 并称线性空间V为赋范线性空间 记为Remark 子空间 V上的范数也是上的范数 n维向量空间 无穷范数与Euclid范数 赋范线性空间 赋范线性空间 连续函数空间 无穷范数 定义于区间 a b 上连续函数的集合C a b 是一线性空间 定义是线性空间C a b 上的一种范数 C a b 关于该范数是一赋范线性空间 记为证明 对 连续函数空间 Euclid范数 定义于区间 a b 上连续函数的集合C a b 是一线性空间 定义是线性空间C a b 上的一种范数 C a b 关于该范数是一赋范线性空间 记为证明 对 内积空间 诱导范数 在内积空间V中 定义了是内积空间上定义的范数 称之为由内积诱导出的范数 内积空间关于其诱导范数是一赋范空间证明 设f和g是内积空间V中的任意元素 由内积的定义非负性齐次性三角不等式 2 距离对于赋范线性空间上的任意两个元素f和g 它们之间的距离为Remark 二 内积空间1 定义设V为一线性空间 若定义实值函数 对任意满足 对称性 线性性 非负性 当且仅当时有 则称实值函数是线性空间V上的一种内积 并称线性空间V关于实值函数是内积空间 对于线性空间 如下定义的实值函数满足内积的三个条件线性空间关于上式所规定的内积是一内积空间 2 性质 内积空间上任意两元素f和g满足Cauchy不等式证明 对内积空间上的任意元素f g和任意实数t 有固定f和g 右端是关于t的一元二次多项式 且该多项式函数值非负 利用二次多项式的判别式有得到Cauchy不等式 内积空间上的任意两元素f和g满足三角不等式 Schwarz不等式 证明 利用Cauchy不等式有两边开平方 三角不等式得证 三 权函数 1 定义定义在 a b 上的实值函数 如果满足 存在则称为区间 a b 的一个权函数 2 带权的内积C a b 带权的内积 Remark 区间端点可以是无穷大 此时为广义积分 常简记为没有确切指出权函数时 约定 x 1 在理论证明和公式推导过程中 如没有明确权函数具体形式 则表示对任意权函数均成立 四 函数逼近问题 设为被逼近函数 为赋范线性空间的一个子集合范数可以是或等 称问题 求使得为函数f x 在赋范集合 上的函数逼近问题 逼近问题之一 最佳平方逼近 为赋范线性空间的有限维子空间 1 假设其维数为n 1 2 函数组是该子空间上的一组线性无关基 3 范数取为求使得 逼近问题之二 最佳一致逼近 为赋范线性空间的有限维子空间 1 假设其维数为n 1 2 函数组是该子空间上的一组线性无关基 3 范数取为求使得 五 Gram矩阵 1 定义设为内积空间 中元素 则称为的Gram矩阵 2 性质 定理1 设为内积空间 中元素 则线性无关的充分必要条件是 Gram矩阵非奇异 即必要性 线性无关 反证法 假设 则存在非零向量使得进而有由于 即 由内积定义知而这与函数组线性无关矛盾 假设不成立 线性无关 充分性 线性无关设与该式做内积根据内积性质即因为即线性无关线性无关 定理2由内积空间中线性无关元素确定的Gram矩阵是实对称正定矩阵 证明 因为均为实数故Gram矩阵是实矩阵G 根据内积性质及Gram矩阵得Gram矩阵矩阵是对称的 对任意非零向量由内积定义且由于函数组线性无关 故即而现在所以即Gram矩阵是实对称正定矩阵 2正交多项式 一 定义内积空间V上的两个元素f和g 如果则称f和g关于内积正交若内积空间上的元素系满足两两正交 即则称为正交系 若则称为标准正交系 当正交函数系中的为i次多项式时 称该函数系为正交多项式系 二 正交多项式系的性质 线性无关性 正交多项式系正交多项式系中任意中任意m个函数线性无关 非负整数互不相同 证明 设用和上式两端作内积 有因为即函数组线性无关 正交性 对任意次数不超过n的多项式证明 因线性无关 设它们是不超过n次多项式函数空间中的一组基 则用与做内积 对得注意 则对任意次数不超过n的多项式 实根性 正交多项式系中的在区间在区间 a b 内有n个互不相同的实单根 证明 首先论证在 a b 内至少有一个实根 反证法 假设在 a b 内无实根 则在 a b 内恒正或恒负 不妨设其恒正 于是有另一方面产生矛盾 其次论证实根一定是奇重根假设为的m重根则为n m次多项式由性质 但当m为偶数时 应有这一矛盾说明只能是奇重根 即只能为的单根 三重根 最后证明在 a b 内有n个实单根 假设仅有mn不可能 个奇重根 记之为于是有其中为偶数 q x 是在 a b 内不变号的次多项式 将上式两端乘以并积分左端积分 由性质 得右端积分 由于q x 在 a b 内不变号 则这一矛盾说明m n 即只能是单根 相邻三项间的关系正交多项式系中任何相邻的三项满足其中分别为的首项和次项系数 证明 比较中的系数 可得故取利用正交多项式的性质 对于不超过k次的多项式存在一组参数 使得有下面确定参数 确定参数当m 0 1 k 2由即得故确定参数将上式和做内积 有解得 注意是首项系数为的k次多项式存在着实数 使得代入表达式 得确定参数在中两端的系数应该相同 即有得到 Remark1的另一种表示方法将Remark2之间的递推关系并不能惟一确定 在允许相差一个常数倍数的意义下是惟一的 Remark3规定首项系数是1 得到更为简单的三项递推关系 其中 三 常用的正交多项式系 勒让德 Legendre 多项式系切比雪夫 Chebyshev 正交多项式系拉盖尔 Laguerre 正交多项式系埃尔米特 Hermite 正交多项式系 1 勒让德 Legendre 多项式系定义多项式系的首项系数次项系数 勒让德多项式系的前六项分别为 图形依次为 勒让德多项式的主要性质 正交性 多项式系是区间 1 1 上关于权函数的正交多项式系 对任意的有证明参考教材66页 证明 不妨设 设 注意 当 递推性利用正交多项式的性质 得到如下递推关系 证明 因为 且为正交多项式系 根据 有 奇偶性n为奇 偶 数时 为奇 偶 函数 证明 归纳法 为偶函数 为奇函数设结论对n m n m 1成立 当m为偶数时 为偶函数 为奇函数当m为奇数时 为偶数时 为奇函数当n m 1为偶数时 当为奇数时 于是 故n为奇 偶 数时 为奇 偶 函数 在区间 1 1 上对零函数的最佳平方逼近性在 1 1 上的所有首多项式中与零的平方误差最小在首项系数为1的n次多项式集合中的元素满足不等式且仅当时 有等号成立 即 证明 利用正交多项式的性质 存在一组实数 使得不超过n 1次的多项式故且仅当时 即时等号成立表明 在范数的意义下 首项系数为1的勒让德多项式是集合中距离零最近的元素 2 切比雪夫多项式系多项式系称之为n次切比雪夫多项式系 切比雪夫多项式主要性质 递推性引入中间变量 则利用三角函数关系得到 即 由知是首项系数为 n 0 的多项式函数系 称之为切比雪夫多项式系 证明 由及归纳法可知为n次多项式 其首项系数设结论对n m成立 即的首项系数为 当n m 1时 其首项系数为故对任意n 即是首项系数为的多项式系 也可用归纳法证明 的次项系数 的次项系数设结论对n m成立 即的次项系数为当n m 1时 其首项系数为的系数 即故对任意n 即的次项系数 其前6项的函数表达形式如下 其图形依次为 正交性 在区间 1 1 上关于权函数 正交 证明 注意 故 奇偶性n为奇 偶 数时 为奇 偶 函数证明 归纳法 为偶数 为奇函数设结论对成立 即当m为偶数 为偶函数 为奇函数当m为奇数 为奇函数 为偶函数 当为偶函数时 当为奇数时 于是对任意 故n为奇 偶 数时 为奇 偶 函数 零点与最值点 在 1 1 内的n个零点为 在 1 1 上有n 1个最值点 它在交错取最大值1 最小值 1 且有 证明 令得或者时故零点为即 因或k n时 取有即在 1 1 上有n 1个最值点 且在轮流取最大值1 最小值 1 显然由的定义知 最佳一致逼近性记则为首项系数为1的n次多项式集合 在区间 1 1 上对零函数的最佳一致逼近性 满足即 证明 因为在区间 1 1 上轮流取最大值最小值 1 且首项系数为故 反证法 若结论不成立 则另外存在使得即令则为不超过n 1次的多项式 由于则 即在共n 1个点轮流取正负号 由连续函数的介值定理知 在n个区间上至少各有一个零点 但是为不超过n 1次的多项式 其零点最多有n 1个 故产生矛盾 因此 在首项系数为1的n次多项式集合中 3 拉盖尔多项式系定义则是区间上关于权函数的正交多项式系 称为拉盖尔多项式系 其首项系数 次项系数并有和三项递推关系 4 爱尔米特多项式系定义则是区间上关于权函数的正交多项式系 称之为爱尔米特多项式系 其首项系数次项系数并有和三项递推关系 常用的正交多项式 3最佳平方逼近 为赋范 内积 线性空间的有限维空间 范数取为 范数取为内积诱导范数 求使得求使得 求使得求使得 一 最佳平方逼近问题的求解 1 多元函数的矩阵表达形式记注意 得其中是Gram矩阵 对称正定 对于上述最佳平方逼近问题 由于 f f 是确定函数 故寻求使达到最小值的解向量即为寻求使达到最小值的解向量 2 二次函数取得最小值的充要条件设为实对称正定矩阵 和是n维列向量 则使得二次函数取得最小值的充要条件是为线性方程组的解 证明 A为实对称正定矩阵有唯一解向量 即有故所以由于是常量 A为对称正定矩阵 故当且仅当时 取得最小值 3 法方程组由于Gram矩阵是实对称正定矩阵 结合上述定理知 求解最佳平方逼近问题 即求的最小值就是求解线性方程组 上述线性方程组称为最佳平方逼近问题的法方程组或正规方程组法方程组的唯一解记为最佳平方逼近的解函数为 4 的等价表示形式即 几何意义函数组是内积空间的组基 故上式表明与内积空间中任意函数正交 因此可视为被逼近函数f在内积空间上的投影 5 平方逼近误差 举例法方程的系数矩阵设的解向量为最佳平方逼近函数为平方误差为 二 基于正交基的最佳平方逼近目的 减少计算量 减少舍入误差的影响 当为内积空间的一组正交函数基时 1 利用已知的正交基如 用二次多项式做最佳平方逼近 可根据不同区间 不同权函数选取正交多项式 2 利用已知的正交基求最佳平方逼近函数例由然后计算出 3 构造正交基对不超过n次的多项式空间利用公式 其中对不完整多项式空间或非多项式空间可用斯密特正交化方法如 4 任意区间上最佳平方逼近问题的转化例若想用Legendre正交多项式求解 作变换问题转化为其中 5 问题转化 1 求解在空间上的最佳平方逼近 2 做逆变换 3 平方误差计算直接计算 间接计算 6 最佳平方逼近问题的一般求解方法例 求f x arctgx在 0 1 上的一次最佳平方逼近函数 法1用Legendre正交多项式作变换则由及得 法2利用1 x做首一正交多项式设令取在找由得 法3直接用线性无关函数族 不用正交多项式设取在找由得 Remark1要求形式给定的最佳平方逼近函数 无论采用哪一组基函数 得到的最佳平方逼近函数的解析里理论上是唯一确定的 但是 实际计算过程中存在着大量的舍入误差 截断误差 数值积分 以致采用不同的基函数所导致的最终数值结果经常并不相等 Remark2采用正交基函数求最小平方逼近函数的计算量小 它避免了线性方程组的求解 Remark3采用不同的方法 构成内积空间的基函数的选取可有不同 在前面的例题中 1 2 3 4曲线拟合的最小二乘方法一 曲线拟合问题给定数据 要求建立一个 最好的 连续函数 反映该组数据的基本特征 确定函数类型 可由物理规律或通过描点作图观察选比较简单的低次多项式 函数类中的代表元素通常包含有若干个参数 一般有 即可以表示为线性拟合模型其中是线性无关的已知函数组 设 正数是第j个采样点处权 是第j个采样点处的拟合 记为或称为拟和残差向量切比雪夫意义下的曲线拟合模型求使得最小二乘意义下的曲线拟合模型求使得 二 最小二乘曲线拟合问题的求解 离散问题的最佳平方逼近 1 最小二乘曲线拟合问题求使得离散形式的内满足内积的定义 最小二乘曲线拟合问题的等价提法 设最小二乘曲线拟合问题 求使得 2 多元函数的矩阵表达式记注意得 其中由离散数据定义的Gram矩阵 对称 为离散Gram矩阵对于上述最佳平方逼近问题 由于是确定函数 故寻求使达到最小值的解析向量即为寻求使达到最小值的解向量 Remark 在一定条件下是正定矩阵 3 二次函数取得最小值充要条件如果离散Gram矩阵是实对称正定矩阵 由定义的二次函数取得最小值的充要条件是是线性方程组的解向量 4 法方