Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 36 ยท Projects and Practice

Project: A Zero Finder Based on the Argument Principle

Build a program that counts zeros in a square with the argument principle, subdivides until each zero is isolated, and polishes them with Newton's method.

Newton's method finds one root near a starting guess, but it cannot tell you how many roots exist, or whether you found them all. The argument principle can: it counts the zeros inside any closed curve by following the image of the curve around the origin. In this project you combine the two ideas into an algorithm that finds all zeros of an analytic function in a rectangle, with a certificate that none was missed.

The plan has four stages:

  1. Count the zeros in a square by the winding number of f(C) around 0.
  2. Subdivide squares that contain more than one zero into four quarters.
  3. Isolate and polish: when a square contains exactly one zero, run Newton's method from its center.
  4. Verify against known roots and by checking the residuals |f(z)|.

The theory comes from the argument principle and winding numbers: if f is analytic on and inside the square, and has no zeros on its boundary, then

Text
number of zeros inside = (1 / 2ฯ€i) โˆฎ f'/f dz = winding number of f(C) around 0

Stage 1: counting by winding

Sample the four sides of the square, evaluate f at the sample points, and add up the angle changes between successive values, arg( f(z_(k+1)) / f(z_k) ). Each step is taken in the principal range (-ฯ€, ฯ€], which is correct as long as the image moves by less than half a turn between samples. Dividing the total by 2ฯ€ gives the winding number.

Failure modes you must detect:

  • A zero on or very near the boundary makes the image pass near 0, so f changes direction wildly between samples. We reject a square if any single step is larger than 1.5 radians, and subdivide it (the new boundaries lie elsewhere).
  • A pole inside the square would count as -1. For this project, f must be analytic (an entire function or a polynomial) on the region.
  • Too few samples. For a function that oscillates, use more samples per side.

Stage 2: subdividing

If a square contains k zeros, k โ‰ฅ 2, split it into four squares of half the side. Each new count is again an integer, and the four counts add up to k (zeros on the shared edges would break this, which is why we start from a slightly off-center square with an irregular center such as 0.013 + 0.007i: zeros on the dividing lines are then very unlikely).

flowchart TD
    A["Square with k zeros"] --> B{"k = 0?"}
    B -->|yes| C["Discard"]
    B -->|no| D{"k = 1?"}
    D -->|yes| E["Newton from the center"]
    E --> F{"Converged inside the square?"}
    F -->|yes| G["Record the zero"]
    F -->|no| H["Subdivide"]
    D -->|no| H
    H --> A

The search: count, discard, polish or split.

Stage 3: Newton polishing

Newton's iteration z โ† z - f(z)/f'(z) converges quadratically near a simple zero, but can wander off if started badly. Because the argument principle has told us exactly one zero is in the square, we try Newton from the center and accept the result only if it lands inside the same square; otherwise we simply subdivide further, which brings the starting point closer to the zero.

If the squares become tiny (below 10โปโท) and still contain k โ‰ฅ 2 zeros, you have found a multiple zero (or two extremely close zeros). We record the center and its multiplicity k.

Try it: the counter

First the counter alone. For p(z) = zโต + 3z + 1 we count the zeros in four squares. From the Rouchรฉ analysis you know that there are 5 zeros in |z| < 2 and one in |z| < 1; the square of half-side 3 contains all of them. The program prints the counts and, at the end, the exact roots from NumPy for comparison.

Python Counting zeros in squares

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second square has half-side 0.9: its corners are at distance about 1.27, and the real root -0.332 lies inside, while the other roots (with moduli about 1.26 and 1.37) are at coordinates like 1.005 ยฑ 0.937i, outside the square. The count is 1. The third square is too small to reach any root and gives 0.

Now the complete algorithm. The function find_zeros is recursive: it counts, discards or subdivides, and calls Newton on squares with exactly one zero. We apply it to the quintic p, compare with np.roots, and then to a non-polynomial function, f(z) = sin z - z/2, on a square of half-side 8, printing each zero together with the residual |f(z)| as evidence.

Python Find all zeros by subdivision

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the second function the zeros are 0, a symmetric pair on the real axis near ยฑ1.8955, and further complex pairs. The residuals near 1e-15 or smaller confirm that each reported number really is a zero. The counting step also tells you the total number of zeros inside the square, so if the list were shorter than the count, you would know Newton or subdivision had missed one.

Extensions

  1. Rectangles. Use different half-widths hx, hy for the sides to search wide, flat regions.
  2. Poles. For a meromorphic function the winding number is N - P. Count poles separately, by applying the counter to 1/f, and find the zeros and poles together.
  3. Multiple roots. Note how (z - 1)ยณ is reported as one zero of multiplicity 3 once the squares get tiny.
  4. Contour integral version. Replace the winding count by (1/2ฯ€i) โˆฎ f'/f dz computed with a trapezoid rule, and compare the cost and reliability of the two counters.
  5. Visual output. Plot the squares that were examined: you will see that the algorithm zooms in on each zero as a small cluster of boxes.

If the algorithm seems to hang or returns an unresolved multiple zero, a zero is probably on a dividing line. Shift the starting center by an irrational-looking amount such as 0.0137, and try again.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the zero finder, what does the winding number of f(C) around 0 equal for analytic f?

    By the argument principle, the winding number equals N - P, and P = 0 for analytic f.
  2. 2. Why do we reject a square if one angle step is larger than about 1.5 radians?

    A zero near the boundary makes the image pass close to 0, so steps can jump by about ฯ€ and the sum of angles may be wrong.
  3. 3. A square contains exactly one zero. What is the safe way to use Newton's method?

    The argument principle tells us exactly one zero is in the square; if Newton lands elsewhere, subdivide and try again.
  4. 4. If tiny squares still report k โ‰ฅ 2 zeros, we have probably found

    Squares that cannot separate the zeros indicate a zero of multiplicity k (or extremely close zeros).

Summary

  • The argument principle gives an integer count of zeros in any square, from the winding number of the image curve.
  • Subdividing squares until each has one zero, then polishing with Newton, finds all zeros with a certificate.
  • Reject unreliable counts (large angle steps) and subdivide again.
  • Verify with residuals |f(z)| and, for polynomials, with np.roots.
  • You have now used the whole toolbox of the course: contours, winding numbers, Cauchy's theorems and the argument principle.

Back to the track page: Complex Analysis