1Preliminaries Lecture-2Eigen Vectors and Eigen ValuesThe eigen vector, x, of a matrix A is a special vector, with the following property xAxλ=Where λ is called eigen value0)det(=−IAλTo find eigen values of a matrix A first find the roots of:Then solve the following linear system for each eigen value to find corresponding eigen vector0)(=−xIAλ2Example−=700430021A1 ,3 ,7321−===λλλ===001 ,021 ,441321xxxEigen ValuesEigen VectorsEigen Values0)det(=−IAλ0)100010001700430021det( =−−λ0)700430021det( =−−−−λλλ7 3, ,10)7)(3)(1(0)0)7)(3)((1(==−==−−−−=−−−−−λλλλλλλλλ3Eigen Vectors0)(=− xIAλ=+−000)100010001700430021(321xxx=000800440020321xxx0 ,0 ,10800044000203213322====++=++=++xxxxxxx=0011x1−=λDeterminant ∑==niiiAAtrace1)(orthogonal is , QIQQQQTT==eseigen valu are where)(1iniiAtraceλλ∑==iniA∏==1)det(λ))(det(detdet BAAB =singular isA ifonly and if 0det =AAAdet1det1=−TQQ =−11detdet ±==TQQ4Rotation matrices are Orthogonal (orthonormal) MatricesΘΘΘΘ−=−1000cossin0sincos)(1ZRθ=ΘΘΘ−ΘΘΘΘΘ−1000100011000cossin0sincos1000cossin0sincosIRRRRTZZTZZ==−))(()()(1θθθθPositive-definite.0 if definite positive ismatrix n n symetricA >×AXXT• All diagonal elements of a positive-definite matrix are strictly positive• Negative definite matrix has all negative eigenvalues• If all eigenvalues of a symmetric matrix are non-negative, it is said to be Positive semi-definite• If a matrix has both positive and negative eigenvalues, it is said to be indefinite5Matrix Factorizationngular upper tria a is Uand ngular,Lower tria a is L ion,decomposit LU ,LUA =matrixagular upper trin is U l,orthonorma is C ion,decompoist QR ,CUA =Singular Value Decomposition (SVD)Theorem: Any m by n matrix A, for which ,can be written as 21OOAΣ=mxnnxn nxnmxnis diagonalare orthogonalΣ21,OOIOOOOTT==2211nm ≥6Singular Value Decomposition (SVD)• For some linear systems Ax=b, Gaussian Elimination or LU decomposition does not work, because matrix A is singular, or very close to singular. SVD will not only diagnose for you, but it will solve it.Singular Value Decomposition (SVD)If A is square, then are all square.21,, OOΣTTOOOO212111==−−)1(1jwdiag=Σ−121)1( OwdiagOAj=−7Singular Value Decomposition (SVD)The condition number of a matrix is the ratio of the largest of the to the smallest of . A matrix is singular if the condition number is infinite, it is ill-conditioned if the condition number is too large.jwjwSingular Value Decomposition (SVD)bAx=• If A is singular, some subspace of “x” maps to zero; the dimension of the null space is called “nullity”.• Subspace of “b” which can be reached by “A” is called range of “A”, the dimension of range is called “rank” of A.8Range and Null SpacexAx=bbRange of ADimension of range is rank of A b=0Null space of ADimension of Null space is Nullity Singular Value Decomposition (SVD)• If A is non-singular its rank is “n”.• If A is singular its rank <n.• Rank+nullity=n9Singular Value Decomposition (SVD)• SVD constructs orthonormal basses of null space and range.• Columns of with zero spans null space.jw2O• Columns of with non-zero spans range.1Ojw21OOAΣ=Solution of Linear System• How to solve Ax=b, when A is singular?• If “b” is in the range of “A” then system hasmany solutions.• Replace by zero if0=jwjw1bOwdiagOxTj12)]1([=10Solution of Linear SystemIf b is not in the range of A, above eq still givesthe solution, which is the best possible solution, it minimizes: || bAxr−≡Cholesky FactorizationA positive-definite symmetric matrix A can be written:TLDLA=L is unit lower triangular matrixD is a diagonal matrix with strict Positive elementsare general lower triangular and general upper triangular matricesRL ,RRLLLDLDATTT===212111Spectral Decomposition of A Symmetric MatrixiiiuAuλ=TiiniiTuuUUA∑==Α=1λNormsnorm vector |,|||||11∑==niixXnorm vector ,)()(|||||2121122XXxXTnii==∑=normmatrix ,||||||||max1||||XxAA==|1|||||max1ijnianj∑==≤≤∞A12Condition Number||||||||)(number Condition 1−= AAAkone.an greater thtly significan is K(A) when d,conditione-not well is and one toclose is K(A) if dconidtione- wellisA matrix The1-D FunctionsFinding the zero of a function13Bisection Method•Find a solution to f(x)=0 on the interval [a,b], where f(a)<0 and f(b)>0 have opposite signs.–Compute the mid point,m, of [a,b], if f(m)=0, then done– else if f(m)>0, then b=m, else a=mnnabpp2||−≤−Bisection Methodf(x)abx1x2x14Newton’s MethodxpxxfbaCfbaf around seriesTaylor small. is || ,0)(].,[ is that ];,[ interval on the abledifferentiy continousltwiceisfunction that theSuppose2−≠′∈. and between lies )( )),((2)()()()()(2xxxpfxxxfxxxfxfξξ′′−+′−+=small. is || )()()(0)( pxxfxpxfpf−′−+≈=)()(xfxfxp′−=)()(111−−−′−=nnnnpfpfppNewton’s Methodf(x)pn-1pn11)()()(−−−−=′nnnnnpppfpfpfZero of the tangent line11)(0)(−−−−=′nnnnpppfpf)()(11nnnnpfpfpp′−=−−f(pn-1)f(pn)15Secant Method)()())((212111−−−−−−−−−=nnnnnnnpfpfpppfppIf derivative can not be computed Use finite difference approximation)()(11nnnnpfpfpp′−=−−Theorem].,[ion approximat initialany for to converging sequence a generates method sNetwon'such that 0 exists e then ther,0)( and0)(such that is ],[ If ].,[Let