Một điểm yếu của phương pháp giảm cơ sở trình bày ở trên là nó thực hiện trên các ma trận và véctơ số chiều lớnN2 và hệ quả là có chi phí tính toán cũng như lưu trữ cực lớn. May
mắn thay, nhờ vào Bổ đề 3.2, phương pháp giảm cơ sở có thể được áp dụng trực tiếp vào PALE (3.1) trong đó mọi phép toán được tiến hành cho các ma trận và véctơ cỡ N. Thêm vào đú, giả sử rằng nghiệm của phương trỡnh (3.1) với vế phải hạng thấpB(à)BT(à)cú thể được xấp xỉ bởi một ma trận hạng thấpX(à) ≈ Z(à)ZT(à), ta cú thể tiếp tục giảm chi phớ tính toán và chi phí lưu trữ ở cả giai đoạn offline và giai đoạn online.
3.4.1 Giai đoạn offline
Trong giai đoạn offline, thay vì giải hệ tuyến tính (3.2), ta tính nghiệm của phương trình PALE (3.1) cho những giỏ trị tham số đó chọn trướcà1, . . . , àk. ChoZj ∈ RNìnj là nhõn tử Cholesky hạng thấp của nghiệm X(àj) ≈ ZjZjT của phương trỡnh (3.1) tại à = àj, j = 1, . . . , k. Những nhân tử này có thể được tính một cách hiệu quả bởi phương pháp luân phương ẩn hạng thấp (LR-ADI) [18, 53, 62], phương pháp không gian con Krylov [26, 67]
hay phương phỏp tối ưu húa trờn đa tạp Riemann [77]. Khi đú, đối với mọià ∈ D, ta tớnh một nghiệm xấp xỉ của (3.1) như sau
X(à)≈mat(Vkx(à)) =:ˆ XRB(à), trong đó
Vk=
vec(Z1Z1T), . . . , vec(ZkZkT)
(3.25) và x(à)ˆ là nghiệm của hệ tuyến tớnh (3.10). Lưu ý rằng, để đơn giản về ký hiệu, ta vẫn ký hiệu ma trận giảm cơ sở (3.25) bởi Vk mặc dù nó khác so với ma trận đó ở (3.9) do nú được xõy dựng từ nghiệm xấp xỉ hạng thấpX(àj) ≈ ZjZjT thay vỡ nghiệm chớnh xỏc X(àj) = mat x(àj)
sử dụng trong (3.9). Tất nhiên, việc này sẽ dẫn đến một xấp xỉ giảm cơ sở khác.
NghiệmXRB(à)cũng cú thể được viết dưới dạng
XRB(à) =
k
X
j=1
ˆ
xj(à)ZjZjT =Vk
ˆ
x1(à)In1 ...
ˆ
xk(à)Ink
VkT, (3.26) trong đú[ˆx1(à), . . . ,xˆ1(à)]T = ˆx(à)và
Vk = [Z1, . . . , Zk]. (3.27) Lưu ý rằng chúng tôi không bao giờ tính ma trậnVk một cách hiển để xây dựng hệ tuyến tính giảm (3.10). Thay vào đó, chúng tôi sử dụng sự phụ thuộc afin (3.23) của ma trận hệ sốL(à)ˆ và vế phảib(à)ˆ rồi tớnh cỏc phần tử của cỏc ma trận độc lập tham sốVTkLpVkcho p= (i−1)nA+jvớii= 1, . . . , nE,j = 1, . . . , nA, và các véctơVTkbpchop= (i−1)nB+j vớii, j = 1, . . . , nB, sử dụng các Bổ đề 3.1, 3.2 và các quan hệ (3.14), (3.21) như sau
(VkTLpVk)rl = h−EiZlZlTATj −AjZlZlTEiT, ZrZrTi
= −2trace ZrT(EiZl)(AjZl)TZr ,
(VTkbp)r = hBiBjT, ZrZrTi= trace (BjTZr)(ZrTBi)
với r, l = 1, . . . , k. Vì vậy, sử dụng cấu trúc củaLp, bp và Vk để giảm chi phí tính toán, chẳng hạn, củaVTkLpVktừO(N4k)xuống cònO(N2n)vớin=n1+. . .+nk. Trong việc tính độ phức tạp tính toán, chúng tôi chưa để ý đến tính thưa của các ma trận Ei và Aj vì chúng còn tùy thuộc vào những ví dụ cụ thể.
Nhận xét 3.4. Kể cả trong trường hợpEivàAj đối xứng, ta vẫn luôn viếtEiT vàATj nếu các ma trận chuyển vị được đề cập. Việc này giúp cho chuyện mở rộng các kết quả lên trường hợp bài toán phi đối xứng được thuận tiện hơn. Cụ thể, xin xem Mục 3.5.
Đối với nghiệm xấp xỉXRB(à), từ Định lý 3.2 ta thu được ước lượng sai số sau đõy kX(à)−XRB(à)kF =kek(à)k ≤∆k(à) (3.28) với∆k(à)như trong (3.18). Ước tử này cú thể được sử dụng trong thủ tục greedy được trỡnh bày ở Thuật toán 2.
Algorithm 2Thuật toán greedy cho phương trình Lyapunov
Input: ngưỡng sai sốtolrb, tập thếDtrain, tham số đầuà1 ∈ Dtrain. Output: ma trận cơ sởVk.
1: Giải PALE (3.1) tạià=à1 để cúX(à1)≈Z1Z1T.
2: Đặt∆max1 > tolrb, M1 ={à1},V1 =Z1, vàk = 2.
3: while∆maxk−1 ≥tolrbdo
4: àk = arg max
à∈Dtrain\Mk−1
∆k−1(à)
5: ∆maxk = ∆k−1(àk)
6: Mk =Mk−1∪ {àk}
7: Giải PALE (3.1) tạià=àkđể cúX(àk)≈ZkZkT
8: Vk = [Vk−1, Zk]
9: k ←k+ 1
10: end while
Để cú thể tớnh chuẩn của thặng dư krk(à)k một cỏch hiệu quả, chỳng ta lại sử dụng biểu diễn afin (3.22). Trước tiên, xét bTpbq với p= (i−1)nB+j, q = (f −1)nB +g và i, j, f, g= 1, . . . , nB. Sử dụng (3.14) và (3.21) ta thu được
bTpbq =hBfBTg, BiBjTi= trace (BiTBf)(BgTBj) .
Các thành phần của véctơbTpLqVkvớip= (i−1)nB+j,q = (f−1)nA+g,i, j = 1, . . . , nB, f = 1, . . . , nE vàg = 1, . . . , nAcó thể được biểu diễn như sau
(bTpLqVk)l =h−AgZlZlTEfT −EfZlZlTATg, BiBjTi
=−trace BiT(EfZl)(AgZl)TBj +BiT(AgZl)(EfZl)TBj
, l= 1, . . . , k.
Cuối cùng, từng thành phần của ma trậnVTkLTpLqVkvớip= (i−1)nA+j,q= (f−1)nA+g vài, f = 1, . . . , nE,j, g= 1, . . . , nAcó thể được tính bởi
(VkTLTpLqVk)rl =h−AgZlZlTEfT −EfZlZlTATg,−AjZrZrTEiT −EiZrZrTATji
= 2 trace (EiZr)T(EfZl)(AgZl)T(AjZr) + (EiZr)T(AgZl)(EfZl)T(AjZr)
vớir, l= 1, . . . , k. Ở đây, ta đã sử dụng Bổ đề 3.2 và các đẳng thức (3.14) và (3.21).
3.4.2 Giai đoạn online
Một khi ma trận giảm cơ sởVkđược xây dựng sao cho ước tử sai số không vượt quá một ngưỡng cho trước, nghiệm của phương trỡnh PALE (3.1) tại mỗi à ∈ D cú thể nhận trong giai đoạn online như ở (3.26). Tuy nhiên, một điểm yếu nghiêm trọng của cách tiếp cận này là nghiệm xấp xỉ XRB(à) chưa chắc đó nửa xỏc định dương vỡ nghiệm của phương trỡnh giảmx(à)ˆ of (3.10) cú thể cú phần tử õm. Khú khăn này cú thể được xử lý bằng cỏch tớnh nghiệm xấp xỉ dưới dạngX(à)≈VkX(à)Vˆ kT =: ˆXRB(à), vớiVknhư trong (3.27) vàX(à)ˆ là nghiệm của phương trình Lyapunov giảm
A(à) ˆˆ X(à) ˆET(à) + ˆE(à) ˆX(à) ˆAT(à) = −B(à) ˆˆ BT(à) (3.29) với E(à) =ˆ VkTE(à)Vk, A(à) =ˆ VkTA(à)Vk và Bˆ(à) = VkTB(à). Do −A(à) và E(à) là đối xứng xác định dương, phương trình này có một nghiệm duy nhất đối xứng nửa xác định dương X(à) = ˆˆ Z(à) ˆZT(à). Khi đú XˆRB(à) cú thể được viết dưới dạng tớch XˆRB(à) = ZRB(à)ZRBT (à)vớiZRB(à) = VkZ(à)ˆ .
Cho
Rˆk(à) = A(à) ˆXRB(à)ET(à) +E(à) ˆXRB(à)AT(à) +B(à)BT(à) (3.30) là thặng dư tương ứng với nghiệm xấp xỉXˆRB(à). Khi đú sai sốX(à)−XˆRB(à)cú thể được ước lượng tương tự như trường hợp hệ tuyến tính
kX(à)−XˆRB(à)kF ≤ kRˆk(à)kF
α(à) ≤ kRˆk(à)kF
αLB(à) =: ˆ∆k(à) (3.31) vớiαLB(à)như trong (3.15). Thay thế nghiệm xấp xỉVkx(à)ˆ trong (3.22) bởi
vec( ˆXRB(à)) = (Vk⊗Vk)vec( ˆX(à)), ta nhận được biểu diễn sau cho thặng dư
kRˆk(à)k2F = kb(à)−L(à)(Vk⊗Vk)vec( ˆX(à))k2
=
nB
X
i,j=1 nB
X
f,g=1
θBijf g(à)trace (BiTBf)(BgTBj) + 2
nB
X
i,j=1 nE
X
f=1 nA
X
g=1
θijf gAEB(à)trace BiT(EfVk) ˆX(à)(AgVk)TBj
+ 2
nB
X
i,j=1 nE
X
f=1 nA
X
g=1
θijf gAEB(à)trace BiT(AgVk) ˆX(à)(EfVk)TBj + 2
nE
X
i,f=1 nA
X
j,g=1
θijf gAE(à)trace (EfVk)T(EiVk) ˆX(à)(AjVk)T(AgVk) ˆX(à) + 2
nE
X
i,f=1 nA
X
j,g=1
θijf gAE(à)trace (EfVk)T(AjVk) ˆX(à)(EiVk)T(AgVk) ˆX(à) ,
vớiθijf gB (à) = θiB(à)θjB(à)θBf(à)θBg(à), θAEBijf g (à) = θBi (à)θBj (à)θEf(à)θgA(à)vàθAEijf g(à) = θEi (à)θAj(à)θEf(à)θgA(à). Và một lần nữa, mọi ma trận độc lập tham số cú thể được tớnh và lưu trữ trước trong giai đoạn offline. Khi đú, ước tử sai số∆ˆk(à)cú thể được tớnh trong giai đoạn online với chi phí thấp.
Chỳ ý rằng trong thuật toỏn greedy, thay vỡ ∆k(à), ta cũng cú thể sử dụng ước tử
∆ˆk(à). Tuy nhiờn, chỳng tụi muốn nhấn mạnh rằng tớnh nghiệm giảm cơ sở XRB(à) như (3.26) sẽ khụng đắt bằng nghiệm XˆRB(à) = VkX(à)Vˆ kT vỡ giải hệ tuyến tớnh (3.10) với L(à)ˆ ∈ Rkìk rẻ hơn giải phương trỡnh Lyapunov (3.29) với E(à)ˆ , A(à)ˆ ∈ Rnìn, trong đú n=n1+. . .+nkcú thể lớn hơn đỏng kểk. Số chiềunphụ thuộc vàom(số cột củaB(à)), tốc độ hội tụ của phương pháp lặp sử dụng để giải (3.1) và số bước lặp greedy. Để giữ chi phớ tớnh toỏn trong giai đoạn offline ở mức thấp, ta tớnh ước tử sai số dựa trờnXRB(à), trong khi ở giai đoạn online khi tớnh nửa xỏc định dương là tối quan trọng, ta sẽ tớnhXˆRB(à). Hơn nữa, do span(Vk) ⊂ span(Vk ⊗Vk), nghiệm xấp xỉ XˆRB(à)được dự đoỏn là sẽ cú sai số bộ hơn. Nhằm mục đớch giữ cấu trỳc hạng thấp củaXˆRB(à)và vỡ thế, giảm chi phớ tớnh toỏn của giai đoạn online, chúng ta nên nén các cột của ma trậnVkvới một ngưỡngtolcc nào đó.
Điều này có thể thực hiện được bằng cách sử dung phân tích QR-hiện hạng (rank-revealing QR decomposition) hay một phân tích SVDVk.