I have sworn upon the altar of God eternal hostility against every form of tyranny over the mind of man. -- Thomas Jefferson

Tuesday, September 22, 2009

Math Interlude*:
Lagrange Interpolation as Self-Checking Algebra Practice

My kids started algebra last year, and, while they seem to get the basic concepts, they need practice – practice using the distributive law correctly to simplify algebraic expressions, practice dealing correctly with all those negative signs, etc.

Of course, I could just give them a huge number of polynomials to multiply, but, aside from being boring, that would require me to work out the answers myself in order to check their answers!

I’ve found a simple alternative that goes back to the great eighteenth-century mathematician Lagrange. “Lagrange interpolation” is actually interesting and useful in itself (although even well-educated technical people seem often to be ignorant of it nowadays), it happens to require quite a lot of multiplying of polynomials, checking of signs, etc. so that it is good algebra practice, and, best of all, it is automatically self-checking.

Here in a nutshell is how it works:

You are given a table of values for the variables x and y, and you want to find a polynomial that gives exactly the correct values of y when you plug in the values for x.

Suppose, for example, you are given the following values:
x y
1 1
2 4
3 9
5 9
and you want to find a polynomial
y = a x3 + b x2 + c x + d
that goes through those points.

There are various ways to solve this problem -- for example, you can use linear algebra if you view (a,b,c,d) as a vector in a four-dimensional space.

The method published by Lagrange uses a much simpler idea.

What we do is find four separate polynomial, each of which vanishes at all but one of the values of x.

For example, expression A:
(x - 2) * (x - 3) * (x - 5)
obviously vanishes when x is 2, 3, or 5, but obviously does not vanish when x is 1.

What is the value of expression A when x equals 1? Well, just plug 1 in for x and you find that the value is -8.

Now, when x is 1, according to our table, we need y to have a value of 1, not -8. So, we will just divide expression A by -8 and multiply it by 1, getting expression B:
1 * (x - 2) * (x - 3) * (x - 5) / (-8)
If you do the same thing for the case where x is 2, you get expression C:
4 * (x - 1) * (x - 3) * (x - 5) / (3)
Run the same trick for x equal to 3, and you get expression D:
9 * (x - 1) * (x - 2) * (x - 5) / (-4)
Finally, for x equals 5, you get expression E:
9 * (x - 1) * (x - 2) * (x - 3) / (24)
Now, expression B gives the right value for y when x is 1, and, it is created so that it will vanish at the other three values of x, so it will not mess up the values of y there. Similarly, expression C is created so that it gives the right value for y when x is 2, and it is zero at the other three values of x.

So, if we simplify expressions B, C, D, and E by multiplying each one out, and then add them all together, combining like terms, we will get a polynomial that gives the right values of y for each of the four values of x.

I don't need practice on algebra, so I had my kids do this. Their answer is expression F:
y = (-2/3) x3 + 5 x2 + (-22/3) x + 4
How do they (and I) know that they did the algebra right?

Simple – they plugged into expression F the values 1, 2, 3, and 5 for x. They should find that the values of y will then be 1, 4, 9, and 9 as planned. If they do not get the right values of y, they need to find their algebra error!

Note that Lagrange interpolation always works: you can choose any real numbers, positive, negative or zero, integral or fractional, for x and for y. (You can even use complex numbers if you wish.)

In particular, the values of x do not have to be evenly space: in my example, I
“skipped” 4, and it worked fine. Nor do the values of y have to be in any pattern: 1, 4, and 9 in my example seemed to be starting a pattern, but I wrecked that pattern by using 9 twice instead of using the “obvious” choice of 16.

The values of x do have to all be different (although, you can play some interesting tricks by letting two values of x get “infinitely close” – basically, you can then control the slope at x as well as the value of y).

You can in fact prove that this is the only polynomial of degree three or lower that goes through our four points. (In general, if you have n points, with different values of x, there is always a unique polynomial of degree n-1 or lower that goes through those points.)

The more points you use, the more complicated the algebra gets. I'd start with only two or three points for someone who is just learning algebra.

Isn't this too hard for kids in first-year algebra? No, my kids have learned it without too much trouble: there is no division of polynomials here, no quadratic formula, no trig functions, etc. This really is just first-year algebra.

But, isn't it complicated?

A little.

But this is the kind of complication that you get in real math applied to real problems. No one in real life (not even in science or engineering) ever faces the problem of multiplying ( x - 2 ) times ( x- 3) just for the fun of it. And, it is very, very rare that anyone ever faces the familiar textbook sort of algebra problem: “A train leaves Albuquerque going towards Santa Fe at 70 mph and a train leaves Santa Fe...” or
Jane had five times as many dolls as Ginger, but after Jane got two more dolls....”

