利用离散序列的差分运算寻找序列的下降沿、上升沿、极大值(波峰)、极小值(波谷)的原理

本文主要是介绍利用离散序列的差分运算寻找序列的下降沿、上升沿、极大值(波峰)、极小值(波谷)的原理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

我们先来看一看对于连续函数,我们通常是怎么求其极值的。
通常我们用函数极值的第一充分条件和第二充分条件来求函数的极值。
函数极值的第一充分条件和第二充分条件的内容如下:
(懒得自己写了,直接把高等数学书上的内容截图发上来吧,大家将就看吧!)
在这里插入图片描述
在这里插入图片描述
在实际工程中,我们用得最多的是第二充分条件。

说完了连续函数求极值点,自然该说离散序列怎么找极值点了,即我们常说的寻找离散序列的波峰、波谷。

为了说明这个问题,首先我们要知道“离散序列差分运算”的概念。
设有序列 . . . , f ( k − 2 ) , f ( k − 1 ) , f ( k ) , f ( k + 1 ) , f ( k + 2 ) , . . . ...,f(k-2),f(k-1),f(k),f(k+1),f(k+2),... ...,f(k2),f(k1),f(k),f(k+1),f(k+2),...
则这个序列第k点的:
一阶前向差分定义为: △ f ( k ) = f ( k + 1 ) − f ( k ) \bigtriangleup f(k)=f(k+1)-f(k) f(k)=f(k+1)f(k)
一阶后向差分定义为: ▽ f ( k ) = f ( k ) − f ( k − 1 ) \bigtriangledown f(k)=f(k)-f(k-1) f(k)=f(k)f(k1)
从上面的定义来看,前向差分和后向差分其实没有本质上的区别,所以它们的性质也相同。
序列f(k)的二阶差分是对其一阶差分的差分,即:
△ 2 f ( k ) = △ [ △ f ( k ) ] = △ [ f ( k + 1 ) − f ( k ) ] = △ f ( k + 1 ) − △ f ( k ) \bigtriangleup ^{2} f(k)=\bigtriangleup [\bigtriangleup f(k)]=\bigtriangleup [f(k+1)-f(k)]=\bigtriangleup f(k+1)-\bigtriangleup f(k) 2f(k)=[f(k)]=[f(k+1)f(k)]=f(k+1)f(k)
      = f ( k + 2 ) − 2 f ( k + 1 ) + f ( k ) =f(k+2)-2f(k+1)+f(k) =f(k+2)2f(k+1)+f(k)

用通俗的话来讲:差分,其实就是下一个数值 ,减去上一个数值 。用下一个数值,减去上一个数值 ,就叫“一阶差分”,对一阶差分的结果再做一次差分,就叫“二阶差分"。

从上面的定义式我们可以看出:
对于序列的前向差分,其最后一个点是没有一阶差分的,其最后两个点是没有二阶差分的。

对于序列的后向差分,其第一个点是没有一阶差分的,其第一个点和第二个点是没有二阶差分的。

那么怎么利用序列的差分运算寻找序列的下降沿、上升沿、极值点(波峰、波谷)呢?
离散序列的差分运算类似于连续函数中的求导运算,所以对比上面连续函数对极值点判定的充分条件,我们可以探索出对离散序列下降沿、上升沿、极值点(波峰、波谷)的找寻方法。具体方法如下:

情况一:寻找下降沿
设离散序列中序号为k的点满足以下条件:
△ f ( k ) = 0 \bigtriangleup f(k)=0 f(k)=0
△ f ( k + 1 ) < 0 \bigtriangleup f(k+1)<0 f(k+1)<0
则序号为k+1的点是一个下降沿。
证明:
因为 △ f ( k ) = 0 \bigtriangleup f(k)=0 f(k)=0,所以有 f ( k + 1 ) − f ( k ) = 0 f(k+1)-f(k)=0 f(k+1)f(k)=0,所以 f ( k + 1 ) = f ( k ) f(k+1)=f(k) f(k+1)=f(k)
又由于 △ f ( k + 1 ) < 0 \bigtriangleup f(k+1)<0 f(k+1)<0
所以 △ f ( k + 1 ) = f ( k + 2 ) − f ( k + 1 ) < 0 \bigtriangleup f(k+1)=f(k+2)-f(k+1)<0 f(k+1)=f(k+2)f(k+1)<0
综上,有 f ( k ) = f ( k + 1 ) > f ( k + 2 ) f(k)=f(k+1)>f(k+2) f(k)=f(k+1)>f(k+2)
所以第k+1个点是一个下降沿的边缘。
此时相关点的位置关系如下图所示:
在这里插入图片描述
情况二:寻找上升沿
设离散序列中序号为k的点满足以下条件:
△ f ( k ) = 0 \bigtriangleup f(k)=0 f(k)=0
△ f ( k + 1 ) > 0 \bigtriangleup f(k+1)>0 f(k+1)>0
则序号为k+1的点是一个上升沿。
证明:
因为 △ f ( k ) = 0 \bigtriangleup f(k)=0 f(k)=0,所以有 f ( k + 1 ) − f ( k ) = 0 f(k+1)-f(k)=0 f(k+1)f(k)=0,所以 f ( k + 1 ) = f ( k ) f(k+1)=f(k) f(k+1)=f(k)
又由于 △ f ( k + 1 ) > 0 \bigtriangleup f(k+1)>0 f(k+1)>0
所以 △ f ( k + 1 ) = f ( k + 2 ) − f ( k + 1 ) > 0 \bigtriangleup f(k+1)=f(k+2)-f(k+1)>0 f(k+1)=f(k+2)f(k+1)>0
综上,有 f ( k ) = f ( k + 1 ) < f ( k + 2 ) f(k)=f(k+1)<f(k+2) f(k)=f(k+1)<f(k+2)
所以第k+1个点是一个上升沿的边缘。
此时相关点的位置关系如下图所示:
在这里插入图片描述

