Inexact Uzawa

Trong topic này, tôi sẽ trình bày ý tưởng thuật toán inexact uzewa. Tài liệu tham khảo chính là bài báo

JAMES H. BRAMBLE,JOSEPH E.VASSILEV PASCIAKy AND APOSTOL T.

ANALYSIS OF THE INEXACT UZAWA ALGORITHM FOR SADDLE POINT PROBLEMS

  1. Tổng quan:
  2. Thuật toán:
  3. Một số kết luận:
  4. Reference

1.

Bài báo đưa ra thuật toán lặp để giải quyết bài toán

\left(\begin{array}{cc} A & B^t\\ B & 0 \end{array}\right) \left(\begin{array}{cc} X\\Y \end{array}\right)= \left(\begin{array}{cc} F\\G\end{array}\right)

Trong đó, A\in R^{N \times N} là ma trận đối xứng xác định dương, B\in R^{N\times M}.
Hệ trên là kết quả của quá trình rời rạc hóa bài toán phương trình đạo hàm riêng liên quan vận tốc – áp suất.

Keyword: indefnite systems, iterative methods, preconditioners, saddle point problems, Stokes equations, Uzawa algorithm (, well/ ill condition, number condition).
Trước hết, tôi sẽ làm rõ các từ khóa cũng như một số khái niệm liên quan.

  • Iterative methods: phương pháp lặp (dùng dãy để tìm nghiệm)
  •  Preconditioners:
  •  Saddle point problems:
  •  Stokes equations:
  •  Well/ ill condition:
  • Number condition:

2.

3.

4.

