l******r 发帖数: 18699 | 1 约瑟夫·拉弗森(Joseph Raphson,1648年-1715年)是英格兰数学家,和牛顿都提出
过后来被人称为的牛顿-拉弗森方法,他的一生鲜为人知,甚至他的出生和逝世的日期
都难以确定,数学史的学家Florian Cajori曾提供出的约瑟夫·拉弗森的大致日期为
1648年-1715年。事实上,约瑟夫·拉弗森早于牛顿50年提出这个方法。不过牛顿凭借
其出色的偷窃本领让自己和约瑟夫·拉弗森共同成为这个方法的发现者。
牛顿历史上不止一次干过偷窃的行当。今天我们看到的牛顿其实是牛顿和许多其他人的
结合体。 |
|
s*m 发帖数: 5 | 2 小弟菜鸟,最近碰到一个问题:
G(x) = |f(x)|^s
这里s是常数,x变量是一个p维向量,求G(x)'=0的根。Newton-Raphson需要求1阶和2阶,也就是
\frac{\partial G}{\partial x} 和 \frac{\partial^2 G}{\partial x \partial x^T
} (T是转置)
不知道大家有没有遇到类似的,对绝对值求导的情况,或指条明路?这种情形下怎么求G(x)'=0的根? |
|
s*m 发帖数: 5 | 3 小弟菜鸟,最近碰到一个难题 (已经更正):
G(x) = |f(x)|^s
这里s是常数,x变量是一个p维向量,求G(x)'=0的根。Newton-Raphson需要求1阶和2阶,也就是
\frac{\partial G}{\partial x} 和 \frac{\partial^2 G}{\partial x \partial x^T
} (T是转置)
不知道大家有没有遇到类似的,对绝对值求导的情况,或指条明路?这种情形下怎么求G(x)'=0的根? |
|
e*****n 发帖数: 124 | 4 目前用newton-raphson,但是解太依赖于给的初始值,想问问有没有办法能够大概估计个
解存在的区间,或者有没有方法能够不是这么以来初值.
另外,我的问题是解ODE方程组,用newton-raphson求fixed-point,然后再分析稳定性.但
newton-raphson好象很难收敛到在saddle point的fixed-point,想问问有啥方法找到这
些不稳定的解.
谢谢 |
|
|
X******i 发帖数: 1384 | 6 谢谢,我没干过数值计算的活,这次是赶鸭子上架。我大学是在法国读的,所以有些中
文术语不清楚,牛顿迭代是不是就是newton raphson?收敛应该是converge吧?
我的问题有点复杂,前面没有解释清楚。关键是逼近值一定要准,因为这只是一个单元
里的逼近值,然后输出到下一个单元作为输入。一共有几千个单元,所以如果不准的话
最后的误差会被放大。我最开始用的是brute forcing,一步一步向交点逼近,计算停止
在误差小于0.1%(举例),但是如果我的step取的不够小的话,可能最靠近交点的逼近
值都不能在0.1%以内,无法converge。但是step取的小的话,计算量又很大。
bisection我也用过,也不准尤其是在多个单元之后,误差会越来越大。
我还试过shooting method,其实差不多就是newton raphson了,两边取tangent line向
中间逼近,但是他的缺点是逼近点在不同的单元里有时在左侧,有时在右侧,不过倒是
有可能互相取消。但是横坐标的数值不是整数,给我后面的运算带来很多麻烦。 |
|
d****o 发帖数: 32610 | 7 【 以下文字转载自 Military 讨论区 】
发信人: Xujiahui (南模是所好学校), 信区: Military
标 题: Re: 法国科学家
发信站: BBS 未名空间站 (Sun Apr 24 00:25:31 2016, 美东)
谢谢,我没干过数值计算的活,这次是赶鸭子上架。我大学是在法国读的,所以有些中
文术语不清楚,牛顿迭代是不是就是newton raphson?收敛应该是converge吧?
我的问题有点复杂,前面没有解释清楚。关键是逼近值一定要准,因为这只是一个单元
里的逼近值,然后输出到下一个单元作为输入。一共有几千个单元,所以如果不准的话
最后的误差会被放大。我最开始用的是brute forcing,一步一步向交点逼近,计算停止
在误差小于0.1%(举例),但是如果我的step取的不够小的话,可能最靠近交点的逼近
值都不能在0.1%以内,无法converge。但是step取的小的话,计算量又很大。
bisection我也用过,也不准尤其是在多个单元之后,误差会越来越大。
我还试过shooting method,其实差不多就是newton raphson了... 阅读全帖 |
|
s****h 发帖数: 921 | 8 x=[x1,x2,...,xn]
min g(x)
st. f1(x)=0
f2(x)=0
...
fm(x)=0
传统算法是Least Square加Gauss-Newton法迭代作.
但当x维数很大的时候,收敛性有一些问题.
但是我的问题有一个特殊之处:
迭代计算,
每次将f(x)从nonlinear方程变成linear方程,h(x).
h(x)和f(x)关系类似h(x)=f(x)/x
这样每次就可以用Least Square解线性方程算出x.
每次再重新迭代.
我发现有趣的是收敛性能更好了.
但是迭代步数增加了.
我感觉有点象Gaussian-Siedel和Newton-Raphson解非线性方程.
前者收敛性能好像好一点,主要对初值要求不高,但收敛步数的确比Newton-Raphson多.
当然,二个算法都没保证一定会收敛. |
|
l***u 发帖数: 91 | 9 20K 个implied vol应该很快啊 一般都是Newton-Raphson
具体看你那20K的implied vol都是什么关系 有没有办法优化Newton Raphson的初始值
来更快的收敛 |
|
j*******y 发帖数: 58 | 10 I think LZ answered very well in logistic regression. The idea indeed is MLE
, which I learned in graduate school; the next step is to solve for MLE,
which is an algorithm problem.LZ didn't mention 'NR" or 'iterative methods',
probably this is because newton raphson and iterative methods are TOO
standard and TOO simple so that he didn't realize that this was part of the
answer.
I learned newton raphson method in the first year of college. It is as
simple as (a+b)^2=a^2+2ab+b^2.
anyone asking me ... 阅读全帖 |
|
q********g 发帖数: 10694 | 11 Sobereva
Department of Chemistry, University of Science and Technology Beijing,
Beijing 100083, China
前言:本文主要介绍过渡态、反应路径的计算方法,并讨论相关问题。由于这类算法极
多,可以互相组合,限于精力不可能面面俱到展开,所以只介绍常用,或者实用价值有
限但有启发性的方法。文中图片来自相关文献,做了一定修改。由于本文作为帖子发布
,文中无法插入复杂公式,故文中尽量将公式转化为文字描述并加以解释,这样必然不
如公式形式严谨,而且过于复杂的公式只能略过,但我想这样做的好处是更易把握方法
的梗概,有兴趣可以进一步阅读原文了解细节。对于Gaussian中可以实现的方法,文中
对其在Gaussian中的使用进行了一些讨论,希望能纠正一些网上流传的误区。虽然绝大
多数人不专门研究计算方法,其中很多方法也不会用到,但多了解一下对开阔思路是很
有好处的。
文中指的“反应”包括构象变化、异构化、单分子反应等任何涉及到过渡态的变化过程
。“反应物”与“产物”泛指这些过程的初态和末态。“优化”若未注明,... 阅读全帖 |
|
X******i 发帖数: 1384 | 12 看来军版都是数学大牛,那我这个数学小白问个问题吧。我有两条相交曲线,每一条都
是几个公式画出来的,就是说不是一个公式。如果我想知道交点的数值通过电脑编程,
我如何才能得到最准确的逼近值?朋友说NEWTON RAPHSON可以,大家有什么想法?
还有一个条件就是尽可能减少计算量。 |
|
s*******e 发帖数: 93 | 13 For 3 you can use Newton–Raphson method to solve x^2=n and get a more exact
answer. |
|
c***f 发帖数: 40 | 14 Implement int sqrt(int x).
Compute and return the square root of x.
这个问题的复杂度是多少呢,
both recursive way and Newton Raphson way |
|
c*******y 发帖数: 1630 | 15 很小的时候,1/sqrt(1/x) 等价于很大
x很大的时候,可以把初始值猜得小一点。 肯定排除二分,起码newton-raphson |
|
p******e 发帖数: 528 | 16 确实是如此,我还没有开始刷题,现在正在自己补数据结构和算法的知识。其实这个问题
也和另外一个问题有关,就是不同背景的人可能会对同一个问题有完全不同的认识。比
方说我
听说有人面试被问如何去求解一个f(x)=0 的一元方程。这个被问的人是数值计算的
背景,
他首先想到的就是类似于Newton-Raphson类似的迭代算法,结果后来有人告诉他面试官
想听的是二分法。其实就是把解f(x)=0作为一个类似于二分查找的变种来问的。所以
无论
哪个参加面试的人怎么改进他的迭代算法都没法通过面试。因为俩人谈不到一块去。。。 |
|
E**********e 发帖数: 1736 | 17 【 以下文字转载自 Java 讨论区 】
发信人: ExpressoLove (MoneyForNothing), 信区: Java
标 题: 怎样使的java double for loop 加快
发信站: BBS 未名空间站 (Sat Jul 30 09:46:45 2016, 美东)
最近用java 编了个newton raphson 的算法。 就是需要大量的2维矩阵/数组迭代。 原
始数据有150000x50。 发现迭代7,8次得到最优解需要有一分钟。如果用cross
validation ,再加个额外的30次cycle的话,那得要1个小时。 但是用python的numpy
pacakge要快点多。 当然所有2维数组计算,乘除, 加减,逆矩阵都是自己写的小
code, 都是用for loop。
请问怎样才能speed up。 |
|
h**********c 发帖数: 4120 | 18 这个不是难在算法上,
1. 不同的硬件,有不同的language extension.
2. ati 没有例题.
你看在第一层,没有透明效果,不需要"深度纹理的屏幕坐标准确地投射到物体上",也有
一圈黑边,再问问你同事,看怎么能优化一下.
我现在能显示n层透明,基本四五层以后,就没什么意义了,另外,我的卡不支持vertex
texture,不知道你手上有没有3d texture的例题. 我以前读一个做caustics的paper,正
好是我学shading language时候老师以前的phd写的,里面用Newton-Raphson 算法来
做折射的ray-tracing,我当时用glsl没做出来(原文用hlsl).
这个东西太依赖硬件,真正的透明要考虑,折射,二次反射,再折射,反射...
必须要有个地方能放vertices的geometry.
难得有对这个感兴趣,以后多切磋切磋. |
|
E**********e 发帖数: 1736 | 19 最近用java 编了个newton raphson 的算法。 就是需要大量的2维矩阵/数组迭代。 原
始数据有150000x50。 发现迭代7,8次得到最优解需要有一分钟。如果用cross
validation ,再加个额外的30次cycle的话,那得要1个小时。 但是用python的numpy
pacakge要快点多。 当然下载所有2维数组计算,乘除, 加减,逆矩阵都是自己写的小
code, 都是用for loop。
请问怎样才能speed up。 |
|
d***s 发帖数: 55 | 20 文件中的字符串格式如下
1993 12 APNUMMATH Jessup, A Case against
1991 8 APNUMMATH Singh & Kulkarni, An Integrated Solution
1990 6 APNUMMATH Joseph & Levine & Liukkonen, Randomized Newton-
Raphson
1982 APP Golomb, Shift Register Sequences, revised edition
需要把作者信息提取出来,就是在“,” 之前用“&" 分隔的字符串,而且前三列的信
息有可能不完整,如最后一行。
请问有什么办法可以处理吗?
考虑用strread,但是有些问题不知如何解决
1:前三列信息不完整
2:第4列如何光提取作者
谢谢!bow~ |
|
b******g 发帖数: 81 | 21 To answer your two questions:
1. 解析方法 is the reason of your maintenance issue. Your formula need to
change when devices change. Numerical analysis seem more promising.
2. My computer science knowledge only tells me Newton-Raphson method -
which is numerical analysis, not symbolic analysis. You might need some
special library to do the symbolic analysis. |
|
h****r 发帖数: 2056 | 22 如果有很多浮点除法运算, Newton–Raphson division就很有帮助了。
也可以事先生成reciprocal表,然后就简单了。 |
|
W**********r 发帖数: 61 | 23 you need reorder the matrix A first to minimize fill-in elements. And
perform symbolical LDU factorization for A. Then you can use Newton-Raphson
algorithm to solve. You can use Matlab, Python, C, whaterever u want.
BTW, remember to use subroutines. |
|
p*******t 发帖数: 501 | 24 【 以下文字转载自 Economics 讨论区 】
发信人: prescient (星辰大海), 信区: Economics
标 题: 问个maximum of simulated estimation问题
发信站: BBS 未名空间站 (Fri Mar 19 20:31:21 2010, 美东)
当在生成好simulator,计算出了对于每个choice的对应的likelihood function的值以
后,下一步就是去找parameter去maximize这个likelihood function的值,无论是用qu
asi-newton还是newton raphson,都要知道函数的first order或者hessian matrix的值
。在这种情况下,应该怎么去找这些的值呢?是不是简单的用倒数定义计算一下在那个
点的各个dimension的斜率就行了呢?
更规范的做法是什么呢? |
|
b*****y 发帖数: 163 | 25 you could solve either of them using non-linear equation solver, such
as Newton-Raphson method. Since the equations have multiple zero crossings,
you need to know the bound of your desired solution and set the initial
guess accordingly. |
|
|
h*********y 发帖数: 135 | 27 为了毕业,构思了一个算法,想和SPICE只是进行算法级的比较,都用Matlab来编程。
但不知哪里有Matlab编好的code, 能实现SPICE的基本算法,主要是
transient analysis,using Newton-Raphson method or integration methods
(e.g. Euler Backward, Trapezoidal method etc.),能处理nonlinear circuit.
我已经用SPICE-like Matlab为关键词在google搜索了半天,没有找到。
好像 CMU EE 有一个 course project to implement the SPICE-like
nonlinear circuit simulator by MATLAB,只有这些线索了。
如果哪位大侠碰巧做过,或者知道哪里有,告知一声,将非常感谢! |
|
k*********g 发帖数: 791 | 28 2分法,更牢靠;
牛顿法快,但这种速度上的优越是trivial的; |
|
|
p*******t 发帖数: 501 | 30 当在生成好simulator,计算出了对于每个choice的对应的likelihood function的值以
后,下一步就是去找parameter去maximize这个likelihood function的值,无论是用qu
asi-newton还是newton raphson,都要知道函数的first order或者hessian matrix的值
。在这种情况下,应该怎么去找这些的值呢?是不是简单的用倒数定义计算一下在那个
点的各个dimension的斜率就行了呢?
更规范的做法是什么呢? |
|
c*******t 发帖数: 953 | 31 这个用Newton-Raphson方法解很快的。 |
|
p*q 发帖数: 312 | 32 for each x=x0, the problem is equivalent to
solving the zero of
F(x0,y0)=0
whose solution is guaranteed by the Implicit Function Theorem.
You can use Newton-Raphson iteration for this
purpose. |
|
j******e 发帖数: 64 | 33 一般情况下我用newton raphson (因为只知道这个),
对于f(x), 当x是scalar或者vector的时候效果很好。
但是当x是matrix的时候,dimensionality很高的时候
就不太行了。请问有什么其他的gradient based method
比较好用, for matrix? Thanks. |
|
d******e 发帖数: 7844 | 34 |f(x)|^s = 0
不就是f(x)=0么?
^T |
|
|
N***m 发帖数: 4460 | 36 绝对值导数未必连续,所以要分区段讨论
阶,也就是
^T
求G(x)'=0的根? |
|
B*********h 发帖数: 800 | 37 ☆─────────────────────────────────────☆
zhuzhu111 (猪猪) 于 (Thu Oct 12 13:42:19 2006) 提到:
how to get the numerical answer of sqrt(37)=6.08276....
(怎么用代数方法解37开平方)
thanks.
☆─────────────────────────────────────☆
emacs (VC) 于 (Thu Oct 12 17:00:52 2006) 提到:
I guess the general method should be Newton-Raphson.
sqrt is a common question being asked in interview, think about sqrt(2) and
sqrt(3).
Another direct method is trial & error, similar to bisection method....
☆─────────────────────────── |
|
c*******d 发帖数: 72 | 38 How do you use taylor expension, since it is already a polynomial?
How about consider solving x^5-31=0 using Newton Raphson? |
|
|
l******e 发帖数: 12192 | 40 10K bonds就算用newton-raphson也用不了一个晚上呀 |
|
k*******d 发帖数: 1340 | 41 我想他只是打个比方,问我除了Newton-Raphson之外有没有什么更快的办法把 |
|
w******g 发帖数: 271 | 42 谢谢各位的指点 ^-^
1. 我指的的implied vol是说:正常的话可以用black scholes带进去一个vol,然后可
以得到bs price of the barrier option。现在我算出了V-V的option price,我想用
newton raphson来求出这个V-Vprice相当与用BS下多大的implied vol来定价。
2.然后在基于这个implied vol,然后带进BS得出BS下的vega/vanna/volga。
这样做可行吗? |
|
a***w 发帖数: 30 | 43 1. Find the autocorrelation of the signal by doing
Fourier Transform, then use such iteration method as
Newton-Raphson to get the FIR coefficients. This can only
get the Minimum phase equivalent. But this is all you can
do with the power spectrum |
|
B******y 发帖数: 9065 | 44 我从IML的帮助文件上看到的Newton-Raphson的方法好麻烦,而且我要实际解决的方程
是多元多次,不是很直接,所以想找个现成的Macro来做。
另外,记得ETS的Package似乎可以做,但我的SAS系统没有买这个Licence,最好能在
STAT里面找到解决方案。 |
|
q********i 发帖数: 795 | 45 一般用的都是maximum likelihood,找最值SAS用newton-raphson 或fisher-scoring.
自己写code做当然可以。不知道有现成的干吗要自己做? |
|
r****y 发帖数: 26819 | 46 这个?
http://rss.acs.unt.edu/Rdoc/library/micEcon/R-ex/maxNR.R
### Name: maxNR
### Title: Newton-Raphson maximisation
### Aliases: maxNR
### Keywords: optimize
### ** Examples
## ML estimation of exponential duration model:
t <- rexp(100, 2)
loglik <- function(theta) sum(log(theta) - theta*t)
## Note the log-likelihood and gradient are summed over observations
gradlik <- function(theta) sum(1/theta - t)
hesslik <- function(theta) -100/theta^2
## Estimate with numeric gradient and Hessian
a <- maxN |
|
w**********y 发帖数: 1691 | 47 I think you didn’t get the spirit of the google interview. Based on the discussion with some friends interviewed by google statistical groups, they want an open mind, quick response ppl with a solid stat background and good skills in R(?)
U did so bad in Logistic regression…When you answered MLE (without any further info), the interviewer already knew your background is very weak…
There is no close form MLE. You need to either use Newton-Raphson or Iterative methods.
Open you mind..if they ask y... 阅读全帖 |
|
s********a 发帖数: 328 | 48 I think you are wrong about the logistic part.
Method for solving Logistic Regression (independent responses) IS MLE, and
the problem is solving the score equation. When you use Fisher Scoring (
close
to Newton-Raphson except that Fisher Scoring uses expected second derivative
instead of real second derivative), it is Equivalent to IRLS in some form.
So
IRLS is a way of solving the MLE score equation. Refer to Nelder, Wedderburn
1972. However, when responses are not independent, MLE is not avai... 阅读全帖 |
|
d******e 发帖数: 7844 | 49 你可能觉得记得IRLS说明你记忆力好。
但你可知道IRLS不过是Newton Raphson在解Logistic Regression上的应用罢了... ... |
|
t***q 发帖数: 418 | 50 以前看过一点点genetic algorithm,说是仿照生物进化的方式进行optimization。后
来又看到一本书上综述了一些numerical optimization,如newton raphson,nelder-
mead等,但是没提genetic algorithm,我肤浅,就上来问一下这个genetic algorithm
算是一种numerical optimization 吗?多谢。 |
|