【数值分析】2 - 插值法

2023-10-23 03:52
文章标签 分析 插值法 数值

本文主要是介绍【数值分析】2 - 插值法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、引言
    • 1.1 插值法引入
    • 1.2 常用插值法
    • 1.3 插值法定义
  • 二、插值法研究的问题
    • 2.1 插值多项式存在的唯一性
    • 2.2 如何构造n次多项式
      • 2.2.1 待定系数法
      • 2.2.2 拉格朗日插值法
        • 2.2.2.1 拉格朗日多项式
        • 2.2.2.2 拉格朗日插值余项
        • 2.2.2.3 例题
        • 2.2.2.4 拉格朗日插值法的问题
      • 2.2.3 牛顿插值法
        • 2.2.3.1 牛顿插值思想
        • 2.2.3.2 差商的定义
        • 2.2.3.3 差商的性质
        • 2.2.3.4 差商表
        • 2.2.3.5 牛顿插值公式
        • 2.2.3.6 牛顿插值余项
        • 2.2.3.7 等距节点公式
        • 2.2.3.8 例题


学习视频:《数值分析》| 华科 | 研究生基础课


一、引言

1.1 插值法引入

许多实际问题都用函数 y = f ( x ) y=f(x) y=f(x) 来表示某种内在规律的数量关系,其中相当一部分函数是通过实验或计算得到的,并且只是 [ a , b ] [a,b] [a,b] 上一系列点 x i x_i xi 的函数值 { f ( x i ) ∣ i = 0 , 1 , . . . , n } \{f(x_i)\ |\ i=0,1,...,n\} {f(xi)  i=0,1,...,n},这只是一张函数表。

有的问题虽然也有解析表达式,但由于计算复杂,使用不方便,通常也要构造一个函数表,如三角函数表、对数表、立方根表、平方根表等。

然而,为了研究函数的变化规律,往往需要知道不在函数表上的函数值,因此,我们希望根据给定的函数表做一个既可以反映函数 f ( x ) f(x) f(x) 的特性,又便于计算的简单函数 p ( x ) p(x) p(x),用 p ( x ) p(x) p(x) 近似 f ( x ) f(x) f(x)插值法就是根据函数表寻找简单函数 p ( x ) p(x) p(x) 的方法之一

寻找简单函数的问题又被称为函数逼近问题,下面给出了一个函数逼近问题的示例:

在这里插入图片描述

那么,什么样的函数是简单函数呢?

通常,我们用代数多项式或分段代数多项式作为简单函数 p ( x ) p(x) p(x),并使得 p ( x i ) = f ( x i ) p(x_i)=f(x_i) p(xi)=f(xi) 对所有的 x i , i = 0 , 1 , . . . , n x_i,i=0,1,...,n xi,i=0,1,...,n 成立。

1.2 常用插值法

  • 多项式插值 p ( x ) p(x) p(x) 为多项式函数(最常用)
  • 分段插值 p ( x ) p(x) p(x) 为分段多项式函数
  • 三角插值 p ( x ) p(x) p(x) 为三角函数

1.3 插值法定义

在这里插入图片描述
在这里插入图片描述

二、插值法研究的问题

  • 满足插值条件的 p ( x ) p(x) p(x) 是否存在且唯一?
  • 如满足插值条件的 p ( x ) p(x) p(x) 存在,如何构造 p ( x ) p(x) p(x)
  • 如何估计用 p ( x ) p(x) p(x) 近似替代 f ( x ) f(x) f(x) 产生的误差?

2.1 插值多项式存在的唯一性

在这里插入图片描述
在这里插入图片描述

因此,通过上述的证明,可以得到如下定理:

在这里插入图片描述

2.2 如何构造n次多项式

2.2.1 待定系数法

在这里插入图片描述

下面还有一种更加简洁的解法:

在这里插入图片描述

2.2.2 拉格朗日插值法

2.2.2.1 拉格朗日多项式

前面介绍的待定系数法中,使用的基函数是 1 , x , x 2 , . . . , x n 1,x,x^2,...,x^n 1,x,x2,...,xn,这样的基函数过于简单,导致求解系数时较为麻烦。因此,有了下面将要介绍的拉格朗日插值法,它使用了更为复杂的拉格朗日基函数

在这里插入图片描述

考虑 n = 1 n=1 n=1 的特殊情况:

在这里插入图片描述

由上可知:

l 0 ( x 0 ) = 1 , l 0 ( x 1 ) = 0 , l 1 ( x 0 ) = 0 , l 1 ( x 1 ) = 1. l_0(x_0)=1,l_0(x_1)=0, \\ l_1(x_0)=0,l_1(x_1)=1. l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1.

可以给出如下的克罗内克Delta函数

