09-240/Classnotes for Tuesday October 13

From Drorbn
Revision as of 03:26, 7 December 2009 by C8sd (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
WARNING: The notes below, written for students and by students, are provided "as is", with absolutely no warranty. They can not be assumed to be complete, correct, reliable or relevant. If you don't like them, don't read them. It is a bad idea to stop taking your own notes thinking that these notes can be a total replacement - there's nothing like one's own handwriting! Visit this pages' history tab to see who added what and when.

Replacement Theorem

...

  1. dim(V) = n
    1. If G generates V then |G| \ge n. If also \,\! |G| = n then G is a basis.
    2. If L is linearly dependent then |L| \le n. If also \,\! |L| = n then L is a basis. If also \,\! |L| < n then L can be extended to a basis. Proofs a1. If G has a subset which is a basis then that subset has n elements, so |G| \ge n.
      a2. Let \beta be a basis of V, then \,\! |B| = n. Now use replacement with G & L = \beta. Hence, |G| \ge |L| = |B| = n.
      a. From a1 and a2, we know |G| \ge n. If \,\! |G| = n then G contains a basis \beta. But \,\! |B| = n, so \,\! |G| = \beta, and hence G is a basis.

      b. Use replacement with G' being some basis of V. |G| = n.

      If |L| = |G| then |R| = n = |G|, so R = G, so (G \backslash R) \cup L generates, so L generates, so L is a basis since it is linearly independent.

      We have that L is basis. If |L| < |G| the nagain find R \subset G such that |R| = |L| and (G \backslash R) \cup L generates.

      1. \beta generates V.
      2. |B| \le |G| - |R| + |L| = n. So by part a, \beta is a basis.
      3.
  2. If V is finite-dimensional (f.d.) and \mathbf W \subset \mathbf V is a subspace of V, then W is also finite, and \operatorname{dim}(\mathbf W) \le \operatorname{dim}(\mathbf V). If also dim(W) = dim(V) then W = V and if dim(W) < dim(V) then any basis of W can be extended to a basis of V.

    Proof: Assuming W is finite-dimensional, pick a basis \beta of W; \beta is linearly independent in V so by Corollary 3 of part b, |B| \le \operatorname{dim}(\mathbf V) \Rightarrow \operatorname{dim}(\mathbf W) = |B| \le \operatorname{dim}(\mathbf V). So span(\beta) = V = W so V = W. ...

    Assume W is not finite-dimensional. \mathbf W \ne \{0\} so pick a x_1 \in W such that x_1 \ne 0. So \{x_1\} is linearly independent in W, and \operatorname{span}(\{x_1\}) \subsetneq \mathbf W. Pick x_2 \in W \backslash \operatorname{span}(\{x_1\}). So \{x_1, x_2\} is linearly dependent and \operatorname{span}(\{x_1, x_2\}) \subsetneq \mathbf W. Pick x_3 \in W \backslash \operatorname{span}(\{x_1, x_2\}) ... continue in this way to get a sequence x_1, x_2, \ldots, x_{n+1} where n = dim(V) and \{x_1, \ldots, x_{n+1}\} is linearly independent. There is a contradiction by Corollary 3.b.

The Lagrange Interpolation Formula

[Aside: (a - x)(b - x) \ldots (z - x) = 0 because x - x = 0]

Where 1 \le i < n,

Let x_i be distinct points in \real.

Let y_i be any points in \real.

Can you find a polynomial P \in \mathbb P_n(\real) such that P(x_i) = y_i? Is it unique?

Example:

x_i = 0, 1, 3
y_i = 5, 2, 2

Can we find a P \in \mathbb P_2 such that

P(0) = 5
P(1) = 2
P(2) = 2?

Solution: Let \tilde P_i(x) = \prod_{j=1, j \ne 1}^{n+1} (x - x_j) \in \mathbb P_n(\real). (Remember capital pi notation.)

Then \tilde P_i(x_k) = \begin{cases}
0 & i \ne k \\
\prod_{i \ne j} (x_i - x_j) & i = k \\
\end{cases}

\tilde P_1 = (x - x_2)(x - x_3) = (x - 1)(x - 3) = x^2 - 4x + 3
\tilde P_2 = (x - 0)(x - 3) = x^2 - 3x
\tilde P_3 = (x - 0)(x - 1) = x^2 - x


\begin{matrix}
\tilde P_1(0) = 3 & \tilde P_1(1) = 0 & \tilde P_1(3) = 0 \\
\tilde P_2(0) = 0 & \tilde P_2(1) = -2 & \tilde P_2(3) = 0 \\
\tilde P_3(0) = 0 & \tilde P_3(1) = 0 & \tilde P_3(3) = 6 \\
\end{matrix}

Set P_i(x) = \frac1{\tilde P_i(x)} \cdot \tilde P_i = \prod_{j \ne i} \frac{(x - x_j)}{(x_i - x_j)}

Then P_i(x_k) = \begin{cases}
0 & i \ne k \\
1 & i = k \\
\end{cases}

P_1(x) = \frac13 x^2 - \frac43 x + 1
P_2(x) = -\frac12 x^2 + \frac32 x
P_3(x) = \frac16 x^2 - \frac16 x

Let P = \sum_{i=1}^{n+1} y_i P_i(x) \in \mathbb P_n(\real)

P = 5 \cdot \left( \frac13 x^2 - \frac43 x + 1 \right) + 2 \cdot \left( -\frac12 x^2 + \frac32 x \right) + 2 \cdot \left( \frac16 x^2 - \frac16 x \right)
\,\! = x^2 - 4x + 5