下载文档原格式
第三章 函数逼近与曲线拟合1 函数的逼近与基本概念1.1问题的提出多数计算机的硬件系统只提供加、减、乘、除四种算术运算指令，因此为了计算大多数有解析表达式的函数的值，必须产生可用四则运算进行计算的近似式，一般为多项式和有理分式函数.实际上，我们已经接触到两种逼近多项式，一种是泰乐多项式，一种是插值多项式.泰乐多项式是一种局部方法，误差分布不均匀，满足一定精度要求的泰乐多项式次数太高，不宜在计算机上直接使用.例如，设()f x 是[1,1]-上的光滑函数，它的Taylor 级数0()k k k f x a x ∞==∑，()(0)!k k f a k =在[1,1]-上收敛。
当此级数收敛比较快时，11()()()n n n n e x f x s x a x ++=-≈。
这个误差分布是不均匀的。
当0x =时，(0)0n e =，而x 离开零点增加时，()n e x 单调增加，在1x =±误差最大。
为了使[1,1]-的所有x 满足()()n f x s x ε-<，必须选取足够大的n ，这显然是不经济的。
插值函数出现的龙格现象表明，非节点处函数和它的插值多项式相差太大。
更重要的是，实际中通过观测得到的节点数据往往有各种误差，此时如果要求逼近函数过全部节点，相当于保留全部数据误差，这是不适宜的。
如图1所示，给出五个点上的实验测量数据，理论上的结果应该满足线性关系，即图1中的实线。
由于实验数据的误差太大，不能用过任意两点的直线逼近函数。
如果用过5个点的4次多项式逼近线性函数，显然误差会很大。
实验数据真函数插值多项式逼近精确的线性逼近图11.2范数与逼近一、线性空间及赋范线性空间要深入研究客观事物，不得不研究事物间的内在联系，给集合的元素之间赋予某种“确定关系”也正是这样的道理.数学上常把在各种集合中引入某些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间.最常用的给集合赋予一种“加法”和“数乘”运算，使其构成线性空间.例如将所有实n 维数对组成的集合，按照“加法”和“数乘”运算构成实数域上的线性空间，记作n R ，称为n 维向量空间.类似地，对次数不超过n 的实系数多项式全体，按通常多项式与多项式加法及数与多项式乘法也构成数域R 上一个线性空间，用n H 表示，称为多项式空间.所有定义在[,]a b 上的连续函数集合，按函数加法和数与函数乘法构成数域R 上的线性空间，记作[,]C a b .类似地，记[,]p C a b 为具有p 阶连续导数的函数空间.在实数的计算问题中，对实数的大小、距离及误差界等是通过绝对值来度量的.实践中，我们常常会遇到对一般线性空间中的向量大小和向量之间的距离进行度量的问题，因此有必要在一般线性空间上，赋予“长度”结构，使线性空间成为赋范线性空间.定义1 设X 是数域K 上一个线性空间，在其上定义一个实值函数，即对于任意,x y X ∈及K α∈，有对应的实数x 和y ，满足下列条件(1) 正定性：0x ≥，而且0x =当且仅当0x =；(2) 齐次性：x x αα=；(3) 三角不等式：x y x y +≤+；称为X 上的范数，定义了范数的线性空间就称为赋范线性空间.以上三个条件刻划了“长度”、“大小”及“距离”的本质，因此称为范数公理.对n X 上的任一种范数，n X ∀∈x,y ，显然有±≥-x y x y .n R 上常用的几种范数有：(1) 向量的∞-范数：1max i i nx ∞≤≤=x(2) 向量的1-范数：11n i i x ==∑x(3) 向量的2-范数：12221()n i i x ==∑x (4) 向量的p -范数：11()n p pi p i x ==∑x其中[1,)p ∈∞，可以证明向量函数()p N x x ≡是nR 上向量的范数. 前三种范数是p -范数的特殊情况（lim p p ∞→∞=x x ）.我们只需表明(1).事实上1111111max max max n n p pp p i i i i i n i n i n i i x x x x ≤≤≤≤≤≤==⎛⎫⎛⎫≤≤≤ ⎪ ⎪⎝⎭⎝⎭∑∑及max 1p →∞=，故由数学分析的夹逼定理有1l i m ma x i p p i nx ∞→∞≤≤==x x 。
数值分析第3章函数逼近和快速傅立叶变换第3章的内容主要涉及函数逼近和快速傅立叶变换。
函数逼近是指通过一系列已知数据点来估计一个函数的近似值。
快速傅立叶变换是一种高效计算连续傅立叶变换的方法。
函数逼近是数值分析中一项重要任务，它涉及到通过一组已知数据点来估计一个未知函数的值。
常用的函数逼近方法包括多项式逼近、三角函数逼近和样条函数逼近。
多项式逼近是利用一组已知数据点来构造一个多项式，使得该多项式在这些数据点上的值与已知数据点的值尽可能接近。
多项式逼近的基本思想是利用多项式的线性组合来近似未知函数，通过最小化误差函数来确定逼近多项式的系数。
多项式逼近的优点是简单易实现，但是当数据点较多或者函数较复杂时，多项式逼近的结果可能不够精确。
三角函数逼近是利用三角函数的线性组合来近似未知函数。
三角函数逼近的基本思想是利用三角函数的周期性来估计未知函数的值。
通过最小化误差函数来确定逼近三角函数的系数。
三角函数逼近适用于具有周期性的函数，在信号处理和图像处理中得到广泛应用。
样条函数逼近是利用多个局部的插值多项式来逼近未知函数。
样条函数逼近的基本思想是将整个待逼近区间分成多个子区间，每个子区间内使用一个插值多项式来逼近未知函数。
通过最小化误差函数来确定样条函数的系数。
样条函数逼近适用于具有较强光滑性的函数，在计算机图形学和计算机辅助设计领域得到广泛应用。
快速傅立叶变换（FFT）是一种高效计算连续傅立叶变换的方法。
傅立叶变换可以将一个连续函数分解成若干个正弦和余弦函数的和，它在信号处理、图像处理和通信等领域有着重要应用。
传统的傅立叶变换算法的时间复杂度为O(n^2)，而快速傅立叶变换算法的时间复杂度为O(nlogn)，能够极大地提高计算效率。
快速傅立叶变换的基本思想是将一个长度为n的序列分解成两个长度为n/2的序列，通过递归地进行这种分解，最终得到长度为1的序列。
然后再通过合并各个子问题的解来得到原始序列的傅立叶变换。
§2函数逼近Ⅰ一些概念定义 设P 是一个数域，V 是一个非空集合，在V 上定义了两种运算：1. 加法：对任意的元素,u v V ∈，在V 中有唯一的元素（记为u v +）与之对应，满足()(),,,,,.u v v u u v V u v u v u v Vωωω+=+∀∈++=++∀∈且V 中存在唯一的元素（称零元素，记为0），使得0,u u u V +=∀∈对每个,u V ∈存在唯一的元素（称为u 的负元素记为-u ）与之对应，满足()0u u +-=2. 数乘 ：对任意的P α∈和u V ∈，在V 中有唯一的元素（记为u α）与之对应，满足()()()()1,,,,,,,,,,,u u u V u u P u V u v u v P u v Vu u u P u Vαβαβαβαααααβαβαβ=∀∈=∀∈∈+=+∀∈∈+=+∀∈∈称V 为一个数域P 上的线性空间。
定义 设V 是P 上的线性空间，内积是VxV 到数域P 的一个映射，即对于V 中的任意元素对u 和v ，有P 中的唯一的一个数（记为（,u v ））与之对应，满足：()()()()()()()()()()()()()1,,,,,,;2,,,,,3,,,,4,0;u,u 00u v u v u v V u v u v u v V Pu v v u u v Vu u u V u ωωωωααα+=+∀∈=∀∈∈=∀∈≥∀∈=⇔=则(),u v 称为u 与v 的内积，定义了内积的线性空间V 成为内积空间。
3. 设V 是一个数域P 上的线性空间。
定义V 到R 的一个映射 ，即对任意的u V ∈，都有一个实数u 与之对应，满足以下性质。
（1）正定性：0,;00u u V u u ≥∀∈=⇔=（2）齐次性：,,u u u V P ααα=∀∈∈（3）三角不等式：,,u v u v u v V +≤+∀∈称 为V 上的范数。
定义了范数的线性空间称为赋范线性空间。