δ i j = { 1 , i = j 0 , i ≠ j \delta_{ij}=\begin{cases} 1 , i=j \\ 0 , i \neq j \end{cases} δij={1,i=j0,i=j

且满足条件 l i ( x j ) = δ i j l_i(x_j)=\delta_{ij} li(xj)=δij

更一般地,下面我们进一步讨论 n ≥ 1 n\ge1 n1 的情况:

在这里插入图片描述

从拉格朗日基函数公式我们可以看出,它仅仅与节点 x x x 有关,而与真实的函数形式 f ( x ) f(x) f(x) 无关,这意味着给定不同的函数和相同的插值节点,求出来的拉格朗日基函数是一样的。

另外,容易得到 ∑ i l i ( x ) = 1 \sum_{i}{l_i(x)=1} ili(x)=1(特别地, f ( x ) = 1 f(x)=1 f(x)=1

在这里插入图片描述

2.2.2.2 拉格朗日插值余项

假设节点 x i ∈ [ a , b ] , i = 0 , 1 , . . . , n x_i\in[a,b],i=0,1,...,n xi[a,b],i=0,1,...,n,且 f ( x ) f(x) f(x) 满足条件 f ( x ) ∈ C n [ a , b ] f(x)\in C^n[a,b] f(x)Cn[a,b] f ( n + 1 ) ( x ) f^{(n+1)}(x) f(n+1)(x) [ a , b ] [a,b] [a,b] 内存在,考虑截断误差 R n ( x ) = L n ( x ) − f ( x ) R_n(x)=L_n(x) - f(x) Rn(x)=Ln(x)f(x)

由插值条件可知, R n ( x ) R_n(x) Rn(x) 至少存在 n + 1 n+1 n+1 个零点(因为在每个插值点处, R n R_n Rn 必然为零),因此,可以将 R n ( x ) R_n(x) Rn(x) 表示为:

R n ( x ) = K ( x ) ∏ i = 0 n ( x − x i ) R_n(x)=K(x)\prod_{i=0}^{n}{(x-x_i)} Rn(x)=K(x)i=0n(xxi)

其中, K ( x ) K(x) K(x) 是一个待确定的函数。

考虑任意一个非插值节点 x ≠ x i ( i = 0 , 1 , . . . , n ) x\neq x_i(i=0,1,...,n) x=xi(i=0,1,...,n),设辅助函数:
g ( t ) = R n ( t ) − K ( x ) ∏ i = 0 n ( t − x i ) g(t)=R_n(t)-K(x)\prod_{i=0}^{n}{(t-x_i)} g(t)=Rn(t)K(x)i=0n(txi)

容易得到, g ( t ) g(t) g(t) 至少有 n + 2 n+2 n+2 个零点( x x x x 0 , x 1 , . . . , x n x_0,x_1,...,x_n x0,x1,...,xn

根据罗尔定理的推广可得,在区间 [ a , b ] [a,b] [a,b] 内至少存在一点 ξ x \xi_x ξx ,使得辅助函数的 n + 1 n+1 n+1 阶导函数为零,即 g ( n + 1 ) ( ξ x ) = 0 g^{(n+1)}(\xi_x)=0 g(n+1)(ξx)=0,从而可以推导出:
R n ( n + 1 ) ( ξ x ) − K ( x ) ( n + 1 ) ! = 0 R_n^{(n+1)}(\xi_x)-K(x)(n+1)!=0 Rn(n+1)(ξx)K(x)(n+1)!=0

从而有:

f ( n + 1 ) ( ξ x ) − L n ( n + 1 ) ( ξ x ) − K ( x ) ( n + 1 ) ! = 0 f^{(n+1)}(\xi_x)-L_n^{(n+1)}(\xi_x)-K(x)(n+1)!=0 f(n+1)(ξx)Ln(n+1)(ξx)K(x)(n+1)!=0

由于 L n L_n Ln n n n 次多项式,因此, L n ( n + 1 ) ( ξ x ) = 0 L_n^{(n+1)}(\xi_x)=0 Ln(n+1)(ξx)=0,所以有:

f ( n + 1 ) ( ξ x ) − K ( x ) ( n + 1 ) ! = 0 f^{(n+1)}(\xi_x)-K(x)(n+1)!=0 f(n+1)(ξx)K(x)(n+1)!=0

从而推导出: K ( x ) = f ( n + 1 ) ( ξ x ) ( n + 1 ) ! K(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!} K(x)=(n+1)!f(n+1)(ξx)

K ( x ) K(x) K(x) 代回得:

R n ( x ) = f ( n + 1 ) ( ξ x ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) R_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\prod_{i=0}^n{(x-x_i)} Rn(x)=(n+1)!f(n+1)(ξx)i=0n(xxi)

综上所述,我们可以得到如下的特殊情况:

在这里插入图片描述

另外,需要注意的是:

在这里插入图片描述

其中,第二点的意思是,如果原函数 f ( x ) f(x) f(x) 的阶数等于 n n n,那么当使用 m > n m>n m>n 个插值节点求出的拉格朗日插值多项式是精确的。

2.2.2.3 例题

例题1

在这里插入图片描述

例题2

在这里插入图片描述
在这里插入图片描述

从这个例题,可以发现,次数高的插值多项式误差更小。但绝对不是次数越高越好哦(次数过高会出现龙格现象)!

2.2.2.4 拉格朗日插值法的问题

拉格朗日插值法虽然简单易用,但是如果要增加或减少节点时,全部的基函数 l i ( x ) l_i(x) li(x) 都要重新计算,不太方便。

那么如何解决这个问题呢?

在这里插入图片描述

其实,上面的思想就是牛顿插值法的思想。本博客将在下面进行介绍。

2.2.3 牛顿插值法

2.2.3.1 牛顿插值思想

在这里插入图片描述

在这里插入图片描述

2.2.3.2 差商的定义

在介绍牛顿插值公式之前,我们需要介绍**差商(均差)**的定义:

首先给出一阶差商的定义式:

在这里插入图片描述

然后基于一阶差商,给出二阶差商的定义式(其实就是一阶差商的一阶差商):

在这里插入图片描述

最后,写出 k + 1 k+1 k+1 阶差商的定义式:

在这里插入图片描述

需要注意的是, k k k 阶差商必须由 k + 1 k+1 k+1 个节点构成, k k k 个节点是构造不出 k k k 阶差商的。

为了统一起见,补充定义函数 f ( x 0 ) f(x_0) f(x0) 为零阶差商,差商的值与 x i x_i xi 的顺序无关。

2.2.3.3 差商的性质

定义 ω \omega ω 如下:

在这里插入图片描述

然后,可以给出差商的4点性质:

在这里插入图片描述

2.2.3.4 差商表

差商表方便在编程的时候计算不同阶数的差商。

有了差商表,我们可以很容易通过递推的方式计算差商:

在这里插入图片描述

2.2.3.5 牛顿插值公式

牛顿插值是通过选取特殊的基函数来实现的,这时,取

φ 0 ( x ) = 1 φ i + 1 ( x ) = ( x − x i ) φ i ( x ) i = 0 , 1 , . . . , n − 1 \varphi_0(x)=1\\ \varphi_{i+1}(x)=(x-x_i)\varphi_i(x) \quad i=0,1,...,n-1 φ0(x)=1φi+1(x)=(xxi)φi(x)i=0,1,...,n1

作为牛顿插值的以 x 0 , x 1 , . . . , x n x_0,x_1,...,x_n x0,x1,...,xn 为节点的基函数,而次数不超过 n n n 的多项式 N n ( x ) N_n(x) Nn(x) 可表示为:

N n ( x ) = c 0 + c 1 ( x − x 0 ) + c 2 ( x − x 0 ) ( x − x 1 ) + . . . + c n ( x − x 0 ) ( x − x 1 ) . . . ( x − x n − 1 ) N_n(x)=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)+...+c_n(x-x_0)(x-x_1)...(x-x_{n-1}) Nn(x)=c0+c1(xx0)+c2(xx0)(xx1)+...+cn(xx0)(xx1)...(xxn1)

其中, c 0 , c 1 , . . . , c n c_0,c_1,...,c_n c0,c1,...,cn 是待定系数,由插值条件决定。

带入插值条件很容易计算得:

在这里插入图片描述
在这里插入图片描述

根据上述结果,运用数学归纳法可以求得:

c k = f [ x 0 , x 1 , . . . , x k ] c_k=f[x_0,x_1,...,x_k] ck=f[x0,x1,...,xk]

因此就得到下面的满足插值条件的 n n n 次牛顿插值多项式:

在这里插入图片描述

2.2.3.6 牛顿插值余项

在这里插入图片描述
在这里插入图片描述

2.2.3.7 等距节点公式

当节点等距分布时: x i = x 0 + i h ( i = 0 , 1 , . . . , n ) x_i=x_0+ih \quad (i=0,1,...,n) xi=x0+ih(i=0,1,...,n),利用差分,减少差商的除法运算次数,提高效率,下面是关于差分的定义

在这里插入图片描述

然后是一些关于差分的性质:

在这里插入图片描述

然后介绍前插和后插公式:

在这里插入图片描述

x x x 靠近 x 0 x_0 x0 时用前插公式,否则用后插公式

使用牛顿前插或者后插公式,先构造差分表如下:

在这里插入图片描述

2.2.3.8 例题

例题1

在这里插入图片描述
在这里插入图片描述

例题2

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

这篇关于【数值分析】2 - 插值法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/265530

相关文章

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景

MyBatis-Plus中静态工具Db的多种用法及实例分析

《MyBatis-Plus中静态工具Db的多种用法及实例分析》本文将详细讲解MyBatis-Plus中静态工具Db的各种用法,并结合具体案例进行演示和说明,具有很好的参考价值,希望对大家有所帮助,如有... 目录MyBATis-Plus中静态工具Db的多种用法及实例案例背景使用静态工具Db进行数据库操作插入

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手:启用 pprof3. CPU Profiling:分析 C

MySQL表锁、页面锁和行锁的作用及其优缺点对比分析

《MySQL表锁、页面锁和行锁的作用及其优缺点对比分析》MySQL中的表锁、页面锁和行锁各有特点,适用于不同的场景,表锁锁定整个表,适用于批量操作和MyISAM存储引擎,页面锁锁定数据页,适用于旧版本... 目录1. 表锁(Table Lock)2. 页面锁(Page Lock)3. 行锁(Row Lock