Chương 1 KIẾN THỨC CHUẨN BỊ 1.1 Một số dạng ma trận Định nghĩa 1. Ma trận A ∈ Mn được gọi là ma trận chuẩn tắc nếu A∗ A = AA∗ , nghĩa là A giao hoán với dạng Hermit của nó. Nếu A ∈ Mn là ma trận Hermit và x∗ Ax ≥ 0 với mọi x ∈ C n thì tất cả các trị riêng của A đều không âm. Hơn nữa, nếu Tr(A) = 0 thì A = 0.
Cho A ∈ Mn là một ma trận Hermitt có các trị riêng được sắp xếp theo thứ tự λmin = λ1 ≤ λ2 ≤. Khi đó λ1 xH x ≤ xH Ax ≤ λn xH x, ∀x ∈ C n xH Ax λmax = λn = max = max xH Ax, x6=0 xH x xH x=1 xH Ax λmin = λn = min H = min xH Ax. Cho A = [aij ] ∈ Mn và đặt n X Ri (A) = |aij |, 1≤i≤n j=1,j6=i nghĩa là tổng theo dòng, ngoại trừ phần tử trên đường chéo chính. Khi đó mọi trị riêng của A đều nằm trong hội các đĩa n [ {z ∈ C : |z − aii | ≤ Ri (A)} ≡ G(A).
i=1 8 9 Hơn nữa, nếu có một hội k đĩa của n đĩa tạo thành một miền liên thông và tách rời khỏi n − k đĩa còn lại, thì A có đúng k trị riêng nằm trong miền này. G(A) trong định lý trên được gọi là miền Geršgorin; từng đĩa đơn đươc gọi là đĩa Geršgorin và biên của chúng được gọi là đường tròn Geršgorin. Ta nói A ≥ 0 nếu mọi phần tử aij là số thực không âm; A > 0 nếu mọi aij là số thực dương. Ma trận A ∈ Mn được gọi là ma trận khả quy nếu thỏa một trong hai điều sau i) n = 1 và A = 0; hoặc ii) n ≥ 2 và tồn tại một ma trận hoán vị P ∈ Mn và số tự nhiên r với 1 ≤ r ≤ n − 1 sao cho B C P T AP = (1.1) 0 D với các ma trận khối B ∈ Mr , D ∈ Mn−r , C ∈ Mr,n−r và 0 ∈ Mn−r,r.
Ngược lại, một ma trận được gọi là bất quả quy nếu nó không thỏa cả hai tính chất trên. Tập hợp tất cả các trị riêng λ của A ∈ Mn được gọi là phổ của A, và được ký hiệu là σ(A). Bán kính phổ của A là số thực không âm ρ(A) = max{|λ| : λ ∈ σ(A)}. Cho A ∈ Mn là một ma trận không âm A ≥ 0 và bất khả quy.
ρ(A) là một trị riêng của A; 3. Tồn tại một vecto, gọi là vecto Perron, x ∈ C n , x > 0 thỏa Ax = ρ(A)x; 4. ρ(A) là trị riêng đơn tức có bội đại số bằng bội hình học và bằng 1. Cho A ∈ Mn là một ma trận dương, A > 0, Khi đó 1.
ρ(A) là một trị riêng của A; 3. Tồn tại một vecto, gọi là Perron vecto, x ∈ C n , x > 0 thỏa Ax = ρ(A)x; 10 4. |λ| < ρ(A) với λ là trị riêng bất kỳ của A và λ 6= ρ(A), tức ρ(A) là trị riêng duy nhất có độ dài lớn nhất; −1 k 6. Một ma trận không âm A ∈ Mn , A ≥ 0 được gọi là ma trận chính nếu nó bất khả quy và có duy nhất một trị riêng lớn nhất (theo modulus).
Cho ma trận A ∈ Mn 1. A được gọi là ma trận ngẫu nhiên (dòng) nếu tổng các phần tử trên mỗi dòng bằng +1. Ma trận ngẫu nhiên là chuyển vị của ma trận ngẫu nhiên dòng; 2. A là ma trận ngẫu nhiên kép (doubly stochastic matrix) nếu A và AT đều là ma trận ngẫu nhiên.
Tập các ma trận ngẫu nhiên là một tập lồi và mỗi ma trận trong đó có cặp (trị riêng, vecto riêng) là (1,1). Cho A ∈ Mn là một ma trận chính và không âm A ≥ 0, khi đó k lim ρ(A)−1 A =L>0 k→∞ với L = xy T , Ax = ρ(A)x, AT y = ρ(A)y, x > 0, y > 0 và xy T = 1. Ma trận A = [aij ] ∈ Mn được gọi là SIA (stochastic, indecompos- able, aperiodic) nếu i) aij ≥ 0 với mọi 0 ≤ i, j ≤ N ; P ii) 0≤j≤N aij = 1 với mọi 0 ≤ i ≤ N ; iii) Giới hạn Q = lim Ak k→∞ tồn tại trong Mn và ma trận Q có các hàng bằng nhau. Ta thấy ma trận ngẫu nhiên, chính cũng là SIA vì thỏa i), ii) và iii) theo định lý 1.
Cho {Ak } là một họ các ma trận SIA trong Mn. Đặt δ(A) = max max |ai1 j − ai2 j |, ta có 0≤j≤N 0≤i1 ,i2 ≤N lim δ (Ak1. Ma trận C ∈ Mn có dạng c1 c2 c3 · · · cn n c1 c2 · · · c cn−1 C = cn−1 cn c1 · · · cn−2 . c2 c3 c4 · · · c1 được gọi là ma trận vòng (circulant matrix).
Như vậy ma trận vòng là một ma trận vuông trong đó mỗi dòng được tạo bởi việc xoay vòng phần tử cuối của dòng trước đó. Dòng đầu tiên (c1 ,. , cn ) là dòng khởi điểm và ký hiệu là A = circ(c1 ,. Ma trận Fourier F bậc M là ma trận với các phần tử có dạng 2πi ajk = ω jk , ω = e M , 0 ≤ j, k ≤ M − 1.
Cụ thể 1 1 1 ··· 1 1 ω1 ω2 ··· ω M −1 1 1 ω2 ω4 ··· ω M −2 2πi F =√ , ω =eM. Tính chất của ma trận Fourier F 1. F là ma trận unita và chính tắc: F F H = F H F = 1; 4. Các vecto hàng (cột) của F vuông góc với nhau.
Từ định nghĩa ma trận vòng và ma trận Fourier, ta có kết quả sau : Mọi ma trận vòng C = circ(v) đều chéo hoá được thành dạng C = F ΛF H trong đó F là ma trận √ Fourier, F H là dạng Hermit của F .,k tức trị riêng √ thứ k của C được tính bằng cách nhân hàng 1 của C với cột k của F , bỏ qua hệ số M .2 Chuẩn ma trận Định nghĩa 1.k : Mn → R được gọi là chuẩn ma trận nếu thỏa các điều sau với mọi A, B ∈ Mn i) kAk ≥ 0, kAk = 0 ⇔ A = 0; ii) kcAk = |c|kAk, ∀c ∈ C ; iii) kA + Bk ≤ kAk + kBk; iv) kABk ≤ kAk. Một số ví dụ về chuẩn i) kAkL1 = ni,j=1 |aij |; P P 1/2 n 2 ii) kAkL2 = |a i,j=1 ij | ; iii) kAkL∞ = max |aij |.k là một chuẩn vecto trên C n. Định nghĩa chuẩn k.k trên Mn là kAk = max kAxk. kxk=1 Ở đây ta dùng "max" thay cho "sup" thông thường trong định nghĩa chuẩn cho toán tử tuyến tính vì A là toán tử tuyến tính liên tục trên một quả cầu đóng B = {x : kxk ≤ 1}.
Từ định nghĩa này ta có thêm một số chuẩn được suy ra từ chuẩn vecto tương ứng Pn i) kAk1 = max i=1 |aij | 1≤j≤n Pn ii) kAk2 = max j=1 |aij | 1≤i≤n √ iii) kAk∞ = max{ λ : λ là trị riêng của A∗ A}.k là một chuẩn ma trận và A ∈ Mn , thì ρ(A) ≤ kAk.k là một chuẩn ma trận trên Mn và A ∈ Mn , khi đó ρ(A) = lim kAk k1/k .3 Đồ thị Định nghĩa 1. Đồ thị không định hướng Γ là một tập hợp n node {P1 , P2 , ., Pn } và một tập E những những cặp không thứ tự các node được gọi là cạnh (edge) , E = {{Pi1 , Pj1 }, {Pi2 , Pj2 },. Đồ thị Γ có thể biễu diễn thông qua một ma trận kề (adjacency matrix) được định nghĩa như sau 1 {Pi , Pj } ∈ E aij = 0 {Pi , Pj } ∈ /E. Một đồ thị định hướng của A ∈ Mn , ký hiệu bởi Γ(A), là một đồ thị trên n node P1 , P2 , ., Pn sao cho có một hình cung (arc) đi từ Pi đến Pj khi và chỉ khi aij 6= 0 Định nghĩa 1.
Đồ thị đơn là một đồ thị không định hướng, không có vòng lặp (cạnh bắt đầu và kết thúc tại cùng một node) và không có nhiều hơn một cạnh giữa hai node khác nhau. Cho một đồ thị đơn Γ có n node, khi đó ma trận Laplace Ln×n của G được định nghĩa L=D−A trong đó A là ma trận kề (adjacency matrix) 1 {Pi , Pj } ∈ E Aij := 0 {Pi , Pj } ∈ /E và ma trận bậc (degree matrix) D là ma trận đường chéo n X Dii = Aij. 0 0 −1 1 0 0 0 1 0 0 0 0 0 1 0 −1 −1 0 0 2 1 1 0 0 0 0 0 0 0 2 Một số tính chất của ma trận Laplace L i) L là ma trận nửa xác định dương; 14 ii) L có các trị riêng thực và 0 = λ1 ≤. ≤ λn ; iii) Lỗ hổng phổ (spectral gap) là trị riêng nhỏ nhất khác 0; iv) Bội của trị riêng λ = 0 bằng với số thành phần liên thông của L.
Một đường đi trực tiếp (directed path) γ trong đồ thị Γ là một dãy các hình cung Pi1 , Pi2 , Pi2 , Pi3 , Pi3 , Pi4. Một danh sách có thứ tự các node trong một đường đi trực tiếp γ là Pi1 , Pi2 , Pi3 , Pi4. Độ dài của đường đi trực tiếp là số lượng các hình cung liên tục nếu nó hữu hạn, ngược lại ta gọi đường đi trực tiếp có độ dài vô hạn. Một chu trình là một đường đi trực tiếp mà bắt đầu và kết thúc tại cùng một node; do đó nó xuất hiện hai lần trong danh sách có thứ tự các node; các node khác chỉ xuất hiện không quá một lần Chu trình có độ dài "1" được gọi là chu trình tầm thường.
Một đồ thị dịnh hướng Γ được gọi là liên thông mạnh nếu giữa hai node bất kỳ Pi , Pj , i 6= j đều tồn tại một đường đi trực tiếp giữa chúng và có độ dài hữu hạn. Đồ thị của A ∈ Mn được gọi là cân bằng nếu ∀i ≤ n, i6=j aij = P i6=j aji. Chương 2 CONSENSUS VÀ HÒA TRỘN CHẤT LỎNG Chương này trình bày ngắn gọn về phương trình đạo hàm riêng mô tả quá trình khuếch tán-bình lưu và việc sai phân phương trình này trên một lưới đều dẫn tới thuật toán consensus.
