Deturck, Wilf - Lecture Notes on Numerical Analysis (523142), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

, em }, to a vector space W with a distinguishedbasis F = {f1 , f2 , . . . , fn }, in the sense that from a knowledge of (t, E, F ) we know the fullmapping T .Next, suppose once more that T is a linear mapping from V to W . Since T is linear,it is easy to see that T carries the 0 vector of V into the 0 vector of W . Consider the setof all vectors of V that are mapped by T into the zero vector of W .

This set is called thekernel of T , and is written ker(T ). Thusker(T ) = {x ∈ V | T x = 0W }.(3.1.5)Now ker(T ) is not just a set of vectors, it is itself a vector space, that is a vector subspaceof V . Indeed, one sees immediately that if x and y belong to ker(T ) and α and β are scalars,thenT (αx + βy) = αT (x) + βT (y) = 0,(3.1.6)so αx + βy belongs to ker(T ) also.Since ker(T ) is a vector space, we can speak of its dimension. If ν = dim ker(T ), then νis called the nullity of the mapping T .Consider also the set of vectors w of W that are of the form w = T v, for some vectorv ∈ V (possibly many such v’s exist). This set is called the image of T , and is writtenim(T ) = {w ∈ W | w = T v, v ∈ V }.(3.1.7)84Numerical linear algebraOnce again, we remark that im(T ) is more than just a set of vectors, it is in fact a vectorsubspace of W , since if w0 and w00 are both in im(T ), and if α and β are scalars, then wehave w0 = T v0 and w00 = T v00 for some v0 , v00 in V .

