（基础数学专业论文）折线函数的迭代根.pdf

摘要第i 页 折线函数的迭代根 基础数学专业 研究生陈晓丰指导教师张伟年 近年来，随着自然科学技术的进步，迭代和迭代根问题也随之不断地发展 迭代是自然界以及人类生活中的一种普遍现象，也是动力系统讨论的主题它 在混沌方面的研究结果给人类整个知识体系带来了继相对论与量子力学之后又 一次巨大的冲击漫长的历史积淀使得以迭代为基本运算形式的迭代方程成为 与微分方程、差分方程、积分方程及动力系统紧密相关的现代数学分支，深刻地 影响着自然科学与工程技术的发展而迭代和迭代根正是这一理论最基础的问 题之一在本文的绪论中将简要地介绍迭代和迭代根的基本理论、基本结果和 基本问题 第二章介绍非单调函数迭代根的一些进展，包括严格逐段单调连续函数的 迭代根，包括区间上段单调连续映射的k 阶迭代根，包括逐段扩张自映射的 迭代根，以及出现平台现象函数的迭代根此外，还介绍了多项式、折线以及集 值函数等特殊函数的迭代根结果 在第三章，我们在前人给出的单调折线函数的2 次迭代根算法的基础上给 出了计算高次迭代根的算法这个算法基于常用的“逐段定义法”思想但是克 服了逆函数计算的困难，这不仅为近似计算一般单调连续函数迭代根提供了可 能，而且对最简单的线性函数给出了直接计算迭代根的公式 第四章，在上一章的基础上，我们又研究了单峰折线函数这类基本的非单 调函数的迭代根虽然对一般单峰函数已经有了迭代根的结果，但是限制在单 峰折线函数类中还没有结果保证单峰折线函数迭代根的存在性我们的研究还 对单峰折线函数类回答了关于严格逐段单调函数迭代根的一个公开问题 关键词：迭代；迭代根；折线；折线迭代根的算法；非单调 第i i 页 a b s t r a c t i t e r a t i v er o o t so fp i e c e w i s el i n e a ru n i m o d a lf u n c t i o n s m a j o r ：m a t h e m a t i c s g r a d u a t es t u d e n t ：c h e nx i a o f e n g s u p e r v i s o r ：z h a n gw e i n i a n i nr e c e n ty e a r s ，a l o n gw i t ht h ep r o g r e s so fs c i e n c ea n de n g i n e e r i n g ，t h e o r yo f i t e r a t i o na n di t e r a t i v er o o t si sa l s od e v e l o p e dc o n t i n u a l l y i t e r a t i o ni sn o to n l ya n u n i v e r s a lp l m n o m e n o ni l ln a t u r ea n dh u m a nl i f e ，b u ta l s oas u b j e c to nd y n a m i c s y s t e u i s i t sr e s u l t so nc h a o sb r i n ga g a i nat r e m e n d o u si m p a c tt ot h ew h o l e k n o w l e d g es y s t e mo fh u m a nb e i n g s ，a f t e lp li n c i p l eo fr e l a t i v i t ya n dq u a n t u m m e c h a n i c si t e r a t i v ee q u a t i o n sa r et h o s ee q u a t i o n sw h i c hi n v o l v ei t e r a t i o na sa b a s i co p e r a t i o na n dc l o s e l yl i n kw i t hd y n a m i c a ls y s t e m s ，d i f f e r e n t i a le q u a t i o n s ， d i f f e r e n c ee q u a t i o n sa n di n t e g r a le q u a t i o n s ，h a v eg r e a t l ya f f e c t e ds c i e n c ea n d e n g i n e e r i n gt i l ep r o b l e mo fi t e r a t i o na n di t e r a t i v er o o t si so n eo ft h em o s tb a s i c p r o h l e m si nt h i st h e o r y i nt h ei n t r o d u c t i o n ，t h eb a s i ct h e o r y ，t h eb a s i cr e s u l t a n dt h eb a s i cp r o b l e mi l li t e r a t i o na n di t e r a t i v er o o t sa r ei n t r o d u c e db r i e f l y i l lc h a p t e r2 ，s o m ep r o g r e s si ni t e r a t i v er o o t so fn o n - m o n o t o n ef u n c t i o n s a r ci n t l o d u c e d ii n c l u d i n gi t e r a t i v er o o t so fp i e c e w i s em o n o t o n ef u n c t i o n s ，k - o r d e r i t e r a t i v er o o t so fk - p i e c em o n o t o n ec o n t i n u o u ss e l f - m a p p i n g so nt i l ei n t e r v a l ，a s w e l la si t e r a t i v er o o t so fp i e c e w i s ee x p a n d i n gs e l b m a p p i n g si na d d i t i o n ，t h e c h a p t e ri n t r o d u c e sr e s u l t so ni t e r a t i v er o o t so ft h es p e c i a lf u n c t i o n s s u c ha st h e p o l y n o n r i a l s ，t h ep i e c e w i s el i n e a rf u n c t i o n sa n dt h es e t v a l u e df l m c t i o n s i l l c h a p t e r3 ，w ep r o d u c et i l ea l g o r i t h mt oc a l c u l a t eh i g h o r d e ri t e r a t i v e r o o t so fu l o n o t o n ep i e c e w i s el i n e a rf l m c t i o n so u ra l g o r i t h mb a s e so nc o m m o n l y u s e d “s u c c e s s i v e l yd e f i n i n gm e t h o d ”，a n dw eo v e r c o m et h ed i f f i c u l t i e so f i n v e r s ef u n c t i o nc a l c u l a t i o nt h ea l g o r i t h mn o to n l yp r o v i d e st h ep o s s i b i l i t yf o r t i l ea p p r o x i m a t ec a l c u l a t i o no fi t e r a t i v er o o t so fg e n e r a lc o n t i n u o u sf u n c t i o n s ， a b s t r a c t 第i i i 页 b u ta l s og i v e st h ef o r n m l a sw h i c hc a l c u l a t ei t e r a t i v er o o t so ft h es i m p l e s tl i n e a r f u n c t i o n sd i r e c t l y i nc h a p t e r4 ，o nt h eb a s i so ft h el a s t c h a p t e r ，w eh a ss t u d i e di t e r a t i v e r o o t so ft h ep i e c e w i s el i n e a ru n i m o d a lf u n c t i o n s ，w h i c hi sak i n do fb a s i cn o n - m o n o t o n ef l m c t i o n s a l t h o u g hw ea l r e a d yh a d s o m er d s u l t so ni t e r a t i v er o o t so f t h eg e n e r a lu n i m o d a lf u n c t i o n s b u td i dn o tk n o wt l l ee x i s t e n c eo fi t e r a t i v er o o t s o ft h ep i e c e w i s el i n e a ru n i m o d a lf u n c t i o n si no u rr e s e a r c hs o m ep r o g r e s sa r e m a d ei nao p e np r o b l e ma b o u ti t e r a t i v er o o t so fp i e c e w i s em o n o t o n ef u n c t i o n s k e y w o r d s ：i t e r a t i o n ；i t e r a t i v er o o t ；p i e c e w i s el i n e a rf u n c t i o n ；a l g o r i t h m s f o lp i e c e w i s el i n e a rr o o t s ；n o n n l o n o t o n e 致谢 本文是在我的导师张伟年教授的悉心指导下完成的，他 的许多重要工作和思想都是本文的基础。正是他三年来对我 始终不渝的关心、鼓励、教诲和帮助使我顺利完成学业。他 的高尚师德、严谨学风和深邃洞察力给予我深刻的启迪和影 响，使我终身受益。在此成文之际，谨向辛勤培育我的恩师 张伟年老师致以我最崇高的敬意和衷心的感谢! 感谢徐冰教授和陈丽博士对我的关心、指导和帮助。在 此，向她们表示深深的谢意! 感谢王志华、石勇国、邹兰和廖静池同学对我的关心和 帮助。 最后，感谢所有关心、支持和帮助我顺利完成学业的老 师、讨论班的同学和朋友。也感谢我的家人多年来对我的理 解和支持。 第一章绪论 迭代是自然界乃至人类生活中的一种普遍现象，事物运动的全过程，尤其是 各个环节之间的事，就涉及求迭代根，解迭代方程以及迭代的逆运算等问题， 同时，它也是动力系统讨论的主题，通过对迭代的研究，不仅可以预测系统的未 来，也可以追溯系统的过去迭代方程是以迭代为基本运算形式的方程，它作为 一种重要的数学方程形式，近几十年来，也一直备受众多国内外学者的关注，它 的发展对自然科学与工程科学的发展有着深刻的影响，而迭代根正是这一理论 最基础的问题本章将介绍迭代和迭代根的相关概念、理论及发展历史 1 1 迭代与迭代根 迭代就是同一运算或操作的多次重复在数学中，乘法和乘方就分别可看 作是加法和乘法的迭代，一切递推关系都是迭代，微分方程解的p i c a r d 逼近就 是一个迭代过程，微分方程的许多定性问题都可以化为拓扑空间上的连续映射 的迭代来处理在计算机科学研究中，随着计算机技术的飞速发展，迭代运算便 于在计算机上实现的优点突现出来，各种各样的计算问题，在计算机上都可以 应用迭代程序来求解同样在其它科学领域中，如：x 射线的透射可看作射线 衰减率的迭代，流体渗透、传热、生物体的生长、人1 2 1 预测等过程也都包含了迭 代现象 在数学中，对于迭代，研究较为广泛的是映射的迭代，它是由同一映射多次 复合产生的 定义1 1 l 设，：x x 是集合x 到自身的一个映射，记 ，o ( z ) = z ，f n ( z ) = fo ，”一1 ( z ) ， 其中n 为正整数，称尸( z ) 为，( z ) 的n 次迭代 由于迭代是一种非线性运算，它比起线性的微分算子要复杂的多线性函数迭 代后具有保线性的特征，非线性函数迭代n 次后不仅其函数结构十分复杂，而 第2 页第一章绪论 且当n o o 时的极限行为还会出现许多意想不到的事情比如，我们将二次函 数f ( x ) = 4 x ( 1 一z ) 进行迭代，会发现p ( z ) 的图像有2 “一1 个“峰”( 如图) 非线性函数的复杂性往往通过迭代而被放大了3 7 , 4 3 , “ 1 0 5 0 f 2f 3f 4 n ! 砌n ；翮n ； 从迭代的定义可见 图1 1 ：非线性函数的迭代 产= i d ，f m or = f m ” 其中i d 是恒同映射，映射的迭代构成了一个半群如果，是拓扑空间x 上的 连续映射，其迭代被认为是构成了一个离散半动力系统 ，：n z + ) 如果， 是x 上的一个同胚，其迭代构成了一个离散动力系统 广：n z ) 迭代所产 生的动力系统刻画了事物运动的重要环节和发展趋势通过对迭代的研究，不仅 可以预测系统在未来的状态和发展趋势，还可以追溯系统在过去的运动过程人 们既关心事物发展的长期性和终极性状态，还关心事物发展的详细过程，尤其 是各个环节之间的事，这就需要计算映射的分数次迭代以及将离散动力系统嵌 入连续流中通过这样的方式，人们可以将离散化问题的各个环节合理的连接 起来，还原成完整的连续的衍变过程因此，关于迭代，有如下三个基本问题： 1n 次迭代p ( z ) 的计算或估计及其极限的收敛性这里，极限的收敛性可以 研究动力系统轨道o r b f ( x ) = ，n ) ：n = 0 ，1 ，2 ，- ) 的长期行为，如u - 极限集等 2 确定，使之第n 次迭代是一个已知映射f 即求解函数方程，n ( z ) = f ( z ) ，v z x ，这里，称为f 的一个n 次迭代根 3 将f 的离散动力系统嵌入流，也就是要找出一个x 上的连续流西( t ，z ) ，使 得f = ( 1 ，z ) 1 2 迭代根的若干进展第3 页 此外，关于稳定性，包括轨道o r b f ( x ) x c v j 始点的依赖性、迭代根，和嵌 入的流曲对已知映射f 的依赖性、甚至整个系统轨道拓扑结构对f 的依赖性， 也是人们关心的问题这些问题直接关系到对微分方程和差分方程解的深入研 究，关系到对运动过程和终极状态的全面掌握，也关系到实验数据的分析处理 因此，研究迭代的规律在现实生活中具有非常重要的意义 有了一种运算，自然就有一种方程形式迭代方程是包含未知映射迭代的 等量形式它作为一种重要的数学方程形式，受到众多学者的关注从一百多年 以前的施罗德( es c h r s d e r ) 、阿贝尔( nh a b e l ) 、巴贝奇( c b a b b a g e ) 到现代的波狄瓦特( ut b s e d e w a d t ) 、库其玛( m k u c z m a ) 、阿克采( j a c z e l ) 、当布勒斯( jgd h o m b r e s ) 、莱斯( r er i c e ) 、那贝亚( s n a b e y a ) 等科学家，漫长的历史积淀使得迭代方程形成了一个独特的理论体系，它已成为 与微分方程、差分方程和动力系统等紧密相关的现代数学分支，在自然界中也有 许多重要的应用例如，在描述倍周期分岔普适性时的费根鲍姆( f e i g e n b a u m ) 现象、微分方程中的不变流形、h a m i l t o n 系统中的不变环面和不变曲线、正规 形问题等都可归结为对迭代方程的研究此外，在实验和工程科学中，例如射线 透射、液体渗流、人口预测、计算机程序生成。乃至天文学、地质学、心理学和 经济决策等方面，也都提出了许多迭代方程问题 1 2 迭代根的若干进展 前面的叙述中已经提到，在实际应用中，我们常常要考虑事物发展的连续变 化过程由于客观条件的限制，我们往往只能通过实验来获得一些时间离散的数 据( 或图象) 例如每隔同一时间间隔r 采集一次数据能不能从这些离散资料 中找出因果关系，从而得到关于整个发展过程的更系统的知识，这属于动态模式 识别问题在数学上，就是要将离散动力系统嵌入连续流，至少要确定每两个数 据采集时刻之间的数据，亦即在已经获得 z ( 打) ：k = 0 ，1 ，2 ，) ，z ( ( + 1 ) r ) = f ( z ( k t ) ) 的情况下确定满足这一变化规律f 的中间过程z ( ( + n ) r ) ，0 a 1 ，k = 0 ，1 ，3 ，这首先就要确定f 的分数次迭代要确定f 的= 1 次迭代，就 第4 页第一章绪论 必须求解迭代方程 广( z ) = f ( z )( 121 ) 的未知函数，即所谓函数的迭代根问题 关于迭代根的研究，最早是由数学家cb a b b a g e ”】开始的，他在1 8 1 5 年 所写的论文“e s s a yt o w a r d st h ec a l c u l u so ff u n c t i o n s ”【q 中首先研究了“单位 迭代根”，即函数方程 ，“( z ) = z ( 1 22 ) 的解方程( 1 22 ) 也就是著名的“b a b b a g e 方程”1 8 2 6 年，nh a b e l 1 】基 于对线性方程 ，( f ( z ) ) = ，( z ) + c( 123 ) 的研究，找到了一种求解某些迭代根的方法方程( 1 23 ) 即所谓“a b e l 方程” es c h r s d e r ”1 把求解迭代根归结为求解齐次方程 ( 124 ) 该方程便是著名的“s c h r s d e r 方程”，它描述了函数代数中的特征值问题在计 算复杂性理论中有一个有趣的问题是计算指数函数的平方迭代根，即求解方程 ，2 ( z ) = e 。( 1 25 ) 1 9 2 4 年，gh h a r d y 在文献【1 5 】指出方程( 1 2 5 ) 有无穷多个解，并且每个解 都依赖于某个区间上任意给定能j - - + n 数之后，u tb 5 e d e w a d t 4 】研究了更 为一般的情形即方程( 1 21 ) ：在f ( x ) 是区间上单增连续函数的情况下，得到了 与ghh a r d y 类似的结论1 9 5 0 年，ri s a a c s 在一篇精辟的论文【1 7 】中完成 了一个奠基性的工作，给出了抽象集上自映射的迭代根存在的充要条件 在实数域中讨论迭代根问题的工作，最早还有mkj rf o r t “1 关于单实变 函数的结果多实变函数方面的结果较少波兰的学者在函数方程和迭代根方 面的研究是很突出的，特别是在单实变的情形有mk u c z m a 的专著闭”1 和其 它论文m3 3 , ”j 可参考单实变函数迭代根的研究，一般限于单调连续函数， 非单调情形的讨论较少鉴于此，1 9 8 3 年，张景中和杨路在文献f 6 6 1 中讨论了 逐段单调连续函数的迭代根，给出了存在任意次连续迭代根的容易检验的充要 13 本文主要i 作第5 页 条件但这类非单调函数的迭代根问题并未完全解决，于是【6 6 】提出了两个公 开问题对此，张广远阻，6 5 1 研究了逐段扩张自映射的迭代根，孙太祥，席鸿建 在 s 6 1 研究了k 段单调连续自映射的次迭代根，他们的研究回答了在某些情 形时的公开问题对这一问题的研究还可参看文献 5 2 ，5 5 ，5 6 ，5 3 ，5 4 】_ 对于迭代根的光滑性，张伟年利用“结构算子”的新方法研究了迭代根的局 部c 1 光滑性和全局c 1 光滑性 7 4 证实了人们对全局光滑迭代根的一个猜 测，并证明它通有地不存在 关于复变函数迭代根的研究，在gk o e n i g s1 2 8 1 的局部结果的基础上， h k n e s e r l 2 6 1 做出了整函数e 2 的二次迭代根的全局结果，之后r er i c e l 4 8 】等人作 了进一步的工作 近年来这方面工作又有了更新的推进，人们不仅研究圆周上的迭代根旧3 6 , 2 q 以及高维映射的迭代根，而且对某些特殊类型的函数的迭代根感兴趣，例如， bc h o c z e w s k i 和mk u c z l n a 研究了多项式的迭代根吲，t p o w i e r z a 研究了 集值映射的迭代根，jk o b a z a 研究了单调折线的迭代根【2 7 】等等 虽然迭代根问题经历了一百多年的发展，取得了很大突破，但是离彻底解 决这个问题的目标还很远，比如在迭代根的存在性，唯一性，光滑性以及解析 表达等方面都没有很好地得到解决最近的一篇文章i a 】对迭代根的研究现状有 这样的描述：“o n es h o u l dn o te x p e c tr e s u l t so ni t e r a t i v er o o t sz nag e n e r a l s i t u a t i o ni nf a c t ，e v e nr o o t so fp o l y n o m i a l sa r en o td e s c r i b e d e v e nw o r s e ：w e d on o tk n o ww h e t h e re v e r yc o m p l e xc u b i cp o l y n o m i a lh a sas q u a r er o o t ” 1 3 本文主要5 - 作 关于单调折线的迭代根，前人讨论了折线的二次迭代根矧本文讨i f ：t a - 调折线的任意次迭代根，包括单增折线的单增折线根、单增折线的单减折线根 以及单减折线的单减折线根，并给出了这些迭代根存在的容易检验的条件这 是前人没有讨论过的 第6 页第一章绪论 另一个重要的问题是计算迭代根计算一般连续函数的迭代根并非易事， 而要写出某个函数迭代根的解析表达则更加困难因此，人们便想到利用计算机 来近似计算迭代根文献【2 1 ，2 5 ，2 2 ，2 4 ，2 3 给出了利用神经网络近似计算迭代 根的算法f 2 2 】指出这种算法对计算低次迭代根比较有效，对个别函数迭代根 的次数可以达到2 0 次， 2 3 】则指出所计算的迭代根次数一般不能超过1 0 次 本文研究- f ) n 何计算单调折线的高次迭代根我们在基于常用的“逐段定义法” 思想，克服了逆函数计算的困难的情况下，给出了计算高次迭代根的较为有效 的算法，并经过计算机验证，可以计算出次数大于2 0 的迭代根，对最简单折线 即线性函数，我们则给出了其迭代根的解析表达，这些都为近似计算一般连续 单调函数的迭代根包括高次迭代根提供了可能 在此基础之上，我们还研究了单峰或单谷折线这类基本的非单调函数的迭 代根所谓单峰或单谷折线f 是指定义在区间【a ，6 】上，只有一个极值点，并 且在【a ：f 1 和陲b 】上是线性的连续函数虽然【5 2 】文对一般单峰函数已经有迭 代根的结果，但是限制在单峰折线函数类中还没有结果保证单峰折线函数迭代 根的存在性本文给出了这类迭代根存在或不存在的条件，包括n ( f ) = n ( f 2 ) 以及n ( f ) n ( f 2 ) 的情形时f 的迭代根存在或不存在的条件，包括f 在其 特征区间【a ， 或k ，b 】上单增以及单减的情形时f 的迭代根存在或不存在的条 件我们的研究还对单峰折线函数类回答了关于严格逐段单调函数迭代根的一 个公开问题，即，若单峰折线f 满足 a 1 时，那么对任意的整数n ( f ) ，f 没有连续的n 次迭代根 当h ( f ) s1 时，对f 的迭代根，则有 定理2 1 2 f p m ( i ，i ) 且h ( f ) 1 假设 ( i ) f 在其特征区间f 。，b 】上递增，并且 ( i i ) 如果f 在i 上达到a t ( 或b 7 ) ，那么f 必在 a t ，6 ，】上达到a t ( 或6 ，) 那么对于整数n 2 ，p 有连续的n 次迭代根另外，这些条件对整数n n ( f ) + 1 还是必要的 定理2 1 3 f p m ( i ，i ) 且h ( f ) 1 假设 ( i ) f 在其特征区间 。，b j 上递减，并且 ( i i ) 或者f ( ) = b 7 且f ( 6 ，) = g ，或者g f ( z ) 1 ，对v z l ，z 2 【a ，b 】， 都有i ，( z 1 ) 一，( z 2 ) 1 。i z 一x 2 i ，则称f 在 a ，b 上扩张如果将 a ，6 】分成 有f l g - + 6 - 区 司使，在每一个区间上扩张则称f 在 a ，b 上逐段扩张 令，= a ，b 】，s e u ，) 表示，上极值都等于a 或b 的逐段扩张自映射之 4 集通常可以把s e ( i ，) 分为四类，s e ( i ，) = us e , ( i ，) ，其中 t = 1 互不相交 f ( a ) = f ( b ) = 。 ， f ( a ) = f ( b ) = ”， f ( a ) = b ，f ( b ) = n ) f ( a ) = a ，f ( b ) = 6 ) 定理2 1 4 若f s e , ( ，nz = 1 ，2 ，3 ，则对任意自然数n ，函数f 有n 次 迭代根的充要条件是存在自然数k ，使得n ( f ) = k “+ 1 定理2 1 5 若f s e 4 ( ，i ) ，则对任意自然数n ，当n 为偶数时，函数f 没有n 次迭代根；当n 为奇数时，f 有n 次迭代根的充要条件是存在自然数 k ，使得n ( f ) = 护+ 1 上面的结论还可以推广到更一般的函数类 s a e ( i ，) = f c ( i ，) ：，( o ，吣) = ( n ，6 ) 存在划分 a = z l z 2 n 且f ( b ) b 如果存在f ( x ) 的不动点p ( o ，b ) ，使f ( x ) 在【o ，p 上的不动点之集毋和，6 上的不动点之集马之间存在着反序的一一对应： 圣：e 1 _ 局，圣( e ) = e 1 ( e e x ，e 1 如) 且当f ( z ) 一z 在( e l ，e 2 ) 上为正( 负) 时，它在( e 2 1 ，e ) 上为负( 正) ，则称f ( x ) 是一个反序函数 定理2 1 7 设i = 【0 ，1 】上的段连续自映射p ( x ) c ( ，i ) 满足条件2 2 ， 令0 = o o a l 0 2 - - f ( a k 一2 ) f ( 1 ) f ( a k 一1 ) f ( a 1 ) o k 一1 ； ( i i l ) 若k 是奇数且f h l l 严格递减，则f ( x ) 有k 次迭代根的充要条件是： f ( o ) = 1 f ( n 2 ) f ( o 一2 ) f ( a k 一1 ) f ( 1 ) f ( a s ) f ( a 1 ) n k 一1 定理2 1 8 设i = 0 ，1 上的段连续自映射f ( z ) e ( ，i ) 满足条件2 2 ， 令o l 0 2 n k 一1 ，且n l ，n 2 ，一，o k 一1 是f ( x ) 的极值点，【0 ，。1 】是f ( x ) 的特征区间，那么 ( i ) 若女是偶数且fe o 。1 严格递减或k 是奇数且f l o ，。】严格递增，则f ( z ) 无 次迭代根； 2 2 特殊类型函数的根及圆周上的推广第1 1 页 ( i i ) 若k 是偶数且fr t o 。i 严格递增，则f ( z ) 有k 次迭代根的充要条件是 f l t o 1 是个反序函数且 0 = f ( 1 ) f ( a k 一2 ) f ( a k 一4 ) f ( a 2 ) f ( o ) f ( a 1 ) f ( a k 一1 ) a l ； ( - l i ) 若是奇数且f l o 。1 严格递减，则f ( x ) 有次迭代根的充要条件是 下 0 = f ( 1 ) f ( a 女一2 ) f ( a 1 ) f ( o ) f ( n 2 ) f ( a k 1 ) 1 ，若或者f ( n ) = b 7 ，f ( e ) = a ，或者f ( o ) 6 ，f ( 6 ) z ，v z 1 ，对任意整数n 2 ，任取( c ，d ) 内n 个点 z o ，z l ，z n l ，满足 x o t 1 z n l f ( x o ) ：= o n 任取分别定义在p ，x o l ，【x 2 ，z 1 】，【x n - 1 ，x n - 2 】上的严格递增的折线函数 ( z ) ，2 ( z ) ， ，n x ( x ) ，满足 令 ，i ( h 孔一l 】) = 【x i x i 】i = 1 ，2 ，n 一1 fm ( x ) ， 21 f - l ( 坼。) 在 x i ，x i 一- 】定义折线函数 i = n + 1 n + 2 i = 一1 一2 胁，= 篇糍；j 。端一! 籀 那么折线函数 f ( x ) = ( z ) ，z x i ，x i 一1 1 ，i = 0 ，1 ，4 - 2 是f ( x ) 在p l ( i ，) 中递增的n 次迭代根，它还满足 l i r a + f ( x ) 2c ，塑m ) = d 扛l聪m萨穗 硅一 碾凡尉 占个 n 内 却 c取任2 一 几数 整意 隆对r f 疋咖满 抚 ， ” z扛一 f 设一 假 第1 6 页第三章单调折线的迭代根 证明现证情况( i )利用f ( z ) 的单调性可以证明由( 312 ) 定义的序列 黾) 严格递增，并且满足 一l i m 。z t 2 b ：。l i + r a 。z ，= d ( 3 16 ) 此外，( c ，d ) = u 以一- ，z 。 利用f l ( x ) ，2 ( z ) ，一，n ( z ) 的性质以及( 31 3 ) 式， 由引理312 ，用归纳法可以证明每一个 在k - 1 1z 0 上是良定的且是严格递增 的折线函数，且满足 ( 。一1 ) = x i ( ) = x i 十li = 0 ，5 = 1 ，土2 ，一 ( 3 17 ) 因此由( 314 ) 式定义的函数，( z ) 的定义域为( c ，d ) ，且，( 。) 是严格递增的折 线函数利用( 3 13 ) 式可以验证f ( x ) 可以使得p ( z ) = f ( z ) 成立，即f ( x ) 是f ( z ) 的n 次迭代根由( 3 16 ) 式，( 3 l7 ) 式以及f ( x ) 的连续性可以得到 ( 3 15 ) 式 对于( i i ) ，其证明过程与( i ) 类似 口 定理3 1 1 如果f ( z ) p l ( i ，i ) 严格递增，并且f ( a ) = a ，f ( b ) = b ，那么对 任意整数n 2 ，v ( z ) 在p l ( i ，i ) 中有严格递增的n 次迭代根，( z ) 证明注意到i f i x ( f ) 是至多可数个互不相交的开区间的并，设厶：= ( 孔，z ) 是其中的一个由于对比，t ，f ( z ) 一2 7 恒正或恒负，根据引理3 1 3 可知，只：= f i b 有严格递增的连续的n 次折线迭代根 ，并且 l i n l ，( z ) = 。”l i m，( z ) = x i + l 定义 m ，= ，： 容易证明，( z ) p l ( ，) 严格递增，并且满足f - ( z ) = f ( z ) 1 ：3 接着，我们考虑，( z ) 严格递减的情况若( c ，d ) 是组成，一f i x ( f ) 的一个 开子区间，则( d ，c t ) ：= ，( ( c ，d ) ) 其中的一个子区问注意到，( z ) 在集合 ( c ，d ) l j ( d ，c 7 )( 318 ) 3l 存在性 第1 7 页 是个自映射从而我们只需在形如( 31 8 ) 的集合上独立地构造f 的迭代根 引理3 1 4 假设，l = ( c ，d ) ，2 = ( d ，c ，) ，d d ，f ( z ) 是定义在i ：= ，lu1 2 上的严格递增的自映射，r ：= f ( z ) | ，p l ( i ， ) ，i = 1 ，2 ，是满射，并且 ( f 1 ( z ) 一z ) ( r ) 一) z ，v x ，1 且玛( ) ，v y 1 2 ，对任意偶数n 2 ，任取， 内孔个点x o ，x l ，一，z 。一l ，使得x o ( c ，d ) ，z l ( d ，c ，) ，并满足 x o x 2 z n 一1 f ( z 1 ) = z n + 1 任取分别定义在( x 0 ，z 2 】，【功，z 1 】，【x n - ，z n - 3 ，【x n - 2 ，z 。】上的严格递减的 折线函数 ( z ) ，2 ( z ) ， 一1 ( z ) ，满足 ( 甄一1 ，z h l ) = f x i + 2 ，z 。】，i = 1 ，3 ，一，n 一1 ， ( q + 1 ，q 1 1 ) = ( q ，x i 十2 ，i = 2 ，4 ， ，n 一2 今 jf ( 墨一。) ，i = 礼+ 2 ，几十3 ， 21 f - 1 ( 坼。) ，。：一1 , - 2 ， 在旧一l ，z 1 】( 或 x i 十1 ，x i 一1 】) 上定义折线函数 施，= 篇糍；j 渊i = 一o , ) 一- 1 , 1 那么折线函数 f ( x ) = ( z ) ，z 【z 。一l ，z h l 】( 或f z 1 ，x i - 1 】) ，i = 0 ，- t - 1 ，士2 满足 此外，( x ) 还满足 ，“( z ) = f ( z ) ，v x ， ( 3 19 ) ( 311 0 ) ( 3 11 2 ) l i m + f ( z ) = 一。吼m ) 2 叱骧m ) = 正。骧m ) 2 c ( 31 1 3 ) 第1 8 页第三章单调折线的迭代根 ( i i ) 假设p l ( x ) y ，v y 如，对任意偶数n 2 ，任取i 内他个点z o ，z 1 ，z 。一1 ，使得x o ( c ，d ) ，z 1 ( d ，一) ，并满足 x o x 2 茁n 一2 f ( x o ) ：= z n ， x l x 3 x n - 1 1 ，在i 内任取n 个点 x o ，x l ，一，x n _ 1 ，使得x o ( c ，d ) ，z l ( f ( z o ) ，f 一1 ( z o ) ) ，并满足 x o 2 7 2 x n - 2 f ( x o ) ：= z n 任取分别定义在【x o ，z 2 】，【x 3 ，z 1 】，【z 。1 1x n - 3 ，【z 。，z 。一2 上的严格递减的 折线函数 ( z ) ，2 ( z ) ，厶一t ( z ) ，满足 ，i ( f 墨一1 ，z t + l 】) = 【x i + 2 ，戤】，i = 1 ，3 ，一，n 一2 ， ( f + 1 ，x i 一1 】) = 【x i ，z 件2 ，i = 2 ，4 ，一，n 一1 31 存在性 第2 1 页 if ( 孔一。) ， i = n + 2 ，n + 3 ，一， 以。1f - l ( 坼。) ，忙吐_ 2 ) 在k l ，x i + 1 】( 或( x i + l ，甄一1 1 ) 上定义折线函数 胁，= 篇0 - 东i 。0 一- - i 麓0 。：象 ! ：0 c s r ， 那么折线函数 ，( z ) = ( z ) ，z 【甄一1 ，x i + l 】( 或【z t + 1 ，z ，一1 ) ，i = 0 ，士1 ，士2 ，一， 满足 ，“( z ) = f ( 善) ， v z j 此外，f ( x ) 还满足 l i m + f ( z ) 2c 7 。味m ) = 以。嗡，( z ) = d ；吼m ) = c ( i i ) 假设f 2 ( z ) 1 ，在j 内任取n 个点 x o ，z 一，z 。一l ，使得e ( c ，d ) ，z le ( f _ 1 ( z o ) ，f ( z o ) ) ，并满足 z o z 2 z n 一1 f ( x 1 ) ：= z n + l ， z l x n - 2 l ，f ( 。) 在p l ( i ，i ) 中有严格递减的n 次迭代根，( z ) 证明与引理3 l1 的证明类似 3 2 计算机算法 从引理31 3 ，3 14 和315 可知，计算折线函数的迭代根关键是要计算 ( 31 3 ) ，( 311 0 ) 和( 311 7 ) 式，也就是要计算折线函数的逆和复合我们知 道，一个折线函数可由其定义域的端点、折点以及该折线在这些点处的函数值 所确定因此，我们用一个2 n 的矩阵 a ：f ，q 现一n 1 ly 2 表示定义在f x l ，z 。】上的折线函数f ( x ) ，其中z l x 2 z 。，x i 是f ( z ) 的折点，i 一2 ，3 ，n l ：并且y 。= f ( x 。) ，i = 1 ，2 ，m 根据函数与其逆的图像的对称性，易知下面这个关于折线函数逆的结论 定理3 2 1 如果f p l ( i ) 严格单调，t 是它的折点之集，那么其逆f - 1 的 折点之集是f ( t ) 32 计算机算法 第2 3 页 定理32l 揭示了折线的折点与逆的折点之间的关系，也为我们计算其逆提 供了一种算法： 算法3 2 1 输入：折线f 的矩阵a 步骤1 ：判断f 是否可逆，即判断a 的第二行的元素是否按升序或降序 排列，若为假，结