情况三:寻找极大值点
设离散序列中序号为k的点满足以下条件:
△ f ( k − 2 ) > 0 \bigtriangleup f(k-2)>0 f(k2)>0
△ f ( k − 1 ) = 0 \bigtriangleup f(k-1)=0 f(k1)=0
△ f ( k ) = 0 \bigtriangleup f(k)=0 f(k)=0
△ f ( k + 1 ) < 0 \bigtriangleup f(k+1)<0 f(k+1)<0
则序号为k的点是一个极大值点。
证明:略,参考情况一、情况二的证明。
此时相关点的位置关系如下图所示:
在这里插入图片描述
情况四:找寻极小值点
设离散序列中序号为k的点满足以下条件:
△ f ( k − 2 ) < 0 \bigtriangleup f(k-2)<0 f(k2)<0
△ f ( k − 1 ) = 0 \bigtriangleup f(k-1)=0 f(k1)=0
△ f ( k ) = 0 \bigtriangleup f(k)=0 f(k)=0
△ f ( k + 1 ) > 0 \bigtriangleup f(k+1)>0 f(k+1)>0
则序号为k的点是一个极小值点。
证明:略,参考情况一、情况二的证明。
此时相关点的位置关系如下图所示:
在这里插入图片描述
需要说明的两点:
①上面情况三、情况四的条件是充分条件,也就是说不满足上面情况的点也有可能是极大值点,极小值点。比如下面图中的k点,它是一个波峰,但它并不满足上面的判定条件。
在这里插入图片描述
②上面的判断条件中并没有用到前面介绍的二阶差分,那为什么要说二阶差分运算呢?因为刚好说到这个知识点,所以就多说了几句嘛。

下面这个链接是运用序列的差分运算找寻离散序列下降沿的例子:
https://www.hhai.cc/thread-232-1-1.html

这篇关于利用离散序列的差分运算寻找序列的下降沿、上升沿、极大值(波峰)、极小值(波谷)的原理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

kotlin中的模块化结构组件及工作原理

《kotlin中的模块化结构组件及工作原理》本文介绍了Kotlin中模块化结构组件,包括ViewModel、LiveData、Room和Navigation的工作原理和基础使用,本文通过实例代码给大家... 目录ViewModel 工作原理LiveData 工作原理Room 工作原理Navigation 工

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

MySQL的隐式锁(Implicit Lock)原理实现

《MySQL的隐式锁(ImplicitLock)原理实现》MySQL的InnoDB存储引擎中隐式锁是一种自动管理的锁,用于保证事务在行级别操作时的数据一致性和安全性,本文主要介绍了MySQL的隐式锁... 目录1. 背景:什么是隐式锁?2. 隐式锁的工作原理3. 隐式锁的类型4. 隐式锁的实现与源代码分析4

MySQL中Next-Key Lock底层原理实现

《MySQL中Next-KeyLock底层原理实现》Next-KeyLock是MySQLInnoDB存储引擎中的一种锁机制,结合记录锁和间隙锁,用于高效并发控制并避免幻读,本文主要介绍了MySQL中... 目录一、Next-Key Lock 的定义与作用二、底层原理三、源代码解析四、总结Next-Key L

Spring Cloud Hystrix原理与注意事项小结

《SpringCloudHystrix原理与注意事项小结》本文介绍了Hystrix的基本概念、工作原理以及其在实际开发中的应用方式,通过对Hystrix的深入学习,开发者可以在分布式系统中实现精细... 目录一、Spring Cloud Hystrix概述和设计目标(一)Spring Cloud Hystr

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动