The man in the box is missing

kw: book reviews, nonfiction, artificial intelligence, algorithms, surveillance

Google is spying on you. So are Facebook, Twitter, and nearly every web site that you use. Never mind the NSA and the CIA and their ilk (another 15 of them, just in the US!). Here's the rub, though. Amongst the many "likes" and other clicks you make daily; and if you like to write, as I do, amongst hundreds to thousands of words you generate; and amongst the photos and links and other "stuff" you might send out into the ether, daily: Is there someone who can digest it all, winnow it, and produce a comprehensive picture of just who you are?

Not a someone, but a something. Namely, an algorithm; strictly speaking, in each such case (Google, etc.) a veritable forest of algorithms that analyze (gather, group, parse, summarize, mathematically rotate in n-space) all the data we generate for them and give to them.

What is an algorithm? It is a recipe. A cookbook is filled with descriptions of algorithms that a cook will follow to produce this or that dish. A computer program contains, in specialized language, recipes that the computer will follow to "cook" data to produce "dishes".

Early electronic computers were used to produce tables for predicting the flight of a mortar shell, which made it easier to aim accurately. The ballistics table was the "dish". These days, the "dish" is more likely to be something that an advertiser will use to influence you to buy something, or a political party will use to influence how you vote, or a "nonprofit" group will use to gain your support. Does any of that worry you?

David Sumpter, a professor and applied mathematician, worried about these things, and he had the tools and the standing to do some digging around. How much of this is true, and how effective are these techniques? His intellectual and mathematical journey and the conclusions he drew are described in Outnumbered: From Facebook and Google to fake news and filter-bubbles — the Algorithms that control our lives.

He describes what he found, and, to cut to the chase, while the power of the algorithms is amazing, the results are slender. The algorithms are not much danger. Even the more powerful algorithms we can expect in the next generation or two are unlikely to be much danger, in and of themselves. The true danger is that powerful people believe their results, even when it can be shown that the best algorithm is no more accurate than the informed opinion of an intelligent expert.

Why is that so? I must back up here: we in the computer field rather loosely talk about "putting the intelligence" into a program. But that does not make the program "artificially intelligent." In every case, we embody some aspect of human intelligence in an algorithm that a computer can perform very fast. For example, I know how to perform a Fourier Series analysis, to analyze the frequencies in some kind of signal, such as a snippet of a song or a portion of a digital photo. It takes a lot of calculations (millions of them to analyze 1/100th of a second of audio). Computers can do those calculations so fast that audio spectrum analyzers that run on a smart phone can produce a sound spectrum  in real time (I use one to "see" bird songs). No computer "invented" the Fourier Series analysis, a human did. So, why is it that a knowledgeable person can still outperform a mechanical "understanding" of social cues? Two things: (1) The human mind works in ways that nobody yet has a clue about; and (2) We instantly recognize similarities, which computers don't do well, while computers instantly find tiny differences, which we have a hard time at. (Just by-the-bye, I made a 40-year career exploiting the synergy of mind and machine.)

So the problem with letting algorithms "do stuff" is that they don't do it any better than we do. This isn't likely to change much in the next few decades. Further, because the data used to "train" the "deep learning" systems in use today (such as for Google Translate) contain lots of human bias, those biases will be reflected in the results produced by the systems. For example, suppose we use the trillions of sentences in Twitter to train a natural-language understanding-and-response system. Is it possible to pre-filter out the trolls, the "hate speech", the bigotry and sexism and this-and-that-phobic utterances? If we don't, the trained system will exhibit the biases and bigotry of the data that went into it. This is a malicious example of "garbage in garbage out."

For most of us, we experience the results of all that spying and calculation in the ads we see online, and even the kinds of results we get from doing a search. I have learned to search for anything meaningful in an Incognito (or inPrivate) window. My wife and I had this experience: a handle on an end table was getting loose. We found that the threads on its screws were getting stripped, probably from being bumped rather hard at some point. We looked online for handle hardware, from various sources. We found something we liked, and ordered handles enough to fix both end tables. Guess what? I got lots of ads for handles, in Google, Facebook, and nearly everywhere else that had banner ads! I got them for a month. I thought of writing to Google, "Dudes, I bought a set of handles the same day. Y'all are way, way too late!" But what's the use? Until they think to check online purchase information, they can't know it.

