标签: newtons-method

你如何编写自己的函数来找到整数的最准确的平方根？

谷歌搜索后,我发现了这个(从原始链接存档),但首先,我没有完全得到它,其次,它也是近似的.

假设平方根为最接近的整数(对于实际的根)或浮点数.

我理解Gradient Descent的作用.基本上它试图通过缓慢向下移动曲线来向局部最优解.我想了解计划梯度下降和牛顿方法之间的实际差异是什么？

从维基百科,我读了这条短线"牛顿的方法使用曲率信息来采取更直接的路线." 这直觉意味着什么？

我正在阅读这份文件:http://software.intel.com/en-us/articles/interactive-ray-tracing

我偶然发现了这三行代码:

SIMD版本已经快了很多,但我们可以做得更好.英特尔为SSE2指令集添加了快速1/sqrt(x)函数.唯一的缺点是它的精度有限.我们需要精度,所以我们使用Newton-Rhapson来改进它:

 __m128 nr = _mm_rsqrt_ps( x ); 
 __m128 muls = _mm_mul_ps( _mm_mul_ps( x, nr ), nr ); 
 result = _mm_mul_ps( _mm_mul_ps( half, nr ), _mm_sub_ps( three, muls ) ); 

此代码假定存在名为"half"(四次0.5f)和变量"three"(四次3.0f)的__m128变量.

我知道如何使用牛顿拉夫森计算函数的零点,我知道如何使用它来计算一个数的平方根,但我看不出这些代码如何执行它.

有人可以向我解释一下吗？

我正在尝试进行一些参数估计,并希望选择参数估计值,以最大限度地减少预测方程中的平方误差超过约30个变量.如果方程是线性的,我只计算30个偏导数,将它们全部设为零,并使用线性方程求解器.但不幸的是,这个等式是非线性的,它的衍生物也是如此.

如果方程式超过单个变量,我只会使用牛顿方法(也称为Newton-Raphson).Web上有丰富的示例和代码来实现Newton的单个变量函数的方法.

鉴于我有大约30个变量,如何使用牛顿方法为这个问题编写数值解？我有闭合形式的方程,可以计算一阶和二阶导数,但我不知道如何从那里开始.我在网上发现了大量的治疗方法,但很快就会进入重基质表示法.我在维基百科上找到了一些适度的帮助,但我在将其转换为代码时遇到了麻烦.

我担心崩溃的地方是矩阵代数和矩阵求逆.我可以使用线性方程求解器反转矩阵,但我担心得到正确的行和列,避免换位错误,等等.

要非常具体:

• 我想使用表将变量映射到它们的值.我可以写一个这样一个表的函数,它返回给出这样一个表作为参数的平方误差.我还可以创建相对于任何给定变量返回偏导数的函数.

• 我对表中的值有一个合理的初始估计,所以我不担心收敛.

• 我不确定如何编写使用估计的循环(每个变量的值表),函数和部分导数函数表来产生新的估计.

最后一点是我要帮助的.任何直接的帮助或指向好的来源将受到热烈的赞赏.

编辑:由于我有封闭形式的第一和第二衍生物,我想利用它们并避免更简单的融合方法,如单面搜索.

我目前正在尝试在RGB(红色,绿色,蓝色)色彩空间和RYB(红色,黄色,蓝色)色彩空间之间转换颜色并再次返回.

基于下面的文章中的细节,我能够使用三线性插值从RYB转换为RGB - 其中参数权重(s,t,u)是RYB颜色,并且立方体的顶点是RGB空间中的3d点.

为可视化绘制灵感的颜色混合和合成 - Gossett和Chen - 第2.1节 - 实现细节

我的困难在于扭转转换过程.

第二篇论文引用了该技术的使用,并且还表明使用牛顿法实现了逆转换.但没有提供进一步的细节.这可能表明在求解三线性插值方程时找到了根.

从注重色彩对比看绘画风格向摄影形象的转换 - 张晓燕,Zhang Xiaoyan 康斯特布尔,M.; 莹鹤;

在我用方程扩展这个问题之前,是否有人用Java/C/C++/C#等语言看到或解决了这个问题？

我目前的方法是采用三线性插值的正演方程(RYB到RGB),展开和重新排列,为3个未知数(参数权重:s,t和u)提供3个联立方程,然后找出如何使用Newton-Raphson方法.我是否以正确的方式解决这个问题？

我将很快编辑这个问题以提供方程式.

非常感谢你的时间,

本

问题的简要说明:我使用Newton Raphson算法在多项式中进行根发现,但在某些情况下不起作用.为什么？

我从"c ++中的数字配方"中得到了一个N​​ewton Raphson混合算法,如果New-Raph没有正确收敛(具有低导数值或者如果收敛速度不快),则将其一分为二.

我用几个多项式检查了算法并且它有效.现在我在我的软件内部进行测试,并且我总是遇到一个特定多项式的错误.我的问题是,我不知道为什么这个多项式只是没有得到结果,而其他人做的很多.因为我想改进任何多项式的算法,需要知道哪一个是没有收敛的原因,所以我可以正确对待它.