Algebra is an abstract science; traditional algebra is about understanding the abstract properties of the four basic arithmetic operations: what does and can happen when you use the operations of addition, subtraction, multiplication and division in a systematic way? (Modern university algebra is about the properties of more general systems of mathematical operations that can operate on elements very different from ordinary real numbers.)

Mathematics is not really about balancing your checkbook or calculating the amount of tile you need to re-tile the kitchen – we have electronic calculators to do that for us.

Mathematics is about the possible abstract structures that can logically exist.

Those structures are often based on arithmetic and geometry, so you do need to know traditional math to understand modern mathematics.

But really learning math means trying not just to learn to get the right answer but actually exploring the universe of mathematics much as traditional explorers explored newly-discovered continents.

Lagrange interpolation is a very simple example of such exploration. Actually graphing the polynomials you get through Lagrange interpolation can also be enlightening: while the method always works, it can give some pretty “snaky” curves if you fit more than three points (for three points, the resulting curve is much nicer).

Is it too complicated? Well, someone unwilling to tackle topics such as Lagrange interpolation is not really learning math. If you want to know what math is really about, rather than just working you way through the watered-down, over-simplified picture of mathematics portrayed in American public-school textbooks, you need to try to wrap you mind around ideas such as Lagrange interpolation.

____________
* From time to time, I plan on posting a “Math Interlude,” in which I’ll try to explain some significant idea in math not known to most educated American adults, that I have in fact taught to my own kids in grade school or middle school, and that a bright middle-school student should be able to grasp.

