今回は、前回までで証明した「部分終結式の基本定理」に基づき、多項式剰余列の係数膨張を抑える「縮小PRSアルゴリズム」および「部分終結式PRSアルゴリズム」の紹介を行いました。
次回からは、モジュラー法による多項式の最大公約子 (GCD) 計算の効率化手法の紹介に入ります。
お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、前回までで証明した「部分終結式の基本定理」に基づき、多項式剰余列の係数膨張を抑える「縮小PRSアルゴリズム」および「部分終結式PRSアルゴリズム」の紹介を行いました。
次回からは、モジュラー法による多項式の最大公約子 (GCD) 計算の効率化手法の紹介に入ります。
今回は、前回のラグランジュ補間のアルゴリズムに続き、ラグランジュ補間の誤差評価を行った後で、スプライン補間と最小二乗法について説明しました。
次回は数値積分の説明を行う予定です。
今回は、前回の内容を踏まえ、2つの補題の証明をした後で「部分終結式の基本定理」の証明を行いました。
次回は、部分終結式の基本定理に基づいて多項式剰余列の係数膨張を抑えるアルゴリズムの紹介を行う予定です。
今回は、前半で、1変数方程式の近似解法として「2分法」および「ニュートン法」を紹介しました。後半では、曲線の推定方法の一つとして「ラグランジュの補間法」を紹介しました。
次回は、ラグランジュの補間法の誤差評価を説明し、曲線の推定の後半として、スプライン補間法と、最小二乗法について説明します。
今回の前半では、前回の話の一般化として、多項式剰余列の各要素の係数を、最初に与えられた多項式の係数を成分にもつ行列式で表す方法について紹介し、部分終結式の導入を行いました。後半では、部分終結式を1つの行列式で表す表現を与え、この授業の目標の一つである「部分終結式の基本定理」に至る補題の証明でよく用いられる、部分終結式を表す行列式の行変形について議論しました。
次回は、「部分終結式の基本定理」の証明の準備として、補題の証明に進む予定です。