Henceαw0 + βw00 = αT v0 + βv00 = T (αv0 + βv00 )(3.1.8)so αw0 + βw00 lies in im(T ), too.The dimension of the vector (sub)space im(T ) is called the rank of the mapping T .A celebrated theorem of Sylvester asserts thatrank(T ) + nullity(T ) = dim(V ).(3.1.9)By the rank of a matrix A we mean any of the following:(a) the maximum number of linearly independent rows that we can find in A(b) same for columns(c) the largest number r for which there is an r × r nonzero sub-determinant in A (i.e., aset of r rows and r columns, not necessarily consecutive, such that the r × r submatrixthat they determine has a nonzero determinant.It is true that the rank of a linear mapping T from V to W is equal to the rank of anymatrix A that represents T with respect to some pair of bases of V and W .It is also true that the rank of a matrix is not computable unless infinite-precisionarithmetic is used.

In fact, the 2 × 2 matrix"111 1 + 10−20#(3.1.10)has rank 2, but if the [2,2]-entry is changed to 1, the rank becomes 1. No computer programwill be able to tell the difference between these two situations unless it is doing arithmeticto at least 21 digits of precision. Therefore, unless our programs do exact arithmetic onrational numbers, or do finite field arithmetic, or whatever, the rank will be uncomputable.What we are saying, really, is just that the rank of a matrix is not a continuous function ofthe matrix entries.Now we are ready to consider one of the most important problems of numerical linearalgebra: the solution of simultaneous linear equations.Let A be a given m × n matrix, let b be a given column vector of length m, and considerthe systemAx = b(3.1.11)of m linear simultaneous equations in n unknowns x1 , x2 , .

. . , xn .Consider the set of all solution vectors x of (3.1.11). Is it a vector space? That’s right,it isn’t, unless b happens to be the zero vector (why?).3.1 Vector spaces and linear mappings85Suppose then that we intend to write a computer program that will in some sense presentas output all solutions x of (3.1.11).

What might the output look like?If b = 0, i.e., if the system is homogeneous, there is no difficulty, for in that case thesolution set is ker(A), a vector space, and we can describe it by printing out a set of basisvectors of ker(A).If the right-hand side vector b is not 0, then consider any two solutions x0 and x00 of(3.1.11). Then Ax0 = b, Ax00 = b, and by subtraction, A(x0 −x00 ) = 0. Hence x0 −x00 belongsto ker(A), so if e1 , e2 , .

. . , eν are a basis for ker(A), then x0 − x00 = α1 e1 + α2 e2 + · · · + αν eν .If b 6= 0 then, we can describe all possible solutions of (3.1.11) by printing out oneparticular solution x00 , and a list of the basis vectors of ker(A), because then all solutionsare of the formx = x00 + α1 e1 + α2 e2 + · · · + αν eν .(3.1.12)Therefore, a computer program that alleges that it solves (3.1.11) should print out abasis for the kernel of A together with, in case b 6= 0, any one particular solution of thesystem.

We will see how to accomplish this in the next section.Exercises 3.11. Show by examples that for every n, the rank of a given n×n matrix A is a discontinuousfunction of the entries of A.2. Consider the vector space V of all polynomials in x of degree at most 2. Let T be thelinear mapping that sends each polynomial to its derivative.(a) What is the rank of T ?(b) What is the image of T ?(c) For the basis {1, x, x2 } of V , find the 3 × 3 matrix that represents T .(d) Regard T as a mapping from V to the space W of polynomials of degree 1. Usethe basis given in part (c) for V , and the basis {1, x − 1} for W , and find the2 × 3 matrix that represents T with respect to these bases.(e) Check that the ranks of the matrices in (c) and (d) are equal.3. Let T be a linear mapping of Euclidean 3-dimensional space to itself.

Suppose T takesthe vector (1, 1, 1) to (1, 2, 3), and T takes (1, 0, −1) to (2, 0, 1) and T takes (3, −1, 0)to (1, 1, 2). Find T (1, 2, 4).4. Let A be an n × n matrix with integer entries having absolute values at most M .What is the maximum number of binary digits that could be needed to represent allof the elements of A?5. If T acts on the vector space of polynomials of degree at most n according to T (f ) =f 0 − 3f , find ker(T ), im(T ), and rank(T ).6. Why isn’t the solution set of (3.1.11) a vector space if b 6= 0?86Numerical linear algebra7. Let aij = ri sj for i, j = 1, .

. . , n. Show that the rank of A is at most 1.8. Suppose that the matrix0 11A =  1 0 −1 −2 11(3.1.13)represents a certain linear mapping from V to V with respect to the basis{(1, 0, 0), (0, 1, 0), (1, 1, 1)}(3.1.14)of V . Find the matrix that represents the same mapping with respect to the basis{(0, 0, 1), (0, 1, 1), (1, 1, 1)}.(3.1.15)Check that the determinant is unchanged.9.

Find a system of linear equations whose solution set consists of the vector (1, 2, 0)plus any linear combination of (−1, 0, 1) and (0, 1, 0).10. Construct two sets of two equations in two unknowns such that(a) their coefficient matrices differ by at most 10−12 in each entry, and(b) their solutions differ by at least 10+12 in each entry.3.2Linear systemsThe method that we will use for the computer solution of m linear equations in n unknownswill be a natural extension of the familiar process of Gaussian elimination.

Let’s begin witha little example, say of the following set of two equations in three unknowns:x+y+z =2(3.2.1)x − y − z = 5.If we subtract the second equation from the first, then the two equations can be writtenx +y + z = 22y + 2z = −3.(3.2.2)We divide the second equation by 2, and then subtract it from the first, gettingx7=2y + z = − 32 .(3.2.3)The value of z can now be chosen arbitrarily, and then x and y will be determined.

Tomake this more explicit, we can rewrite the solution in the form7x0  23  y  =  − 2  + z  −1  .z10(3.2.4)3.2 Linear systems87In (3.2.4) we see clearly that the general solution is the sum of a particular solution(7/2, −3/2, 0), plus any multiple of the basis vector (0, −1, 1) for the kernel of the coefficient matrix of (3.2.1).The calculation can be compactified by writing the numbers in a matrix and omittingthe names of the unknowns. A vertical line in the matrix will separate the left sides andthe right sides of the equations.

Thus, the original system (3.2.1) is"111 21 −1 −1 5#.(3.2.5)−→ 2) := (−−→ 1) − (−−→ 2) and we haveNow we do (−rowrowrow"1 1 120 2 2 −3#.(3.2.6)−→ 2) := (−−→ 2)/2, and then (−−→ 1) := (−−→ 1) − (−−→ 2) bring us to the final formNext (−rowrowrowrowrow"71 0 020 1 1 − 32#(3.2.7)which is the matrix equivalent of (3.2.3).Now we will step up to a slightly larger example, to see some of the situations thatcan arise. We won’t actually write the numerical values of the coefficients, but we’ll useasterisks instead.

So consider the three equations in five unknowns shown below.∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ .∗ ∗ ∗ ∗ ∗ ∗(3.2.8)The first step is to create a 1 in the extreme upper left corner, by dividing the first rowthrough by the [1,1] element. We will assume for the moment that the various numbersthat we want to divide by are not zero. Later on we will take extensive measures to assurethis.After we divide the first row by the [1,1] element, we use the 1 in the upper left-handcorner to zero out the entries below it in column 1.

That is, we let t = a21 and then doThen let t = a31 and do−−→−→ − t ∗ −−→row(2):= −row(2)row(1).(3.2.9)−−→−→ − t ∗ −−→row(3):= −row(3)row(1).(3.2.10)The result is that we now have the matrix1 ∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ ∗ .0 ∗ ∗ ∗ ∗ ∗(3.2.11)88Numerical linear algebraWe pause for a moment to consider what we’ve done, in terms of the original set ofsimultaneous equations. First, to divide a row of the matrix by a number correspondsto dividing an equation through by the same number. Evidently this does not changethe solutions of the system of equations.

Характеристики

Список файлов книги