Chương 1 Một số kiến thức cơ bản Trong chương này, Luận văn sẽ trình bày một số kiến thức cơ bản về không gian tuyến tính, Hệ trực chuẩn và quy tắc Gram Schmid, Một số kiến thức về vecto và ma trận, khái niệm về ma trận giả nghịch đảo. Mô hình bài toán tối ưu và thuật toán Gradient giải bài toán tối ưu không ràng buộc. Mô hình mạng Neural và một số thuật toán huấn luyện mạng trên cơ sở lý thuyết đại số tuyến tính và lý thuyết tối ưu. Các kiến thức được tham khảo trong các tài liệu [1],[2],[4],[5],[6].
Không gian vectơ tuyến tính Định nghĩa 1. Không gian vector tuyến tính E là một tập hợp các phần tử, gọi là vector, định nghĩa trên một trường vô hướng K thoả mãn các điều kiện sau: i) Tồn tại phép cộng (+): Với mọi X, Y ∈ E ⇒ X + Y ∈ E thỏa mãn các tính chất: – Tính giao hoán: X + Y = Y + X – Tính kết hợp: (X + Y ) + Z = X + (Y + Z) – Tồn tại phần tử θ ∈ E thỏa mãn: X + θ = θ + X = X – Tồn tại phần tử đối (−X) thỏa mãn: X + (−X) = (−X) + X = θ ii) Tồn tại phép nhân (×): Mọi số vô hướng a ∈ K, X ∈ E ⇒ a × X ∈ E, đồng thời thỏa mãn: 3 – Tồn tại phần tử đơn vị 1 của trường K thỏa mãn: 1 × X = X – Phép nhân thỏa mãn các tính chất: a × (b × X) = (a × b) × X; (a + b) × X = a × X + b × X; a × (X + Y ) = a × X + a × Y ∀a, b ∈ K; X, Y ∈ E., Xn được gọi là hệ độc lập tuyến tính nếu: α1 X1 + α2 X2 +. = αn = 0 Hệ vectơ không độc lập tuyến tính gọi là hệ phụ thuộc tuyến tính. Cơ sở, số chiều của không gian vectơ Số chiều của không gian vectơ E chính là số vectơ độc lập tuyến tính cực đại trong E.
Ta thường kí hiệu En là không gian vectơ có số chiều n. Khi đó, hệ vectơ độc lập tuyến tính cực đại lập nên một hệ cơ sở của không gian E. Tọa độ của vectơ Xét vectơ X ∈ E, giả sử {e1 , e2 , ., en } là một hệ cơ sở của E. Khi đó ta có khai triển X = x1 e1 + x2 e2 +.
+ xn en với x1 , x2 ,. Khi đó bộ số (x1 , x2 , ., xn ) được gọi là tọa độ của vectơ X trong hệ cơ sở {e1 , e2 ,. Từ đây, ta chỉ xét không gian tuyến tính E = Rn gồm các phần tử là các vectơ có tọa độ là các số thực. Trường K chỉ xét trường số thực R.
Không gian tích vô hướng Định nghĩa 1. Xét không gian tuyến tính E = Rn , ta đưa vào ánh xạ h.i : E × F → K thỏa mãn các tính chất: 4 i) Xác định dương: hX, Xi ≥ 0, ∀X ∈ E. ii) Tính tuyến tính: hX, αY + βZi = αhX, Y i + βhX, Zi, ∀X, Y, Z ∈ E, α, β ∈ K. iii) Tính đối xứng: hX, Y i = hY, Xi.
Khi đó hX, Y i được gọi là tích vô hướng của hai vectơ X và Y. Hai vectơ X, Y được gọi là trực giao nếu hX, Y i = 0. Hệ vectơ cơ sở {e1 , e2 , ., en } được gọi là hệ trực giao nếu hei , ej i = 0, ∀i 6= j. Kí hiệu kxk = hX, Xi 2 được gọi là chuẩn của vectơ X.
Hệ vectơ cơ sở {e1 , e2 , ., en } được gọi là hệ trực chuẩn nếu hei , ej i = 0, ∀i 6= j và kei k = 1, ∀i = 1, 2,. • Trong không gian E = Rn , chúng ta thường xét hệ trực chuẩn dạng: {e1 , e2 , ., yn ) xác định trên hệ cơ sở trực chuẩn. Khi đó chúng ta dễ dàng xác định được: n X hX, Y i = xi. Thuật toán Gram-Schmid Xét hệ vecto độc lập tuyến tính {X1 , X2 , ., Xn } , giả sử rằng hệ chưa là hệ trực chuẩn, ta cần biến đổi hệ trên về hệ trực chuẩn {V1 , V2 ,.
Khi đó ta có thể sử dụng phương pháp biến đổi theo ý tưởng sau đây: Xuất phát V1 = X1. Để nhận được vector trực giao thứ 2 ta sử dụng X2 nhưng trừ bớt đi một phần của Y2 theo hướng của V1 : V2 = X2 − aV1 , với a được chọn sao cho V2 trực giao với V1. Điều này đòi hỏi : hV1 , V2 i = hV1 , X2 − aV1 i = hV1 , X2 i − ahV1 , V1 i = 0 hay 5 hV1 , X2 i a= hV1 , V1 i Tương tự như vậy, để nhận được vectơ trực giao thứ k, ta sử dụng Xk nhưng trừ với đi một phần của Xk theo hướng của Vk−1 , tức là: k−1 X hVi , Vk i V k = Xk − Vi i=1 hVi , Vi i Để chuẩn hóa độ dài các vectơ về 1, ta cần biến đổi: Vk Vk := , ∀k = 1, 2, 3, ., n kVk k Tổng quát, ta thu được thuật toán chuẩn hóa như sau: Thuật toán Input: {X1 , X2 , ., Xn } là hệ độc lập tuyến tính., Vn } là hệ trực chuẩn. Bước 1: Khởi động V1 = X1 Bước 2: Với mọi k = 2, 3, ., n, xác định: k−1 X hVi , Vk i V k = Xk − Vi i=1 hVi , Vi i Bước 3: Chuẩn hóa Vk Vk := , ∀k = 1, 2, 3,.
Các phép toán cơ bản về ma trận Trong phần này, luận văn đề cập đến một số các phép toán về ma trận để sử dụng được với học máy cơ bản. Một số kí hiệu cơ bản i) Kí hiệu A = (aij )N ×M là ma trận có N hàng và M cột, phần tử aij là phần tử nằm tại hàng tứ i và cột thứ j. 6 ii) Kí hiệu AT = (aji )N ×M là ma trận chuyển vị của ma trận A, các phần tử của ma trận chuyển vị chính là phần tử đối xứng qua đường chéo chính trong ma trận A. iii) Ma trận A với số hàng bằng số cột được gọi là ma trận vuông.
iv) Kí hiệu E = (0)N ×M là ma trận không là ma trận tất cả các phần tử đều bằng 0. v) Kí hiệu I là ma trận đợn vị gồm các phần tử trên đường chéo chính bằng 1, các phần tử còn lại bằng 0. Cho ma trận vuông A cấp N , định nghĩa định thức của ma trận A là số được xác định bằng công thức: X det(A) = (−1)Nσ a1i1 a2i2 ., iN ) là một hoán vị của tập (1, 2, ., N ), số Nσ chính bằng số cách chuyển từ hoán vị (i1 , i2 , ., iN ) về trạng thái (1, 2, 3, ., N ), tổng lấy với mọi hoán vị của (1, 2,. Khi đó, nếu A là ma trận có det(A) 6= 0 thì A được gọi là ma trận không suy biến.
Các phép toán cơ bản 1. Phép nhân ma trận A với một số k vô hướng, kí hiệu kA = (kaij )N ×M 2. Phép cộng ma trận cùng cấp A + B = (aij + bij )N ×M 3. Phép nhân hai ma trận trong đó số hàng của ma trận A bằng số cột của ma trận B XK A×B =( aik bkj )N ×M với A = (aij )N ×K , B = (bij )K×M k=1 7 1.
Một số ma trận đặc biệt 1. Ma trận nghịch đảo Cho ma trận A là ma trận vuông cấp N , giả sử ma trận A là ma trận không suy biến. Khi đó tồn tại ma trận B thỏa mãn tính chất: A × B = B × A = I với I là ma trận đơn vị. Khi đó ma trận B được gọi là ma trận nghịch đảo của ma trân A và kí hiệu là A−1.
Ma trận liên hợp A∗ Cho ma trận A là ma trận vuông, kí hiệu Bij là ma trận thu được khi bỏ đi hàng j và cột thứ j của ma trận A. Khi đó giá trị bij = (−1)i+j det(Bij ) được gọi là phần bù đại số của phần tử aij. Ma trận A∗ = (bij ) được gọi là ma trận liên hợp của ma trận A. Ma trận giả nghịch đảo Cho ma trận A là ma trận bất kì, ta định nghĩa ma trận giả nghịch đảo A+ là ma trận thỏa mãn các tính chất: + AA+ A = A + (AA+ )∗ = AA+ (AA+ là một ma trận Hermite) + (A+ A)∗ = A+ A (A+ A là một ma trận Hermite) + Nếu A khả nghịch, ma trận giả nghịch đảo và ma trận nghịch đảo là một: A+ = A−1 + Giả nghịch đảo của giả nghịch đảo chính là ma trận ban đầu: (A+ )+ = A.
+ Phép lấy giả nghịch đảo giao hoán với phép chuyển vị: (AT )+ = (A+ )T + Phép lấy giả nghịch đảo giao hoán với phép liên hợp: (A∗ )+ = (A+ )∗ + Giả nghịch đảo của tích của một đại lượng vô hướng với A là tích của nghịch đảo của đại lượng vô hướng đó với A+ : (αA)+ = α−1 A+ , ∀α 6= 0 8 Khi đó dễ dàng xác định với A là một ma trận bất kì thì ma trận A+ được xác định bởi công thức A+ = (AT × A)−1 × AT 1. Chuẩn của vectơ và ma trận Xét vector X = (x1 , x2 , ., xN ), ma trận A = (aij )N ×M. Khi đó trong tính toán, chúng ta thường sử dụng các công thức tính chuẩn của vectơ và ma trận như sau: 1 N ! X 2 kXk1 = max |xi |; kXk2 = |x1 | + |x2 | +. + |xN |; kXk3 = x2i i=1 M X N X kAk1 = max |aij |; kAk2 = max |aij |; kAk3 = max |aij | i=1,.M j=1 i=1 Cần chú ý rằng các chuẩn trên đã được chứng minh là tương đương theo nghĩa nếu một phương pháp lặp nào đã hội tụ với một chuẩn thì sẽ hội tụ với mọi chuẩn tương đương.
Do đó trong tính toán ta có thể tùy chọn chuẩn. Lý thuyết về bài toán tối ưu Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh hưởng đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội.