数值分析--第3章函数逼近与快速傅里叶变换

实验报告实验项目名称函数逼近与快速傅里叶变换实验室数学实验室所属课程名称数值逼近实验类型算法设计实验日期班级学号姓名成绩512*x^10 - 1280*x^8 + 1120*x^6 - 400*x^4 + 50*x^2 - 1并得到Figure，图像如下：实验二：编写程序实现[-1,1]上n阶勒让德多项式，并作画（n=0,1，…，10 在一个figure中）。

要求：输入Legendre(-1,1,n)，输出如a n x n+a n-1x n-1+…多项式。

在MATLAB的Editor中建立一个M-文件，输入程序代码，实现勒让德多项式的程序代码如下：function Pn=Legendre(n,x)syms x;if n==0Pn=1;else if n==1Pn=x;else Pn=expand((2*n-1)*x*Legendre(n-1)-(n-1)*Legendre(n-2))/(n);endx=[-1:0.1:1];A=sym2poly(Pn);yn=polyval(A,x);plot (x,yn,'-o');hold onend在command Windows中输入命令：Legendre（10），得出的结果为：Legendre(10)ans =(46189*x^10)/256 - (109395*x^8)/256 + (45045*x^6)/128 - (15015*x^4)/128 + (3465*x^2)/256 - 63/256并得到Figure，图像如下：实验三：利用切比雪夫零点做拉格朗日插值，并与以前拉格朗日插值结果比较。

在MATLAB的Editor中建立一个M-文件，输入程序代码，实现拉格朗日插值多项式的程序代码如下：function [C,D]=lagr1(X,Y)n=length(X);D=zeros(n,n);D(:,1)=Y';for j=2:nfor k=j:nD(k,j)=(D(k,j-1)- D(k-1,j-1))/(X(k)-X(k-j+1));endendC=D(n,n);for k=(n-1):-1:1C=conv(C,poly(X(k)));m=length(C);C(m)= C(m)+D(k,k);end在command Windows 中输入如下命令：clear,clf,hold on;k=0:10;X=cos(((21-2*k)*pi)./22); %这是切比雪夫的零点Y=1./(1+25*X.^2);[C,D]=lagr1(X,Y);x=-1:0.01:1;y=polyval(C,x);plot(x,y,X,Y,'.');grid on;xp=-1:0.01:1;z=1./(1+25*xp.^2);plot(xp,z,'r')得到Figure ，图像如下所示：比较后发现，使用切比雪夫零点做拉格朗日插值不会发生龙格现象。

数值分析知识点总结数值分析知识点总结：本文提供了数值分析中的一些重要知识点和例题，但更多的例题可以参考老师布置的作业题和课件相关例题。

第1章数值分析与科学计算引论：绝对误差和相对误差是衡量近似值精度的指标，有效数字则是描述近似值精度的一种方式。

其中，相对误差限是绝对误差的上界。

有效数字的计算方法为：如果近似值x的误差限是某一位的半个单位，该位到x的第一位非零数字共有n位，就说x*共有n位有效数字。

一个比较好用的公式是f(x)的误差限：f(x)f'(x)(x)。

第2章插值法：插值多项式的余项表达式可以用来估计截断误差。

三次样条插值与三次分段埃尔米特插值有所不同，但哪一个更优越需要根据实际情况而定。

确定n+1个节点的三次样条插值函数需要多少个参数？为确定这些参数，需加上什么条件？三弯矩法可以用来求解三次样条表达式。

第3章函数逼近与快速傅里叶变换：带权(x)的正交多项式是在特定区间上满足一定条件的多项式，其中[-1,1]上的勒让德多项式具有重要性质。

切比雪夫多项式也有其独特的性质。

用切比雪夫多项式零点做插值点得到的插值多项式与拉格朗日插值有所不同。

最小二乘拟合的法方程可以用来拟合曲线，但当次数n较大时，不直接求解法方程。

第4章数值积分与数值微分：XXX让德求积公式和XXX-XXX求积公式是数值积分中的两种方法，其中高斯求积公式可以用来计算定积分。

勒让德多项式的零点就是高斯点，这种形式的高斯公式被称为XXX让德求积公式。

中点方法是一种数值积分方法，其公式如下：插值型的求导公式有两点公式和三点公式。

第5章介绍了解线性方程组的直接方法，其中包括LU矩阵的推导过程。

