求多根的紧缩法

Question

我正在尝试实现 deflation method 以在 Julia 上查找多项式的多个根。在deflation方法中，新函数是由实际函数除以x - x_roots[i]生成的，必须找到新生成函数的根。但是 g(x) = g(x) / (x - x_root) 给了我一个堆栈溢出错误，因为它可能生成了一个无限递归关系。如何在每个步骤中生成一个新函数？

function deflation(f::Function, order)
    roots=[]
    n=1
    g(x)=f(x)
    x_root=Muller_method(f,-5,0,5,1e-5,50)
    while n<=order
        x_root=Muller_method(a,-5,0,5,1e-5,50)
        g(x)=g(x)/(x-x_root)
        append!(roots,x_root)
        n=n+1
    end
return (roots)

Answer 1

这样的事情会导致无限递归：

julia> g(x) = x
g (generic function with 1 method)

julia> g(1)
1

julia> g(x) = g(x) / 2
g (generic function with 1 method)

julia> g(1)
ERROR: WhosebugError:
Stacktrace:
 [1] g(::Int64) at ./REPL[3]:1 (repeats 79984 times)

这是因为函数（或方法）定义不像变量赋值那样工作：g(x) 的每个 re-definition 都会覆盖前一个（注意上面的 g 如何只有一个方法）。当方法定义引用自身时，它是递归的，即它在函数被调用时引用它自己的版本。

至于你的紧缩方法，也许你可以定义一个新函数来关闭当前找到的根的向量。考虑以下示例以了解其工作原理：

julia> f(x) = (x-1) * (x-2)
f (generic function with 1 method)

julia> roots = Float64[]
Float64[]


# g is defined once, and accounts for all currently found roots
julia> g(x) = f(x) / reduce(*, x-root for root in roots; init=one(x))
g (generic function with 1 method)


# No roots are identified at the beginning
julia> g(1+eps())  
-2.2204460492503126e-16

julia> g(2+eps())
0.0


# But the results produced by g update as roots are identified
julia> push!(roots, 1.)
1-element Array{Float64,1}:
 1.0

julia> g(1+eps())
-0.9999999999999998

julia> g(2+eps())
0.0

求多根的紧缩法

Deflation Method for Multiple Root Finding

numerical-methods

julia