CATEGORII DOCUMENTE 

Bulgara  Ceha slovaca  Croata  Engleza  Estona  Finlandeza  Franceza 
Germana  Italiana  Letona  Lituaniana  Maghiara  Olandeza  Poloneza 
Sarba  Slovena  Spaniola  Suedeza  Turca  Ucraineana 
Symmetric positivedefinite matrices have many interesting and desirable properties. For example, they are nonsingular, and LU decomposition can be performed on them without our having to worry about dividing by 0. In this section, we shall prove several other important properties of symmetric positivedefinite matrices and show an interesting application to curve fitting by a leastsquares approximation.
The first property we prove is perhaps the most basic.
Lemma 13
Any symmetric positivedefinite matrix is nonsingular.
Proof Suppose that a matrix A is singular. Then by Corollary 3, there exists a nonzero vector x such that Ax = 0. Hence, x^{T}Ax = 0, and A cannot be positivedefinite.
The proof that we can perform LU decomposition on a symmetric positivedefinite matrix A without dividing by 0 is more involved. We begin by proving properties about certain submatrices of A. Define the kth leading submatrix of A to be the matrix A_{k} consisting of the intersection of the first k rows and first k columns of A.
Lemma 14
If A is a symmetric positivedefinite matrix, then every leading submatrix of A is symmetric and positivedefinite.
Proof That each leading submatrix A_{k} is symmetric is obvious. To prove that A_{k} is positivedefinite, let x be a nonzero column vector of size k, and let us partition A as follows:
Then, we have
since A is positivedefinite, and hence A_{k} is also positivedefinite.
We now turn to some essential properties of the Schur complement. Let A be a symmetric positivedefinite matrix, and let A_{k} be a leading k k submatrix of A. Partition A as
Then, the Schur complement of A with respect to Ak is defined to be
(By Lemma 14, Ak is symmetric and positivedefinite; therefore, exists by Lemma 13, and S is well defined.) Note that our earlier definition (23) of the Schur complement is consistent with definition (29), by letting k = 1.
The next lemma shows that the Schurcomplement matrices of symmetric positivedefinite matrices are themselves symmetric and positivedefinite. This result was used in Theorem 12, and its corollary is needed to prove the correctness of LU decomposition for symmetric positivedefinite matrices.
Lemma 15
If A is a symmetric positivedefinite matrix and A_{k} is a leading data k k submatrix of A, then the Schur complement of A with respect to A_{k} is symmetric and positivedefinite.
Proof That S is symmetric follows from Exercise 17. It remains to show that S is positivedefinite. Consider the partition of A given in equation (28).
For any nonzero vector x, we have x^{T}Ax > 0 by assumption. Let us break x into two subvectors y and z compatible with A_{k} and C, respectively. Because A_{k}^{1} exists, we have
by matrix magic. (Verify by multiplying through.) This last equation amounts to 'completing the square' of the quadractic form. (See Exercise 62.)
Since x^{T}Ax > 0 holds for any nonzero x, let us pick any nonzero z and then choose , which causes the first term in equation (30) to vanish, leaving
as the value of the expression. For any z 0, we therefore have z^{T}Sz = x^{T}Ax > 0, and thus S is positivedefinite.
Corollary 16
LU decomposition of a symmetric positivedefinite matrix never causes a division by 0.
Proof Let A be a symmetric positivedefinite matrix. We shall prove something stronger than the statement of the corollary: every pivot is strictly positive. The first pivot is a_{11}. Let e_{1} be the first unit vector, from which we obtain . Since the first step of LU decomposition produces the Schur complement of A with respect to A_{1} = (a_{11}), Lemma 15 implies that all pivots are positive by induction.
Fitting curves to given sets of data points is an important application of symmetric positivedefinite matrices. Suppose that we are given a set of m data points
(x_{1},y_{1}),(x_{2},y_{2}),,(x_{m},y_{m}),
where the y_{i} are known to be subject to measurement errors. We would like to determine a function F (x) such that
y_{i} = F(x_{i}) + _{i},
for i = 1, 2, . . . , m, where the approximation errors i are small. The form of the function F depends on the problem at hand. Here, we assume that it has the form of a linearly weighted sum,
where the number of summands n and the specific basis functions f_{j} are chosen based on knowledge of the problem at hand. A common choice is f_{j}(x) = x^{j}^{1}, which means that
F(x) = c_{1} + c_{2}x + c_{3}x^{2} + + c_{n}x^{n}^{1}
is a polynomial of degree n  1 in x.
By choosing n = m, we calculate each y_{i} exactly in equation (31). Such a highdegree F 'fits the noise' as well as the data, however, and generally gives poor results when used to predict y for previously unseen values of x. It is usually better to choose n significantly smaller than m and hope that by choosing the coefficients c_{j} well, we can obtain a function F that finds the significantl patterns in the data points without paying undue attention to the noise. Some theoretical principles exist for choosing n, but they are beyond the scope of this text. In any case, once n is chosen, we end up with an overdetermined set of equations that we wish to solve as well as we can. We now show how this can be done.
Let
denote the matrix of values of the basis functions at the given points; that is, a_{ij} = f_{j}(x_{i}). Let c = (c_{k}) denote the desired sizen vector of coefficients. Then,
is the sizem vector of 'predicted values' for y. Thus,
= Ac  y
is the sizem vector of approximation errors.
To minimize approximation errors, we choose to minimize the norm of the error vector , which gives us a leastsquares solution, since
Since
we can minimize  by differentiating ^{2} with respect to each c_{k} and then setting the result to 0:
The n equations (32) for k = 1, 2, . . . , n are equivalent to the single matrix equation
(Ac y)^{T}A = 0
or, equivalently (using Exercise 13), to
A^{T}(Ac  y) = 0 ,
which implies
A^{T}Ac = A^{T}y .
In statistics, this is called the normal equation. The matrix A^{T} A is symmetric by Exercise 13, and if A has full column rank, then A^{T}A is positivedefinite as well. Hence, (A^{T}A)^{1} exists, and the solution to equation (33) is
c = ((A^{T}A)^{1}A^{T})y
= A^{+}y ,
where the matrix A^{+} = ((A^{T}A)^{1}A^{T}) is called the pseudoinverse of the matrix A. The pseudoinverese is a natural generalization of the notion of a matrix inverse to the case in which A is nonsquare. (Compare equation (34) as the approximate solution to Ac = y with the solution A^{1}b as the exact solution to Ax = b.)
As an example of producing a leastsquares fit, suppose that we have 5 data points
(1,2),(1,1),(2,1),(3,0),(5,3),
shown as black dots in Figure 3. We wish to fit these points with a quadratic polynomial
F(x) = c_{1} + c_{2}x + c_{3}x^{2}.
We start with the matrix of basisfunction values
whose pseudoinverse is
Multiplying y by A^{+}, we obtain the coefficient vector
which corresponds to the quadratic polynomial
F(x) = 1.200  0.757x + 0.214x^{2}
as the closestfitting quadratic to the given data, in a leastsquares sense.
As a practical matter, we solve the normal equation (33) by multiplying y by A^{T} and then finding an LU decomposition of A^{T} A. If A has full rank, the matrix A^{T} A is guaranteed to be nonsingular, because it is symmetric and positivedefinite. (See Exercise 13 and Theorem 6.)
61
Prove that every diagonal element of a symmetric positivedefinite matrix is positive.
62
Let be a 2 2 symmetric positivedefinite matrix. Prove that its determinant ac  b^{2} is positive by 'completing the square' in a manner similar to that used in the proof of Lemma 15.
63
Prove that the maximum element in a symmetric positivedefinite matrix lies on the diagonal.
64
Prove that the determinant of each leading submatrix of a symmetric positivedefinite matrix is positive.
65
Let A_{k} denote the kth leading submatrix of a symmetric positivedefinite matrix A. Prove that det(A_{k})/det(A_{k}_{1}) is the kth pivot during LU decomposition, where by convention det(A_{0}) = 1.
66
Find the function of the form
F(x) = c_{1} + c_{2}x lg x + c_{3}e^{x}
that is the best leastsquares fit to the data points
(1,1),(2,1),(3,3),(4,8) .
67
Show that the pseudoinverse A^{+} satisfies the following four equations:
AA^{+} A = A ,
A^{+} AA^{+ }= A^{+ },
(AA^{+})^{T }= AA^{+ },
(A^{+}A)^{T }= A^{+}A .
311 Shamir's boolean matrix multiplication algorithm
In Section 3, we observed that Strassen's matrixmultiplication algorithm cannot be applied directly to boolean matrix multiplication because the boolean quasiring Q = (, , , 0, 1) is not a ring. Theorem 10 showed that if we used arithmetic operations on words of O(lg n) bits, we could nevertheless apply Strassen's method to multiply n n boolean matrices in O(n^{lg 7}) time. In this problem, we investigate a probabilistic method that uses only bit operations to achieve nearly as good a bound but with some small chance of error.
a. Show that R = (, , , 0, 1), where is the XOR (exclusiveor) function, is a ring.
Let A = (a_{ij}) and B = (b_{ij}) be n n boolean matrices, and let C = (c_{ij}) = AB in the quasiring Q. Generate A' = (a'_{ij}) from A using the following randomized procedure:
If a_{ij} = 0, then let a'_{ij} = 0.
If A_{ij} = 1, then let a'_{ij} = 1 with probability 1/2 and let a'_{ij} = 0 with probability 1/2. The random choices for each entry are independent.
b. Let C' = (c'_{ij}) = A'B in the ring R. Show that c_{ij} = 0 implies c'_{ij} = 0. Show that c_{ij} = 1 implies c'_{ij} = 1 with probability 1/2.
c. Show that for any > 0, the probability is at most /n^{2} that a given c'_{ij} never takes on the value c_{ij} for lg(n^{2}/) independent choices of the matrix A'. Show that the probability is at least 1  that all c'_{ij} take on their correct values at least once.
d. Give an O(n^{lg 7 }lg n)time randomized algorithm that computes the product in the boolean quasiring Q of two n n matrices with probability at least 1  1/n^{k} for any constant k > 0. The only operations permitted on matrix elements are , , and .
312 Tridiagonal systems of linear equations
Consider the tridiagonal matrix
a. Find an LU decomposition of A.
b. Solve the equation Ax = (1 1 1 1 1)^{T} by using forward and back substitution.
c. Find the inverse of A.
d. Show that for any n n symmetric, positivedefinite, tridiagonal matrix A and any nvector b, the equation Ax = b can be solved in O(n) time by performing an LU decomposition. Argue that any method based on forming A^{}^{1} is asymptotically more expensive in the worst case.
e. Show that for any n n nonsingular, tridiagonal matrix A and any nvector b, the equation Ax = b can be solved in O(n) time by performing an LUP decomposition.
313 Splines
A practical method for interpolating a set of points with a curve is to use cubic splines. We are given a set of n + 1 pointvalue pairs, where x_{0} < x_{1} < < x_{n}. We wish to fit a piecewisecubic curve (spline) f(x) to the points. That is, the curve f(x) is made up of n cubic polynomials f_{i}(x) = a_{i} + b_{i}x + c_{i}x^{2} + d_{i}x^{3} for i = 0,1, . . . , n  1, where if x falls in the range x_{i} x x_{i }_{+ 1}, then the value of the curve is given by f(x) = f_{i}(x  x_{i}). The points x_{i} at which the cubic polynomials are 'pasted' together are called knots. For simplicity, we shall assume that x_{i} = i for i = 0,1, . . . , n.
To ensure continuity of f(x), we require that
f(x_{i}) = f_{i}(0) = y_{i },
f(x_{i}_{+1}) = f_{i}(1) = y_{i}_{+1}
for i = 0, 1, . . . , n  1. To ensure that f(x) is sufficiently smooth, we also insist that there be continuity of the first derivative at each knot:
for i = 0, 1, . . . , n  1.
a. Suppose that for i = 0, 1, . . . , n, we are given not only the pointvalue pairs but also the first derivatives D_{i} = f'(x_{i}) at each knot. Express each coefficient a_{i}, b_{i}, c_{i}, and d_{i} in terms of the values y_{i}, y_{i}_{+1}, D_{i}, and D_{i}_{+1}. (Remember that x_{i} = i.) How quickly can the 4n coefficients be computed from the pointvalue pairs and first derivatives?
The question remains of how to choose the first derivatives of f(x) at the knots. One method is to require the second derivatives to be continuous at the knots:
for i = 0, 1, . . . ,n  1. At the first and last knots, we assume that ; these assumptions make f(x) a natural cubic spline.
b. Use the continuity constraints on the second derivative to show that for i = 1, 2, . . . , n  1,
D_{i }_{ 1} + 4D_{i} + D_{i }_{+ 1} = 3(y_{i }_{+ 1}  y_{i }_{ 1}) .
c. Show that
2D_{0 }+ D_{1} = 3(y_{1}  y_{0}) ,
D_{n }_{ 1 }+ 2D_{n} = 3(y_{n}  y_{n }_{ 1}) .
d. Rewrite equations (35)(37) as a matrix equation involving the vector D = D_{0}, D_{1}, . . . , D_{n} of unknowns. What attributes does the matrix in your equation have?
e. Argue that a set of n + 1 pointvalue pairs can be interpolated with a natural cubic spline in O(n) time (see Problem 312).
f. Show how to determine a natural cubic spline that interpolates a set of n + 1 points (x_{i}, y_{i}) satisfying x_{0} < x_{1} < < x_{n}, even when x_{i} is not necessarily equal to i. What matrix equation must be solved, and how quickly does your algorithm run?
There are many excellent texts available that describe numerical and scientific computation in much greater detail than we have room for here. The following are especially readable: George and Liu [81], Golub and Van Loan [89], Press, Flannery, Teukolsky, and Vetterling[161, 162], and Strang[181, 182].
The publication of Strassen's algorithm in 1969 [183] caused much excitement. Before then, it was hard to imagine that the naive algorithm could be improved upon. The asymptotic upper bound on the difficulty of matrix multiplication has since been considerably improved. The most asymptotically efficient algorithm for multiplying n n matrices to date, due to Coppersmith and Winograd [52], has a running time of O(n^{2.376}). The graphical presentation of Strassen's algorithm is due to Paterson [155]. Fischer and Meyer [67] adapted Strassen's algorithm to boolean matrices (Theorem 10) .
Gaussian elimination, upon which the LU and LUP decompositions are based, was the first systematic method for solving linear systems of equations. It was also one of the earliest numerical algorithms. Although it was known earlier, its discovery is commonly attributed to C. F. Gauss (17771855). In his famous paper [183], Strassen also showed that an n n matrix can be inverted in O(n^{lg 7}) time. Winograd [203] originally proved that matrix multiplication is no harder than matrix inversion, and the converse is due to Aho, Hopcroft, and Ullman [4].
Strang [182] has an excellent presentation of symmetric positivedefinite matrices and on linear algebra in general. He makes the following remark on page 334: 'My class often asks about unsymmetric positive definite matrices. I never use that term.'
Symmetric positivedefinite matrices have many interesting and desirable properties. For example, they are nonsingular, and LU decomposition can be performed on them without our having to worry about dividing by 0. In this section, we shall prove several other important properties of symmetric positivedefinite matrices and show an interesting application to curve fitting by a leastsquares approximation.
The first property we prove is perhaps the most basic.
Lemma 13
Any symmetric positivedefinite matrix is nonsingular.
Proof Suppose that a matrix A is singular. Then by Corollary 3, there exists a nonzero vector x such that Ax = 0. Hence, x^{T}Ax = 0, and A cannot be positivedefinite.
The proof that we can perform LU decomposition on a symmetric positivedefinite matrix A without dividing by 0 is more involved. We begin by proving properties about certain submatrices of A. Define the kth leading submatrix of A to be the matrix A_{k} consisting of the intersection of the first k rows and first k columns of A.
Lemma 14
If A is a symmetric positivedefinite matrix, then every leading submatrix of A is symmetric and positivedefinite.
Proof That each leading submatrix A_{k} is symmetric is obvious. To prove that A_{k} is positivedefinite, let x be a nonzero column vector of size k, and let us partition A as follows:
Then, we have
since A is positivedefinite, and hence A_{k} is also positivedefinite.
We now turn to some essential properties of the Schur complement. Let A be a symmetric positivedefinite matrix, and let A_{k} be a leading k k submatrix of A. Partition A as
Then, the Schur complement of A with respect to Ak is defined to be
(By Lemma 14, Ak is symmetric and positivedefinite; therefore, exists by Lemma 13, and S is well defined.) Note that our earlier definition (23) of the Schur complement is consistent with definition (29), by letting k = 1.
The next lemma shows that the Schurcomplement matrices of symmetric positivedefinite matrices are themselves symmetric and positivedefinite. This result was used in Theorem 12, and its corollary is needed to prove the correctness of LU decomposition for symmetric positivedefinite matrices.
Lemma 15
If A is a symmetric positivedefinite matrix and A_{k} is a leading data k k submatrix of A, then the Schur complement of A with respect to A_{k} is symmetric and positivedefinite.
Proof That S is symmetric follows from Exercise 17. It remains to show that S is positivedefinite. Consider the partition of A given in equation (28).
For any nonzero vector x, we have x^{T}Ax > 0 by assumption. Let us break x into two subvectors y and z compatible with A_{k} and C, respectively. Because A_{k}^{1} exists, we have
by matrix magic. (Verify by multiplying through.) This last equation amounts to 'completing the square' of the quadractic form. (See Exercise 62.)
Since x^{T}Ax > 0 holds for any nonzero x, let us pick any nonzero z and then choose , which causes the first term in equation (30) to vanish, leaving
as the value of the expression. For any z 0, we therefore have z^{T}Sz = x^{T}Ax > 0, and thus S is positivedefinite.
Corollary 16
LU decomposition of a symmetric positivedefinite matrix never causes a division by 0.
Proof Let A be a symmetric positivedefinite matrix. We shall prove something stronger than the statement of the corollary: every pivot is strictly positive. The first pivot is a_{11}. Let e_{1} be the first unit vector, from which we obtain . Since the first step of LU decomposition produces the Schur complement of A with respect to A_{1} = (a_{11}), Lemma 15 implies that all pivots are positive by induction.
Fitting curves to given sets of data points is an important application of symmetric positivedefinite matrices. Suppose that we are given a set of m data points
(x_{1},y_{1}),(x_{2},y_{2}),,(x_{m},y_{m}),
where the y_{i} are known to be subject to measurement errors. We would like to determine a function F (x) such that
y_{i} = F(x_{i}) + _{i},
for i = 1, 2, . . . , m, where the approximation errors i are small. The form of the function F depends on the problem at hand. Here, we assume that it has the form of a linearly weighted sum,
where the number of summands n and the specific basis functions f_{j} are chosen based on knowledge of the problem at hand. A common choice is f_{j}(x) = x^{j}^{1}, which means that
F(x) = c_{1} + c_{2}x + c_{3}x^{2} + + c_{n}x^{n}^{1}
is a polynomial of degree n  1 in x.
By choosing n = m, we calculate each y_{i} exactly in equation (31). Such a highdegree F 'fits the noise' as well as the data, however, and generally gives poor results when used to predict y for previously unseen values of x. It is usually better to choose n significantly smaller than m and hope that by choosing the coefficients c_{j} well, we can obtain a function F that finds the significantl patterns in the data points without paying undue attention to the noise. Some theoretical principles exist for choosing n, but they are beyond the scope of this text. In any case, once n is chosen, we end up with an overdetermined set of equations that we wish to solve as well as we can. We now show how this can be done.
Let
denote the matrix of values of the basis functions at the given points; that is, a_{ij} = f_{j}(x_{i}). Let c = (c_{k}) denote the desired sizen vector of coefficients. Then,
is the sizem vector of 'predicted values' for y. Thus,
= Ac  y
is the sizem vector of approximation errors.
To minimize approximation errors, we choose to minimize the norm of the error vector , which gives us a leastsquares solution, since
Since
we can minimize  by differentiating ^{2} with respect to each c_{k} and then setting the result to 0:
The n equations (32) for k = 1, 2, . . . , n are equivalent to the single matrix equation
(Ac y)^{T}A = 0
or, equivalently (using Exercise 13), to
A^{T}(Ac  y) = 0 ,
which implies
A^{T}Ac = A^{T}y .
In statistics, this is called the normal equation. The matrix A^{T} A is symmetric by Exercise 13, and if A has full column rank, then A^{T}A is positivedefinite as well. Hence, (A^{T}A)^{1} exists, and the solution to equation (33) is
c = ((A^{T}A)^{1}A^{T})y
= A^{+}y ,
where the matrix A^{+} = ((A^{T}A)^{1}A^{T}) is called the pseudoinverse of the matrix A. The pseudoinverese is a natural generalization of the notion of a matrix inverse to the case in which A is nonsquare. (Compare equation (34) as the approximate solution to Ac = y with the solution A^{1}b as the exact solution to Ax = b.)
As an example of producing a leastsquares fit, suppose that we have 5 data points
(1,2),(1,1),(2,1),(3,0),(5,3),
shown as black dots in Figure 3. We wish to fit these points with a quadratic polynomial
F(x) = c_{1} + c_{2}x + c_{3}x^{2}.
We start with the matrix of basisfunction values
whose pseudoinverse is
Multiplying y by A^{+}, we obtain the coefficient vector
which corresponds to the quadratic polynomial
F(x) = 1.200  0.757x + 0.214x^{2}
as the closestfitting quadratic to the given data, in a leastsquares sense.
As a practical matter, we solve the normal equation (33) by multiplying y by A^{T} and then finding an LU decomposition of A^{T} A. If A has full rank, the matrix A^{T} A is guaranteed to be nonsingular, because it is symmetric and positivedefinite. (See Exercise 13 and Theorem 6.)
61
Prove that every diagonal element of a symmetric positivedefinite matrix is positive.
62
Let be a 2 2 symmetric positivedefinite matrix. Prove that its determinant ac  b^{2} is positive by 'completing the square' in a manner similar to that used in the proof of Lemma 15.
63
Prove that the maximum element in a symmetric positivedefinite matrix lies on the diagonal.
64
Prove that the determinant of each leading submatrix of a symmetric positivedefinite matrix is positive.
65
Let A_{k} denote the kth leading submatrix of a symmetric positivedefinite matrix A. Prove that det(A_{k})/det(A_{k}_{1}) is the kth pivot during LU decomposition, where by convention det(A_{0}) = 1.
66
Find the function of the form
F(x) = c_{1} + c_{2}x lg x + c_{3}e^{x}
that is the best leastsquares fit to the data points
(1,1),(2,1),(3,3),(4,8) .
67
Show that the pseudoinverse A^{+} satisfies the following four equations:
AA^{+} A = A ,
A^{+} AA^{+ }= A^{+ },
(AA^{+})^{T }= AA^{+ },
(A^{+}A)^{T }= A^{+}A .
311 Shamir's boolean matrix multiplication algorithm
In Section 3, we observed that Strassen's matrixmultiplication algorithm cannot be applied directly to boolean matrix multiplication because the boolean quasiring Q = (, , , 0, 1) is not a ring. Theorem 10 showed that if we used arithmetic operations on words of O(lg n) bits, we could nevertheless apply Strassen's method to multiply n n boolean matrices in O(n^{lg 7}) time. In this problem, we investigate a probabilistic method that uses only bit operations to achieve nearly as good a bound but with some small chance of error.
a. Show that R = (, , , 0, 1), where is the XOR (exclusiveor) function, is a ring.
Let A = (a_{ij}) and B = (b_{ij}) be n n boolean matrices, and let C = (c_{ij}) = AB in the quasiring Q. Generate A' = (a'_{ij}) from A using the following randomized procedure:
If a_{ij} = 0, then let a'_{ij} = 0.
If A_{ij} = 1, then let a'_{ij} = 1 with probability 1/2 and let a'_{ij} = 0 with probability 1/2. The random choices for each entry are independent.
b. Let C' = (c'_{ij}) = A'B in the ring R. Show that c_{ij} = 0 implies c'_{ij} = 0. Show that c_{ij} = 1 implies c'_{ij} = 1 with probability 1/2.
c. Show that for any > 0, the probability is at most /n^{2} that a given c'_{ij} never takes on the value c_{ij} for lg(n^{2}/) independent choices of the matrix A'. Show that the probability is at least 1  that all c'_{ij} take on their correct values at least once.
d. Give an O(n^{lg 7 }lg n)time randomized algorithm that computes the product in the boolean quasiring Q of two n n matrices with probability at least 1  1/n^{k} for any constant k > 0. The only operations permitted on matrix elements are , , and .
312 Tridiagonal systems of linear equations
Consider the tridiagonal matrix
a. Find an LU decomposition of A.
b. Solve the equation Ax = (1 1 1 1 1)^{T} by using forward and back substitution.
c. Find the inverse of A.
d. Show that for any n n symmetric, positivedefinite, tridiagonal matrix A and any nvector b, the equation Ax = b can be solved in O(n) time by performing an LU decomposition. Argue that any method based on forming A^{}^{1} is asymptotically more expensive in the worst case.
e. Show that for any n n nonsingular, tridiagonal matrix A and any nvector b, the equation Ax = b can be solved in O(n) time by performing an LUP decomposition.
313 Splines
A practical method for interpolating a set of points with a curve is to use cubic splines. We are given a set of n + 1 pointvalue pairs, where x_{0} < x_{1} < < x_{n}. We wish to fit a piecewisecubic curve (spline) f(x) to the points. That is, the curve f(x) is made up of n cubic polynomials f_{i}(x) = a_{i} + b_{i}x + c_{i}x^{2} + d_{i}x^{3} for i = 0,1, . . . , n  1, where if x falls in the range x_{i} x x_{i }_{+ 1}, then the value of the curve is given by f(x) = f_{i}(x  x_{i}). The points x_{i} at which the cubic polynomials are 'pasted' together are called knots. For simplicity, we shall assume that x_{i} = i for i = 0,1, . . . , n.
To ensure continuity of f(x), we require that
f(x_{i}) = f_{i}(0) = y_{i },
f(x_{i}_{+1}) = f_{i}(1) = y_{i}_{+1}
for i = 0, 1, . . . , n  1. To ensure that f(x) is sufficiently smooth, we also insist that there be continuity of the first derivative at each knot:
for i = 0, 1, . . . , n  1.
a. Suppose that for i = 0, 1, . . . , n, we are given not only the pointvalue pairs but also the first derivatives D_{i} = f'(x_{i}) at each knot. Express each coefficient a_{i}, b_{i}, c_{i}, and d_{i} in terms of the values y_{i}, y_{i}_{+1}, D_{i}, and D_{i}_{+1}. (Remember that x_{i} = i.) How quickly can the 4n coefficients be computed from the pointvalue pairs and first derivatives?
The question remains of how to choose the first derivatives of f(x) at the knots. One method is to require the second derivatives to be continuous at the knots:
for i = 0, 1, . . . ,n  1. At the first and last knots, we assume that ; these assumptions make f(x) a natural cubic spline.
b. Use the continuity constraints on the second derivative to show that for i = 1, 2, . . . , n  1,
D_{i }_{ 1} + 4D_{i} + D_{i }_{+ 1} = 3(y_{i }_{+ 1}  y_{i }_{ 1}) .
c. Show that
2D_{0 }+ D_{1} = 3(y_{1}  y_{0}) ,
D_{n }_{ 1 }+ 2D_{n} = 3(y_{n}  y_{n }_{ 1}) .
d. Rewrite equations (35)(37) as a matrix equation involving the vector D = D_{0}, D_{1}, . . . , D_{n} of unknowns. What attributes does the matrix in your equation have?
e. Argue that a set of n + 1 pointvalue pairs can be interpolated with a natural cubic spline in O(n) time (see Problem 312).
f. Show how to determine a natural cubic spline that interpolates a set of n + 1 points (x_{i}, y_{i}) satisfying x_{0} < x_{1} < < x_{n}, even when x_{i} is not necessarily equal to i. What matrix equation must be solved, and how quickly does your algorithm run?
There are many excellent texts available that describe numerical and scientific computation in much greater detail than we have room for here. The following are especially readable: George and Liu [81], Golub and Van Loan [89], Press, Flannery, Teukolsky, and Vetterling[161, 162], and Strang[181, 182].
The publication of Strassen's algorithm in 1969 [183] caused much excitement. Before then, it was hard to imagine that the naive algorithm could be improved upon. The asymptotic upper bound on the difficulty of matrix multiplication has since been considerably improved. The most asymptotically efficient algorithm for multiplying n n matrices to date, due to Coppersmith and Winograd [52], has a running time of O(n^{2.376}). The graphical presentation of Strassen's algorithm is due to Paterson [155]. Fischer and Meyer [67] adapted Strassen's algorithm to boolean matrices (Theorem 10) .
Gaussian elimination, upon which the LU and LUP decompositions are based, was the first systematic method for solving linear systems of equations. It was also one of the earliest numerical algorithms. Although it was known earlier, its discovery is commonly attributed to C. F. Gauss (17771855). In his famous paper [183], Strassen also showed that an n n matrix can be inverted in O(n^{lg 7}) time. Winograd [203] originally proved that matrix multiplication is no harder than matrix inversion, and the converse is due to Aho, Hopcroft, and Ullman [4].
Strang [182] has an excellent presentation of symmetric positivedefinite matrices and on linear algebra in general. He makes the following remark on page 334: 'My class often asks about unsymmetric positive definite matrices. I never use that term.'

Vizualizari: 799
Importanta:
Termeni si conditii de utilizare  Contact
© SCRIGROUP 2019 . All rights reserved
Distribuie URL
Adauga cod HTML in site