Page 191 - Matrix Analysis & Applied Linear Algebra

186 Chapter 4 Vector Spaces
Example 4.3.5

Problem: Given a set of m points S = {(x 1 ,y 1 ), (x 2 ,y 2 ), . .., (x m ,y m )} in
which the x i ’s are distinct, explain why there is a unique polynomial
2
(t)= α 0 + α 1 t + α 2 t + ··· + α m−1 t m−1 (4.3.9)
of degree m − 1 that passes through each point in S.
Solution: The coefficients α i must satisfy the equations
2
α 0 + α 1 x 1 + α 2 x + ··· + α m−1 x m−1 = (x 1 )= y 1 ,
1 1
2
α 0 + α 1 x 2 + α 2 x + ··· + α m−1 x m−1 = (x 2 )= y 2 ,
2 2
.
.
.
2
α 0 + α 1 x m + α 2 x + ··· + α m−1 x m−1 = (x m )= y m .
m
m
Writing this m × m system as
1 x ··· x
 2 m−1     
x 1
1 1 α 0 y 1
 1 x 2 x 2 2 ··· x m−1   α 1   y 2 
2
 . . . .   .  =  . 
 . . . . .
. . . ··· .   .   . 
.
x 2 ··· x m−1
1 x m m m α m−1 y m
reveals that the coefficient matrix is a square Vandermonde matrix, so the result
of Example 4.3.4 guarantees that it is nonsingular. Consequently, the system has
a unique solution, and thus there is one and only one possible set of coefficients
for the polynomial (t) in (4.3.9). In fact, (t) must be given by
 m 
m ! (t − x j )
j =i

(t)=   .
m
y i !
i=1 j =i (x i − x j )
Verify this by showing that the right-hand side is indeed a polynomial of degree
m − 1 that passes through the points in S. The polynomial (t) is known as
27
the Lagrange interpolation polynomial of degree m − 1.
If rank (A m×n ) <n, then the columns of A must be a dependent set—
recall (4.3.3). For such matrices we often wish to extract a maximal linearly
independent subset of columns—i.e., a linearly independent set containing as
many columns from A as possible. Although there can be several ways to make
such a selection, the basic columns in A always constitute one solution.
27
Joseph Louis Lagrange (1736–1813), born in Turin, Italy, is considered by many to be one
of the two greatest mathematicians of the eighteenth century—Euler is the other. Lagrange
occupied Euler’s vacated position in 1766 in Berlin at the court of Frederick the Great who
wrote that “the greatest king in Europe” wishes to have at his court “the greatest mathe-
matician of Europe.” After 20years, Lagrange left Berlin and eventually moved to France.
Lagrange’s mathematical contributions are extremely wide and deep, but he had a particularly
strong influence on the way mathematical research evolved. He was the first of the top-class
mathematicians to recognize the weaknesses in the foundations of calculus, and he was among
the first to attempt a rigorous development.