J:牛顿法的默示副词 [英] J: Tacit adverb of Newton's method

问题描述

我在布伦特方法的'addons/math/misc/brent.ijs'实现中发现它是副词.我也想将牛顿的方法构建为副词，但比构建隐式动词要困难得多.

I've found in 'addons/math/misc/brent.ijs' implementation of Brent's method as an adverb. I would like to build a Newton's method as an adverb too but it's much harder than building tacit verbs.

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

Here is a explicit version of Newton's iteration:

   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^:_'

什么是默认的?

推荐答案

TL; DR

每个评论，一个简短的答案；与原始显式newton_i和newton对应的默认值分别是:

TL;DR

Per the comments, a short answer; the tacit equivalent to the original, explicit newton_i and newton are, respectively:

n_i =: d.0 1 (%/@:) (]`-`) (`:6) 
newton =: n_i (^:_)

通常可以在这里的关键见解是(a)一个函数与其自身的零位导数"相同，并且(b)由于J，我们可以同时计算函数在J中的零位导数"和一阶导数.语言的数组性质.其余的只是集邮.

The key insights here are that (a) that a function is identical to its own "zeroeth derivative", and that (b) we can calculate the "zeroeth" and first derivative of a function in J simultaneously, thanks to the language's array-oriented nature. The rest is mere stamp-collecting.

在理想世界中，给定功能f，我们想产生像(] - f % f d. 1)这样的动词串.问题在于，J中的隐式状语编程使我们产生一个动词，该动词只一次提及输入函数(f).

In an ideal world, given a function f, we'd like to produce a verb train like (] - f % f d. 1). The problem is that tacit adverbial programming in J constrains us to produce a verb which mentions the input function (f) once and only once.

因此，我们使用了一个偷偷摸摸的技巧:我们同时计算的两个导数:零"导数(这是一个恒等函数)和一阶导数.

So, instead, we use a sneaky trick: we calculate two derivatives of f at the same time: the "zeroth" derivative (which is an identity function) and the first derivative.

   load 'trig'
   sin              NB. Sine function (special case of the "circle functions", o.)
1&o.

   sin d. 1 f.      NB. First derivative of sine, sin'.
2&o.

   sin d. 0 f.      NB. "Zeroeth" derivative of sine, i.e. sine.
1&o."0

   sin d. 0 1 f.    NB.  Both, resulting in two outputs.
(1&o. , 2&o.)"0

   znfd =: d. 0 1   NB. Packaged up as a re-usable name.
   sin znfd f.
(1&o. , 2&o.)"0

然后我们只需在它们之间插入一个分隔线:

Then we simply insert a division between them:

   dh =: znfd (%/@) NB. Quotient of first-derivative over 0th-derivattive

   sin dh
%/@(sin d.0 1)

   sin dh f.
%/@((1&o. , 2&o.)"0)

   sin dh 1p1  NB. 0
_1.22465e_16

   sin 1p1     NB. sin(pi) = 0
1.22465e_16
   sin d. 1 ] 1p1  NB. sin'(pi) = -1
_1
   sin dh 1p1  NB. sin(pi)/sin'(pi) = 0/-1 = 0
_1.22465e_16

(%/@)位于znfd的右侧，因为J中的隐式副词编程是LIFO(即从左到右，其中正常" J是从右到左).

The (%/@) comes to the right of the znfd because tacit adverbial programming in J is LIFO (i.e. left-to-right, where as "normal" J is right-to-left).

正如我所说，剩下的代码只是集邮，使用标准工具构建动词火车，该火车从原始输入中减去该商:

As I said, the remaining code is mere stamp collecting, using the standard tools to construct a verb-train which subtracts this quotient from the original input:

   ssub  =: (]`-`) (`:6)     NB. x - f(x)

   +: ssub                   NB. x - double(x)
] - +:
   -: ssub                   NB. x - halve(x)
] - -:

   -: ssub 16                NB. 16 - halve(16)
8
   +: ssub 16                NB. 16 - double(16)
_16
   *: ssub 16                NB. 16 - square(16)
_240
   %: ssub 16                NB. 16 - sqrt(16)
12

因此:

    n_i =: znfd ssub         NB. x - f'(x)/f(x)

最后，使用 ^:_的应用到固定点"功能 ，我们有:

And, finally, using "apply until fixed point" feature of ^:_, we have:

    newton =: n_i (^:_)

Voila.

这篇关于J:牛顿法的默示副词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！