diff options
| -rw-r--r-- | li/02_solving | 40 | ||||
| -rw-r--r-- | zhilova/02_set_theory | 102 |
2 files changed, 142 insertions, 0 deletions
diff --git a/li/02_solving b/li/02_solving new file mode 100644 index 0000000..ae67d6b --- /dev/null +++ b/li/02_solving @@ -0,0 +1,40 @@ +Ax = b where A = mxn, x = 1xm, b = 1xn. x_i and b_i are defined to be in +the ith row of their corresponding vectors. + +If C is an invertible mxm matrix, CAx = Cb is equivalent to Ax = b. +(1) + If x_0 satisfies Ax_0 = b, CAx_0 = Cb is satisfied. +(2) + If x_1 satisfies CAx_0 = Cb, C^{-1} CAx_0 = C^{-1} Cb \to Ax_0 = b + is satisfied. + +(I believe this proof requires associativity) + + LU Decomposition/Factorization + +Goal: Factorize A into a lower triangular and upper triangular matrices +L and U respectively. (These are very non-unique) + +A = LU. Conventionally, L is mxm, and U is mxn. +Ax = b ---> LUx = b ---> Y = Ux, LY = b. + +If we assert that L is an invertible matrix (e.g. ones down the +diagonal), this is trivial to solve + 1 0 0 y1 b1 +( c21 1 0 ... ) * ( y2 ) = ( b2 ) + c31 c32 1 y3 b3 + ... ... ... +Y has a unique solution by construction. ( ex: y1 = b1, c21*y1 + y2 = b2 ...) + +U is upper triangular, meaning that it is strictly zero below the +diagonal started at the top-left. (However, we have no control over the +values of the diagonal or the values above the diagonal) + +[Note] How do we ensure that L and U retain the properties of the +original matrix's solution? (i.e. not just matrices of zero) + +Using a series of row operations (written as invertible matrices C_1, +C_2, ..., C_k -- that is, adding a multiple to a lower row) will turn A +into echelon (upper triangular), and C_1^{-1}C_2^{-1}*...*C_k^{-1} = L +(lower triangular). U is not reduced-echelon, but it is echelon/upper +triangular. diff --git a/zhilova/02_set_theory b/zhilova/02_set_theory new file mode 100644 index 0000000..1ed6be2 --- /dev/null +++ b/zhilova/02_set_theory @@ -0,0 +1,102 @@ +Review of Basic Set Theory: 1.2 + +Sets are represented by capital letters like A, B, C. + +Sets can be like {1, 2, 3, ...}, (0, 1), reals, R^k, etc. + + Operations + +A \cup B - union of A and B, refers to a set such that x \in A \cup B +iff x\in A OR x\in B. + +A \cap B - intersection, refers to a set such that x \in A \cup B iff +x\in A AND x\in B. + +A \setminus B (written as \) - difference, x\in A \setminus B iff x\in A +and x\not\in B + +B^c = \overbar{B} - complement, equivalent to \Omega \setminus B or +C \setminus B, where C or \Omega is the sample space of the problem. + +Universe ex: all possible combinations of two coin flips. + +Countable union: + + +\infty n + U A_i or U + i=1 i=1 + +Represents union of a list of indexed sets. + +Countable intersection is analagous. + +UNcountable intersection/union is a union or intersection over an +uncountable set like the reals or (0, 1). + +Symmetric difference: (A \union B) \setminus (A \cap B). (think of XOR) + + DeMorgan's Laws (and proofs) + +(A \cap B)^c = A^c \cup B^c + +Let x \in (A\cap B)^c \to x \not\in A \cap B. + +If x\in A, x\not\in B \to x\in B^c. If x\in B, x\not\in A \to x\in A^c. +Therefore, x\in A^C \cup B^c. + +(The proof the other way is similarly trivial) + +(A \cup B)^C = A^C \cap B^c + +These laws can be generalized to infinite unions (although not through +induction, which merely proves it for arbitrary large, finite sets). + +Prove: Let B be the union of all A^c where A \in C. x\in B iff x \in +(infinite intersection of all A where A \in C)^c + + +[Proof omitted at present] + + Distributive laws + +C_1 \cap (C_2 \cup C_3) = (C_1 \cap C_2) \cup (C_1 \cap C_3) +C_1 \cup (C_2 \cap C_3) = (C_1 \cup C_2) \cap (C_1 \cup C_3) + + Sample space and probability + +Example sample space is n ordered Bernoulli trials [finite] + or (0,1) or (0,1)^2 or R [continuous] + +C = { w_1, w_2, ... } where w_i is an elementary event. ??MUST?? be +countable. + +If A \subseteq C, A is an event (random event) in C. + + Probability set function + +Assign to each w_j a number p(w_j) \in [0, 1]. + +\sum_{j=1}^\infty p(w_j) = 1. +p_j := p(w_j) also known as random weights + +P(A) = \sum_{j : w_j \in A} p(w_j) [ the sum can be generalized to integral] + + Properties of P(A) + +P : subsets of C --> [0, 1] + +1) P(C) = 1 +2) \forall A \subseteq C, 0 \leq P(A) \leq 1 +3) If A_1, A_2 \subseteq C and A_1 \cap A_2 = \empty, + P(A_1 \cup A_2) = P(A_1) + P(A_2) +4) \forall A_1, A_2 \subseteq C, + P(A_1\cup A_2) = P(A_1) + P(A_2) - P(A_1 \cap A_2) +5) \forall A \subseteq C + P(A) + P(A^c) = 1. +6) P(\empty) = 0 +7) P(A) is nondecreasing: If A_1 \subseteq A_2 \subseteq C, +P(A_1) \leq P(A_2) + +sigma-algebra backed by C is a set which contains C, and is closed under +countable union and complement w.r.t C. (these are not unique, e.g. +{C, \empty} and P(C) are both valid sigma-algebras). |