不会newton多项式 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

不会newton多项式

不会newton多项式# JobHunting - 待字闺中

c*t2013-01-20 08:01

1 楼

数学白痴，不会大家说的newton多项式。请问newton多项式是不是在面试里就是求sqrt
的？

j*y2013-01-20 08:01

2 楼

求 sqrt的是牛顿迭代吧？
牛顿多项式是拿来插值用的

sqrt

【在 c********t 的大作中提到】

: 数学白痴，不会大家说的newton多项式。请问newton多项式是不是在面试里就是求sqrt
: 的？

c*t2013-01-20 08:01

3 楼

好吧，牛顿迭代除了sqrt，还有什么其他用吗？
没有的话，我就死背吧。

【在 j*****y 的大作中提到】

: 求 sqrt的是牛顿迭代吧？
: 牛顿多项式是拿来插值用的
:
: sqrt

c*a2013-01-20 08:01

4 楼

sqrt用binary search啊
超级简单

c*t2013-01-20 08:01

5 楼

double的呢？

【在 c*****a 的大作中提到】

: sqrt用binary search啊
: 超级简单

l*s2013-01-20 08:01

6 楼

牛顿迭代在machine learning里面貌似很有用
好多模型，比如最大熵，CRF，SVM，等的training方法都是基于这个的，叫L-BFGS。

d*g2013-01-20 08:01

7 楼

其实能不用尽量都不用，算逆矩阵太费事~~

【在 l*******s 的大作中提到】

: 牛顿迭代在machine learning里面貌似很有用
: 好多模型，比如最大熵，CRF，SVM，等的training方法都是基于这个的，叫L-BFGS。

n*r2013-01-20 08:01

8 楼

正解。

【在 d*********g 的大作中提到】

:
: 其实能不用尽量都不用，算逆矩阵太费事~~

l*s2013-01-20 08:01

9 楼

所以说那玩意nb 虽然太费事但是速度比其他的那些迭代快不少

【在 d*********g 的大作中提到】

:
: 其实能不用尽量都不用，算逆矩阵太费事~~

l*a2013-01-20 08:01

10 楼

我很好奇的是面世官真的希望以数学公式作为码工的衡量标准？
这东西能反映出工作中哪方面的能力呢

【在 l*******s 的大作中提到】

: 所以说那玩意nb 虽然太费事但是速度比其他的那些迭代快不少

l*s2013-01-20 08:01

11 楼

肯定不会让当场实现牛顿法的
那玩意在白板上能写到吐血。

【在 l*****a 的大作中提到】

: 我很好奇的是面世官真的希望以数学公式作为码工的衡量标准？
: 这东西能反映出工作中哪方面的能力呢

s*l2013-01-20 08:01

12 楼

:发信人: dreamstring (ric_li), 信区: JobHunting
:标题: Re: 不会newton多项式
:发信站: BBS 未名空间站 (Tue Jan 22 10:27:34 2013, 美东)
:【在 lingandcs (lingandcs) 的大作中提到: 】
:: 牛顿迭代在machine learning里面貌似很有用
:: 好多模型，比如最大熵，CRF，SVM，等的training方法都是基于这个的，叫L-BFGS。
BFGS (L-BFGS) 不是严格意义上的牛顿法，而属于拟牛顿法(Quasi-Newton Method).
http://en.wikipedia.org/wiki/BFGS_method
http://en.wikipedia.org/wiki/L-BFGS
http://en.wikipedia.org/wiki/Quasi-Newton_method
:其实能不用尽量都不用，算逆矩阵太费事~~
Quasi-Newton 方法不用算二阶导 (Hessian Matrix) 以及逆矩阵 (inverse of
Hessian),
而是通过一阶导 (gradient vector)来做近似计算 (approximation)。
http://en.wikipedia.org/wiki/Quasi-Newton_method
One of the chief advantages of quasi-Newton methods over Newton's method is
that the Hessian matrix H (or B, in the case of quasi-Newton methods, its
approximation) does not need to be inverted. Newton's method, and its
derivatives such as interior point methods, require the Hessian to be
inverted, which is typically implemented by solving a system of linear
equations and is often quite costly. In contrast, quasi-Newton methods
usually generate an estimate of inv(B) directly.
...
Implementations
Owing to their success, there are implementations of quasi-Newton methods in
almost all programming languages. The NAG Library contains several routines
[1] for minimizing or maximizing a function[2] which use quasi-Newton
algorithms.
In MATLAB's Optimization toolbox, the fminunc function uses (among other
methods) the BFGS Quasi-Newton method. Many of the constrained methods of
the Optimization toolbox use BFGS and the variant L-BFGS. Many user-
contributed quasi-Newton routines are available on MATLAB's file exchange.
Mathematica includes quasi-Newton solvers. R's optim general-purpose
optimizer routine uses the BFGS method by using method="BFGS"[1].
In the SciPy extension to Python, the scipy.optimize.minimize function
includes, among other methods, a BFGS implementation.
http://www.scipy.org/doc/api_docs/SciPy.optimize.lbfgsb.html

c*a2013-01-20 08:01

13 楼

public static double sqrt(double x){
if(x==1 || x==0) return x;
if(x<0)return -1;
double stopCase = 0.00001;
double left = 0, right = x<1? 1:x;
while(right-left>stopCase){
double mid = left + (right - left)/2;
double midSqr = mid * mid;
if(midSqr ==x)return mid;
else if(midSqr > x) right = mid;
else left = mid;
}
return (left+right)/2.0;
}
这样行不行
算不出来的double就return接近的

【在 c********t 的大作中提到】

: double的呢？