【正文】 （ Mandelbrot） 167。 A fractal is a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reducedsize copy of the whole, a property called selfsimilarity NOVA紀(jì)錄片： hunting the hidden dimension ―尋找隱藏的維度” 4‘30?‘， 26‘30‘? ， 30‘00‘? ? 分形應(yīng)用： 計(jì)算機(jī)虛擬現(xiàn)實(shí)技術(shù)；天線設(shè)計(jì)；醫(yī)學(xué)； 分形 fractal 科赫雪花（ Koch snowflake）： 初始為正三角形； 將每條邊等分三段； 以中段為底向外做等邊三角形 移除被三等分的邊的中段。) 0 10 20 3000 . 20 . 40 . 60 . 81f ( x ) = 1 x0 10 20 301 0 . 500 . 511 . 52x 1 08 f ( x ) = 2 * ( 1 1 . 5 x )0 10 20 3000 . 10 . 20 . 30 . 40 . 5f ( x ) = ( 1 + 1 0 x ) / 1 20 10 20 3000 . 10 . 20 . 30 . 40 . 5f ( x ) = ( 1 + x ) / 3振蕩序列 收斂序列 發(fā)散序列 收斂序列 ? 迭代法的核心問題： – 迭代函數(shù)收不收斂 – 收斂速度快不快 ? 借助于計(jì)算機(jī)，用迭代法對(duì) 分形的研究更加簡(jiǎn)單化 例 2： 迭代法用于 分形 (fractal)研究 分形 是 一種粗糙的或分裂 的 幾何形狀 ， 其每一部分都是整體的縮小比例的復(fù)制 （自相似性） 分形是具有 自相似性 的 幾何形狀 。) ? title(39。 ? plot(x1, 39。 ? for iii = 2 : N ? x1(iii) = 1 x1(iii 1)。 如何利用迭代法解方程？ ? 迭代法基本原理： 如果迭代序列｛ x（ k+1） = ? (x（ k） )｝ 收斂， 則其極限點(diǎn) x*為方程 ? (x)= x 的解。 (Iterative method: attempts to solve a problem by finding successive approximations to the solution starting from an initial guess；（ es from wikipedia） ) ? 應(yīng)用很廣： ?線性方程組求解、非線性方程求解、非線性方程組求解、特征值求解、最優(yōu)化方法、分形等，以及數(shù)字信號(hào)處理中的維納濾波、卡爾曼濾波等等都要用到 迭代法 ? 典型方法： ?數(shù)值計(jì)算： Jacobi法、 GaussSeidel法 、 Newton迭代法、最快下降法（ Steepest Descent） ?迭代法解一般 (非線性 )方程 ? 迭代序列的 基本公式 ： ( 1 ) ( ) 0( ) ,kkx x x a?? ???(x)為：任意 n維空間到 n維空間的函數(shù)。2,1] X=[3 5] norm(A,1), norm(A,inf) norm(X,1), norm(X,inf) 167。 因 ?任意性，則有 1( ) m a x | | || ||in iAA???????若 （最大特征根）， 則 ?02 必是 A2 的最大特征根。 定理 對(duì)任意算子范數(shù) || A / D()xt ()xnL T I()xt ()ynA / D()yt離 散L T I()yn可表示為矩陣形式 0000 0 0( ) ( )0 0 ... 00 0 0aay n ax n x ya????? ? ?????1)尺度算子： LTI：線性時(shí)不變系統(tǒng) ? 為什么叫做 “ 算子范數(shù) ” ？ ? 線性時(shí)不變算子 的矩陣表示 ?線性時(shí)不變 算子的矩陣表示 1 1 0 0 0 ( 1 ) ( 2) ( 1 )0 1 .. . 0 0 ( 2) ( 3 ) ( 2)( ) ( 1 ) ( ) 0 0 .. . 1 0 .. . .. .0 0 0 1 1 ( 1 ) ( ) ( 1 )0 0 0 0 1 ( ) 0 ( )x x xx x xy n x n x nx n x n x nxn xn??? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ??2)差分算子 1111( 1 )1 0 0 0 0 ( 1 ) ( 1 ) ( 2)1 1 .. . 0 0 ( 2) ...( ) ( ) 1 1 .. . 0 0 .. .()1 1 1 1 0 ( 1 )1 1 1 1 1 ( )()nniinixx xxxy n x ixixnxnxi????????? ? ? ? ???? ? ? ???? ? ? ???? ? ? ?? ? ???? ? ? ????? ? ? ???? ? ? ?? ? ? ? ?????????3)累加算子 不考慮邊界問題 0 0 0 0 0 ( 1 ) 01 0 .. . 0 0 ( 2 ) ( 1 )( ) ( 1 ) 0 1 .. . 0 0 .. . .. .0 0 .. . 0 0 ( 1 ) ( 2 )0 0 0 1 0 ( ) ( 1 )xxxy n x nx n x nx n x n? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ??? ? ? ? ? ?4)時(shí)移算子 用 D表示 線性微分方程 0 1 2 0 1 2( 1 ) ( 2 ) ( 1 ) ( 2 )0 1 2 0 1 2( 1 ) ( 2 ) ( ) ( 1 ) ( 2) ( ) ( 1 ) ( 2) a x n a x n a x n b y n b y n b y na I a D a D x b I b D b D yDD? ? ? ? ? ? ? ? ?? ? ? ?? ? ? ? ?? ? ? ?可 記 為 ：其 中 ， ， 為 一 階 ， 二 階 時(shí) 移 算 子?線性時(shí)不變 算子的矩陣表示 0 0 0 1 0 2 0 ( 1 )1 0 1 1 1 2 1 ( 1 )( 1 ) 0 ( 1 ) 1 ( 12 2 2 22 2 2 22102 2 2) 2 ( 1 ) ( 1 )2......( ) ( )... ... ... ... ...... ... ... ... ......j j j jN N N Nj j j jN N N NNj k iNijjNNjjNN N N N NN N Ne e e ee e e ey k e x ie e e e? ? ? ?? ? ? ??? ? ? ?? ? ? ?? ? ? ?? ? ? ??????? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ????( 0) ( 0)( 1 ) ( 1 ) ... ...( 1 ) ( 2)( 1 ) ( 1 )xyxyx N y Nx N y N????????????? ? ? ?? ? ? ?? ? ? ?? ? ? ???? ? ? ???? ? ? ?? ? ? ???? ? ? ?5)傅立葉變換 ?線性時(shí)變 算子的矩陣表示 ?譜半徑 （討論特征根與范數(shù)的關(guān)系 ） 矩陣 A的 譜半徑 記為 ? (A) = ，其中 ?i 為 A 的特征根。 所以有些矩陣范數(shù)又叫做 “算子范數(shù)”。 ||F不是算子范數(shù) 求矩陣的算子范數(shù) ? 例：已知矩陣 A，求算子 1范數(shù)和算子 ∞ 范數(shù)。 vvF xxAAx ||||||||m ax||||0 ???? ??注： Freebies范數(shù)不是算子范數(shù) 021|| |||| || 1 m a x 1|| ||xnvFi vIxInx???? ? ??設(shè) A＝ I（單位陣），其 || 否則，必存在某個(gè)向量范數(shù) || 即使 A中元素全為實(shí)數(shù)，其特征根和相應(yīng)特征向量 仍可能是復(fù)數(shù)。 ||2的直接推廣 對(duì)方陣 以及 有 nnRA ?? nRx??22 |||||||||||| xAxA F ?? ??2. 算子 范數(shù) 由向量范數(shù) || 0||||)1( ???? AAA （ 正定性 ) ||||||||||)2( AA ?? ?? C??對(duì)任意 (齊次性 ) ||||||||||||)3( BABA ??? （ 三角不等式 ) (4) || AB || ? || A || ? 矩陣范數(shù)（ Matrix norm） Rm?n空間的 矩陣范數(shù) || 定義： 收斂意義上的等價(jià)，即在不同范數(shù)下的收斂性是一致的 定理 Rn 上一切范數(shù)都等價(jià)。 0 0niix x x?? ? ??x1xx0?x√ aa?xx√ ? ? ?x y x y√ 不滿足性質(zhì) 2 aa?xx 不滿足性質(zhì) 1 0? ? ?x x 0 ? 例：判斷下面定義式是否是向量范數(shù) （ 1） （ 2） ?向量范數(shù)應(yīng)用： 判斷向量的大小 12?xx 12?xx 向量不能比大小 √ 向量通過定義范數(shù)比大小 ? 最重要的用途之一： 分析向量收斂性，定義向量的極限： 向量序列 收斂 于向量 ,是指對(duì)每一個(gè) 1 ? i ? n 都有 。 || 對(duì)任意 滿足下列條件： nRyx ???,00||||。 向量和矩陣的范數(shù) ? 為了研究線性方程組 近似解的誤差估計(jì)和迭代法的收斂性， 引進(jìn)向量（矩陣）的 范數(shù) 的概念。0,1,4]。 4 1 01 4 10 1 4????????程序 A=[4,1,0。 12L LD ??1 / 2 1 / 2 1 / 2( ) ( )T T TU D L D L D D L? ? ?? 已知 cholesky分解 ， 求 LU分解 ： : TTA A x b A A x A b? ? ?如 果 秩 ， 有 滿 則 ?任意滿秩方程組求解，可轉(zhuǎn)化為對(duì)稱正定方程組求解。 即 L 的元素不會(huì)增大， 誤差可控， 不需選主元 。 0?xAx T ??x?定義： ?若 A為 n階滿秩方陣 ， 則有 ATA為對(duì)稱正定矩陣 ( ) ( ) 0T T Tx A A x A x A x?? 又 ∵ ATA為對(duì)稱矩陣 0TTx A Ax ?由于 A滿秩，即方程 A x = 0 只有 0解，所以任意 非零向量有： 根據(jù)正定矩陣定義， 則有 ATA為對(duì)稱正定矩陣 ?對(duì)稱正定矩陣 Cholesky分解： 證明： ∵ 先將 對(duì)稱 正定陣 A 做 LU 分解 ： U = uij = u11 uij / uii 1 1 1 u22 unn 記為 DU A 對(duì)稱 TUL ~? 即 1122() TTA LD LDLD L? ?記 D1/2 = 11u22unnuWhy is uii 0? Since det(Ak) 0 2/1~ LDL ?則 仍是下三角陣 TLLA ~~?nnLR??定理 設(shè)矩陣 A