One Response to “Inexact Uzawa”

  1. vanchanh123 Says:

    Ngày 02/202/2012

    Hôm nay, tôi sẽ viết một chút liên quan đến khái niệm Preconditioner ( [1] ).

    Đó là một kỹ thuật làm tăng tính ổn định cho bài toán số.

    Trước tiên, ta bàn về nguồn gốc: vì sao ta quan tâm đến kỹ thuật này?

    Đối với một bài toán số, người ta rất quan tâm đến tính ổn định (stable) của bài toán, nghĩa là dữ liệu input có một sai số bé, lớn thì ảnh hưởng thế nào đến lời giải của bài toán.

    Một số đánh ảnh hưởng của dữ liệu đầu vào đến nghiệm được tác giả [2] chỉ ra trong trang 41 của tài liệu [2] bởi BĐT sau:

    \frac{||\Delta x||}{||x||}\le ||A||||A^{-1}||(\frac{||\Delta A||}{||A||}+\frac{||\Delta b||}{||b||}).

    Với \Delta A, \Delta b là nhiễu tương ứng với A, b.
    x là nghiệm ptr Ax=b, x+\Delta x là nghiệm ptr (A+\Delta A)(x+\Delta x)=(b+\Delta b).
    Đặt \kappa(A)=||A||||A^{-1}|| gọi là số điều kiện (number condition) của ma trận A.

    Phép chứng minh cho BĐT trên xem ở phần phụ lục.
    Bất đẳng thức trên chỉ ra rằng: khi số điều kiện của A nhỏ thì bài toán sẽ ổn định.

    Ta đã liên kết được tính ổn định với số điều kiện.

    Bây giờ, ta quay lại vấn đề Preconditioner.
    Đó là kỹ thuật chuyển đối bài toán Ax=b thành A'x'=b' với \kappa(A') bé. Và dễ dàng tính x theo x'.

    Trong [3], Tác giả đưa ra 3 loại Preconditioner:

      Left Preconditioner
      Right Preconditioner
  2. Những tiêu chuẩn cần cho một ma trẫn Precondition [4]
    1. Split Preconditioner

    Điều tuyệt vời mà Preconditioner mang lại là ta có thể làm việc trên một bài toán mới với số điều kiện nhỏ hơn. Khi đó, nghiệm sẽ tương đương về mặt lý thuyết nhưng lợi ích trong tính toán số lại cao hơn nhiều so với bải toán gốc.

    Để thu được một điều tuyệt vời như vậy, ta phải tốn công sức để chuyển đổi bài toán gốc sang bài toán mới. Tức là phải tìm ra ma trận Preconditioner thích hợp.
    Phần tiếp theo, tôi sẽ:

      Làm rõ các loại Precondition trên.
      Tìm cách xây dựng ma trận preconditoner [4].
      Và giải thích vì sao chọn ma trận Preconditioner phải “close” A.
      Ref
      Chứng minh BĐT.
      Có vẻ mệnh đề 1) mâu thuẩn với định lý 2. 4 trang 2.4)

      Dù số điều kiện có lớn thì nó cũng là số cố định!!!! Như vậy, lập luận nói đến sự ảnh hưởng của số điều kiện có vẻ không ổn!

    Tài liệu tham khảo
    [1] http://en.wikipedia.org/wiki/Preconditioner.
    [2] Trịnh Anh Ngọc. Bài Giảng Giải tích số 1, 2009.
    [3]Michele Benzi. Preconditioning Techniques for Large Linear, Journal of Computational Physics, 2002.
    Systems: A Survey

    [4] http://rene.ma.utexas.edu/CNA/NSPCG/manuals/usernsp/node7.html.

    Phụ lục:
    Phụ lục 1: Chứng minh BĐT đánh giá tính ổn định của bài toán Ax=b.

    (A+\Delta A)(x+\Delta x)=(b+\Delta b).

    \underbrace{Ax}_{b}+\Delta A\Delta x+A\Delta x +\Delta A x =b+\Delta b.

    [\Delta A+A]\Delta x  = \Delta b -\Delta A x.

    Lấy \Delta A bé sao cho \Delta A+A khả nghịch (Ta cần chứng minh có thể chọn \Delta A như vậy!).

    Điều trên được chứng minh bởi bài tập sau:
    Mệnh đề 1: Cho T\in \mathbf{L}(\mathbf{R}^n)||.||_{*} là chuẩn đều trong \mathbf{L}(\mathbf{R}^n).
    a) Giả sử: ||G||_{*} <1. Với G=Id_{\mathbf{R}^n}-T thì

    b) Cho T là song ánh, chứng minh tồn tại a sao cho mệnh đề sau đúng
    " \forall S\in \mathbf{L}(\mathbf{R}^n) \Leftrightarrow ||S-T||_{*}<a thì S là song ánh"

    Áp dụng mệnh đề trên với A khả nghịch (A tương ứng với ánh xạ tuyến tính (A là ma trận biểu diễn của một ax T nào đó trong cơ sở chính tắc)ta sẽ có A là 1 song ánh trên \mathbf{L}(\mathbf{R}^n)).

    Nên chỉ cần chọn \Delta A sao cho: ||\Delta A||_{*}<a ( a chọn như kết quả trên) thì ta sẽ có: A+\Delta A sẽ khả nghịch.

    Quay lại,
    Ta có:
    \Delta x  = [\Delta A+A]^{-1}(\Delta b -\Delta A x).

    ||\Delta x||   \le ||[I+\Delta A.A^{-1}]^{-1}||.||A^{-1}||(||\Delta b|| +||\Delta A||.{|| x||}) (2).

    Mặt khác, ||b||=||Ax||\le ||A||. ||x|| \Rightarrow ||\Delta b||=\frac{||\Delta b||}{||b||}||b||\le \frac{||\Delta b||}{||b||} ||A||.||x||(3)

    Từ (2), (3), chia 2 vế cho ||x|| (gs ||x||>0), ta có:

    \frac{||\Delta x||}{||x||}   \le ||[I+\Delta A.A^{-1}]^{-1}||.||A^{-1}||.||A||(\frac{||\Delta b||}{||b||} +\frac{||\Delta A||}{||A||} ) (4).

    Tiếp theo, ta đánh giá: ||[I+\Delta A.A^{-1}]^{-1}||

    Dùng khai triển Taylor cho hàm f(x)=\frac{1}{1+x}= 1-x+O(x^2)

    Nên ||(I+A\Delta A)^{-1}|| \approx 1+||A||.||\Delta A||. Do bỏ đi số hạng bậc nhiễu 2 \Delta A .

    Do vậy, từ (4) thu được:

    \frac{||\Delta x||}{||x||}   \le  ||A^{-1}||.||A||(\frac{||\Delta b||}{||b||} +\frac{||\Delta A||}{||A||} ) +||A||||\Delta A||.||\Delta b||(5).

    Phụ lục 2: Ảnh hưởng số điều kiện

    Tồn tại ma trận S sai khác theo nghĩa tương đối bằng nghịch đảo số điều kiện của A

    \min_{S:\det{S}=0}\frac{||S-A||}{||A||}=\frac{1}{Cond(A)}

    Nếu ma trận A có số điều kiện lớn thì ma trận A gần (theo nghĩa tương đối) với ma trận suy biến.

    Nếu dựa vào mệnh đề 1 và BĐT (5), ta không thể thấy ảnh hưởng của số điều kiện vào tính ổn định hoặc bị chi phối tính gần “tuyệt đối” ma trận không suy biến.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: