You will definitely understand what iteration means.

Editor's Note

There is an interesting phenomenon in science communication, that is, the more basic and difficult the knowledge is, the richer and more popular science books there are. An obvious example is that popular science books on mathematics and physics far exceed those on other subjects. The popular interpretations of famous conjectures and paradoxes in mathematics, relativity and quantum mechanics in physics can be described as numerous. This at least shows that difficult knowledge can also have easy-to-understand entry points. A good popular science writer can reduce the difficulty of readers' understanding through the author's efforts in explanation. This article wants to start from elementary mathematics and talk in depth about "iteration", a very important concept in mathematical knowledge.

Written by Ding Jiu (Professor of Mathematics at the University of Southern Mississippi)

The word iteration may be unfamiliar to some people, but it has a long history in mathematics. About 3,500 years ago, the ancient Babylonians came up with a clever way to approximate the square root of a given positive number A one after another. In today's standard terms, it is to use the well-known Newton iteration method to solve the equation x^2 – A = 0. Today, iteration has left an active presence in almost all areas of the mathematical world, and various iteration methods for solving equations are the tools that computational mathematicians and engineers never leave.

To illustrate what iteration is, let's take out an ideal calculator with an assumed error of zero, enter a number, say 0.5, and then press the square key labeled "x^2". The result will appear on the small screen: 0.25. If you press the square key again, the result will be 0.0625. Press it again and again, and you will get 0.00390625. If you press it again and again, a series of numbers will appear, starting with the "initial number" 0.5:

0.5, 0.25, 0.0625, 0.00390625, 0.0000152587890625, …

Although we may lose patience and don’t want to press the button again after calculating these steps, we can at least know from the changing trends of the above numbers that these smaller and smaller numbers will eventually tend to 0.

This calculation is indeed simple enough that even kindergarten children can do it. Even if they throw away their calculators, elementary school students can use paper and pen to calculate such "squares" one by one. If expressed using the mathematical concepts learned in junior high school, the square key on the calculator represents the function "x squared".

The first number 0.5 in the above series is an initial value we chose, the second number 0.25 is the function value of the x-squared function when x = 0.5, the third number 0.0625 is the function value of the x-squared function when x = 0.25, and the fourth number 0.00390625 is the function value of the x-squared function when x = 0.0625, and the fifth number 0.0000152587890625 is the function value of the x-squared function when x = 0.00390625, and so on.

If we regard the x-squared function as a "black box", then when we input the value of x, the black box will output the function value x2. The above calculator operation is actually to select an initial value and input it into the black box, and then input the function value spit out by the black box into the same black box again and again, over and over again, until infinity. The whole process of this "black box operation" is called function iteration in mathematics, or iteration for short.

In general, suppose we have a function y = f(x) defined on some interval of real numbers, which maps the domain interval into itself - that is, the independent variable x and the dependent variable y of this function both take values ​​in the domain.

When considering iteration, we will inevitably encounter the two important terms "fixed point" and "periodic point". If there is a point x* in the domain of function f that satisfies the equation f(x*) = x*, that is, the iterative result of x* under f is still x*, then this point is called a fixed point of function f.

The algebraic meaning of a fixed point is x = x*, a solution to the equation f(x) = x, and the geometric meaning is the coordinates of the intersection of the graph of the function f in the xy-Cartesian coordinate system on the plane and the diagonal y = x of the coordinate system. Because this intersection point is both on the graph of the function f and on the diagonal of the coordinate system, its two Cartesian coordinates (x*, y*) simultaneously satisfy the two equations y* = f(x*) and y* = x*.

From the above, we can see that when the initial point is a periodic point, the given function will return to the initial point for the first time after iterating to a certain step, and then repeat the cycle indefinitely, just like a strong student running around the school's oval track every morning. When the initial point is not a periodic point, all the iterative points starting from this point will naturally never return to the initial point. Since it will never return to the initial point, will the final state of these iterative points be unpredictable?

There is another situation where the initial point is neither a periodic point nor a final periodic point, that is, all the iteration points corresponding to it are different from each other, but we can still predict the final direction of the iterative point sequence, for example, the sequence eventually converges to a fixed number, or gets closer and closer to a fixed periodic orbit, or diverges to positive infinity, or diverges to negative infinity, or the sequence of its absolute value diverges to positive infinity. For the analysis and solution of predictability under these different conditions, the mathematical tools of elementary algebra are not enough, and some knowledge of elementary differential calculus is required. This is why higher mathematics is a very useful subject. Specifically, the "mean value theorem" or "monotone convergence theorem" in differential calculus is often the mathematical backing of this analytical process. Since this article is a "brief explanation of iteration", I will still use simple language to explain the application of one of the theorems later, but it will help to understand if it is supplemented by the visual effect of images. To this end, we first introduce the "pictorial representation" of function iteration, which is clearer to the eyes, compared with the aforementioned "algebraic representation" that relies on function assignment.

When checking the final direction of the iterative point sequence, if it is too time-consuming to calculate the function value again and again by hand or with a calculator to obtain each iterative point, we can also use the graph of the function to do the equivalent of the algebraic method, as long as the graph curve can be drawn accurately enough. This geometric method allows us to move forward rapidly from the initial point along a shortcut path that turns alternately up and down and left and right, so that we can intuitively observe the "motion trajectory" of the iterative point sequence, and then easily see the final destination of the track.

More generally, the above-mentioned "graph iteration method" can quickly prove that for a linear function f(x) = ax + b, as long as the absolute value of the coefficient a of the x term is strictly less than 1, that is, |a| < 1, then the sequence of iteration points starting from any real number will eventually tend to the only fixed point x* = b/(1-a) of f, and if |a| > 1, then the sequence of iteration points starting from any real number not equal to b/(1-a) will eventually diverge to infinity. In contrast, the analytical proof of these two facts takes a little more time.

For the above linear function whose straight line graph is quite flat and whose absolute value of slope is less than 1, the fixed point x* = b/(1-a) attracts the points around it like a beautiful girl attracts the boys around it, so all the iterative point orbits starting from these nearby points will eventually tend to it, so this fixed point is figuratively called attractive. In fact, the fixed point x* not only attracts all the points near it, but also attracts all the points on the real axis, so it is a globally attractive fixed point.

On the other hand, when the straight-line graph of a linear function looks quite steep, so that the absolute value of its slope is greater than 1, since the fixed point x* = b/(1-a) "repels" the points around it that are different from it, just like a warmongering away from the pacifists around him, all the iterative point sequences starting from these points will eventually "stay away" from it and are unwilling to approach it. This fixed point is called repelling, and further, it is globally repelling.

From the above, we can see that for any linear function that satisfies the condition |a| ≠ 1, its only fixed point is either globally attractive or globally repelling. A direct inference is that the function has no other periodic points. The reason is simple, because if there is a periodic point with a period greater than 1, for example, its period is three, then all iterative points starting from this periodic point always "take turns" among the three points of the same period-3 orbit. How can they tend to a fixed point or diverge to infinity?

After reading this, I believe that readers will not only understand the mathematics, but will also apply the knowledge they have gained to the two remaining linear functions f(x) = x + b and g(x) = -x + b that do not meet the above conditions, and see where their respective iterative trajectories will eventually lead to.

Once again, both of the above nonlinear functions show the normal behavior of their iteration point orbits: for all initial points, the final direction of the iteration point sequence is predictable, and, except for the only fixed point and two periodic points with a period of 2, they have no other periodic points. In the next popular science article, I will discuss those simple functions that have both fixed points and periodic points with a period of 2 or higher, and trace some of their historical connections with natural science.

So far, I have not formally used advanced mathematics. I have only used elementary mathematics to discuss iteration problems and introduce basic concepts. Some readers with doctoral, master's or even bachelor's degrees in science and engineering may feel that "the content is too shallow". However, as Paul Halmos (1916-2006), a master of mathematical writing and presentation and a Hungarian-American mathematician, has always emphasized during his lifetime, the more elementary the public report is, the more it can capture people's hearts. Now, I will try to use a quadratic polynomial to demonstrate a wonderful use of elementary differential calculus in function iteration. Even if the reader has never been exposed to calculus, it doesn't matter, because I know that she or he at least knows middle school algebra and has a certain geometric intuition. In addition, I have promised to explain mathematics in simple language before, otherwise I will be ashamed of the five words "you will definitely understand" promised in the title.

The function I gave is f(x) = 2x(1-x), but its domain is restricted to the closed interval [0, 1]. Obviously, the graph of f is a parabola passing through two points (0, 0) and (1, 0), opening downward, with the axis of symmetry x = 1/2 and the highest point at (1/2, 1/2). It is located in the unit square on the coordinate plane, so the range of f is [0, 1/2], so f maps [0, 1] into itself. Therefore, starting from any point in the domain interval, we can iterate f infinitely.

At this point, we have to jump from elementary mathematics to advanced mathematics, and what we need is the "monotone convergence theorem" mentioned above: a monotone bounded sequence must have a limit. Its proof requires the "completeness axiom" about all real numbers. This axiom is the starting point of the "Advanced Calculus" textbook in the United States, and belongs to the "Mathematical Analysis" course of the Department of Mathematics in China. But we can use the following visual example to help understand the above theorem: Imagine a team of tens of thousands of soldiers walking forward, which is equivalent to a monotonically increasing sequence. If there is no obstacle in front of them, the team of soldiers will continue to walk far away. However, if there is an insurmountable wall in front of them, then the group of soldiers who keep moving forward can only gather at the foot of the wall in the end, which is equivalent to an increasing sequence with an upper bound that must converge to a point.

In fact, we proved a general assertion above. We will give it as a final gift for this article:

Proposition . If a sequence of iteration points of a function f converges to x*, and f is continuous in x*, then x* is a fixed point of f.

"Function iteration" is a mathematical topic with rich content and wide applications. In view of the length of this article, I only popularized some orderly iterative processes that "can foresee the future". However, from order to disorder, that is, chaos, more magical scenes are still ahead. Explaining the mathematical operations behind it in simple elementary language will be the guiding ideology of continuing to talk about iteration.

Written on Monday, March 27, 2023

Hattiesburg Summer House

This article is supported by the Science Popularization China Starry Sky Project

Produced by: China Association for Science and Technology Department of Science Popularization

Producer: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.