多项式牛顿迭代学习笔记

前置知识

求导

有一个函数$f(x)$,它的导数就是关于它的图像的斜率的函数,记为$f'(x)$

$f'(x)$的导数记为$f”(x)$或$f^{(2)}(x)$,称为二阶导数,还有三阶导数、四阶导数等等

以下是一些常用的求导公式($a$均为常数)

  • $f(x)=a, f'(x)=0$
  • $f(x)=x^a, f'(x)=a\cdot x^{a-1}$
  • $[f(x)*g(x)]’=f'(x)*g(x)+f(x)*g'(x)$

泰勒展开

简单地说就是一个式子,$$f(x)=\sum \limits_{i=0}^n\frac{f^{(i)}(x_0)\cdot (x-x_0)^i}{i!}$$展开是这样$$f(x)=f(x_0)+\frac{f^{(1)}(x_0)\cdot (x-x_0)^1}{1!}+\frac{f^{(2)}(x_0)\cdot (x-x_0)^2}{2!}+\dots+\frac{f^{(n)}(x_0)\cdot (x-x_0)^n}{n!}$$具体的推导思路可以看浅显易懂——泰勒展开式 – SoHardToNamed

Newton’s Method

已知$F(x)$,求
$$F(G(x))\equiv 0\pmod{x^n}$$
假设已知
$$F(H(x))\equiv 0\pmod{x^{\frac{n}{2}}}$$
将$F(G(x))$在$H(x)$处泰勒展开得
$$F(G(x))=F(H(x))+F'(H(x))\cdot (G(x)-H(x))+\frac{F”(H(x))\cdot (G(x)-H(x))^2}{2}\\+\dots+\frac{F^{(n)}(H(x))\cdot (G(x)-H(x))^n}{n!}$$
因为$G(x)$的前$\frac{n}{2}$项是$H(x)$,所以$G(x)-H(x)$的最低的次数就是$\frac{n}{2}$,所以从泰勒展开式的第三项开始,在$\bmod x^n$意义下均为$0$,所以$$F(G(x))\equiv F(H(x))+F'(H(x))\cdot (G(x)-H(x))\equiv 0\pmod{x^n}$$$$G(x)\equiv H(x)-\frac{F(H(x))}{F'(H(x))}\pmod{x^n}$$

应用

多项式开根

求解$$G^2(x)\equiv F(x)\pmod{x^n}\tag{1}$$
式$(1)$等价于$$G^2(x)-F(x)\equiv 0\pmod{x^n}\tag{2}$$
构造$$A(G(x))\equiv G^2(x)-F(x)\pmod{x^n}\tag{3}$$
将$F(x)$看作一个常数,则$$A'(G(x))\equiv 2\cdot G(x)\pmod{x^n}\tag{4}$$
将式$(3)$代入牛顿迭代式得$$G(x)\equiv H(x)-\frac{A(H(x))}{A'(H(x))}\pmod{x^n}\tag{5}$$
带入式$(3), (4)$化简得$$G(x)\equiv H(x)-\frac{H^2(x)-F(x)}{2\cdot H(x)}\pmod{x^n}\tag{6}$$

参考资料

多项式牛顿迭代和多项式开根 – litble

牛顿迭代法在多项式运算的应用 – Miskcoo

Newton’s Method of Polynomial – Picks


多项式牛顿迭代学习笔记》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注