menu

Condition number của một ma trận

Đăng lúc 31/10/2014, trong chuyên mục Toán cao cấp

Bạ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? Bài viết tham khảo từ trang Mathematics for Collegebài giảng của Dheeraj Bhardwaj.

Chúng ta cùng bắt đầu bài viết bằng việc xét dạng tổng quát của hệ phuơng trình như sau:

Hệ phuơng trình điều kiện yếu và mạnh là gì?

Định nghĩa

Một hệ phuơng trình được gọi là ill-conditioned nếu sự thay đổi nhỏ các hệ số của ma trân $A$ hoặc sự thay đổi nhỏ ở trong vế phải $C$ dẫn đến sự thay đổi lớn trong vector nghiệm $X$.

Một hệ phuơng trình được gọi là well-conditioned nếu sự thay đổi nhỏ các hệ số của ma trân $A$ hoặc sự thay đổi nhỏ ở trong vế phải $C$ dẫn đến sự thay đổi nhỏ trong vector nghiệm $X$.

Ví dụ 1 – ill-conditioned system of equations

Xét hệ phuơng trình sau đây

Hệ phuơng trình này có nghiệm là

Thay đổi một chút ở vế phải của hệ

sẽ cho ta nghiệm mới là

Còn nếu ta thay đổi một chút các số trong ma trận

ta sẽ nhận được nghiệm

Cả hai nghiệm mới nhận được này điều khác xa nghiệm cũ dù ta chỉ thay một chút ít giá trị các hệ số. Do đó, ta nói hệ phuơng trình trong trường hợp này ill-conditioned.

Ví dụ 2 – well-conditioned system of equations

Xét hệ phuơng trình

Hệ này có nghiệm

Cũng tuơng tự trên, ta tiến hành thay đổi một chút ít ở vế phải của hệ

khi đó nghiệm mới là

Còn nếu ta thay đổi trong ma trận ở vế trái

và nghiệm mới là

Cả hai nghiệm mới nhận được này điều thay đổi rất ít so với nghiệm cũ khi có sự thay đổi ít ở vế phải hay ở ma trận hệ số. Ta nói hệ này well-conditioned.

Điều gì sẽ xảy ra nếu hệ phuơng trình là ill-conditioned hay well-conditioned?

Nếu hệ phuơng trình là ill-conditioned, ta không nên tin tưởng quá nhiều vào nghiệm. Sở dĩ như vậy vì bạn thử nghĩ xem, mỗi khi bạn giải một phuơng trình nào đó, hoặc bạn chuyển từ bài toán thực tế sang việc phải giải một hệ phuơng trình tuyến tính, bạn muốn thử với nhiều hệ số khác nhau để thấy sự thay đổi của nghiệm. Trong khi bạn chỉ thay đổi rất rất ít ở hệ số, vậy mà nghiệm lại sai khác một số rất lớn. Bạn có hài lòng được điều này không?

Tiếp theo, chúng ta sẽ đi tìm hiểu chúng ta có thể tin bao nhiêu phần vào nghiệm của một phuơng trình, cách tin là như thế nào. Mỗi ma trận khả nghịch đều có một condition number và một machine epsilon, dựa vào hai lượng này, chúng ta có thể định lượng xem bao nhiêu con số trong kết quả nghiệm là đáng tin cậy.

Để có thể tính được condition number của một ma trận nghịch đảo, ta cần phải biết trước chuẩn của ma mận đó là gì và làm cách nào để có thể xác định được nó.

Chuẩn của ma trận

Cũng giống như định thức (determinant) của ma trận, chuẩn của ma trận cũng là một đại lượng vô hướng (scalar number). Tuy nhiên, chuẩn thì luôn duơng phải được định nghĩa cho tất cả các ma trận (bất kể ma trận vuông hay ma trận chữ nhật, ma trận khả nghịch hay không).

Định nghĩa Chuẩn của ma trận

Chuẩn của ma trận được định nghĩa tuơng ứng với chuẩn của vector được cho bởi

Chuẩn của ma trận đo được sức ảnh hướng của sự thay đổi trong ma trận đến sự thay đổi trong vector nghiệm.

Một trong những định nghĩa phổ biến của chuẩn ma trận là tổng trị tuyệt lớn nhất theo cột (maximum absolute column sum). Chuẩn này được tính bằng cách lấy tổng tất cả các hệ số trên mỗi cột rồi so sánh giữa các giá trị với nhau, giá trị nào lớn nhất chính là chuẩn của ma trận. Đối với ma trận $m$ dòng $n$ cột,

