Các Phương pháp Trực tiếp cho Hệ phương trình Tuyến tính

Các phương pháp trực tiếp giải hệ phương trình tuyến tính Ax = b trong một số hữu hạn các bước số học, điển hình là bằng cách phân tích ma trận và sau đó giải các hệ tam giác bằng phép thế.

Definition

Một phương pháp trực tiếp là một thuật toán tính toán nghiệm chính xác của một hệ phương trình tuyến tính — với sai số làm tròn — trong một số hữu hạn các phép toán được xác định trước, trái ngược với một phương pháp lặp tạo ra một chuỗi các xấp xỉ.

Scope

Chủ đề này bao gồm phép khử Gauss, biểu thức của nó dưới dạng phân tích LU, vai trò của phép xoay trục trong việc kiểm soát sự gia tăng lỗi, phép thế xuôi và thế ngược cho các hệ tam giác, và số lượng phép toán làm cho các bộ giải trực tiếp trở nên thực tế cho các ma trận dày đặc và có dải.

Core questions

• Phép khử Gauss làm giảm một hệ phương trình về dạng tam giác như thế nào, và tại sao điều này tương đương với phân tích LU?
• Tại sao phép xoay trục là cần thiết, và phép xoay trục một phần và hoàn chỉnh kiểm soát sự gia tăng lỗi làm tròn như thế nào?
• Chi phí tính toán của một phép giải trực tiếp là bao nhiêu, và việc khai thác cấu trúc (đối xứng, có dải, thưa thớt) làm giảm chi phí đó như thế nào?
• Trong những điều kiện nào thì phép khử Gauss với xoay trục một phần ổn định ngược trong thực tế?

Key theories

Phân tích LU với xoay trục một phần

Phép khử Gauss với hoán đổi hàng phân tích một ma trận thành PA = LU với L là ma trận tam giác dưới đơn vị và U là ma trận tam giác trên; xoay trục một phần giới hạn các hệ số nhân và làm cho phương pháp đáng tin cậy cho hầu hết các ma trận gặp phải trong thực tế.

Hệ số tăng trưởng và ổn định ngược

Sai số ngược của phép khử Gauss được điều chỉnh bởi hệ số tăng trưởng của các phần tử trong quá trình khử; mặc dù sự tăng trưởng theo cấp số nhân có thể xảy ra trong các trường hợp được tạo ra, xoay trục một phần giữ cho sự tăng trưởng đủ nhỏ để phương pháp ổn định ngược cho hầu hết các vấn đề thực tế.

Mechanisms

Phép khử Gauss tiến hành theo từng cột: ở mỗi bước, một phần tử xoay trục được chọn (xoay trục một phần chọn ứng cử viên có độ lớn lớn nhất trong cột hiện tại), các bội số của hàng xoay trục được trừ đi từ các hàng bên dưới để tạo ra các số 0, và các hệ số nhân được lưu trữ để tạo thành L. Ma trận U tam giác trên thu được được giải bằng phép thế ngược và vế phải được xử lý bằng phép thế xuôi. Đối với một ma trận dày đặc n-nhân-n, phép phân tích tốn khoảng hai phần ba n-lập phương phép toán, trong khi mỗi lần giải tam giác tốn bậc n-bình phương.

Clinical relevance

Các bộ giải trực tiếp là công cụ mặc định bất cứ khi nào một hệ thống dày đặc hoặc có dải kích thước vừa phải phải được giải với độ chính xác đầy đủ — trong lắp ráp phần tử hữu hạn, mô phỏng mạch, điều khiển, và như là phép giải bên trong các sơ đồ số lớn hơn — và một phép phân tích duy nhất có thể được tái sử dụng để giải nhiều vế phải một cách hiệu quả.

History

Các phương pháp khử có nguồn gốc từ Gauss và trước đó, nhưng hành vi của chúng trong số học chính xác hữu hạn đã được làm rõ bởi phân tích lỗi ngược của Wilkinson vào những năm 1960, cho thấy rằng xoay trục một phần kiểm soát sự gia tăng lỗi và giải thích độ tin cậy thực nghiệm của phương pháp đã được quan sát từ lâu trên các máy tính đời đầu.

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

Khi nào nên ưu tiên phương pháp trực tiếp hơn phương pháp lặp?

Các phương pháp trực tiếp được ưu tiên khi ma trận dày đặc hoặc có kích thước vừa phải, khi nhiều vế phải chia sẻ một ma trận (do đó một phép phân tích duy nhất được tái sử dụng), hoặc khi cần một nghiệm được đảm bảo hữu hạn, độ chính xác đầy đủ. Các hệ thống thưa thớt rất lớn thường ưu tiên các phương pháp lặp.

Phép xoay trục có luôn đảm bảo sai số nhỏ không?

Xoay trục một phần đảm bảo ổn định ngược trong thực tế cho hầu hết các ma trận, nhưng nó không khắc phục được tình trạng xấu: nếu bản thân ma trận gần như suy biến, ngay cả một phép giải ổn định ngược cũng có thể trả về một nghiệm với sai số tiến lớn.