作者znmkhxrw (QQ)
看板Math
标题Re: [分析] Hermite内插演算法的证明
时间Sun Aug 6 23:49:31 2023
原文吃光光, 这里举个wiki的例子
https://en.wikipedia.org/wiki/Hermite_interpolation#General_case
求满足 p(-1)=2, p'(-1)=-8, p''(-1)=56
p(0) =1, p'(0) = 0, p''(0) = 0
p(1) =2, p'(1) = 8, p''(1) =56
的八次多项式p(x), 其中这九个条件我叫他(●)
依照
画表演算法(相同的x摆一起, 画table, 相同的x以微分值值取代...blabla)
我们构造出函数p(x) = 2 - 8(x+1) + 28(x+1)^2 - 21(x+1)^3 + 15x(x+1)^3
- 10x^2(x+1)^3 + 4x^3(x+1)^3 - x^3(x+1)^3(x-1)
+ x^3(x+1)^3(x-1)^2
如何证明p(x)符合条件(●)
----------------------------------------------------
我从结果论知道p(x)是符合的, 而且任给我例子我都可以
硬爆去证明是对的
但是我就是无法从general case去证明这套演算法都符合
因为这general case很难写...
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.102.225.191 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1691336973.A.E9E.html
1F：推 Vulpix : 那你要不要试试看先做九个多项式出来？08/07 04:31
2F：→ Vulpix : 第一个先叫做u(x)吧。u(-1)=1,u'(-1)=u"(-1)=u(0)=08/07 04:33
3F：→ Vulpix : u'(0)=u"(0)=u(1)=u'(1)=u"(1)=0。其他八个也类似。08/07 04:35
4F：→ Vulpix : 都是某个导数(零阶导数也算导数)=1，其他导数=0。08/07 04:36
5F：→ Vulpix : 那个演算法我没有去仔细研究，不过看起来……好像08/07 04:37
6F：→ Vulpix : 比较有Newton form的感觉。08/07 04:38
是牛顿形式没错
7F：推 cmrafsts : 没错，这东西应该是Newton form的推广而不是08/07 04:42
8F：→ cmrafsts : 像他写的Lagrange的推广。Lagrange的话可以写出一个08/07 04:43
我这篇原文前面写Lagrange是因为最初在问退化的那一篇我还不知道牛顿形式 而我这里只?
有说到演算法就是指列差分表来写牛顿形式
9F：→ cmrafsts : 容易验证的形式。我第一篇推文的意思是既然你的问题08/07 04:44
10F：→ cmrafsts : 中f只是用来提供线性代数条件的，那你就用一个满足08/07 04:44
11F：→ cmrafsts : 那些条件的多项式P代替f，然後说明用P去跑会满足条08/07 04:45
12F：→ cmrafsts : 件。由退化规则，P和f会写出一样的L。08/07 04:45
13F：→ cmrafsts : 改用P写出的极限是constant family P的极限，所以08/07 04:48
14F：→ cmrafsts : P=L08/07 04:48
c大你P取代f那边我理解了, 可是後面constant family P然後得到P=L我就不懂了…
15F：推 Vulpix : Lagrange form 的退化计算方式，我的文章里面有写。08/07 05:02
这里重新整理一下问题跟符号:
不管Lagrange还是牛顿形式的退化都会是同一个多项式, say L(x)
然後列表演算法的多项式我叫他T(x)
想证:
(1) L(x) 满足微分条件
(2) T(x) 满足微分条件
(3) L(x) = T(x)
由於存在唯一满足微分条件的多项式, 因此上面(1)~(3)任意两个都能得到剩下那个
我这篇原文的叙述方式应该让(1)~(3)搅在一起了 不好意思
16F：→ cmrafsts : 所以问题应该只是为什麽退化规则长这样而已。08/07 05:27
※ 编辑: znmkhxrw (59.102.225.191 台湾), 08/07/2023 05:34:40
17F：→ cmrafsts : 不是说你写的，是维基一开始也说是Lagrange的推广08/07 05:37
喔喔 这我觉得可以接受欸 不同的x的话 Lagrange形式跟牛顿形式本来就是同一个多项式 两
者都可以取极限来退化然後推广到Hermite
只是差别在牛顿形式在不同的x有套递回列表演算法 而且在有相同x中只要改变一些演算法规
则(相同x如何处理)就可以证明(也是我想看到的)这样规则下出来的多项式会符合Hemite的微
分条件
※ 编辑: znmkhxrw (59.102.225.191 台湾), 08/07/2023 05:37:43
18F：→ cmrafsts : 你用P去插值的结果一定得回P，和点无关 08/07 05:42
19F：推 Vulpix : 关於我在一楼的建议，他的好处是立刻可知u是 08/07 14:20
20F：→ Vulpix : ( a(x+1)^2+b(x+1)+1/8 )*x^3*(x-1)^3，剩下两个 08/07 14:25
21F：→ Vulpix : 常数就算一下导数。 08/07 14:25
22F：→ Vulpix : u这种情况算是九个里面最难算的了，因为在x=-1那边 08/07 14:28
23F：→ Vulpix : 是u=1而不是u"=1。 08/07 14:29
嗨V大, 当我得到u_1(x)~u_9(x)并且满足你说的那些条件(一个为1, 其他导数为0)
p(x)就是u_i的线性组合, 所以只要找u_i就好了?
※ 编辑: znmkhxrw (114.25.66.212 台湾), 08/07/2023 19:16:15
24F：推 Vulpix : 对，而且u_1的系数就是f(-1)，其他导数也不用微分 08/07 20:02
25F：→ Vulpix : 了。接下来其实还要说明u_i是特定类型的极限，这样 08/07 20:02
26F：→ Vulpix : 可能才能完整回答你的原问题。 08/07 20:02
28F：→ Vulpix : p(-1)=2, p'(-1)=-8, p''(-1)=56 检查起来很轻松。 08/14 16:51
29F：→ Vulpix : 如果想检查 p(0) =1, p'(0) = 0, p''(0) = 0，你就 08/14 16:52
30F：→ Vulpix : 要换一个 p(x) 的写法。例如改用下图： 08/14 17:03
33F：→ Vulpix : 牛顿的演算法可以保证两个多项式相等，不放心的人也 08/14 17:12
34F：→ Vulpix : 可以用插值多项式的唯一性这个大定理砸他。 08/14 17:13
35F：→ Vulpix : 总之这个形状能让我们轻松计算在 x=0 的导数。 08/14 17:14
36F：→ Vulpix : 然後 p(1)=2, p'(1)=-8, p''(1)=56 也是同理。 08/14 17:15
37F：→ Vulpix : top row 那一串系数是偏心的，对 x=-1 太友好。 08/14 17:16
38F：→ PPguest : 唯一性需要符合函数值以及高阶导数的条件,如果能用 08/14 20:13
39F：→ PPguest : 唯一性的话,就不需要检查了XD 08/14 20:14
40F：→ PPguest : 我在想,Newton form 应该也能写成矩阵的形式,类似 08/14 21:12
42F：→ PPguest : 然後解就会是divided difference 的样子 08/14 21:16
44F：→ PPguest : 要变成类似V大之前做的得到高阶导数的等式应没希望 08/14 21:46
45F：推 Vulpix : 没有啊，这种东西的反矩阵最容易跑出差分矩阵了， 08/14 21:59
46F：→ Vulpix : 在适当的极限下，导数一个一个乖乖现形。 08/14 22:00
47F：→ PPguest : 我原本是想,在V大那篇推文里的 Neville's algorithm 08/14 22:31
48F：→ PPguest : 推广版告诉我们符合条件的多项式其首项系数的长相 08/14 22:33
49F：→ PPguest : 想在Hermite形式的多项式从已知的一个推到下一个 08/14 22:36
51F：→ PPguest : 已知 2-8(x+1)+28(x+1)^2 满足f,f',f''在-1的值 08/14 22:38
52F：→ PPguest : 再加一项(x+1)^3,系数先未知,前面三个条件还是会符 08/14 22:40
53F：→ PPguest : 合,最後一个条件是在0多项式=1,未知系数就是首项系 08/14 22:45
54F：→ PPguest : 数,我们又知道符合条件的首项系数,有没有办法证明这 08/14 22:46
55F：→ PPguest : 样取,多项式是否就会满足第4个条件？ 08/14 22:47
57F：→ Vulpix : 一个多项式。 08/14 23:07
58F：→ Vulpix : 例如说，先看 f[z_3,z_2]=-1。到此为止，f 的插值 08/14 23:14
59F：→ Vulpix : 多项式有两种写法：2-(x+1) 或 1-x，看我们是从 z_2 08/14 23:15
60F：→ Vulpix : 走过来还是从 z_3。 08/14 23:16
61F：→ Vulpix : 所以到了 f[z_3,z_2.z_1]=7，f 的插值多项式有三种 08/14 23:17
62F：→ Vulpix : 相异的写法（本来有四种，但简并了）：1-x+7x(x+1) 08/14 23:18
63F：→ Vulpix : 或 2-(x+1)+7(x+1)x 或 2-8(x+1)+7(x+1)^2。 08/14 23:19
64F：→ Vulpix : 第一、二种一定一样，因为就只是又加上了 7x(x+1)。 08/14 23:21
65F：→ PPguest : 如果没有c大的证明以及V大矩阵的证明,那还能确定在 08/14 23:23
66F：→ Vulpix : 第二、三种，至少那个 2 是同一个东西，就先不管。 08/14 23:24
67F：→ PPguest : Hermite的talbe中,不同的走法会是同个多项式吗？ 08/14 23:24
68F：→ Vulpix : -(x+1)+7(x+1)x = f[0,-1](x+1)+f[0,-1,-1](x+1)x 08/14 23:27
69F：→ Vulpix : -8(x+1)+7(x+1)^2=f[-1,-1](x+1)+f[0,-1,-1](x+1)^2 08/14 23:27
70F：→ Vulpix : RHS 相减得 {f[0,-1]-f[-1,-1]-f[0,-1,-1]}(x+1)， 08/14 23:29
71F：→ Vulpix : 其中 f[0,-1,-1] 系数的 -1 是 "0" 跟 "-1" 的差。 08/14 23:30
72F：→ Vulpix : 然後因为 f[0,-1,-1] = (f[-1,-1]-f[0,-1])/(-1-0) 08/14 23:31
73F：→ Vulpix : 所以 LHS 的差 = 0，故第二、三种也一样。 08/14 23:32
74F：→ Vulpix : 就慢慢递回上去。不过就跟你的疑问一样，其实均差的 08/14 23:34
75F：→ Vulpix : 递回公式在简并的时候其实须要厘清。 08/14 23:35
76F：→ Vulpix : 如果把递回当作均差的定义，那可能要证一下对称性。 08/14 23:37
77F：→ Vulpix : 就像刚刚上面的 f[0,-1,-1]，其实在其中一个情况下 08/14 23:38
78F：→ Vulpix : 应该记作 f[-1,-1,0] 会更适当，当然两项是相等的。 08/14 23:39
79F：→ PPguest : 均差定义我是当作一切都 well-defined 直接用(遮脸 08/15 19:43
80F：→ PPguest : V大说的不同走法其实都是同一个多项式看起来没问题. 08/15 19:43
81F：→ PPguest : 下面是用一样的手法来证明一般情况的大纲 08/15 19:43
82F：→ PPguest : 欲证：在 Hermite table(相同的点排在一起),不同走 08/15 19:43
83F：→ PPguest : 法写出来的多项式都是同一个。 08/15 19:44
84F：→ PPguest : pf:用数学归纳法来证 08/15 19:44
85F：→ PPguest : 1a.(满足)一个点(条件)的多项式只有一种写法,成立. 08/15 19:44
86F：→ PPguest : b.两点的分成两种情况: 08/15 19:44
87F：→ PPguest : i.两点相同的显然成立; 08/15 19:44
88F：→ PPguest : ii.两点不同时把两个多项式相减说明等於0.会用到 08/15 19:45
89F：→ PPguest : f[z_1,z_2](z_1-z_2) = f[z_1]- f[z_2] 08/15 19:45
90F：→ PPguest : 2.假设n-2,n-1个点的情况都会成立,欲证n个点也成立. 08/15 19:45
91F：→ PPguest : 一样分成两种情况: 08/15 19:45
92F：→ PPguest : a.(n个点的)头尾两点相同时,因为相同的点排在一起, 08/15 19:45
93F：→ PPguest : n个点都是同个点,显然成立; 08/15 19:45
94F：→ PPguest : b.头尾两点不同时,由n-1个点的假设,走法分成两类, 08/15 19:46
95F：→ PPguest : 例如从f[z_i,...,z_i+n-2]到f[z_i,...,z_i+n-1] 08/15 19:46
96F：→ PPguest : 跟从f[z_i+1,...,z_i+n-1]到f[z_i,...,z_i+n-1], 08/15 19:46
97F：→ PPguest : 同一类的走法都是同一个多项式. 08/15 19:46
98F：→ PPguest : 从两类各挑一个走法,目标是两个多项式相减等於0. 08/15 19:46
99F：→ PPguest : 特别挑经过f[z_i+1,...,z_i+n-2]的走法, 08/15 19:46
100F：→ PPguest : 由n-2个点的假设,目标式剩最高和次高次数的两项, 08/15 19:46
101F：→ PPguest : 最後会用到递回公式. 08/15 19:47
103F：推 Vulpix : 2a是没有必要的。 08/16 20:56
105F：→ Vulpix : 例如我们想说明绿线跟蓝线可以写出相同的多项式， 08/16 21:36
106F：→ Vulpix : 可以直接把绿线换成红线，最後接向上的箭头。 08/16 21:38
107F：→ Vulpix : 因为在绿色三角形里面，我们想怎麽换都已经假设能换 08/16 21:39
108F：→ Vulpix : 。而蓝线则是换成红线接向下的箭头。 08/16 21:39
109F：→ Vulpix : 之後就是2b的想法：最右边的(留白的)菱形，走上面或 08/16 21:42
110F：→ Vulpix : 走下面都可以，这点是由均差的递回公式保证的。 08/16 21:43
111F：→ Vulpix : 毕竟在真正的一般情况下，0,0,0不一定会被放在一起 08/16 21:43
112F：推 Vulpix : 不过要说偏心问题，其实均差表还是不够不偏心。 08/16 22:16
113F：→ Vulpix : 本来相异的 z_i 应该可以有 (n+1)! 种 Newton form 08/16 22:16
114F：→ Vulpix : 但他只给了 2^n 种。 08/16 22:17
115F：推 PPguest : 想问V大,"(n个点的)头尾两点"你怎麽理解,是指什麽？ 08/16 23:22
116F：推 Vulpix : 你指的不就是三角形底边(左)的端点吗？ 08/16 23:31
117F：→ Vulpix : 我知道你想分开重复或不重复的点，但是也没有非得要 08/16 23:32
118F：→ Vulpix : 把同样的 z 相邻摆放。 08/16 23:33
119F：→ Vulpix : 例如z_0=5, z_1=9, z_2=5，那在用 f[5,9] 和 f[9,5] 08/16 23:37
120F：→ Vulpix : 算 f[5,9,5] 的时候，就要用 f[5,9,z] 的极限来算。 08/16 23:37
121F：→ PPguest : 同意不用把同样z相邻摆放.证明的修改2的部分用旧的 08/17 00:17
122F：→ PPguest : 2b一直到剩下两项,头尾两点相同会直接等於0,两点不 08/17 00:18
123F：→ PPguest : 同的用递回公式. 08/17 00:19
124F：→ PPguest : "2a是没有必要的"是指不需要排成相邻吗？ 08/17 00:22
125F：→ PPguest : "走法分成两类...同一个多项式"会很难看懂吗？ 08/17 00:28
126F：→ PPguest : ^2b里的 08/17 00:28
127F：推 PPguest : @z大 08/14 22:31 的部分晚点我再po一篇文证明 08/17 00:34
128F：→ znmkhxrw : 我等你们讨论到一个段落後再整理起来阅读XDDD 08/17 00:48
129F：推 Vulpix : 只是「相同与不同」可以一起写，所以说没必要分开 08/17 00:56
130F：→ Vulpix : 来多写字。 08/17 00:56
131F：→ PPguest : 了解.可能是因为 f[5,9,z]的极限 要另外处理,所以当 08/17 20:37
132F：→ PPguest : 提到均差的递回公式时,脑袋错误地只理解为分母不为0 08/17 20:37
133F：→ PPguest : 的递回公式.因此看到分母为0却要用公式会觉得奇怪. 08/17 20:37
134F：→ PPguest : 但个人还是偏好分开来讲,直接等於0要说用公式很奇怪 08/17 20:40
135F：推 PPguest : 写一个最一般版本的证明大纲 08/17 23:28
136F：→ PPguest : 欲证:(不需把同样的点相邻摆放,包含单一table外的) 08/17 23:28
137F：→ PPguest : 所有走法写出来的多项式都是同一个. 08/17 23:28
138F：→ PPguest : 证明:用数学归纳法 08/17 23:28
139F：→ PPguest : 1a.(满足)一个点(条件)的多项式只有一种写法,成立. 08/17 23:28
140F：→ PPguest : b.两点,把两个多项式相减说明等於0,两点不同时,用 08/17 23:29
141F：→ PPguest : 递回公式 f[x_1,x_2](x_1-x_2) = f[x_1]- f[x_2] 08/17 23:29
142F：→ PPguest : 2.假设n-2,n-1个点的情况都会成立,欲证n个点也成立. 08/17 23:29
143F：→ PPguest : n个点每种排列都一张table,n!张保证包含全部走法. 08/17 23:29
144F：→ PPguest : a.所有table都同个多项式.用同开头table同多项式和 08/17 23:29
145F：→ PPguest : 同多项式出现在不同开头table得证. x_i,x_j开头 08/17 23:30
146F：→ PPguest : table选某个头x_i尾x_j顺序及顺序倒过来的table. 08/17 23:30
147F：→ PPguest : b.同开头table都同个多项式.用table内都同个多项式 08/17 23:30
148F：→ PPguest : 和同开头table都有同个多项式得证.用n-1个点假设 08/17 23:30
149F：→ PPguest : c.单一table内都同个多项式.n-1个点假设得两类同多 08/17 23:30
150F：→ PPguest : 项式的走法,从两类各挑一个走法,说明两多项式相 08/17 23:31
151F：→ PPguest : 减等於0.利用n-2个点假设挑走法,让目标式剩最高 08/17 23:31
152F：→ PPguest : 和次高的两项.头尾两点不同时,用递回公式. 08/17 23:31