※ 本文轉寄自 ptt.cc, 文章原始頁面
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
由唯一性,
https://i.imgur.com/aRny5PA.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
Re: 回文串
134
[分析] Hermite內插演算法的證明
Math08/05 04:17
14157
Re: [分析] Hermite內插演算法的證明
Math08/06 19:28
16152
Re: [分析] Hermite內插演算法的證明
Math08/06 23:49
27
Re: [分析] Hermite內插演算法的證明
Math08/07 07:01
314
Re: [分析] Hermite內插演算法的證明
Math08/19 21:47
310
> Re: [分析] Hermite內插演算法的證明
Math08/22 21:16
推
→
→
→
→
→
→
推
→
推