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

[znmkhxrw (QQ)]

 
原文吃光光, 這裡舉個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
推 Vulpix      : 那你要不要試試看先做九個多項式出來？
→ Vulpix      : 第一個先叫做u(x)吧。u(-1)=1,u'(-1)=u"(-1)=u(0)=
→ Vulpix      : u'(0)=u"(0)=u(1)=u'(1)=u"(1)=0。其他八個也類似。
→ Vulpix      : 都是某個導數(零階導數也算導數)=1，其他導數=0。
→ Vulpix      : 那個演算法我沒有去仔細研究，不過看起來……好像
→ Vulpix      : 比較有Newton form的感覺。
 
是牛頓形式沒錯
推 cmrafsts    : 沒錯，這東西應該是Newton form的推廣而不是
→ cmrafsts    : 像他寫的Lagrange的推廣。Lagrange的話可以寫出一個
 
我這篇原文前面寫Lagrange是因為最初在問退化的那一篇我還不知道牛頓形式 而我這裡只?
有說到演算法就是指列差分表來寫牛頓形式
→ cmrafsts    : 容易驗證的形式。我第一篇推文的意思是既然你的問題
→ cmrafsts    : 中f只是用來提供線性代數條件的，那你就用一個滿足
→ cmrafsts    : 那些條件的多項式P代替f，然後說明用P去跑會滿足條
→ cmrafsts    : 件。由退化規則，P和f會寫出一樣的L。
→ cmrafsts    : 改用P寫出的極限是constant family P的極限，所以
→ cmrafsts    : P=L
 
c大你P取代f那邊我理解了, 可是後面constant family P然後得到P=L我就不懂了…
推 Vulpix      : Lagrange form 的退化計算方式，我的文章裡面有寫。
 
這裡重新整理一下問題跟符號:
 
不管Lagrange還是牛頓形式的退化都會是同一個多項式, say L(x)
 
然後列表演算法的多項式我叫他T(x)
 
想證:
(1) L(x) 滿足微分條件
(2) T(x) 滿足微分條件
(3) L(x) = T(x)
 
由於存在唯一滿足微分條件的多項式, 因此上面(1)~(3)任意兩個都能得到剩下那個
 
我這篇原文的敘述方式應該讓(1)~(3)攪在一起了 不好意思
 
→ cmrafsts    : 所以問題應該只是為什麼退化規則長這樣而已。
※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/07/2023 05:34:40
 
→ cmrafsts    : 不是說你寫的，是維基一開始也說是Lagrange的推廣
喔喔 這我覺得可以接受欸 不同的x的話 Lagrange形式跟牛頓形式本來就是同一個多項式 兩
者都可以取極限來退化然後推廣到Hermite

只是差別在牛頓形式在不同的x有套遞迴列表演算法 而且在有相同x中只要改變一些演算法規
則(相同x如何處理)就可以證明(也是我想看到的)這樣規則下出來的多項式會符合Hemite的微
分條件
※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/07/2023 05:37:43
 
