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

看板Math作者cmrafsts (喵喵)時間9月前 (2023/08/07 07:02)推噓2(2推 0噓 5→)

留言7則, 2人參與討論串4/6 (看更多)

既然你只是要知道爲什麼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 (IF). 1. Let P(x) be the desired polynomial. We start with N distinct values b_1,...,b_N and P(b_1),...,P(b_N) to form the table. The accuracy of the interpolation formula in 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}) has 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 terms of degree at least m_n+1-s > 0 on each entry in the s+1th column. As there are m_n+1 column in that rectangle, 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 ※ 編輯: cmrafsts (160.39.29.33 美國), 08/07/2023 07:18:06

推

znmkhxrw

08/07 19:16, 9月前 , 1^F

08/07 19:16, 1^F

→

znmkhxrw

08/07 19:17, 9月前 , 2^F

08/07 19:17, 2^F

→

znmkhxrw

08/07 19:17, 9月前 , 3^F

08/07 19:17, 3^F