Invert 4x4 matrix - Giải pháp ổn định số nhất cần thiết

Question

Tôi muốn đảo ngược ma trận 4x4. Số của tôi được lưu trữ ở định dạng điểm cố định (chính xác là 1.15.16).

Với số học dấu phẩy động, tôi thường chỉ xây dựng ma trận điểm nối và chia cho yếu tố quyết định (ví dụ: brute force the solution). Điều đó làm việc cho tôi cho đến nay, nhưng khi giao dịch với số điểm cố định tôi nhận được một sự mất chính xác không thể chấp nhận do tất cả các phép nhân được sử dụng.

Lưu ý: Trong số học điểm cố định, tôi luôn vứt bỏ một số bit quan trọng nhất có kết quả tức thời.

Vậy - Cách ổn định số nhất để đảo ngược ma trận là gì? Tôi không quan tâm nhiều về hiệu suất, nhưng chỉ đơn giản là đi đến điểm nổi sẽ là làm chậm kiến ​​trúc mục tiêu của tôi.

Answer 1

Tôi nghĩ câu trả lời cho điều này phụ thuộc vào dạng chính xác của ma trận. Một phương pháp phân hủy tiêu chuẩn (LU, QR, Cholesky vv) với xoay vòng (một điều cần thiết) là khá tốt trên điểm cố định, đặc biệt là cho một ma trận 4x4 nhỏ. Xem cuốn sách 'Bí quyết số' của Press et al. để có mô tả về các phương pháp này.

This paper cung cấp một số thuật toán hữu ích, nhưng sau một khoản hoàn trả không may. Họ đề nghị một (phân tách) Cholesky phân hủy với một số tính năng bổ sung quá phức tạp để liệt kê ở đây.

Answer 2

Loại bỏ Gauss cũ đồng đều sẽ hoạt động tốt.

Tùy thuộc vào thư viện/lớp/cấu trúc bạn đang sử dụng. Bạn có thể xem qua số GSL.

Answer 3

Để giảm thiểu lỗi cắt ngắn và các lỗi khác, hãy sử dụng "xoay vòng" - xem chương về ma trận đảo ngược trong Công thức số. Họ có giải thích tốt nhất tôi đã tìm thấy cho đến nay.

Answer 4

Câu trả lời meta: Có thực sự là ma trận 4x4 chung không? Nếu ma trận của bạn có một biểu mẫu đặc biệt, thì có các công thức trực tiếp để đảo ngược sẽ nhanh và duy trì hoạt động của bạn.

Ví dụ, nếu đó là một tiêu chuẩn tọa độ đồng nhất chuyển đổi từ đồ họa, như:

[ux vx wx tx] 
[uy vy wy ty] 
[uz vz wz tz] 
[ 0 0 0 1] 

(giả định một thành phần của luân chuyển, quy mô, ma trận dịch)

sau đó có một easily-derivable direct formula, đó là

[ux uy uz -dot(u,t)] 
[vx vy vz -dot(v,t)] 
[wx wy wz -dot(w,t)] 
[ 0 0 0  1 ] 

(ma trận ASCII bị lấy cắp từ trang được liên kết.)

Có thể bạn không thể đánh bại điều đó vì mất độ chính xác ở điểm cố định.

Nếu ma trận của bạn đến từ một số miền nơi bạn biết nó có cấu trúc nhiều hơn, thì có thể có một câu trả lời dễ dàng.

Answer 5

Nếu ma trận đại diện cho phép biến đổi affine (nhiều lần trường hợp này với ma trận 4x4 miễn là bạn không giới thiệu thành phần co giãn) thì nghịch đảo chỉ đơn giản là chuyển vị trí của phần quay 3x3 trên cùng với cột cuối cùng bị phủ định . Rõ ràng nếu bạn yêu cầu một giải pháp tổng quát thì nhìn vào loại bỏ Gaussian có lẽ là dễ nhất.

Answer 6

Bạn có thể xem xét tăng gấp đôi lên 1,31 trước khi thực hiện thuật toán thông thường của mình.Nó sẽ tăng gấp đôi số phép nhân, nhưng bạn đang làm một ma trận nghịch đảo và bất cứ điều gì bạn làm là sẽ được khá gắn liền với số nhân trong bộ vi xử lý của bạn.

Đối với bất kỳ ai quan tâm đến việc tìm phương trình cho một nghịch đảo 4x4, bạn có thể sử dụng một gói toán học tượng trưng để giải quyết chúng cho bạn. TI-89 sẽ làm điều đó ngay cả, mặc dù nó sẽ mất vài phút.

Nếu bạn cho chúng tôi biết ý tưởng của ma trận đảo ngược đối với bạn và cách nó phù hợp với phần còn lại của quá trình xử lý, chúng tôi có thể đề xuất các lựa chọn thay thế.

-Adam

Answer 7

Hãy để tôi đặt một câu hỏi khác nhau: làm bạn chắc chắn cần phải đảo ngược ma trận (gọi nó là M), hay bạn cần phải sử dụng nghịch đảo ma trận để giải quyết các phương trình khác? (ví dụ: Mx = b cho M đã biết, b) Thông thường có nhiều cách khác để thực hiện điều này một cách rõ ràng cần tính toán nghịch đảo. Hoặc nếu ma trận M là một hàm của thời gian & nó thay đổi từ từ sau đó bạn có thể tính toán nghịch đảo đầy đủ một lần, & có các cách lặp lại để cập nhật nó.

Answer 8

Tôi muốn đặt câu hỏi thứ hai mà Jason S nêu ra: bạn có chắc chắn rằng bạn cần đảo ngược ma trận của mình không? Điều này gần như không bao giờ cần thiết. Không chỉ vậy, nó thường là một ý tưởng tồi. Nếu bạn cần giải quyết Ax = b, nó ổn định về số lượng để giải quyết hệ thống trực tiếp hơn so với nhân b với nghịch đảo A.

Thậm chí nếu bạn phải giải quyết Ax = b và nhiều hơn cho nhiều giá trị b, bạn vẫn có thể đảo ngược A. Bạn có thể yếu tố A (nói hệ số LU hoặc hệ số Cholesky) và lưu các yếu tố do đó bạn không phải làm lại công việc đó mọi lúc, nhưng bạn vẫn sẽ giải quyết hệ thống mỗi lần bằng cách sử dụng hệ số.