【数值分析】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

相关文章

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

关于MyISAM和InnoDB对比分析

《关于MyISAM和InnoDB对比分析》:本文主要介绍关于MyISAM和InnoDB对比分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录开篇:从交通规则看存储引擎选择理解存储引擎的基本概念技术原理对比1. 事务支持:ACID的守护者2. 锁机制:并发控制的艺

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

Python主动抛出异常的各种用法和场景分析

《Python主动抛出异常的各种用法和场景分析》在Python中,我们不仅可以捕获和处理异常,还可以主动抛出异常,也就是以类的方式自定义错误的类型和提示信息,这在编程中非常有用,下面我将详细解释主动抛... 目录一、为什么要主动抛出异常?二、基本语法:raise关键字基本示例三、raise的多种用法1. 抛

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三