多项式牛顿迭代

本页面最后更新于: 2020/09/25


Description

给定多项式 ,已知有 满足:

求出模 意义下的

Newton's Method

考虑倍增。

首先当 时, 的解需要单独求出。

假设现在已经得到了模 意义下的解 ,要求模 意义下的解

处进行泰勒展开,有:

因为 的最低非零项次数最低为 ,故有:

则:

Examples

多项式求逆

设给定函数为 ,有方程:

应用 Newton's Method 可得:

时间复杂度

多项式开方

设给定函数为 ,有方程:

应用 Newton's Method 可得:

时间复杂度

多项式 exp

设给定函数为 ,有方程:

应用 Newton's Method 可得:

时间复杂度

本页面最近更新:2020/09/25更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面的全部内容在 CC BY-SA 4.0 SATA 协议之条款下提供,附加条款亦可能应用
0 条评论
未登录用户


Copyright © 2016 - 2020 OI Wiki Team

最近更新: c4f7a45, 2020-09-25

联系方式:Telegram 群组 / QQ 群组