Thuật toán tốt nhất để tránh mất độ chính xác?

Question

Bài tập về nhà gần đây tôi nhận được yêu cầu chúng tôi thực hiện các biểu thức có thể tạo ra sự mất chính xác khi được thực hiện trong máy tính và thay đổi chúng để tránh mất mát này.

Thật không may, các hướng dẫn thực hiện việc này chưa được thực hiện rất rõ ràng. Từ xem các ví dụ khác nhau được thực hiện, tôi biết rằng có một số phương pháp làm điều này: sử dụng chuỗi Taylor, sử dụng liên hợp nếu rễ vuông có liên quan, hoặc tìm một mẫu số chung khi hai phân số đang được trừ.

Tuy nhiên, tôi gặp một số sự cố khi nhận thấy chính xác khi nào mất chính xác sẽ xảy ra. Cho đến nay điều duy nhất tôi biết chắc chắn là khi bạn trừ đi hai con số gần giống nhau, sự mất chính xác xảy ra vì các số thứ tự cao là đáng kể và bạn mất những số đó từ vòng tròn.

Câu hỏi của tôi là một số tình huống phổ biến khác mà tôi nên tìm kiếm, và những gì được coi là phương pháp 'tốt' để tiếp cận chúng?

Ví dụ, đây là một vấn đề:

f(x) = tan(x) − sin(x) when x ~ 0 

thuật toán tốt nhất và tồi tệ nhất cho việc đánh giá này ra khỏi ba lựa chọn là gì:

(a) (1/ cos(x) − 1) sin(x), 
(b) (x^3)/2 
(c) tan(x)*(sin(x)^2)/(cos(x) + 1). 

Tôi hiểu rằng khi x gần số không, tan (x) và sin (x) gần như giống nhau. Tôi không hiểu làm thế nào hoặc tại sao bất kỳ thuật toán nào tốt hơn hoặc tệ hơn để giải quyết vấn đề.

Answer 1

Quy tắc chung khác thường được sử dụng là: Khi thêm chuỗi số dài, hãy bắt đầu thêm từ các số gần nhất bằng 0 và kết thúc bằng số lớn nhất.

Giải thích lý do tại sao điều này là tốt là khéo léo. khi bạn đang thêm số nhỏ vào một số lớn, có khả năng chúng sẽ bị loại bỏ hoàn toàn bởi vì chúng nhỏ hơn chữ số thấp nhất trong hệ thống hiện tại của một số lớn. lấy ví dụ tình trạng này:

a = 1,000,000; 
do 100,000,000 time: 
    a += 0.01; 

nếu 0.01 nhỏ hơn chữ số mantissa thấp nhất, sau đó vòng lặp không làm gì và kết quả cuối cùng là một == 1.000.000 nhưng nếu bạn làm điều này như thế này:

a = 0; 
do 100,000,000 time: 
    a += 0.01; 
a += 1,000,000; 

So với số thấp từ từ tăng lên và bạn có nhiều khả năng kết thúc với thứ gì đó gần với == 2.000.000, đó là câu trả lời đúng.
Đây là ofcourse một ví dụ cực đoan nhưng tôi hy vọng bạn sẽ có được ý tưởng.

Answer 2

Tôi phải học lại lớp số khi tôi còn là sinh viên, và điều đó thật đau đớn. Nhưng dù sao, IEEE 754 là tiêu chuẩn điểm nổi thường được thực hiện bởi các CPU hiện đại. Nó rất hữu ích để hiểu những điều cơ bản của nó, vì điều này mang lại cho bạn rất nhiều trực giác về những gì không làm. Giải thích đơn giản của nó là các máy tính lưu trữ các số dấu chấm động trong một cái gì đó như ký hiệu khoa học cơ bản-2 với một số cố định các chữ số (bit) cho số mũ và cho phần định trị. Điều này có nghĩa là giá trị tuyệt đối của một số càng lớn thì chính xác nó càng ít được biểu diễn. Đối với các phao 32 bit trong IEEE 754, một nửa các mẫu bit có thể đại diện giữa -1 và 1, mặc dù các con số lên tới khoảng 10^38 có thể biểu diễn bằng phao 32 bit. Đối với các giá trị lớn hơn 2^24 (khoảng 16,7 triệu), phao 32 bit không thể đại diện chính xác cho tất cả các số nguyên.

