c********t
发帖数: 5706 | 1 数学白痴，不会大家说的newton多项式。请问newton多项式是不是在面试里就是求sqrt
的？ |
j*****y
发帖数: 1071 | 2 求 sqrt的是牛顿迭代吧？
牛顿多项式是拿来插值用的
sqrt
【在 c********t 的大作中提到】
: 数学白痴，不会大家说的newton多项式。请问newton多项式是不是在面试里就是求sqrt
: 的？
|
c********t
发帖数: 5706 | 3 好吧，牛顿迭代除了sqrt，还有什么其他用吗？
没有的话，我就死背吧。
【在 j*****y 的大作中提到】
: 求 sqrt的是牛顿迭代吧？
: 牛顿多项式是拿来插值用的
:
: sqrt
|
c*****a
发帖数: 808 | 4 sqrt用binary search啊
超级简单 |
c********t
发帖数: 5706 | 5 double的呢？
【在 c*****a 的大作中提到】
: sqrt用binary search啊
: 超级简单
|
l*******s
发帖数: 1258 | 6 牛顿迭代在machine learning里面貌似很有用
好多模型，比如最大熵，CRF，SVM，等的training方法都是基于这个的，叫L-BFGS。 |
d*********g
发帖数: 154 | 7
其实能不用尽量都不用，算逆矩阵太费事~~
【在 l*******s 的大作中提到】
: 牛顿迭代在machine learning里面貌似很有用
: 好多模型，比如最大熵，CRF，SVM，等的training方法都是基于这个的，叫L-BFGS。
|
n****r
发帖数: 471 | 8 正解。
【在 d*********g 的大作中提到】
:
: 其实能不用尽量都不用，算逆矩阵太费事~~
|
l*******s
发帖数: 1258 | 9 所以说那玩意nb 虽然太费事 但是速度比其他的那些迭代快不少
【在 d*********g 的大作中提到】
:
: 其实能不用尽量都不用，算逆矩阵太费事~~
|
l*****a
发帖数: 14598 | 10 我很好奇的是面世官真的希望以数学公式作为码工的衡量标准？
这东西能反映出工作中哪方面的能力呢
【在 l*******s 的大作中提到】
: 所以说那玩意nb 虽然太费事 但是速度比其他的那些迭代快不少
|
l*******s
发帖数: 1258 | 11 肯定不会让当场实现牛顿法的
那玩意在白板上能写到吐血。
【在 l*****a 的大作中提到】
: 我很好奇的是面世官真的希望以数学公式作为码工的衡量标准？
: 这东西能反映出工作中哪方面的能力呢
|
s*********l
发帖数: 103 | 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*****a
发帖数: 808 | 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的呢？
|
