根据参考重新创建混合平分和假位置算法

Question

我正在尝试从下面的网站重新创建一个混合二分算法（算法 3）（link 带您到我正在引用的算法的确切部分）

https://www.mdpi.com/2227-7390/7/11/1118/htm#sec3-mathematics-07-01118

我不太确定我目前输入的内容是否正确，我被困在网站算法的第 29 行，我不确定它是什么意思，尤其是交叉符号。

到目前为止的代码

/* Math function to test on */
function fn(x) {
    //return x * x - x - 2; /* root for this is x = 2 */
    return x*x*x-2; /* root for this is x = (2)^(1/3) */
}

function blendedMethod(a, b, eps, maxIterations, fn) {
    let k = 0,
        r, fa, fb, ba, bb, eps_a;

    do {
        let m = (a + b) * .5;
        let eps_m = Math.abs(fn(m));

        let fn_a = fn(a),
            fn_r;
        let s = a - ((fn_a * (b - a)) / (fn(b) - fn_a));
        let eps_s = Math.abs(fn(s));

        if (eps_m < eps_s) {
            r = m;
            fn_r = fn(r);
            eps_a = eps_m;
            if (fn_a * fn_r < 0) {
                ba = a;
                bb = r;
            } else {
                ba = r;
                bb = b;
            }

        } else {
            r = s;
            fn_r = fn(r)
            eps_a = eps_s;
            if (fn_a * fn_r < 0) {
                fa = a;
                fb = r;
            } else {
                fa = r;
                fb = b;
            }

            /* line 29 here! */
            /* [a, b] = [ba, bb] ∩ [fa, fb] */
            /* either fa,fb or ba,bb haven't yet been defined */
            /* so this will fail with NaN */
            a = Math.max(ba, fa);
            b = Math.min(bb, fb);
        }

        r = r;
        eps_a = Math.abs(fn_r)
        k = k + 1;

    } while (Math.abs(fn(r)) > eps || k < maxIterations)

    /* think this is the root to return*/
    return r;
}

console.log(blendedMethod(1,4,0.00001,1000,fn));

编辑：修复了一些错误，唯一的问题是该算法在条件语句中定义了 fa,fb 或 ba,bb 而没有定义其他两个。因此，当涉及到下面的这些计算时，它会因 NaN 而失败，并在下一次迭代中搞砸。 a = Math.max(ba,fa); b = Math.min(bb,fb);

Answer 1

你说得对，这个交集没有意义。在每一步骤中只定义了一个子间隔。由于所有间隔都是连续的嵌套子集，因此未在当前循环中设置的间隔的陈旧旧值仍然是新间隔的超集。新的间隔可以直接在每个分支中设置。或者方法选择分支可以与区间选择分支完全分开。

实现不是很经济，因为在只需要 2 次评估的情况下计算了 6 个或更多函数值。这个想法是时间复杂度的主导因素是函数评估，因此任何求根算法的有效度量是函数评估的数量。为此，始终保持点和函数值成对，成对生成它们，成对分配它们。

let fn_a =f(a), fn_b=f(b)
do {
    let m = (a + b) * .5;
    let fm = f(m);
    let s = a - (fn_a * (b - a)) / (fn_b - fn_a)
    let fn_s = f(s);
    let c,fn_c; 
    // method selection
    if(Math.abs(fn_m) < Math.abs(fn_s)) {
        c = m; fn_c = fn_m;
    } else {
        c = s; fn_c = fn_s;
    }
    // sub-interval selection
    if( fn_a*fn_c > 0 ) {
        a = c; fn_a = fn_c;
    } else {
        b = c; fn_b = fn_c; 
    }
while( Math.abs(b-a) > eps );

也不清楚混合方法以何种方式避免或减轻基础算法的缺点。为了避免 regula falsi 方法的停滞（偏离割线步骤），最好引入一个停滞计数器并在 1 或 2 个停滞步骤后应用二分步骤。或者只是简单地交替错误位置和二分步骤。两种变体都确保缩短包围间隔。

一方面，对正则假方法的已知有效修改是像 Illinois variant that add a weight factor to the function values, thus shifting the root approximation towards the repeated, stalled interval bound. On the other hand there are more general algorithms that combine the ideas of the bracketing interval and reverse interpolation like the Dekker and Brent methods.

这样的变体

根据参考重新创建混合平分和假位置算法

Recreating Blended Bisection and False Position algorithm from reference

javascript

numerical-methods

bisection