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

既然你只是要知道爲什麼degeneration law長那樣的話... --------------------------------------------------------------- Let F be a field of characteristic 0, a_1,...,a_n be n different values in F, m_1+1,...,m_n+1 be n positive integers. Given c_ij values in F where 0 <= j <= m_i. There is a unique polynomial P(x) with degree < N where N = (m_1+1) + ... + (m_n+1). We claim that P(x) is the one given by Hermite's algorithm. The algorithm constructs a table T the values of which are given by values in n small rectangles following degeneration law (DL) and inductively filling in difference quotients. On the other hand, the values on the top row are those appearing in the intepolation formula and once given, the whole table is determined by inductive formulas (IF) and only addition and multiplication are involved in the rule. 1. Let P(x) be the desired polynomial. We start with N different values b_1,...,b_N to form the table. The accuracy of this case is guaranteed by Newton form. The value b_1,...,b_N are given by a_1, a_1+y_11,..., a_1+y_(1m_1), a_2, a_2+y_21,..., a_2+y_{2m_2},..., a_n, a_n+y_n1,..., a_n+y_(nm_n), regarded as values in the polynomial ring F[{y_ij}]. The table thus written is denoted by T({y_ij}) with values in the function field F({y_ij}). 2. We claim that T({y_ij}) have values in F[{y_ij}]. Suppose the top row is d_0,...,d_(N-1). The interpolation formula is d_0+d_1(x-b_1)+...+d_(N-1)(x-b_1)...(x-b_(N-1))=P(x). Suppose 0 <= m <= N-1 is the least one such that d_m is not in F[{y_ij}]. We separate P(x) into the tow parts d_0+...+d_m(x-b_1)...(x-b_m) + higher terms. This is the only way to decompose P(x) into a multiple of (x-b_1)...(x-b_(m+1)) and a polynomial of degree atmost m in F({y_ij})[x]. Since P(x) is actually in F[{y_ij}][x], such decomposition is made within F[{y_ij}]. However, the leading coefficient of the first part is not in F[{y_ij}] and we get a contraction. 3. We now evaluate at y_ij = 0 for all possible (i,j). The interpolate formula is d_0(0)+...+d_(N-1)(0)(x-a_1)^(m_1)...(x-a_n)^(m_n)=P(x). The table T(0) is given by having d_0(0),...,d_(N-1)(0) on the top row and (IF) because a ring homomorphism preserves (IF). It suffices to check the values in n small rectangles follow (DL). We call the rth small rectangle T({y_ij})_r and we are looking at T(0)_r. 4. Consider the problem where we are considering the interpolation with only conditions on values and higher derivatives at a_r, the table being T'({y_rj}), and the polynomial solving this problem denoted by P'. T'(0) follows (DL) because we have Taylor expansion. Since P-P' has vanishing order at least m_n+1, T({y_ij})_r and T'({y_rj}) differ from a polynomial of order at least m_n+1 > 0 on each entry. Therefore, T(0)_r=T'(0). -- 第01話 似乎在課堂上聽過的樣子 第02話 那真是太令人絕望了 第03話 已經沒什麼好期望了 第04話 被當、21都是存在的 第05話 怎麼可能會all pass 第06話 這考卷絕對有問題啊 第07話 你能面對真正的分數嗎 第08話 我，真是個笨蛋 第09話 這樣成績，教授絕不會讓我過的 第10話 再也不依靠考古題 第11話 最後留下的補考 第12話 我最愛的學分 --
※ 批踢踢實業坊(ptt.cc), 來自: 160.39.29.33 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1691362921.A.E78.html