I did three little experiments. First, in a Firefox Private window, I went to www.google.com and began typing "how to peel", and then I recorded the auto-complete results:

• a mango
• butternut squash
• garlic
• pearl onions
• a kiwi
• an orange
• ginger eggs
• a banana
• tomatoes

When I did the same thing, logged into my Gmail account (on another tab), the first result was

• a pineapple

followed by the next 8 items above, from "mango" to "banana". Yesterday, I happened to look up YouTube videos about peeling pineapples. No surprise there.

Then I did the same process, starting with "best books for". The auto-complete list was:

• young adults
• teens
• 3 year olds
• men
• toddlers
• 2 year olds
• 4 year olds
• men 2018
• babies

When I did the same thing "as myself", I got exactly the same list. Did you notice, as I did, the glaring omission of women or girls? That is funny, because my wife and I use the same account credentials and the same email accounts. Maybe females don't search online for books (but I'd be surprised...)

Then again, in private, I entered the search term "genealogical". The results list, first page, was:

• the definition
• genealogical.com
• www.dictionary.com/browse/genealogical
• www.thefreedictionary.com/genealogical
• delgensoc.org
• [2 "top stories"]
• "How genealogical sleuthing led to suspect in Warwicks joggers death" - The Providence Journal
• "Genealogical Society learns about creating digital family histories" - Community Journal
• www.archive.gov/research/alic/reference/genealogy.html
• www.archive.gov/research/genealogy
• www.ngsgenealogy.org
• - not detailed
• www.newyorkfamilyhistory.org

The page also included a photo-ad from ancestry.com for its software and service. After that, logged in again as myself, I entered "genealogical", with these results:

• [3 ads]
• www.myheritage.com/Genealogy
• www.geneticsdigest.com
• www.genealogy.com
• the definition
• genealogical.com
• en.wikipedia.org/wiki/Genealogy

and then the rest as above, from www.dictionary.com through the rest except the newyorkfamilyhistory one. The photo-ad for ancestry.com was the same. Are these differences significant? Not usually.

The book ends on a slightly melancholy note. Dr. Sumpter found he'd become something of a wet blanket at parties, because when people started grumbling about what Google and FB and others were doing, he had the real info, which was less flashy. Sure, if an algorithm can sell 0.1% more fribble widgets, and if the market for fribble widgets is usually a few million, that 0.1% could be a few thousand more of them being sold. But people want something to be a little scared about. There's nothing scary about fractions of a percent. Even filter-bubbles turn out to be a toothless bugaboo. Nothing pops a bubble quicker than outside info from a source that isn't trying to change your mind, but is just presenting the facts as seen from elsewhere. All of us have more than one source of information. Sooner or later, any bubble we've been in will come up against "real life" from another angle.

I have to tell this story, a bittersweet one. In 1980 the first Chinese students were allowed to come to American colleges. A few years later some Chinese nationals who had relatives in the US were allowed to visit them. A Chinese friend of ours, a man in his seventies, was visited by his sister. For a few days, she said a lot about how good the Chinese system was, how Communism was better than Democracy, and so forth. I understand, of course, that in China, speaking any other way could get a person in trouble. Our friend and his wife didn't argue with her. They just took her along the next time they went to the grocery store, at a Walmart. The dear lady saw the rows and rows of fresh produce, the bread, and everything else, and began to cry. I must have been rather hard for her to return to China a few weeks later.