10 comments:

  1. Cool! Something else for me to play around with.
    I once failed an algebra test with one of those the train left problems. I wrote I'd look at the train schedule. A snarky little kid I was.

    ReplyDelete
  2. Just found your blog and don't think it will be very useful for me for a few years, mostly because my kids are not even kindergarten aged yet. :)

    Can you post some stuff on when and how you started homeschooling? And do you think it's possible to sort of part-time homeschool to augment a US public school education? We live in a "very good" school district and, although I doubt they will learn everything I think they should in even a good public school, I'm not quite mentally prepared to completely give up my protein and genetics research.

    I see the links you posted to other homeschoolers and plan to check those out too. Thanks.

    ReplyDelete
  3. Hi, “anonymous”! Incidentally, if you could make up some screen-name, (one that preserves your anonymity – e.g., “StarMom” or whatever suits your fancy), it would make it easier to know if you are the same person as some other “anonymous” or not.

    Even though I “own” this blog, it limits the lengths of my own comments, so I am replying to you in two parts.

    You wrote:
    >Can you post some stuff on when and how you started homeschooling?

    Yeah. Briefly, our kids learned the alphabet (names of the letters, upper and lower case) between the ages of two and three. We started reading at age three-and-a half, using Houghton-Mifflin’s “Phonics Library” (no longer sold, I think, but I think any beginning phonics-based series would work). For the first couple months, I was not sure the kids were getting it, then it clicked. By their fourth birthday, they were reading at a second-grade level, and their reading skills have continued to advance at about twice the speed of standard public-school students ever since.

    This is not particularly exceptional, by the way. Teach ‘em to sound out words, get ‘em lots of books, and kids just take off in reading.

    I think reading is, overwhelmingly, the most important issue. We average a trip a week to the public library. I’ve tried to encourage “long-ago-and-far-away” books from the beginning: i.e., not “Junie B. Jones” or “Babysitters Club” but rather starting with the “Magic Treehouse” series (very simple-minded beginning chapter books) and Disney’s movie synopses books, and then moving on to “Chronicles of Narnia,” the “Redwall” series, “Harry Potter,” etc.

    A lot of adults, for some reason, think that kids want to read books about kids just like themselves. Of course, normal kids want to read about dragons and princesses, knights and castles, horses and rocket ships, etc. – i.e., stuff not in their own everyday lives.

    This is not “escapist” in the commonly used pejorative sense: it is rather the development of a sense of wonder and imagination.

    C. S. Lewis has a great essay that I need to dig up about the denigration of “escapist” literature: people need to remember that the “Odyssey” is science fiction and that “A Midsummer Night’s Dream” is fantasy – escapist literature can be very high quality indeed. (I am a fan of C. S. Lewis’, incidentally, even though I am not a religious believer: I think Lewis had some piercing insights into some of the inanities of modern life.)

    The other basic approach that we have taken is to deal with serious science and history from kindergarten on. Kindergartners cannot of course learn Schrodinger’s equation or the theory of stellar structure, but they can learn about black holes or how atoms are like miniature solar systems (sort of, but you can just tell them “sort of”), or even evolution.

    I’ve posted on this general point elsewhere on the bog if you wander through past posts: one very good book I will mention again here is Jennifer Morgan’s weirdly beautiful “The Universe Tells Our Cosmic Story” trilogy, suitable for kids around ages four to nine.

    I do aspire to create a systematic list of all the books we have used (and I’d like to see other homeschoolers do the same), but this will take a while. Check back here from time to time. Such lists will eventually be posted at my larger site, https://sites.google.com/site/homeschoolingphysicist/ ; currently, that site is empty and simply points over to this blog.

    If we all work together, perhaps we can improve the education of America’s children a bit.

    Dave

    ReplyDelete
  4. Anonymous,

    You wrote:
    >And do you think it's possible to sort of part-time homeschool to augment a US public school education?

    It’s called “afterschooling,” and, if you Google the kitchentablemath.blogspot.com archives, you can find a lot of information about this.

    I would say, in brief, that I think afterschooling does not work as well as homeschooling, but that afterschooling works enormously better than the all-too-common approach of parents who simply take a “hands-off” approach.

    I myself went through the public schools, and, in effect, I afterschooled myself. I was desperately bored through most of grade school (though I did have a lot of time for pleasant daydreaming!). Junior-high and high school were a bit better, mainly because we were grouped by ability, so that the classes were a bit more interesting.

    I think my experience illustrates the main problems with afterschooling: kids tend to get way beyond grade level (good), but then find the school day rather boring. Also, a typical school year involves spending well over a thousand hours a year in school – that is an awfully big chunk of time out of the year, and it is just not possible to make up for that “lost time” in afterschooling.
    (CONT.)

    ReplyDelete
  5. (CONT.)
    Anonymous also wrote:
    >We live in a "very good" school district and, although I doubt they will learn everything I think they should in even a good public school…

    I have not looked into the public schools systematically, but, from what I have seen, the “good” public schools have nice physical facilities, teachers who are somewhat more pleasant and personable, and, probably most important, middle-class and professional families who will provide some support to your child’s fellow students.

    All of that does matter.

    However, we had a neighbor who was an assistant professor at the local ed school and who was very positive about public schools – until, that is, her daughter reached kindergarten age, and the mom/professor started doing systematic on-site investigations of the local public schools to see how they would work for her daughter.

    She was appalled. She said that even the “good” public schools were educational disasters.

    Since she was an education professor strongly predisposed towards a favorable judgment of public schools, I found her conclusions pretty convincing.

    A very small number of public schools are flexible with bright students and will let them go at their own pace. Normally, this takes a fair amount of pushing on the part of the parents and proof that the child is “gifted,” and it’s a real hassle. (Someday, I’ll post about the “giftedness” meme: one mom on a “giftedness” forum explained to me privately – not on the public forum – that “giftedness” is really just a ploy to allow some reasonably bright students to learn what all reasonably bright students should be learning).

    There are also some private schools (so-called “Sudbury-model” schools) that are extremely unstructured. To my mind, they do not provide enough structure, but they might work with a highly motivated kid with strong parental support: at least, they will not waste your kid’s time nor actively prevent him or her from working up to his ability.

    On this blog, you’ll often find me sounding rather evangelical about homeschooling, but I, and most homeschoolers, do know that homeschooling just is not feasible for some families. I hope we homeschoolers do all remember that the real goal is not homeschooling as an end in itself but rather enabling your child to acquire a solid liberal education (“liberal” of course not in the contemporary political sense, but in the old sense of an education appropriate to a free human being).

    The most important thing is that the parents take positive responsibility for their children’s education, rather than just unthinkingly taking a “hands-off” approach and hoping for the best.

    Obviously, you are taking that responsibility seriously, and I and many other homeschoolers, afterschoolers, etc. will provide what information and advice we can to help you along.

    Wishing you the best,

    Dave

    ReplyDelete
  6. Lisa,

    My daughter recently worked on a sample problem for a standardized test where you had to find what important piece of information was missing in a toy advertisement.

    She chose “size of the toy.”

    The “correct” answer was “the address of the toy store.”

    My daughter said, “That’s not a problem! You can just look up the address on the Web.”

    Of course, what makes both your story and my daughter’s answer funny is that, in real life, her and your solutions truly are how anyone would deal with those situations!

    On the general issue of word problems, I’m beginning to think we use word problems in the wrong way in math.

    When people do “word problems” in real life, it tends to be very simple problems (calculating a tip or a discount on a purchase) or something having to do with cooking or carpentry. Almost the only people who ever use algebra after they get out of school are scientists and engineers and people in related technical fields.

    So, perhaps we should focus on the actual math skills (as I illustrated in my “Lagrange interpolation” posts) and limit the word problems to simple real-world examples and to real examples from science and engineering for which the student can see some purpose.

    I myself actually learned algebra by teaching myself whatever algebra I needed to understand relativity (in Herman Bondi’s little book, “Relativity and Common Sense”).

    By the way, if you try the “Lagrange interpolation” thing on some simple cases, it is sort of magical to see how it works out. My kids actually did work out the example I gave in the post, without my knowing what the correct answer was. Maybe this sort of number magic is cooler than trains to Albuquerque, etc.

    So, maybe the trains to Albuquerque and Julie’s and Jan’s marble collections should be banished forever from math texts.

    Dave

    ReplyDelete
  7. Hi Dave,

    I'm the anonymous from before, I guess I'll use this name. It's my degree, but not really what I do.

    I just ordered some of the books you recommended, some of the Magic Treehouse and one of the Universe ones. I'm looking forward to getting them. The kids love books and are just learning to read themselves, so these will be great. It is so fun to hear them sound out words and the look on their faces when they get it right is awesome.

    ReplyDelete
  8. biochemist wrote:
    >It is so fun to hear them sound out words and the look on their faces when they get it right is awesome.

    Yeah, it is. Almost all parents have that feeling when their kids take their first step, first ride a two-wheeler, first make it all the way across the swimming pool, etc. It’s sad that so many parents hand off reading completely to the schools, and miss the fun of seeing their kids start to read.

    The Magic Treehouse books are good beginning “chapter books” – something interesting actually happens, and the settings are interesting times and places in history. Do be aware though that your kids will tend to outgrow them after a couple years. That’s a good thing, of course, as that means they are ready to move on to “Narnia,” “Harry Potter,” etc. (as well as old classics such as “Dr. Dolittle,” the original “Nancy Drew,” and of course “Alice In Wonderland,” etc.).

    Osborne does, every six books or so, turn out somewhat more advanced books in the Magic Treehouse series: “Christmas in Camelot” is the one I recall – I think they subtitle these “Merlin Missions.” Those are still interesting to slightly more advanced readers.

    Some books you may want to keep in mind for two to four years down the line, though too advanced for your kids now:

    Mahlon Hoagland’s The Way Life Works This is a bizarrely brilliant book, written by the co-discoverer of transfer RNA, that uses whimsical cartoons to explain biology (mid-to-upper grade-school reading level). My wife has a Ph.D. in biology, and there was some stuff in here she did not know (discovered after she finished her degree). We read this together (one of the kids reading out loud while I and the other child read along silently, stopping as needed for me to explain any difficult words or ideas) when the kids were in second grade. This remains their favorite book that we have used in the last five years. It’s also available in an expanded, textbook-style version, as Exploring the Way Life Works.

    Anne Millard and Particia Vanags, Usborne History of the World (this is the “white” book, not the “Internet-linked” book) also uses cartoons to give a nice, brief overview of world history up to 1900. The book is admirably neutral – not pro-Christian nor anti-Christian, not “politically correct” nor hiding past atrocities, but just a nice description of the broad course of world history at an early to mid-grade school reading level.

    Irving Adler, Giant Golden Book of Mathematics long out of print but available through libraries and used-book sources online. This presents some very advanced concepts in math at a mid-grade school level (the reader should know at least long multiplication, and possibly long division). This was what “New Math” was supposed to be; unfortunately, the schools failed to implement “New Math” properly in the classrooms. This is the first book that actually got me excited about math in grade school (like most little boys, I did not really care whether 8 x 7 was 54 or 56). It’s about the connection of math to music and rocket ships and art and biology – why math really does matter.

    Finally, I assume you know about the publisher “Dorling Kindersley.” DK has recently produced a wonderful series of history books, written by Peter Ackroyd, “Voyages through Time” (mid-to-upper grade school level). These have the fantastic illustrations that DK is renowned for, but much better writing that most DK books. My kids fight over who gets to read these.

    Anyway, I hope this will give you some ideas to look at over the slightly longer term (it will be less time than you think, now that they have started reading, before they are reading pretty advanced books!). The reading levels I have given above are very approximate – it all depends, really, on the individual child. We did read most of these together as I explained above (all except the Adler book): these books are actually good enough that I kind of enjoyed them, too.

    All the best,

    Dave

    ReplyDelete
  9. Dave,

    I just found your blog and it has hit a chord. Funny how parenting and education issues can be the same world over when we live many timezones apart. We live in the Asian part of the world.

    We have recently made the decision to homeschool our only son (6yo) because of "unique opportunites" to accelerate. It has been a torture from Day 1 however, as he feels he is learning nothing. Instead, he rushes home for some "real learning" in math and science. I have come to realize that he needs daily learning to feel whole, and reading your post affirms it. So while I have never been keen on afterschooling, I will actually try to put in some effort because I realize this is how he likes to spend a part of his day.

    Perhaps at some point, we'll go back to homeschooling full time.

    Starmom

    ReplyDelete
  10. Sorry, I mean "... made a decision to send our son to public school ..." Must be a freudian slip :).

    Starmom

    ReplyDelete