Định nghĩa thứ hai là tổng trị tuyệt lớn nhất theo dòng (maximum absolute row sum), 

Tính chất của chuẩn ma trận

  1. Với ma trận $[A]$, $\Vert A\Vert\ge 0$.
  2. Với ma trận $[A]$, đại lượng vô hướng $k$, $\Vert kA\Vert = \vert k\vert\Vert A \Vert$.
  3. Với hai ma trận cùng bậc $[A],[B]$, $\Vert A+B \Vert \le \Vert A \Vert + \Vert B\Vert$
  4. Với hai ma trận $[A],[B]$ có thể nhân lại với nhau dưới dạng $[A][B]$, $\Vert AB \Vert \le \Vert A\Vert \Vert B \Vert$

Ví dụ 3

Với ma trận

Khi ấy,

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.

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

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

với $\Vert X \Vert_{\infty}=2,\Vert C \Vert_{\infty}=7.999.$

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

ta được nghiệm mới

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

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

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

Khi ấy,

với chuẩn của các sai số là $\Vert \Delta X \Vert_{\infty}=5.999,\Vert \Delta C \Vert_{\infty}= 0.001.$

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

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à

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ạnh ở phần trước.

Xem lại Ví dụ 2

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

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

với $\Vert X \Vert_{\infty}=2,\Vert C \Vert_{\infty}=7.$

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

ta được nghiệm mới

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

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

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

Khi ấy,

với chuẩn của các sai số là $\Vert \Delta X \Vert_{\infty}=0.001,\Vert \Delta C \Vert_{\infty}= 0.001.$

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

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à

Đế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 $\Vert \Delta X \Vert_{\infty} / \Vert X \Vert_{\infty}$ và $\Vert \Delta C \Vert_{\infty} / \Vert C \Vert_{\infty}$ hoặc $\Vert \Delta A \Vert_{\infty} / \Vert A \Vert_{\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à

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à $\Vert A\Vert\Vert A^{-1}\Vert$

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

Con số $\Vert A\Vert\Vert A^{-1}\Vert$ đượ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]$.

Bây giờ ta sẽ đi chứng minh rằng với hệ phương trình $[A][X]=[C]$ thì

  • highlight Xem chứng minh

    Thật vậy, với $[A][X]=[C]$ thì khi $[A]$ thành $[A’]$ thì $[C]$ sẽ thành $[C’]$ thỏa

    Suy ra

    Ký hiệu sự thay đổi ở $A$ và $X$ lần lượt là $[\Delta A], [\Delta X]$ thỏa

    Khi đó,

    Khai triển biểu thức trên ta sẽ có,

    Rút gọn,

    Mặt khác ta có (ứng dụng tính chất của chuẩn)

    Nhân cả hai vế với $\Vert A\Vert$

    Hay ta có điều phải chứng minh

Số chữ số đáng tin cậy trong kết quả nghiệm?

Theo như kết quả trên, ta thấy rằng sai lệch trong kết quả nghiệm $\le$ $\operatorname{A}$ $\times$ mối quan hệ tương giao ở vế phải của phương trình.

Hay nói cách khác, sai lệch trong kết quả nghiệm sẽ $\le$ $\operatorname{cond}(A)\times \epsilon_{\text{mach}}$ ($\epsilon_{\text{mach}}$ là machine epsion).

Do đó $\operatorname{cond}(A)\times \epsilon_{\text{mach}}$ sẽ cho chúng ta số chữ số đáng tin cậy trong kết quả nghiệm, giả sử là $m$. Khi ấy ta cần tìm giá trị lớn nhất có thể có của $m$ sao cho

Ví dụ 4

Chúng ta có thể tin bao nhiêu chữ số trong kết quả nghiệm của hệ sao đây?

Với $[A]=\begin{bmatrix}1 & 2 \\ 2 & 3.999 \end{bmatrix},$ thì

Khi đó,

Giả sử machine epsion $\epsilon_{\text{mach}}=2^{-23}=0.119209\times 10^{-6}$, khi ấy,

Ta cần tìm giá trị lớn nhất của $m$ thỏa $\operatorname{cond}(A)\times \epsilon_{\text{mach}} \le 0.5 \times 10^{-m}$ và được $m\le 2$.

Vậy ta có thể tin tưởng rằng ít nhất có 2 chữ số trong kết quả nghiệm là đáng tin cậy tương ứng với hằng số $\epsilon_{\text{mach}}=2^{-23}$.

toán cao cấp
giải tích số
condition number
ma trận
chuẩn
Top