Điều này có nghĩa cho bạn là bạn thường muốn tránh những điều sau:

1. Có giá trị trung gian là rất lớn khi câu trả lời chính thức dự kiến ​​sẽ được nhỏ.

2. Thêm/trừ các số nhỏ đến/từ số lớn. Ví dụ, nếu bạn đã viết một cái gì đó như:

   cho (chỉ số float = 17.000.000; index < 17.000.001; index ++) {}

Vòng lặp này sẽ không bao giờ chấm dứt bởi vì 17.000.000 + 1 được làm tròn xuống đến 17.000.000. Nếu bạn có một cái gì đó như:

float foo = 10000000 - 10000000.0001 

Giá trị cho foo sẽ là 0, không -0,0001, do làm tròn lỗi.

Answer 3

Một điều cần tránh là trừ các con số gần như bằng nhau, vì điều này cũng có thể dẫn đến tăng độ nhạy cảm với lỗi làm tròn. Đối với các giá trị gần 0, cos (x) sẽ gần bằng 1, vì vậy 1/cos (x) - 1 là một trong những phép trừ mà bạn muốn tránh nếu có thể, vì vậy tôi sẽ nói rằng (a) nên tránh .

Answer 4

Câu hỏi của tôi là những gì một số tình huống phổ biến khác tôi nên tìm cho, và những gì được coi là 'tốt' phương pháp tiếp cận họ?

Có một số cách bạn có thể bị mất chính xác nghiêm trọng hoặc thậm chí thảm khốc.

Lý do quan trọng nhất là số dấu phẩy động có số chữ số giới hạn, ví dụ: đôi có 53 bit. Điều đó có nghĩa là nếu bạn có chữ số "vô ích" không phải là một phần của giải pháp nhưng phải được lưu trữ, bạn sẽ mất chính xác.

Ví dụ (Chúng tôi đang sử dụng các loại thập phân cho trình diễn):

2,598765000000000000000000000100 -

2,598765000000000000000000000099

Phần thú vị là 100-99 = 1 câu trả lời. Như 2.598765 là bình đẳng trong cả hai trường hợp, nó không thay đổi kết quả, nhưng lãng phí 8 chữ số. Tệ hơn nhiều, bởi vì máy tính không biết rằng các chữ số là vô ích, nó buộc phải lưu trữ nó và nhồi nhét 21 số không sau nó, lãng phí ở tất cả 29 chữ số. Thật không may là không có cách nào để phá vỡ nó cho sự khác biệt, nhưng có những trường hợp khác, ví dụ: exp (x) -1 là hàm xuất hiện rất thường xuyên trong vật lý.

Hàm exp gần 0 gần như tuyến tính, nhưng nó thực thi 1 làm số đầu. Vì vậy, với 12 chữ số có nghĩa exp (0,001) -1 = 1,00100050017-1 = 1.00050017e-3

Nếu chúng ta sử dụng thay vì một hàm expm1(), sử dụng các dòng taylor:

1 + x + x^2/2 + x^3/6 ...-1 =

x + x^2/2 + x^3/6 =: expm1 (x)

expm1 (0,001) = 1.00500166667e-3

Tốt hơn nhiều.

Vấn đề thứ hai là các hàm có độ dốc rất dốc như tang của x gần pi/2. tan (11) có độ dốc 50000 có nghĩa là bất kỳ độ lệch nhỏ nào gây ra bởi lỗi làm tròn trước đó sẽ được khuếch đại bởi hệ số 50000! Hoặc bạn có những điểm kỳ dị nếu ví dụ: kết quả đạt 0/0, điều đó có nghĩa là nó có thể có bất kỳ giá trị nào.

Trong cả hai trường hợp, bạn tạo hàm thay thế, chỉ đơn giản là hàm gốc. Nó là không sử dụng để làm nổi bật các phương pháp tiếp cận giải pháp khác nhau bởi vì không có đào tạo bạn sẽ chỉ đơn giản là không "nhìn thấy" vấn đề ở nơi đầu tiên.

Một cuốn sách hay để học và đào tạo: Forman S. Acton: Máy tính thực tế được thực hiện