→ cmrafsts    : 你用P去插值的結果一定得回P，和點無關
推 Vulpix      : 關於我在一樓的建議，他的好處是立刻可知u是
→ Vulpix      : ( a(x+1)^2+b(x+1)+1/8 )*x^3*(x-1)^3，剩下兩個
→ Vulpix      : 常數就算一下導數。
→ Vulpix      : u這種情況算是九個裡面最難算的了，因為在x=-1那邊
→ Vulpix      : 是u=1而不是u"=1。
嗨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
推 Vulpix      : 對，而且u_1的係數就是f(-1)，其他導數也不用微分
→ Vulpix      : 了。接下來其實還要說明u_i是特定類型的極限，這樣
→ Vulpix      : 可能才能完整回答你的原問題。
推 Vulpix      : https://i.imgur.com/I5iV7U8.png
→ Vulpix      : p(-1)=2, p'(-1)=-8, p''(-1)=56 檢查起來很輕鬆。
→ Vulpix      : 如果想檢查 p(0) =1, p'(0) = 0, p''(0) = 0，你就
→ Vulpix      : 要換一個 p(x) 的寫法。例如改用下圖：
→ Vulpix      : https://i.imgur.com/I5iV7U8.jpg
→ Vulpix      : 得到 https://i.imgur.com/qCGeCra.png。
→ Vulpix      : 牛頓的演算法可以保證兩個多項式相等，不放心的人也
→ Vulpix      : 可以用插值多項式的唯一性這個大定理砸他。
→ Vulpix      : 總之這個形狀能讓我們輕鬆計算在 x=0 的導數。
→ Vulpix      : 然後 p(1)=2, p'(1)=-8, p''(1)=56 也是同理。
→ Vulpix      : top row 那一串係數是偏心的，對 x=-1 太友好。
→ PPguest     : 唯一性需要符合函數值以及高階導數的條件,如果能用
→ PPguest     : 唯一性的話,就不需要檢查了XD
→ PPguest     : 我在想,Newton form 應該也能寫成矩陣的形式,類似
→ PPguest     : V大那篇的 https://i.imgur.com/sPmLIUo.png
→ PPguest     : 然後解就會是divided difference 的樣子
推 Vulpix      : https://i.imgur.com/SRL3DTh.png 啊。
→ PPguest     : 要變成類似V大之前做的得到高階導數的等式應沒希望
推 Vulpix      : 沒有啊，這種東西的反矩陣最容易跑出差分矩陣了，
→ Vulpix      : 在適當的極限下，導數一個一個乖乖現形。
→ PPguest     : 我原本是想,在V大那篇推文裡的 Neville's algorithm
→ PPguest     : 推廣版告訴我們符合條件的多項式其首項係數的長相
→ PPguest     : 想在Hermite形式的多項式從已知的一個推到下一個
→ PPguest     : 例如 https://i.imgur.com/I5iV7U8.jpg
→ PPguest     : 已知 2-8(x+1)+28(x+1)^2 滿足f,f',f''在-1的值
→ PPguest     : 再加一項(x+1)^3,係數先未知,前面三個條件還是會符
→ PPguest     : 合,最後一個條件是在0多項式=1,未知係數就是首項係
→ PPguest     : 數,我們又知道符合條件的首項係數,有沒有辦法證明這
→ PPguest     : 樣取,多項式是否就會滿足第4個條件？
推 Vulpix      : https://i.imgur.com/7r7nNrW.png 這兩條路其實是同
→ Vulpix      : 一個多項式。
→ Vulpix      : 例如說，先看 f[z_3,z_2]=-1。到此為止，f 的插值
→ Vulpix      : 多項式有兩種寫法：2-(x+1) 或 1-x，看我們是從 z_2
→ Vulpix      : 走過來還是從 z_3。
→ Vulpix      : 所以到了 f[z_3,z_2.z_1]=7，f 的插值多項式有三種
→ Vulpix      : 相異的寫法（本來有四種，但簡併了）：1-x+7x(x+1)
→ Vulpix      : 或 2-(x+1)+7(x+1)x 或 2-8(x+1)+7(x+1)^2。
→ Vulpix      : 第一、二種一定一樣，因為就只是又加上了 7x(x+1)。
→ PPguest     : 如果沒有c大的證明以及V大矩陣的證明,那還能確定在
→ Vulpix      : 第二、三種，至少那個 2 是同一個東西，就先不管。
→ PPguest     : Hermite的talbe中,不同的走法會是同個多項式嗎？
→ Vulpix      : -(x+1)+7(x+1)x = f[0,-1](x+1)+f[0,-1,-1](x+1)x
→ Vulpix      : -8(x+1)+7(x+1)^2=f[-1,-1](x+1)+f[0,-1,-1](x+1)^2
→ Vulpix      : RHS 相減得 {f[0,-1]-f[-1,-1]-f[0,-1,-1]}(x+1)，
→ Vulpix      : 其中 f[0,-1,-1] 係數的 -1 是 "0" 跟 "-1" 的差。
→ Vulpix      : 然後因為 f[0,-1,-1] = (f[-1,-1]-f[0,-1])/(-1-0)
→ Vulpix      : 所以 LHS 的差 = 0，故第二、三種也一樣。
→ Vulpix      : 就慢慢遞迴上去。不過就跟你的疑問一樣，其實均差的
→ Vulpix      : 遞迴公式在簡併的時候其實須要釐清。
→ Vulpix      : 如果把遞迴當作均差的定義，那可能要證一下對稱性。
→ Vulpix      : 就像剛剛上面的 f[0,-1,-1]，其實在其中一個情況下
→ Vulpix      : 應該記作 f[-1,-1,0] 會更適當，當然兩項是相等的。
→ PPguest     : 均差定義我是當作一切都 well-defined 直接用(遮臉
→ PPguest     : V大說的不同走法其實都是同一個多項式看起來沒問題.
→ PPguest     : 下面是用一樣的手法來證明一般情況的大綱
→ PPguest     : 欲證：在 Hermite table(相同的點排在一起),不同走
→ PPguest     : 法寫出來的多項式都是同一個。
→ PPguest     : pf:用數學歸納法來證
→ PPguest     : 1a.(滿足)一個點(條件)的多項式只有一種寫法,成立.
→ PPguest     :  b.兩點的分成兩種情況:
→ PPguest     :    i.兩點相同的顯然成立;
→ PPguest     :   ii.兩點不同時把兩個多項式相減說明等於0.會用到
→ PPguest     :      f[z_1,z_2](z_1-z_2) = f[z_1]- f[z_2]
→ PPguest     : 2.假設n-2,n-1個點的情況都會成立,欲證n個點也成立.
→ PPguest     :  一樣分成兩種情況:
→ PPguest     :  a.(n個點的)頭尾兩點相同時,因為相同的點排在一起,
→ PPguest     :    n個點都是同個點,顯然成立;
→ PPguest     :  b.頭尾兩點不同時,由n-1個點的假設,走法分成兩類,
→ PPguest     :    例如從f[z_i,...,z_i+n-2]到f[z_i,...,z_i+n-1]
→ PPguest     :    跟從f[z_i+1,...,z_i+n-1]到f[z_i,...,z_i+n-1],
→ PPguest     :    同一類的走法都是同一個多項式.
→ PPguest     :    從兩類各挑一個走法,目標是兩個多項式相減等於0.
→ PPguest     :    特別挑經過f[z_i+1,...,z_i+n-2]的走法,
→ PPguest     :    由n-2個點的假設,目標式剩最高和次高次數的兩項,
→ PPguest     :    最後會用到遞迴公式.
→ PPguest     : 連結是 table 示意圖 https://imgur.com/UT8kI4N
推 Vulpix      : 2a是沒有必要的。
→ Vulpix      : https://i.imgur.com/uaGwKyV.png
→ Vulpix      : 例如我們想說明綠線跟藍線可以寫出相同的多項式，
→ Vulpix      : 可以直接把綠線換成紅線，最後接向上的箭頭。
→ Vulpix      : 因為在綠色三角形裡面，我們想怎麼換都已經假設能換
→ Vulpix      : 。而藍線則是換成紅線接向下的箭頭。
→ Vulpix      : 之後就是2b的想法：最右邊的(留白的)菱形，走上面或
→ Vulpix      : 走下面都可以，這點是由均差的遞迴公式保證的。
→ Vulpix      : 畢竟在真正的一般情況下，0,0,0不一定會被放在一起
推 Vulpix      : 不過要說偏心問題，其實均差表還是不夠不偏心。
→ Vulpix      : 本來相異的 z_i 應該可以有 (n+1)! 種 Newton form
→ Vulpix      : 但他只給了 2^n 種。
推 PPguest     : 想問V大,"(n個點的)頭尾兩點"你怎麼理解,是指什麼？
推 Vulpix      : 你指的不就是三角形底邊(左)的端點嗎？
→ Vulpix      : 我知道你想分開重複或不重複的點，但是也沒有非得要
→ Vulpix      : 把同樣的 z 相鄰擺放。
→ Vulpix      : 例如z_0=5, z_1=9, z_2=5，那在用 f[5,9] 和 f[9,5]
→ Vulpix      : 算 f[5,9,5] 的時候，就要用 f[5,9,z] 的極限來算。
→ PPguest     : 同意不用把同樣z相鄰擺放.證明的修改2的部分用舊的
→ PPguest     : 2b一直到剩下兩項,頭尾兩點相同會直接等於0,兩點不
→ PPguest     : 同的用遞迴公式.
→ PPguest     : "2a是沒有必要的"是指不需要排成相鄰嗎？
→ PPguest     : "走法分成兩類...同一個多項式"會很難看懂嗎？
→ PPguest     : ^2b裡的
推 PPguest     : @z大 08/14 22:31 的部分晚點我再po一篇文證明
→ znmkhxrw    : 我等你們討論到一個段落後再整理起來閱讀XDDD
推 Vulpix      : 只是「相同與不同」可以一起寫，所以說沒必要分開
→ Vulpix      : 來多寫字。
→ PPguest     : 了解.可能是因為 f[5,9,z]的極限 要另外處理,所以當
→ PPguest     : 提到均差的遞迴公式時,腦袋錯誤地只理解為分母不為0
→ PPguest     : 的遞迴公式.因此看到分母為0卻要用公式會覺得奇怪.
→ PPguest     : 但個人還是偏好分開來講,直接等於0要說用公式很奇怪
推 PPguest     : 寫一個最一般版本的證明大綱
→ PPguest     : 欲證:(不需把同樣的點相鄰擺放,包含單一table外的)
→ PPguest     :      所有走法寫出來的多項式都是同一個.
→ PPguest     : 證明:用數學歸納法
→ PPguest     : 1a.(滿足)一個點(條件)的多項式只有一種寫法,成立.
→ PPguest     :  b.兩點,把兩個多項式相減說明等於0,兩點不同時,用
→ PPguest     :    遞迴公式 f[x_1,x_2](x_1-x_2) = f[x_1]- f[x_2]
→ PPguest     : 2.假設n-2,n-1個點的情況都會成立,欲證n個點也成立.
→ PPguest     :   n個點每種排列都一張table,n!張保證包含全部走法.
→ PPguest     :  a.所有table都同個多項式.用同開頭table同多項式和
→ PPguest     :    同多項式出現在不同開頭table得證. x_i,x_j開頭
→ PPguest     :    table選某個頭x_i尾x_j順序及順序倒過來的table.
→ PPguest     :  b.同開頭table都同個多項式.用table內都同個多項式
→ PPguest     :    和同開頭table都有同個多項式得證.用n-1個點假設
→ PPguest     :  c.單一table內都同個多項式.n-1個點假設得兩類同多
→ PPguest     :    項式的走法,從兩類各挑一個走法,說明兩多項式相
→ PPguest     :    減等於0.利用n-2個點假設挑走法,讓目標式剩最高
→ PPguest     :    和次高的兩項.頭尾兩點不同時,用遞迴公式.