Re: [分析] Hermite內插演算法的證明
提供另一種證法，
已知 存在唯一的插值多項式 和 不同插值條件 插值多項式的首項係數，
證明會符合條件。
定理
￣￣
設 x_0, x_1,..., x_n 為 [a,b] 區間中 n+1 個不同的點，
m_i 為 x_i 重複出現的次數(正整數)，N = Σ_{k=0到n} m_k,
z_0, z_1,..., z_{N-1}為包含重複的 x_0, x_1,..., x_n 共 N 個點的任一種排列方式.
函數 f(x) 有適當的條件，f[z_0,z_1,...,z_{N-1}] 是均差。
N-2
令 p(x) = f[z_0] + f[z_0,z_1] (x-z_0) + ... + f[z_0,z_1,...,z_{N-1}] Π (x-z_k).
k=0
假設 次數至多 J-1 次、唯一、滿足插值條件：
y_0, y_1,..., y_j 是 j+1 個不同的點，
r_i 為 y_i 重複出現的次數(正整數)，J = Σ_{k=0到j} r_k,
對 i = 0,1,...,j 以及 所有 m 滿足 0 ≦ m ≦ r_i -1 都有
q^(m)(y_i) = f^(m)(y_i),
的插值多項式 其首項係數為 f[y_0,...,y_i,..,y_i,...,y_j].
└────┘
r_i個y_i
則 對於 i = 0,1,...,n 以及 所有 m 滿足 0 ≦ m ≦ m_i -1 都有
p^(m)(x_i) = f^(m)(x_i).
註：p^(m) 表示函數 p 微 m 次，p^(0)(x) = p(x).
證明：
1. 已知 存在次數至多 N-1 次、唯一的插值多項式 P(x) 滿足插值條件。
N-2
因為 {1,(x-z_0),...,Π (x-z_k)} 是 N-1 次多項式的一組 basis,
k=0
所以存在唯一的係數 c_0, c_1,..., c_{N-1} 使得
N-2
P(x) = c_0 + c_1 (x-z_0) + ... + c_{N-1} Π (x-z_k).
k=0
2. 證明對 i = 0,1,...,N-1 都有 c_i = f[z_0,z_1,...,z_i].
用數學歸納法。
(1) c_0 = P(z_0) = f(z_0) = f[z_0].
(2) 假設對 i = 0,1,...,j-1 都有 c_i = f[z_0,z_1,...,z_i].
設 r_i 為 x_i 在 z_0, z_1,..., z_j 出現的次數(整數)。
j-1
令 P_j(x) = c_0 + c_1 (x-z_0) +...+ c_j Π (x-z_k) 為 P(x) 的前 j+1 項。
k=0
從 P(x) 的後 N-(j+1) 項容易看出
對每個 x_i ∈ {z_0,z_1,...,z_j} 以及 所有 m 滿足 0 ≦ m ≦ r_i -1 都有
P_(j)^(m)(x_i) = f^(m)(x_i).
另外，P_j(x) 是至多 j 次的多項式，
因此由插值多項式的唯一性知 P_j(x) 是滿足 j+1 個條件的插值多項式。
已知 滿足那 j+1 個條件插值多項式的首項係數是 f[z_0,z_1,...,z_j],
故 c_j = f[z_0,z_1,...,z_j].
由數學歸納法，i = 0,1,...,N-1 都有 c_i = f[z_0,z_1,...,z_i]
3. 由 2. 知 P(x) = p(x), 因此 p(x) 滿足插值條件。 □
接下來回過頭來證明 不同插值條件 插值多項式的首項係數長什麼樣子，
過程中先證明 高階導數版本的 Neville's algorithm.
定理
￣￣
設 x_0, x_1,..., x_n 為 [a,b] 區間中 n+1 個不同的點，
m_i 為 x_i 重複出現的次數(正整數)，N = Σ_{k=0到n} m_k,
函數 f(x) 有適當的條件，f[x_0,...,x_i,..,x_i,...,x_n] 是均差。
└────┘
m_i個x_i
設 s_0, s_1,..., s_{N-1} 為 0 到 n 的整數，數字 i 總共重複出現 m_i 次，
P_{s_0,s_1,...,s_{N-1}}(x) = P_{0^{m_0},1^{m_1},...,n^{m_n}}(x) 為
次數至多 N-1 次、唯一的插值多項式滿足插值條件：
對 i = 0,1,...,n 以及 所有 m 滿足 0 ≦ m ≦ m_i -1 都有
P^(m)_{s_0,s_1,...,s_{N-1}}(x_i) = f^(m)(x_i).
則
N-1 f^(k)(x_0)
(1) 當 n = 0, 對所有 N > 0, P_{0^N}(x) = Σ ────── (x-x_0)^k.
k=0 k!
(2) 當 n > 0, 對所有 k 不等於 h,
https://i.imgur.com/aRny5PA.png
(3) P_{s_0,s_1,...,s_{N-1}}(x) 的首項係數是 f[x_0,...,x_i,..,x_i,...,x_n].
└────┘
m_i個x_i
證明：
N-1 f^(k)(x_0)
(1) 令 p(x) = Σ ────── (x-x_0)^k.
k=0 k!
p(x) 是至多 N-1 次的多項式，容易驗證 對所有 m 滿足 0 ≦ m ≦ N-1
p^(m)(x_0) = f^(m)(x_0).
由唯一性，P_{0^N}(x) = p(x).
(2) 令
https://i.imgur.com/lJWUkTJ.png
顯然 p(x) 是至多 N-1 次的多項式。
(a) 當 i 不等於 k 和 h,
https://i.imgur.com/PPs6OkQ.png
對於所有 m 滿足 1 ≦ m ≦ m_i -1,
https://i.imgur.com/7VLRpU5.png
(b) 當 i 等於 k 和 i 等於 h,
因為分子分母同乘 -1 時 h, k 位置互換，所以不失一般性，假設 i = k.
https://i.imgur.com/soHLiwz.png
對於所有 m 滿足 1 ≦ m ≦ m_k -1,
https://i.imgur.com/YsnzPVu.png
(3) 用數學歸納法。
(a) N = 1 時，P_{0}(x) 的首項係數是 f(x_0) = f[x_0].
(b) 假設 N = j-1 時成立。令 N = j.
f^(j-1)(x_0)
(i) n = 0 時，P_{0^j}(x) 首項係數 為 ────── = f[x_0,....,x_0].
(j-1)! └─────┘
j個x_0
(ii) n > 0 時，可以找到 k 不等於 h 的兩點 x_k, x_h, 由 (2)
https://i.imgur.com/aRny5PA.png
以及 N = j-1 的假設，
計算 P_{0^{m_0},1^{m_1},...,n^{m_n}}(x) 的首項係數。
https://i.imgur.com/cry7zcz.png
由數學歸納法，
P_{s_0,s_1,...,s_{N-1}}(x) 的首項係數是 f[x_0,...,x_i,..,x_i,...,x_n].
└────┘
m_i個x_i □
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.192.240.6 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1692710174.A.8E5.html
※ 編輯: PPguest (123.192.240.6 臺灣), 08/22/2023 21:31:46
推
08/23 03:02,
8月前
, 1F
08/23 03:02, 1F
→
08/23 03:02,
8月前
, 2F
08/23 03:02, 2F
→
08/23 03:02,
8月前
, 3F
08/23 03:02, 3F
→
08/23 03:02,
8月前
, 4F
08/23 03:02, 4F
→
08/23 03:02,
8月前
, 5F
08/23 03:02, 5F
→
08/23 03:02,
8月前
, 6F
08/23 03:02, 6F
→
08/23 03:02,
8月前
, 7F
08/23 03:02, 7F
跟你理解的不一樣。
1.這篇均差的定義我沒特別講，但跟你講的一樣，預設是用均差的遞迴關係式 以及
定義好 F[x_0,....,x_0] 來定義的，只要 f 滿足適當的條件，均差就會有那些性質。
└─────┘
m_0 個 x_0
2.整篇都假設已經證明 存在唯一的插值多項式，
第一個定理又假設已經知道 不同插值條件 插值多項式的首項係數，
來證明 p(x) = P(x).
第二個定理的(1)(2) 是證明 高階導數版本的 Neville's algorithm,
也就是插值多項式的遞迴關係式。
(3)則是證明 第一個定理假設的 首項係數。
3.兩個定理我故意順序倒過來。
原本我有把「已知 唯一性...不同條件下插值多項式的首項係數」寫進定理裡面，
但越想越奇怪，一般定理好像都不會把一些已知的性質放進定理裡面，所以才拿掉。
看起來順序倒過來的情況下，把首項係數的假設加進第一個定理的敘述會比較好。
我就補上去。
4.第二個定理 (3) 的證明補上 n=0 的情況。
※ 編輯: PPguest (123.192.240.6 臺灣), 08/23/2023 12:08:22
把第二個定理 (3) 的證明寫清楚一點。
※ 編輯: PPguest (123.192.240.6 臺灣), 08/23/2023 16:06:40
推
08/24 02:11,
8月前
, 8F
08/24 02:11, 8F
→
08/24 02:11,
8月前
, 9F
08/24 02:11, 9F
這個我之前有在定理敘述補上。
假設 次數至多 J-1 次、唯一、滿足插值條件：
y_0, y_1,..., y_j 是 j+1 個不同的點，
r_i 為 y_i 重複出現的次數(正整數)，J = Σ_{k=0到j} r_k,
對 i = 0,1,...,j 以及 所有 m 滿足 0 ≦ m ≦ r_i -1 都有
q^(m)(y_i) = f^(m)(y_i),
的插值多項式 其首項係數為 f[y_0,...,y_i,..,y_i,...,y_j].
└────┘
r_i個y_i
以下面這張圖紅線的走法為例，
https://i.imgur.com/I5iV7U8.jpg
在第一個定理的證明，我至少需要
滿足 p(0) = 1, p'(0) = 0, 至多一次的插值多項式 的首項係數、
滿足 p(0) = 1, p'(0) = 0, p''(0) = 0, 至多二次的插值多項式 的首項係數、
滿足 p(-1) = 2, p(0) = 1, p'(0) = 0, p''(0) = 0,
至多三次的插值多項式的首項係數、
滿足 p(-1) = 2, p(0) = 1, p'(0) = 0, p''(0) = 0, p(1) = 2,
至多四次的插值多項式的首項係數、
滿足 p(-1) = 2, p(0) = 1, p'(0) = 0, p''(0) = 0, p(1) = 2, p'(1) = 8,
至多五次的插值多項式的首項係數、
滿足 p(-1) = 2, p(0) = 1, p'(0) = 0, p''(0) = 0, p(1) = 2, p'(1) = 8,
p''(1) = 56, 至多六次的插值多項式的首項係數、
滿足 p(-1) = 2, p'(-1) = -8, p(0) = 1, p'(0) = 0, p''(0) = 0, p(1) = 2,
p'(1) = 8, p''(1) = 56, 至多七次的插值多項式的首項係數、
滿足 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, 至多八次的插值多項式的首項係數。
※ 編輯: PPguest (123.192.240.6 臺灣), 08/24/2023 20:25:45
推
08/24 20:57,
8月前
, 10F
08/24 20:57, 10F
討論串 (同標題文章)
完整討論串 (本文為第 6 之 6 篇)：