相关例题可以在教材第4章作业题和课件中找到。

第6章介绍了解线性方程组的迭代法，判断迭代法是否收敛的条件如下：第7章介绍了非线性方程与方程组的数值解法，其中牛顿法是一种常见的方法。

对于单根且光滑的f(x)=0，牛顿法是局部二阶收敛的。

简化牛顿法和牛顿下山法都是非线性方程组的求解方法。

实验三函数逼近与快速傅里叶变换P95专业班级：信计131 班姓名：段雨博学号：2013014907一、实验目的1、熟悉 matlab 编程。

2、学习最小二乘法及程序设计算法。

二、实验题目1、对于给函数f x1在区间1,1 上取 x i 1 0.2i i0,1,10 ，试求3次125x2曲线拟合，试画出拟合曲线并打印出方程，与第二章计算实习题 2 的结果进行对比。

2、由实验给出数据表x0.00.10.20.30.50.8 1.0y 1.00.410.500.610.91 2.02 2.46试求 3 次、 4 次多项式的曲线拟合，再根据数据曲线形状，求一个另外函数的拟合曲线，用图示数据曲线及相应的三种拟合曲线。

3.给定数据点 x i , y i如表所示00.50.60.70.80.91x x i1 1.75 1.96 2.19 2.44 2.71 3.00y i用最小二乘法求拟合数据的二次多项式，并求平方误差。

三、实验原理与理论基础1．最小二乘原理与线性拟合：在函数的最佳平方逼近中 f ( x)C[ a,b] ，如果 f ( x) 只在一组离散点集 { x i , i 0,1..., m} 上给出，这就是科学实验中经常见到的实验数据｛{( x i, y i ), i 0,1...m} ｝的曲线拟合，这里y i f (x i)(i0,1...m) ，要求一个函数y S * ( x) 与所给数据 {( x i , y i ), i 0,1...m} 拟合，若记误差(01 ,... m ) T，设0 ( x),1 (x),... n (x) 是C[a,b]上线性无关函数族，在span{0 ( x),1 ( x),...n (x)} 中找一函数 S * (x) 使误差平方和m m m222[ S * ( x)y i ]2min[ S( x i )y i ] ，这2ii 0i0i 0里S(x)a0 0 ( x)a0 1 ( x)... a n n ( x) （ n m ）。

数值分析知识点总结说明：本文只提供部分较好的例题，更多例题参考老师布置的作业题和课件相关例题。

一、第1章 数值分析与科学计算引论1. 什么是绝对误差与相对误差？什么是近似数的有效数字？它与绝对误差和相对误差有何关系？相对误差限：**r re ε=的一个上界。

有效数字：如果近似值*x 的误差限是某一位的半个单位，该位到*x 的第一位非零数字共有n 位，就说x *共有n 位有效数字。

即x *=±10m ×(a 1+a 2×10-1+…+a n ×10-(n-1))，其中a 1≠0，并且*11102m n x x -+-≤⨯。

其中m 位该数字在科学计数法时的次方数。

例如9.80的m 值为0，n 值为3，绝对误差限*211102ε-=⨯。

2. 一个比较好用的公式：f(x)的误差限：()***()'()()f x f x x εε≈ 例题：二、第2章插值法例题：5. 给出插值多项式的余项表达式，如何用其估计截断误差？6. 三次样条插值与三次分段埃尔米特插值有何区别？哪一个更优越？7. 确定n+1个节点的三次样条插值函数需要多少个参数？为确定这些参数，需加上什么条件？8. 三弯矩法：为了得到三次样条表达式，我们需要求一些参数：对于第一种边界条件，可导出两个方程：，那么写成矩阵形式：公式 1对于第二种边界条件，直接得端点方程：，则在这个条件下也可以写成如上公式1的形式。

对于第三种边界条件，可得：也可以写成如下矩阵形式：公式 2求解以上的矩阵可以使用追赶法求解。

（追赶法详见第五章）例题：数值分析第5版清华大学出版社第44页例7三、第3章函数逼近与快速傅里叶变换的正交多项式？什么是[-1,1]上的勒让德多项式？它有3.什么是[a,b]上带权()x什么重要性质？4.什么是切比雪夫多项式？它有什么重要性质？5.用切比雪夫多项式零点做插值点得到的插值多项式与拉格朗日插值有何不同?6.什么是最小二乘拟合的法方程？用多项式做拟合曲线时，当次数n较大时，为什么不直接求解法方程？例题请参考第3章书上的作业题和课件上的例题。