下面我将发布我可以提供的有关算法和我遇到错误的多项式的所有信息.

多项式:

f(t)= t^4 + 0,557257315256597*t^3 - 3,68254086033178*t^2 +
+ 0,139389107255627*t + 1,75823776590795

它的第一个衍生物:

 f'(t)= 4*t^3 + 1.671771945769790*t^2 - 7.365081720663563*t + 0.139389107255627

情节:

根(由Matlab提供):

  -2.133112008595826          1.371976341295347          0.883715461977390 
  -0.679837109933505

算法:

double rtsafe(double* coeffs, int degree, double x1, double x2,double xacc,double xacc2)
    {
    int j;
    double df,dx,dxold,f,fh,fl;
    double temp,xh,xl,rts;
    double* dcoeffs=dvector(0,degree);
    for(int i=0;i<=degree;i++)
        dcoeffs[i]=0.0;
    PolyDeriv(coeffs,dcoeffs,degree);
    evalPoly(x1,coeffs,degree,&fl);
    evalPoly(x2,coeffs,degree,&fh);
    evalPoly(x2,dcoeffs,degree-1,&df);
if ((fl > 0.0 && fh > 0.0) || (fl < 0.0 && fh < 0.0))
    nrerror("Root must …

对于赋值,我们被要求创建一个返回反函数的函数.基本问题是从平方函数创建平方根函数.我想出了一个使用二进制搜索的解决方案和另一个使用牛顿方法的解决方案.我的解决方案似乎适用于cube-root和square-root但不适用于log10.这是我的解决方案:

#Binary Search
def inverse1(f, delta=1e-8):
    """Given a function y = f(x) that is a monotonically increasing function on
    non-negative numbers, return the function x = f_1(y) that is an approximate
    inverse, picking the closest value to the inverse, within delta."""
    def f_1(y):
        low, high = 0, float(y)
        last, mid = 0, high/2
        while abs(mid-last) > delta:
            if f(mid) < y:
                low = mid
            else:
                high = mid
            last, mid = mid, (low + high)/2
        return mid
    return f_1

#Newton's …

我发现'addons/math/misc/brent.ijs'将布伦特的方法作为副词实现.我想建立一个牛顿方法作为副词,但它比构建默认动词要困难得多.

这是牛顿迭代的显式版本:

   newton_i =: 1 : '] - u % u d.1'

有了这样的用法:

   2&o. newton_i^:_ (1) NB. (-: 1p1) must be found
1.5708
   2 o. 1.5708 NB. after substitution we get almost 0
_3.67321e_6

当然,为方便起见:

    newton =: 1 : 'u newton_i^:_'

什么是默认的等价物？

在尝试实现牛顿方法的代码以找到平方根的值时(使用迭代),我遇到了一个问题.我试图让功能在达到一定精度后停止打印值,但我似乎无法使其正常工作.以下是我的代码.

MySqrt <- function (x, eps = 1e-6, itmax = 100, verbose = TRUE){
  i <- 1
  myvector <- integer(0)
  GUESS <- readline(prompt="Enter your guess: ")
  GUESS <- as.integer(GUESS)
  while(i <= itmax){
      GUESS <- (GUESS + (x/GUESS)) * 0.5
      myvector <- c(myvector, GUESS)
      if (abs(GUESS-x) < eps) break
      i <- i + 1
  }

  myvector

为什么if语句不起作用？

我正在使用Scipy做一个优化问题,我正在采用一个顶点和大小的NNxNN连接的扁平网络,连接它的两侧(即,使其周期性),并最小化能量函数,以便它卷曲形成一个圆筒.(见下面的链接.)

因为我具备的功能energy(xyz-position)和它的坡度,我决定用在SciPy的手册推荐的三种方法- ,,Newton-CG - ,并比较他们是如何进行的.BFGSL-BFGS-B

我所说的优化功能如下,我只是更换'Newton-CG'与'BFGS'和'L-BFGS-B'根据情况:

from scipy.optimize import minimize
res = minimize(energy, xyzInit, method='Newton-CG', jac = energy_der,  options={'disp': True}) 

我发现了以下一般行为(我给出的输出数据NN=9,对应于一个3*9^2=243参数空间) -

1. BFGS系统地未能找到正确的最小值(对于低值NN),并且根本没有收敛到大的值NN.有关最终结果,请参阅https://plot.ly/~apal90/162/.

    NN=9
    Method: BFGS
    Warning: Desired error not necessarily achieved due to precision loss.
    Current function value: 204.465912
    Iterations: 1239
    Function evaluations: 1520
    Gradient evaluations: 1508
    Time taken for minimisation: 340.728140116
   

   Run Code Online (Sandbox Code Playgroud)

2. Newton-CG发现小的正确的最小值NN(<= 8),但是从NN …