Toán học

[Kỳ 2] Tính hợp lý nghiệm hệ phuơng trình và khái niệm ‘condition number’ của một ma trận

BBạn sẽ tìm hiểu thế nào là một hệ phuơng trình điều kiện yếu và điều kiện mạnh, chuẩn của một ma trận, condition number của ma trận là gì và ảnh hưởng của nó tới nghiệm hệ phuơng trình ra sao?

Tiếp theo kỳ trước vốn nói về

  • Sự khác nhau giữa hệ phuơng trình điều kiện yếu (ill-conditioned systems of equations) và hệ phuơng trình điều kiện mạnh (well-conditioned ).
  • Định nghĩa và tìm chuẩn của một ma trận (norm of a matrix).

Ở kỳ này, chúng ta sẽ tiếp tục tìm hiểu 

  • Định nghĩa là cách đánh giá condition number của một ma trận
  • Mối liên hệ giữa chuẩn và condition number của một ma trận
  • Mối quan hệ giữa condition number của một ma trận với các điều kiện mạnh yếu của một hệ phuơng trình tuyến tính và bạn có thể tin bao nhiêu phần vào nghiệm của các hệ này?
Đọc thêm : Chuyên mục Toán Cao Cấp của Math2IT.

Mối liên hệ giữa chuẩn và condition number của một ma trận

Xem lại ví dụ 1

Trước khi đi vào định nghĩa condition number của một ma trận là gì. Ta hãy cùng nhau xem xét các ví dụ cụ thể cho dễ hiểu. Trở lại với ví dụ 1 về hệ phương trình điều kiện yếu ở kỳ trước.

    \[ \begin{bmatrix}1 & 2 \\2 & 3.999 \end{bmatrix}\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}4 \\ 7.999 \end{bmatrix}.\]

Hệ này có nghiệm là

    \[\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}2 \\ 1 \end{bmatrix}.\]

Ký hiệu hệ trên dưới dạng 

    \[[A][X]=[C],\]

với \left\|X \right\|_{\infty}=2,\left\|C \right\|_{\infty}=7.999.

Thử thay đổi một lượng nhỏ ở vế phải

    \[ \begin{bmatrix}1 & 2 \\2 & 3.999 \end{bmatrix}\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}4.001 \\ 7.998 \end{bmatrix},\]

ta được nghiệm mới

    \[\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}-3.999 \\ 4.000 \end{bmatrix}.\]

Ký hiệu lại hệ mới ở trên dưới dạng

    \[[A][X']=[C'].\]

Sự thay đổi ở vế phải giữa hệ mới so với hệ cũ sẽ là

    \[[\Delta C]=[C']-[C],\]

vè sự thay đổi ở vector nghiệm X giữa hệ mới so với hệ cũ sẽ là

    \[[\Delta X]=[X']-[X].\]

Khi ấy,

    \[  [\Delta C] = \begin{bmatrix}4.001 \\ 7.998 \end{bmatrix} - \begin{bmatrix}4 \\ 7.999 \end{bmatrix} = \begin{bmatrix}0.001 \\ -0.001 \end{bmatrix}, [\Delta X] = \begin{bmatrix}-3.999 \\ 4.000 \end{bmatrix} - \begin{bmatrix}2 \\ 1 \end{bmatrix} = \begin{bmatrix} -5.999\\ 3.000 \end{bmatrix}.\]

với chuẩn của các sai số là \left\|\Delta X \right\|_{\infty}=5.999,\left\|\Delta C \right\|_{\infty}= 0.001.

Sự tương giao nếu xem xét dưới chuẩn sẽ là

    \begin{align*}  \dfrac{\left\|\Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}} = \dfrac{5.999}{2} &= 2.9995,\\  \dfrac{\left\|\Delta C \right\|_{\infty}}{\left\| C \right\|_{\infty}} = \dfrac{0.001}{7.999} &= 1.250 \times 10^{-4}.  \end{align*}

Nhìn vào hai con số trên, bạn có thể dễ dàng nhận ra rằng với một sự thay đổi rất nhỏ ở vế phải (1.250\times 10^{-4}), ta nhận được một sự thay đổi rất lớn ở nghiệm (2.995). Chính xác hơn, mối tương giao ấy có giá trị là

    \[\dfrac{\left\|\Delta X \right\|_{\infty} / \left\| X \right\|_{\infty}}{\left\|\Delta C \right\|_{\infty} / \left\| C \right\|_{\infty}} = \dfrac{2.9995}{1.250\times 10^{-4}}=23993\]

Hãy ghi nhớ con số 23993 này trước khi đi vào xem xét tiếp ví dụ 2 về hệ phương trình điều kiện mạnhkỳ trước.

Xem lại ví dụ 2

    \[ \begin{bmatrix}1 & 2 \\2 & 3 \end{bmatrix}\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}4 \\ 7 \end{bmatrix}.\]

Hệ này có nghiệm là

    \[\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}2 \\ 1 \end{bmatrix}.\]

Ký hiệu hệ trên dưới dạng 

    \[[A][X]=[C],\]

với \left\|X \right\|_{\infty}=2,\left\|C \right\|_{\infty}=7.

Thử thay đổi một lượng nhỏ ở vế phải

    \[ \begin{bmatrix}1 & 2 \\2 & 3 \end{bmatrix}\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}4.001 \\ 7.001 \end{bmatrix},\]

ta được nghiệm mới

    \[\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}1.999\\ 1.001 \end{bmatrix}.\]

Ký hiệu lại hệ mới ở trên dưới dạng

    \[[A][X']=[C'].\]

Sự thay đổi ở vế phải giữa hệ mới so với hệ cũ sẽ là

    \[[\Delta C]=[C']-[C],\]

vè sự thay đổi ở vector nghiệm X giữa hệ mới so với hệ cũ sẽ là

    \[[\Delta X]=[X']-[X].\]

Khi ấy,

    \[  [\Delta C] = \begin{bmatrix}4.001 \\ 7.001 \end{bmatrix} - \begin{bmatrix}4 \\ 7 \end{bmatrix} = \begin{bmatrix}0.001 \\ 0.001 \end{bmatrix},  [\Delta X] = \begin{bmatrix}1.999\\ 1.001 \end{bmatrix} - \begin{bmatrix}2 \\ 1 \end{bmatrix} = \begin{bmatrix} -0.001\\ 0.001 \end{bmatrix}.\]

với chuẩn của các sai số là \left\|\Delta X \right\|_{\infty}=0.001,\left\|\Delta C \right\|_{\infty}= 0.001.

Sự tương giao nếu xem xét dưới chuẩn sẽ là

    \begin{align*}  \dfrac{\left\|\Delta X \right\|_{\infty}}{\left\| X \right\|_{\infty}} = \dfrac{0.001}{2} &= 5\times 10^{-4},\\  \dfrac{\left\|\Delta C \right\|_{\infty}}{\left\| C \right\|_{\infty}} = \dfrac{0.001}{7} &= 1.429 \times 10^{-4}.  \end{align*}

Nhìn vào hai con số trên, bạn có thể dễ dàng nhận ra rằng với một sự thay đổi rất nhỏ ở vế phải (1.429\times 10^{-4}), ta nhận được một sự thay đổi cũng rất nhỏ ở nghiệm (5\times 10^{-4}). Chính xác hơn, mối tương giao ấy có giá trị là

    \[\dfrac{\left\|\Delta X \right\|_{\infty} / \left\| X \right\|_{\infty}}{\left\|\Delta C \right\|_{\infty} / \left\| C \right\|_{\infty}} = \dfrac{5\times 10^{-4}}{1.429\times 10^{-4}}=3.5.\]

Đến đây ta sẽ đặt ra câu hỏi liệu rằng có bất kỳ mối liên hệ nào giữa \left\|\Delta X \right\|_{\infty} / \left\| X \right\|_{\infty}\left\|\Delta C \right\|_{\infty} / \left\| C \right\|_{\infty} hoặc \left\|\Delta A \right\|_{\infty} / \left\| A \right\|_{\infty}? Nếu có thì nó có thể giúp chúng ta hiểu thêm gì về việc xác định ngay một hệ là điều kiện mạnh hay yếu hay không?

Nếu quả thật có mối liên hệ đó, nó sẽ cho chúng ta dữ liệu vô cùng hữu ích khi xem xét đánh giá condition number của một ma trận. Rằng ta có thể tin tưởng bao nhiêu chữ số trong kết quả nghiệm tìm được khi giải hệ phương trình tương ứng. May mắn thay, có một mối liên hệ thật sự như vậy, nó là

    \begin{align*}  \dfrac{\left\|\Delta X \right\|}{\left\| X \right\|} &\le \left\|A\right\|\left\|A^{-1}\right\| \dfrac{\left\|\Delta C \right\|}{\left\| C \right\|}, \\  \dfrac{\left\|\Delta X \right\|}{\left\| X + \Delta X \right\|} &\le \left\|A\right\|\left\|A^{-1}\right\| \dfrac{\left\|\Delta A \right\|}{\left\| A \right\|}.  \end{align*}

Hai bất đẳng thức trên cho ta thông tin : Sự thay đổi trong mối tương quan giữa chuẩn của vế phải C hoặc các hệ số trong ma trận A sẽ ảnh hưởng đến kết quả nghiệm X với một lượng tương ứng là \left\|A\right\|\left\|A^{-1}\right\|

Định nghĩa condition number của ma trận

Con số \left\|A\right\|\left\|A^{-1}\right\| được định nghĩa là condition number của ma trận A. Ký hiệu là \operatorname{cond}(A).

Nếu kết hợp thêm với machine epsilon, chúng ta sẽ có một đánh giá tương đối tốt về nghiệm của hệ [A][X]=[C].

Đọc tiếp : kỳ 3 (kỳ cuối).

Math2IT

Math2IT

Đây là tác giả chung cho các bài viết không do trực tiếp tác giả cụ thể nào của Math2IT viết. Có thể đó là các bài dịch từ các bài viết nước ngoài hoặc các bài viết thiên về kỹ thuật và thông báo.