Will artificial intelligence make the algorithms work any better? Many of them are already being called AI, but it is hyped. It is just the rapid application of human intelligence. Anyway, we may be in a waning cycle of hype about artificial intelligence. Computer software is in no danger of replacing us any time soon. Before there were electronic computers, people had cleverly devised mechanical aids of many kinds to speed up the processes we needed. Napier's Bones were devised in the 1600's to simplify multiplication and division. Slide rules (I still have a few) preceded the pocket calculator by a few generations, and could also perform trigonometric and logarithmic calculations. I have an old copy of Machinery's Handbook, which contains "log tables", in case you need greater accuracy than a slide rule can produce. The first mainframe computer I used was no more accurate than the table of logarithms, it was just faster.

So far, all these things are tools. The algorithms used on our social data are tools used by marketers and propagandists. If we keep ourselves aware of these facts, we'll have better sales resistance, and "fake news" resistance. And we'll also be able to turn the tools back on themselves to our own benefit: sometimes the ads they show us are for something that we really can use, and we didn't even need to go looking for it!

Our life in bits and bytes

kw: book reviews, nonfiction, algorithms, prediction, sociology

What would life be like if the atoms that make us up were just big enough to see, if we could witness directly how they slide, merge and separate? How complex could our life be if the sum total of our lives could be described by, say, 1,000 characteristics, or perhaps 100? How about 10?

Yet how quick we are to pigeonhole people according to one or two, or at most five, distinguishing items! What do most of us now about, for example, Yo Yo Ma? Male, Chinese, famous musician (maybe you know he is a cellist), … anything else? How about that he is French born, a Harvard graduate, and has earned 19 Grammys? That's six items, more than most people probably now about him.

To what extent do you think you could predict his tastes and buying habits from these six items? If another person shares these six characteristics, to what extent will he also share certain tastes in clothing or food or books to read? Some people wish us to think, "to a great extent". In The Formula: How Algorithms Solve All Our Problems and Create More by Luke Dormehl, some of the people he interviewed claim to do just that. (Maybe you've made a profile on a dating site that starts matching you up when you've entered no more than four or five items. And how fully have you completed your FaceBook profile?). But some go to quite an extreme in another direction, using "big data" to pry inside our skulls.

What kind of big data? All your searches on Google, Yahoo, Alta Vista, Bing, or whatever; every click, Twitter text, FaceBook, LinkedIn, blog post, or online chat. We create tons of data about our day-to-day, even moment-by-moment activities. There was recently an item on the noon radio news about a company that aggregates such data and sells "packages" to companies, who pay $1 to $2 million dollars on some periodic basis for it (That's all I remember, I was listening with half an ear while folding laundry). Why is all that data so valuable? Because businesses believe they can better predict which products will sell to what kind of people if they crunch it.

A few months ago a handle on a drawer broke. Naturally, the cabinet is decades old and nothing even remotely similar in style could be found at Home Depot or a decorator's salon. So of course I looked online for something with the right spacing of mounting holes, with an appearance that would be compatible with the cabinet, in a set of four, so the handles would all match. It took a few days. I bought a set I liked, online, and installed them. For the next several months, however, ads about cabinet door handles appeared everywhere I went online: Google, FaceBook, Amazon, eBay. They all knew I'd been looking for door hardware. None of them knew I was done looking! (Google, are you listening? Do, please, close the loop and collect purchase data also.)

What is The Formula? Luke Dormehl calls it an Algorithm. What is an algorithm? To anyone but a mathematician it is a Recipe or a Procedure. I used to have a book, which I used into unusability: How to Keep Your Volkswagen Alive: A Manual of Step-by-Step Procedures for the Compleat Idiot by John Muir and Richard Sealey. With its help I kept my 1966 Bug alive into Moon Unit territory. The "procedures" were recipes, or algorithms, for things like setting valve clearances, changing a wheel bearing, or overhauling an engine. In computer science, an algorithm is the detailed instructions to a computer to direct it what you want it to do, very, very exactly.

Here is the kicker. A traditional algorithm is carried out in a procedural manner (don't pay attention to claims of non-procedural, object-oriented computer language gurus. At the root, a computer CPU carries out a series of procedural instructions), according to a "computer code" or "program", written in one or more formal languages. Some time ago I looked at the internal release notes for the Android OS used in many cell phones. That version, at least, released in 2009, had modules written in 40 computer languages. No matter how complex the program or program system, the instructions are written by a person, or perhaps by many persons, and no matter how many, their knowledge is finite. There are also time constraints, so that the final product will be biased, firstly by the limitations of the programmer(s), secondly by tactical decisions of what to leave out for the sake of time or efficiency, and thirdly by the simplifications or shortcuts this or that programmer might have made so that some operation was easier to write the code for. They may also be biased by inner prejudices of the programmer(s).

Another kicker: A kind of start-stop-start process had been going on around Neural Networks. They try to mimic the way our brains are wired. There are two kinds, hardware and software. Hardware neural nets are difficult to construct and more difficult to change, but they have much greater speed, yielding almost immediate results. Because people who can wire up such hardware are quite rare compared to people who can write computer software, hardware nets are also rare, and nearly all the research being done with them is being done using software simulations. "Machine learning" by neural nets can be carried out by either hard- or software nets, but I'll defer remarks on one significant difference for the moment.

A neural network created for a specific task—letter recognition in handwritten text, for example—is trained by providing two kinds of inputs. One is a series of target images to "view", perhaps in the form of GIF files, or with appropriate wiring, a camera directly attached. The other is the "meaning" that each target image is to have. A training set may have five exemplars of the lower-case "a", along with five indicators meaning "that is an a", five of "b" and their indicators, and so forth. The innards of the net somehow extract and store various characteristics of the training data set. Then it is "shown" an image to identify, and it will produce some kind of output, perhaps the ASCII code for the letter.

The inner workings of neural nets are pretty opaque, and perhaps unknowable without extremely diligent enumeration of all the things happening at every connection inside. But at the root, in a software neural network there is a traditional algorithm that describes the ways that the network connections will interact, which ones will be for taking input or making output, which ones will store things worth "remembering", and so forth. This is one reason that software nets are rather slow, even on pretty fast hardware. The simulation program cannot produce the wholly parallel processing that a hardware net uses (brains use wholly parallel processing, and are hard-put at linear processing, the opposite of computer CPU's). If the net is small, with only a few dozen or a few hundred nodes, the node-by-node computations can be accomplished rapidly, but a net that can recognize faces, for example, has to be a lot bigger than that. It will be hundreds of times slower.

Now for the other significant difference. The computer running the simulation is digital, while a hardware network is analog. I remember the first time I used a computer, that I was quite impressed to see calculations with 7-8 digits of significance, and if I used double precision, 15 digits. That sounds very precise, and for many uses, it is. Fifteen digit precision means one can specify the size of something about the size of a continent to the nearest nanometer. That is about the size of five or 10 atoms. However, a long series of calculations will not maintain such a level of precision. For many practical uses, calculations of much lower precision are sufficient. Before computers came along, buildings and bridges were built, and journeys planned; a slide rule was accurate enough to do the calculations. My best precision using a slide rule was 3-4 digits. But "real life"systems are typically nonlinear, and the sums tend to partly cancel one another out. You might start with very accurate measurements (but it's quite unlikely they are more accurate than 4-6 digits). Run a simulation based upon those figures a few dozen steps, and somewhere along the line there might have been a calculation similar to this:

324.871 659 836 648 - 324.860 521 422 697 → 0.011 138 413 951 016 4

If you've been counting digits, you might notice that the digits 0164 (which I colored red) are superfluous...where did they come from? That is the rounding error, both that which arose from representing the two numbers above in binary format, and that from the conversion of the result back into decimal form for display. But the bigger problem is that, counting only the black digits, only 11 are useful. Four have been lost. Further, if you were to start with decimal numbers that can be represented exactly in binary form, such as 75/64 = 1.171 875 and 43/128 = 0.335 937 5, multiplying them results in 3,225/8,182 = 0.393 676 757 812 5, which has 13 digits of precision, whereas the original numbers had seven each. Thus it typically takes twice as many digits to represent the result of a multiplication, as were needed to represent the two multiplicands.

I could go on longer, but an interested person can find ways to determine error propagation in all kinds of digital systems, many of which have long been studied already. By contrast, an analog system is not limited by rounding errors. Rather, real wires and real electronic components have thermal noise, which can trouble systems that run at temperatures we might find comfortable. Further, Extracting the outputs in numerical form takes delicate equipment, and the more accurately you want those output numbers to be, the more delicate and expensive the equipment gets. However, until readout, the simulation runs with no errors due to subtraction or multiplication, other than gradual amplification of thermal noise.

Suffice it to say, both direct procedural algorithms and neural network machine-learning systems are in use everywhere, trying to predict what the public is going to do, be it buying, voting, dating, relocating, or whatever. That is the main reason for science, after all: predicting the future. Medical science in the form of a doctor (or more than one) looks at a sick person and first tries to find a diagnosis, an evaluation of what the problem is. The next step is a prognosis, a prognostication or prediction; it is the doctors' expectation of the progress of the disease or syndrome, either under one treatment or another, or under none. A chemist trying to determine how to make a new polymer will use knowledge of chemical bonding to predict what a certain mixture of certain chemicals will produce. Then the experiment is carried out to either confirm the expectation (the prediction), or if it does not, to learn what might have gone against expectation and why. The experiments that led to the invention of Nylon took ten years. But based upon them, many other kinds of polymers later proved easier and quicker to develop. It is even so in biological science. Insect or seashell collecting can be a fun hobby, but a scientist will visit a research museum (or several) to learn all the places a certain animal lives, and when various specimens were collected, and then determine if there is a trend such as growing or shrinking population. Is the animal going extinct? Or is it flourishing and increasing its range worldwide?

In the author's view, The Formula represents the algorithms used in the business world, broadly construed, to predict what you might like, and thus present you with advertising to trigger your desire for that thing. My experience with cabinet handles shows that they often get their timing wrong. Many cool and interesting ads showed up, but it was too late. However, that isn't the author's point. The predictive methods find what ads to show us for products, or prospective dating partners on eHarmony or OK Cupid, or those that manage a politician's image, all tend to narrow our choices. A case in point from the analog world: one of the best jobs I had before going into Engineering came about because an Employment Agent, leafing through job sheets, muttered, "You wouldn't be interested in that," but I quickly said, "Try me!"

Try making some Google searches while logged in to Google, and then (perhaps using a different browser, and if you're really into due diligence, on a different computer network such as a library), making the same searches while not logged in. The "hits" in the main column will be similar, or possibly the same. But the ads on the right are tailored to your own search history and other indicators that Google has gathered.

Is all this a bad thing? Maybe. You can game the system a little, but as time goes on, your history will more and more outweigh things you do differently today. Sure, I got a sudden influx of ads about cabinet handles after searching for same, but if I had a history as a very skilled handyman (I don't!), the exact ads I saw might have been quite different. And I might have also seen ads about certain power tools intended to make the mounting of new cabinet handles even easier.

The author has four concerns and spends a chapter on each.

1. Are algorithms objective? They cannot be. Programmers are not objective, and machine learning is dependent on the training set, which depends on the persons who create it, and they are not objective.
2. Can an algorithm really predict human relationships? We have proverbs that give us pause, such as, "Opposites attract", and "If you're not near the one you love, you'll love the one you're near".
3. Can algorithms make the law more fair? I was once asked by a supervisor if I thought he was fair. I replied, "Too much concern for fairness can result in harshness. We (his 'direct reports') wish to be treated not just fairly but well. We'd like a little mercy with our justice." Mr. Dormehl cites the case of an experiment with an inflexible computer program, given the speed records from a car on a long-distance trip. It issued about 500 virtual tickets. A different program, that averaged speed over intervals just a little longer, issued one ticket.
4. Can an algorithm create art? Since all the programs created to date operate by studying what makes existing artworks more or less popular, they can only copy the past. True creation means doing what has not been done. Picasso and others who developed Cubism did so against great opposition. Now their works sell for millions. It was art even before it was popular, but the "populace" didn't see it that way for a couple decades.

The book closes with a thoughtful section titled "How to Stay Human in the World of the Formula." While he has some suggestions, I think the best way is to avoid being totally predictable. In many ways, that is hard for me, because I am a man of regular habits. I'm quite happy eating the same meat-and-cheese sandwich for lunch day after day, taking the same route to a work place (or these days, a place I volunteer), eating at a certain kind of restaurant and eschewing most "fine dining" places, wearing a certain kind of garb depending on the season, playing (on acoustic instruments, not electronic devices) certain kinds of music to the exclusion of others, and so forth. But I am also the kind of guy, when I make a mobile, it will be quite different from any other I have ever made: different materials, different color schemes, and different numbers of hanging objects clustered—or not—in various ways. I made one out of feathers once; not my most successful mobile. When I write a formal document or a letter for sending via snail mail, though I type it because handwriting is so slow, I usually pick a new typeface in which to print it; I have a collection of nearly 2,000 font files, carefully selected either for readability or as specialized drop caps (I love drop caps, though I am careful in their use). I haven't bothered to try alternate typefaces for this blog, because there are only 7 available anyway, and the default is as good as any.

The author proposes that we "learn more about the world of The Formula". Sure. But as long as Google's Edge Rank (formerly Page Rank) is a black box, and as long as everyone out there from FaceBook and LinkedIn to Amazon and NetFlix keep tweaking their own black box "recommendation engines", it will be a kind of arms race between the cleverest consumers and the marketers. But, hasn't that always been true?

xMandelbrot on a faster CPU

kw: algorithms, beauty, mathematics

I noted in Mandel Spider my discovery of the xMandelbrot Viewer. It zooms to any level and uses bignum (increased precision) calculations when the zoom level would overwhelm ordinary floating point calculations. I dug into a similar region using the new quad-core CPU computer my son and I recently built. The image below is a deep enough zoom that 38-digit calculations were used, with the limits shown in the Overview pane shown at the bottom of the post. Note that the application needs Java 5 or later, but I found that simple to install.


You find out the extent of calculations by a histogram in the Palette Editor, which was used to set the color palette here. The MaxIterations parameter was set to 500, and the histogram shows that the actual number of iterations ranged from about 300 to about 450.

Such an image requires 15 minutes to produce on the dual-core CPU on my laptop. This took about one minute on the new computer. About a 4x increase is due to the faster processors and that there were four rather than two. The other nearly 4x is due to the faster front-side bus and memory speed.

As you can see in this control panel overview, the X and Y limits only differ after 25 digits. This is a 10-trillion-trillion-X zoom (10 septillion X). There is no real value in such extreme zooms, because the view looks the same after a few thousand X; that is the way fractals are. It simply provides a way to test the efficiency of one's algorithms and hardware.

The main lesson from this is, for more speed, throw more iron at the problem. That is why the weather bureau and military simulation experts keep rushing to produce ever-faster supercomputers. The fastest now are in the petaflop range, approaching an exaflop (10¹⁸ math operations per second). My "poor little" home computer just loafs along at about a gigaflop, a billion times slower, but that's ten times as fast as the early Cray supercomputers. Nice to have a pocket supercomputer when you need it.

Mandel Spider

kw: mathematics, beauty, algorithms

Recent rumination about recursive calculations, rounding errors, high-precision calculations, and strange attractors such as those near the edges of the Mandelbrot Set led me to search for software that I could use to explore some of these ideas. This image is from the best site I've so far encountered:

Just for fun, I call it the Mandel Spider. The overview window, shown below, gives the coordinates. Look carefully, the first difference between Xmin and Xmax occurs in the 18th digit after the decimal. The "window" size is 5.0×10^-19 by 3.7×10^-19.

The viewer is the xMandelbrotViewer by David Eck. Over "window" sizes much larger than I've shown here (larger than about 10^-5) the viewer uses ordinary 32-bit floating point math, which is very fast. As you zoom to smaller and smaller areas, it uses "bignum" math, probably of the BCD variety, to add sufficient precision so that there are five or six guard digits beyond the precision needed to dissect the chosen area into about 750×500 pixels. The image above used 28-digit arithmetic, and ran quite slowly. It took about five minutes on my laptop. I'll have to try it on my newer desktop, which has a fast quad processor. A lot will depend on the smarts of Java 5.

I don't know the limits of the program yet. It gets more time consuming the deeper one goes. It also lets you set the maximum iterations parameter, as high as 50,000, though the default is 100. I used 1,000 for the image above, and of course most of the points (the sky blue ones) required many fewer iterations. But at this depth, we're totally inside an area that would be entirely black with only 250 iterations, the limit imposed by most viewers.

I'm still looking for software that lets me set the precision as I like, to see how it might affect the look of an image. From a bit of exploration I've found that the attractor for most points near the Mandelbrot Set is simple enough to minimize rounding problems, but the closer you get to the edge of the set (the more iterations needed to prove that a point is not in the Set), the more chaotic the attractor is, and the more I would expect rounding errors to tend to overwhelm the calculation. But that is still in the future for me. Maybe I'll find an article by someone who has already done the experiment…

Simpson's Rule and Beyond

kw: numerical integration, algorithms, derivations

On July 28 I posted a derivation of the (1-4-1)/6 method known as Simpson's Rule. It is based on projecting a parabola through three points to determine the area between the curve defined by those points and the X-axis. Simply put, the area under any portion of a parabola defined by three points (X0,Y0), (X1,Y1), and (X2,Y2), for which X1 is the midpoint of the interval (so X2-X1 = X1-X0), and h=X2-X0, is

As = h(Y0+4Y1+Y2)/6

I have also seen in the literature, again presented without proof, that performing a convergence acceleration on a Trapezoid rule integration using one, then two steps in an interval is equivalent to Simpson's rule. This is quite simple to prove.

The Trapezoid rule is based on using the area between a line segment and the X-axis to approximate the area under a curve that passes through the segment's end points. For a single segment, you multiply the width of the interval (h) by the average of the end-points. Formally, A = ½h•(Y0+Y1). If you add a third point at the center of the interval, making two segments, and call the Y at the midpoint Ym, the area is A = ¼h•(Y0+Y1+2Ym).

Now let us rename the points so we can derive the rule: Y0, Y1, Y2 in order. Let us sum areas for Y = 1/X, from X=1 to X=2, to show the convergence. First, we need the three points with which we'll work:

(X0,Y0) = (1,1)
(X1,Y1) = (1.5,0.6666667)
(X2,Y2) = (2,0.5)

Now, the 1-step area is

A1 = ½h•(Y0+Y2) = 0.5*1.5 = 0.75

and the 2-step area is

A2 = ¼h•(Y0+2Y1+Y2) = 0.25*2.833333 = 0.7083333

The actual area under the curve 1/X within X={1,2} is ln(2)=0.6931472.

The error in A1 is +0.0568528 and that in A2 is +0.0151861. We are gratified to find that there is indeed convergence; A2 is much smaller than A1. Now, A1/A2 = 3.74..., and if we were to pursue further analysis (such as by using four steps, 8 steps, etc.), we find that doubling the number of steps in an interval increases the accuracy by a factor of about four. This is second-order convergence, characteristic of the Trapezoid rule.

The second-order nature of the convergence means that we can combine these two areas to produce a third, better estimate:

Ae = (4•A2-A1)/3 = (4*0.7083333-0.75)/3 = 0.6944444, which has an error of 0.001297.

Firstly, note that the combined error is 1/44th of the error in A1. It would take a Trapezoid rule summation with sixteen steps in the same interval to achieve this level of accuracy. Now, let us use the formula for Ae, substituting back the Y values:

Ae = h(4•A2-A1)/3 = h(4•¼(Y0+2Y1+y2)-½(Y0+Y2))/3 = h(2Y0+4Y1+2Y2-Y0-Y2)/6 = h(Y0+4Y1+Y2)/6. This is Simpson's rule. QED

Clue to a later post: Simpson's rule also converges, at an even higher order...