数值分析第3章函数逼近和快速傅立叶变换第3章的内容主要涉及函数逼近和快速傅立叶变换。

函数逼近是指通过一系列已知数据点来估计一个函数的近似值。

快速傅立叶变换是一种高效计算连续傅立叶变换的方法。

函数逼近是数值分析中一项重要任务，它涉及到通过一组已知数据点来估计一个未知函数的值。

常用的函数逼近方法包括多项式逼近、三角函数逼近和样条函数逼近。

多项式逼近是利用一组已知数据点来构造一个多项式，使得该多项式在这些数据点上的值与已知数据点的值尽可能接近。

多项式逼近的基本思想是利用多项式的线性组合来近似未知函数，通过最小化误差函数来确定逼近多项式的系数。

多项式逼近的优点是简单易实现，但是当数据点较多或者函数较复杂时，多项式逼近的结果可能不够精确。

三角函数逼近是利用三角函数的线性组合来近似未知函数。

三角函数逼近的基本思想是利用三角函数的周期性来估计未知函数的值。

通过最小化误差函数来确定逼近三角函数的系数。

三角函数逼近适用于具有周期性的函数，在信号处理和图像处理中得到广泛应用。

样条函数逼近是利用多个局部的插值多项式来逼近未知函数。

样条函数逼近的基本思想是将整个待逼近区间分成多个子区间，每个子区间内使用一个插值多项式来逼近未知函数。

通过最小化误差函数来确定样条函数的系数。

样条函数逼近适用于具有较强光滑性的函数，在计算机图形学和计算机辅助设计领域得到广泛应用。

快速傅立叶变换（FFT）是一种高效计算连续傅立叶变换的方法。

傅立叶变换可以将一个连续函数分解成若干个正弦和余弦函数的和，它在信号处理、图像处理和通信等领域有着重要应用。

传统的傅立叶变换算法的时间复杂度为O(n^2)，而快速傅立叶变换算法的时间复杂度为O(nlogn)，能够极大地提高计算效率。

快速傅立叶变换的基本思想是将一个长度为n的序列分解成两个长度为n/2的序列，通过递归地进行这种分解，最终得到长度为1的序列。

然后再通过合并各个子问题的解来得到原始序列的傅立叶变换。

---------------------------------------------------------------最新资料推荐------------------------------------------------------第三章函数逼近与快速傅里叶变换曲线拟合与最小二乘法第三章函数逼近与快速傅里叶变换曲线拟合与最小二乘法线性最小二乘拟合多项式拟合超定方程组的最小二乘解3.1 曲线拟合与最小二乘法一、拟合问题设变量 x, y 通过观测得 m 对数据我们希望用 m 对数据构造一个近似函数)(xp. 由于观测数据都带有观测误差, 而且一般m 也比较大, 用插值方法要求)(xp严格经过数据点不可取. 于是, 我们希望寻找的近似函数)(xp在各个 xi的函数值)(ixp与观测值yi尽可能接近, 这就是所谓的数据拟合问题. 二、最小二乘法的基本原理从整体考虑近似函数)(xp与所给数据点()),, 2 , 误差的大小，常用的方法有以下三种：一是误差绝对值的最大值imir0max，即误差向量的范数；二是误差绝对值的和=miir0||，即误差向量 r 的 1-范数；三是误差平方和=miir02的算术平方根，即考虑误差向量 r 的 2范数；前两种方法简单、自然，但不便于微分运算，后一种方法相当于考虑 2范数的平方，因此在曲线拟合中常采用误差平方和=miir02来度量误差的整体大小。

数据拟合的具体作法：1 / 11对给定数据，在取定的函数类中,求 )(xp, 使误差的平方和最小，即min])([0202==i=i=miimiyxpr 从几何意义上讲，就是寻求与给定点的距离平方和为最小的曲线)(xpy =。

函数)(xp称为拟合函数或最小二乘解，求拟合函数)(xp的方法称为曲线拟合的最小二乘法。

在曲线拟合中，函数类可有不同的选取方法. 多项式拟合形式比较规范，方法也比较简单，但在实际应用中，针对所讨论问题的特点，拟合函数可能为其他类型，如指数函数、有理函数、三角函数等，这就是一般最小二乘拟合问题。