Re: [分析] Hermite內插演算法的證明

看板Math作者 (QQ)時間2年前 (2023/08/06 23:49), 2年前編輯推噓16(16推 0噓 136→)
留言152則, 4人參與, 最新討論串3/6 (看更多)
原文吃光光, 這裡舉個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://www.ptt.cc/bbs/Math/M.1691336973.A.E9E.html
推
08/07 04:31, 2年前 , 1F
那你要不要試試看先做九個多項式出來？
08/07 04:31, 1F
→
08/07 04:33, 2年前 , 2F
第一個先叫做u(x)吧。u(-1)=1,u'(-1)=u"(-1)=u(0)=
08/07 04:33, 2F
→
08/07 04:35, 2年前 , 3F
u'(0)=u"(0)=u(1)=u'(1)=u"(1)=0。其他八個也類似。
08/07 04:35, 3F
→
08/07 04:36, 2年前 , 4F
都是某個導數(零階導數也算導數)=1，其他導數=0。
08/07 04:36, 4F
→
08/07 04:37, 2年前 , 5F
那個演算法我沒有去仔細研究，不過看起來……好像
08/07 04:37, 5F
→
08/07 04:38, 2年前 , 6F
比較有Newton form的感覺。
08/07 04:38, 6F
是牛頓形式沒錯
推
08/07 04:42, 2年前 , 7F
沒錯，這東西應該是Newton form的推廣而不是
08/07 04:42, 7F
→
08/07 04:43, 2年前 , 8F
像他寫的Lagrange的推廣。Lagrange的話可以寫出一個
08/07 04:43, 8F
我這篇原文前面寫Lagrange是因為最初在問退化的那一篇我還不知道牛頓形式 而我這裡只? 有說到演算法就是指列差分表來寫牛頓形式
→
08/07 04:44, 2年前 , 9F
容易驗證的形式。我第一篇推文的意思是既然你的問題
08/07 04:44, 9F
→
08/07 04:44, 2年前 , 10F
中f只是用來提供線性代數條件的，那你就用一個滿足
08/07 04:44, 10F
→
08/07 04:45, 2年前 , 11F
那些條件的多項式P代替f，然後說明用P去跑會滿足條
08/07 04:45, 11F
→
08/07 04:45, 2年前 , 12F
件。由退化規則，P和f會寫出一樣的L。
08/07 04:45, 12F
→
08/07 04:48, 2年前 , 13F
改用P寫出的極限是constant family P的極限，所以
08/07 04:48, 13F
→
08/07 04:48, 2年前 , 14F
P=L
08/07 04:48, 14F
c大你P取代f那邊我理解了, 可是後面constant family P然後得到P=L我就不懂了…
推
08/07 05:02, 2年前 , 15F
Lagrange form 的退化計算方式，我的文章裡面有寫。
08/07 05:02, 15F
這裡重新整理一下問題跟符號: 不管Lagrange還是牛頓形式的退化都會是同一個多項式, say L(x) 然後列表演算法的多項式我叫他T(x) 想證: (1) L(x) 滿足微分條件 (2) T(x) 滿足微分條件 (3) L(x) = T(x) 由於存在唯一滿足微分條件的多項式, 因此上面(1)~(3)任意兩個都能得到剩下那個 我這篇原文的敘述方式應該讓(1)~(3)攪在一起了 不好意思
→
08/07 05:27, 2年前 , 16F
所以問題應該只是為什麼退化規則長這樣而已。
08/07 05:27, 16F
※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/07/2023 05:34:40
→
08/07 05:37, 2年前 , 17F
不是說你寫的，是維基一開始也說是Lagrange的推廣
08/07 05:37, 17F
喔喔 這我覺得可以接受欸 不同的x的話 Lagrange形式跟牛頓形式本來就是同一個多項式 兩 者都可以取極限來退化然後推廣到Hermite 只是差別在牛頓形式在不同的x有套遞迴列表演算法 而且在有相同x中只要改變一些演算法規 則(相同x如何處理)就可以證明(也是我想看到的)這樣規則下出來的多項式會符合Hemite的微 分條件 ※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/07/2023 05:37:43
→
08/07 05:42, 2年前 , 18F
你用P去插值的結果一定得回P，和點無關
08/07 05:42, 18F
推
08/07 14:20, 2年前 , 19F
關於我在一樓的建議，他的好處是立刻可知u是
08/07 14:20, 19F
→
08/07 14:25, 2年前 , 20F
( a(x+1)^2+b(x+1)+1/8 )*x^3*(x-1)^3，剩下兩個
08/07 14:25, 20F
→
08/07 14:25, 2年前 , 21F
常數就算一下導數。
08/07 14:25, 21F
→
08/07 14:28, 2年前 , 22F
u這種情況算是九個裡面最難算的了，因為在x=-1那邊
08/07 14:28, 22F
→
08/07 14:29, 2年前 , 23F
是u=1而不是u"=1。
08/07 14:29, 23F
嗨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
推
08/07 20:02, 2年前 , 24F
對，而且u_1的係數就是f(-1)，其他導數也不用微分
08/07 20:02, 24F
→
08/07 20:02, 2年前 , 25F
了。接下來其實還要說明u_i是特定類型的極限，這樣
08/07 20:02, 25F
→
08/07 20:02, 2年前 , 26F
可能才能完整回答你的原問題。
08/07 20:02, 26F
推
08/14 16:51, , 27F
08/14 16:51, 27F
→
08/14 16:51, , 28F
p(-1)=2, p'(-1)=-8, p''(-1)=56 檢查起來很輕鬆。
08/14 16:51, 28F
→
08/14 16:52, , 29F
如果想檢查 p(0) =1, p'(0) = 0, p''(0) = 0，你就
08/14 16:52, 29F
→
08/14 17:03, , 30F
要換一個 p(x) 的寫法。例如改用下圖：
08/14 17:03, 30F
→
08/14 17:11, , 31F
08/14 17:11, 31F
→
08/14 17:11, , 32F
。
08/14 17:11, 32F
還有 80 則推文
→
08/16 22:16, , 113F
本來相異的 z_i 應該可以有 (n+1)! 種 Newton form
08/16 22:16, 113F
→
08/16 22:17, , 114F
但他只給了 2^n 種。
08/16 22:17, 114F
推
08/16 23:22, , 115F
想問V大,"(n個點的)頭尾兩點"你怎麼理解,是指什麼？
08/16 23:22, 115F
推
08/16 23:31, , 116F
你指的不就是三角形底邊(左)的端點嗎？
08/16 23:31, 116F
→
08/16 23:32, , 117F
我知道你想分開重複或不重複的點，但是也沒有非得要
08/16 23:32, 117F
→
08/16 23:33, , 118F
把同樣的 z 相鄰擺放。
08/16 23:33, 118F
→
08/16 23:37, , 119F
例如z_0=5, z_1=9, z_2=5，那在用 f[5,9] 和 f[9,5]
08/16 23:37, 119F
→
08/16 23:37, , 120F
算 f[5,9,5] 的時候，就要用 f[5,9,z] 的極限來算。
08/16 23:37, 120F
→
08/17 00:17, , 121F
同意不用把同樣z相鄰擺放.證明的修改2的部分用舊的
08/17 00:17, 121F
→
08/17 00:18, , 122F
2b一直到剩下兩項,頭尾兩點相同會直接等於0,兩點不
08/17 00:18, 122F
→
08/17 00:19, , 123F
同的用遞迴公式.
08/17 00:19, 123F
→
08/17 00:22, , 124F
"2a是沒有必要的"是指不需要排成相鄰嗎？
08/17 00:22, 124F
→
08/17 00:28, , 125F
"走法分成兩類...同一個多項式"會很難看懂嗎？
08/17 00:28, 125F
→
08/17 00:28, , 126F
^2b裡的
08/17 00:28, 126F
推
08/17 00:34, , 127F
@z大 08/14 22:31 的部分晚點我再po一篇文證明
08/17 00:34, 127F
→
08/17 00:48, , 128F
我等你們討論到一個段落後再整理起來閱讀XDDD
08/17 00:48, 128F
推
08/17 00:56, , 129F
只是「相同與不同」可以一起寫，所以說沒必要分開
08/17 00:56, 129F
→
08/17 00:56, , 130F
來多寫字。
08/17 00:56, 130F
→
08/17 20:37, , 131F
了解.可能是因為 f[5,9,z]的極限 要另外處理,所以當
08/17 20:37, 131F
→
08/17 20:37, , 132F
提到均差的遞迴公式時,腦袋錯誤地只理解為分母不為0
08/17 20:37, 132F
→
08/17 20:37, , 133F
的遞迴公式.因此看到分母為0卻要用公式會覺得奇怪.
08/17 20:37, 133F
→
08/17 20:40, , 134F
但個人還是偏好分開來講,直接等於0要說用公式很奇怪
08/17 20:40, 134F
推
08/17 23:28, , 135F
寫一個最一般版本的證明大綱
08/17 23:28, 135F
→
08/17 23:28, , 136F
欲證:(不需把同樣的點相鄰擺放,包含單一table外的)
08/17 23:28, 136F
→
08/17 23:28, , 137F
所有走法寫出來的多項式都是同一個.
08/17 23:28, 137F
→
08/17 23:28, , 138F
證明:用數學歸納法
08/17 23:28, 138F
→
08/17 23:28, , 139F
1a.(滿足)一個點(條件)的多項式只有一種寫法,成立.
08/17 23:28, 139F
→
08/17 23:29, , 140F
b.兩點,把兩個多項式相減說明等於0,兩點不同時,用
08/17 23:29, 140F
→
08/17 23:29, , 141F
遞迴公式 f[x_1,x_2](x_1-x_2) = f[x_1]- f[x_2]
08/17 23:29, 141F
→
08/17 23:29, , 142F
2.假設n-2,n-1個點的情況都會成立,欲證n個點也成立.
08/17 23:29, 142F
→
08/17 23:29, , 143F
n個點每種排列都一張table,n!張保證包含全部走法.
08/17 23:29, 143F
→
08/17 23:29, , 144F
a.所有table都同個多項式.用同開頭table同多項式和
08/17 23:29, 144F
→
08/17 23:30, , 145F
同多項式出現在不同開頭table得證. x_i,x_j開頭
08/17 23:30, 145F
→
08/17 23:30, , 146F
table選某個頭x_i尾x_j順序及順序倒過來的table.
08/17 23:30, 146F
→
08/17 23:30, , 147F
b.同開頭table都同個多項式.用table內都同個多項式
08/17 23:30, 147F
→
08/17 23:30, , 148F
和同開頭table都有同個多項式得證.用n-1個點假設
08/17 23:30, 148F
→
08/17 23:30, , 149F
c.單一table內都同個多項式.n-1個點假設得兩類同多
08/17 23:30, 149F
→
08/17 23:31, , 150F
項式的走法,從兩類各挑一個走法,說明兩多項式相
08/17 23:31, 150F
→
08/17 23:31, , 151F
減等於0.利用n-2個點假設挑走法,讓目標式剩最高
08/17 23:31, 151F
→
08/17 23:31, , 152F
和次高的兩項.頭尾兩點不同時,用遞迴公式.
08/17 23:31, 152F
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1apy4DwU (Math)
討論串 (同標題文章)
完整討論串 (本文為第 3 之 6 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共6篇)
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1apy4DwU (Math)