intro Link to heading

The simplest way to find a root of an equation is by scanning root candidates from an intial value, e.g. $x = x_a$, with increment $\Delta x$ until sign of the function change from previously ${\rm sign}(f(x_a))$, or if possible until $f(x) = 0$ (Rahmansyah & Ahhad, 2013). It is a typical solution in optics if met the physical limit of a resolution (Rom39, 2015).

example Link to heading

  • Suppose that there is a function $$\tag{1} f(x) = x^2 - 104.25x + 425, $$ whose root is to be find.
  • Navigate the mouse on a point to view value of $(x, f(x))$ on following figure of Equation (1).
    Figure 1. Plot of $f(x)$ against $x$.
  • The quadratic form of Equation (1) can not be seen since it is only plotted for $x \in [0, 10]$, which seems to be linear but unfortunately not.
  • Following data are used for Figure 1.
    x
[
0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0,
3.5, 4.0, 4.5, 5.0, 5.5, 6.0, 6.5,
7.0, 7.5, 8.0, 8.5, 9.0, 9.5, 10.0
]

f(x)
[
425.0, 373.125, 321.75, 270.875, 220.5,
170.625, 121.25, 72.375, 24.0, -23.875,
-71.25, -118.125, -164.5, -210.375,
-255.75, -300.625, -345.0, -388.875,
-432.25, -475.125, -517.5
]
  • Code 1. Generate data $x$ and $f(x)$.
    def f(x):
  y1 = x**2
  y2 = -104.25 * x
  y3 = 425
  y = y1 + y2 + y3
  return y

xx = []
yy = []
for ix in range(21):
  x = 0.5 * ix
  xs = "{x:" + f'{x}' + ","
  ys = "y:" + f'{f(x)}' + "},"
  print(xs, ys)

  xx.append(x)
  yy.append(f(x))

print()
print("x")
print(xx)

print()
print("f(x)")
print(yy)
    url https://onecompiler.com/python/3zxfanw68
    This code generates two types of data, in the form of
    • list of dictionary {x: value, y:value},
    • list of $x$ and $f(x)$.

flowchart Link to heading

  • Following flowchart shows how scanning method works. At the end it average two points, where the root lies, as the root.
    flowchart TD B --> I --> P1 --> P2 --> o2a o1a --> P2 o2b --> P3 --> C1 --"N"--> P5 --> o3a C1 --"Y"--> P6 --> o4a o3b --> C2 --"Y"--> o1b C2 --"N"--> O2 --> o5a o4b --> O1 ---> o5b --> E B(["Begin"]) I[/"xa, xb, Δx"/] P1["x = xa"] P2["s1 = sign(f(x))"] P3["s2 = sign(f(x+Δx))"] P5["x = x + Δx"] P6["root = x + Δx/2"] C1{"s1 · s2 < 0?"} C2{"x ≤ xb?"} O1[/"root"/] O2[/"no root"/] E(["End"]) o1a(("1")); o1b(("1")) o2a(("2")); o2b(("2")) o3a(("3")); o3b(("3")) o4a(("4")); o4b(("4")) o5a(("5")); o5b(("5")) classDef style1 fill:none, color:inherit classDef style2 fill:#888, color:#fff class B,E,I,P1,P2,P3,P4,P5,P6,C1,C2,O1,O2 style1 class o1a,o1b,o1c,o2a,o2b,o3a,o3b,o4a,o4b,o5a,o5b style2 linkStyle default stroke:#8a8
    Figure 2. Flowchart for finding roots of $f(x)$.

algorithm Link to heading

  1. Start.
  2. Define $x_a$, $x_b$, $\Delta x$.
  3. Initiate $x = x_a$.
  4. Caculate $s_1 = {\rm sign}(f(x))$.
  5. Caculate $s_2 = {\rm sign}(f(x + \Delta x))$.
  6. If $s_1 s_2 < 0$ go to to Step 11.
  7. Advance $x$ with $\Delta x$.
  8. If $x \le x_b$ go to Step 4.
  9. Display no root found.
  10. Go to Step 13.
  11. Calculate ${\rm root} = x + \frac12 \Delta x$.
  12. Display root value.
  13. End.

code Link to heading

  • Code 2. Scanning method to find a root of $f(x)$.
    console.log("Scanning method");

// round to n digit
function roundn(x, n) {
  let mag = Math.pow(10, n);
  let y = Math.round(x * mag) / mag;
  return y;
}


// define a Function
function f(x) {
  let y = x*x - 104.25*x + 425;
  return y;
}

// define range and step
let xa = 0;
let xb = 10;
let dx = 0.1;
let x = xa;
let sx = Math.sign(f(x));
let sxnew;

console.log("x\tf(x)");
while(x <= xb) {
  sxnew = sx;
  sx = Math.sign(f(x))

  let y = f(x);

  let xx = roundn(x, 3);
  let yy = roundn(y, 3);
  console.log(xx, '\t', yy);

  if(sx * sxnew <= 0) {
    break;
  }

  x += dx;
  sxnew = Math.sign(f(x));
}
console.log();

let x1 = roundn(x-dx, 3);
let x2 = roundn(x, 3);
console.log("Root is located between");
console.log(x1, '\t', x2);
    url https://onecompiler.com/javascript/3zxfe9c7m.
  • Result
    $ node scanning_method.js
x       f(x)
0        425
0.1      414.585
0.2      404.19
0.3      393.815
0.4      383.46
0.5      373.125
0.6      362.81
0.7      352.515
0.8      342.24
0.9      331.985
1        321.75
1.1      311.535
1.2      301.34
1.3      291.165
1.4      281.01
1.5      270.875
1.6      260.76
1.7      250.665
1.8      240.59
1.9      230.535
2        220.5
2.1      210.485
2.2      200.49
2.3      190.515
2.4      180.56
2.5      170.625
2.6      160.71
2.7      150.815
2.8      140.94
2.9      131.085
3        121.25
3.1      111.435
3.2      101.64
3.3      91.865
3.4      82.11
3.5      72.375
3.6      62.66
3.7      52.965
3.8      43.29
3.9      33.635
4        24
4.1      14.385
4.2      4.79
4.3      -4.785

Root is located between
4.2      4.3
  • Discussion
    • It finds $4.2 < r_1 < 4.3$, whose value is supposed to be $4.25$.
    • The root can be obtained by averaging the values bracketing it, i.e. $\frac12(4.2 + 4.3) = 4.25$, which is true accidentally for this case.
    • Previous step will not work for general case, e.g. $f(x) = x^2 - 104.125x + 412.5$.

challenges Link to heading

  • Write code to implement the algorithm or the flowchart using Python. You can modify the given JavaScript code.
  • Is there any relation between increment of $x$, $\Delta x$ with the accuracy of the result? Explain using examples.

refs Link to heading