Tìm nguồn gốc của một số lượng lớn các chức năng với một biến

Question

Tôi đang làm việc với Python/numpy/scipy để viết một trình theo dõi tia nhỏ. Các bề mặt được mô hình hóa như các hàm hai chiều cho chiều cao trên mặt phẳng bình thường. Tôi giảm vấn đề tìm điểm giao nhau giữa tia và bề mặt để tìm gốc của hàm với một biến. Các chức năng liên tục và có thể thay đổi.

Có cách nào để thực hiện điều này hiệu quả hơn chỉ đơn giản là lặp qua tất cả các chức năng, sử dụng trình tìm gốc scipy (và có thể sử dụng nhiều quy trình)?

Chỉnh sửa: Các hàm là sự khác biệt giữa hàm tuyến tính đại diện cho tia và hàm bề mặt, bị ràng buộc với mặt phẳng giao nhau.

Answer 1

Ví dụ sau đây cho thấy tính toán gốc cho 1 triệu bản của hàm x ** (a + 1) - b (tất cả với a và b) song song khác nhau bằng phương pháp chia đôi. Mất khoảng 12 giây ở đây.

import numpy 

def F(x, a, b): 
    return numpy.power(x, a+1.0) - b 

N = 1000000 

a = numpy.random.rand(N) 
b = numpy.random.rand(N) 

x0 = numpy.zeros(N) 
x1 = numpy.ones(N) * 1000.0 

max_step = 100 
for step in range(max_step): 
    x_mid = (x0 + x1)/2.0 
    F0 = F(x0, a, b) 
    F1 = F(x1, a, b) 
    F_mid = F(x_mid, a, b) 
    x0 = numpy.where(numpy.sign(F_mid) == numpy.sign(F0), x_mid, x0) 
    x1 = numpy.where(numpy.sign(F_mid) == numpy.sign(F1), x_mid, x1) 
    error_max = numpy.amax(numpy.abs(x1 - x0)) 
    print "step=%d error max=%f" % (step, error_max) 
    if error_max < 1e-6: break 

Ý tưởng cơ bản là chỉ cần chạy tất cả các bước thông thường của một công cụ tìm gốc song song trên một vector của các biến, sử dụng một chức năng có thể được đánh giá trên một vector của các biến và vector tương đương (s) các thông số xác định các hàm thành phần riêng lẻ. Các điều kiện được thay thế bằng sự kết hợp của các mặt nạ và numpy.where(). Điều này có thể tiếp tục cho đến khi tất cả các rễ đã được tìm thấy với độ chính xác cần thiết, hoặc luân phiên cho đến khi đủ rễ đã được tìm thấy rằng nó là giá trị để loại bỏ chúng khỏi vấn đề và tiếp tục với một vấn đề nhỏ hơn mà loại trừ những gốc rễ.

Các chức năng tôi chọn để giải quyết là tùy ý, nhưng nó sẽ giúp ích nếu các chức năng được xử lý tốt; trong trường hợp này tất cả các chức năng trong gia đình đều đơn điệu và có chính xác một gốc tích cực. Ngoài ra, đối với phương pháp bisection, chúng ta cần đoán cho biến có các dấu hiệu khác nhau của hàm, và những biến thể cũng khá dễ dàng để tìm ra ở đây (các giá trị ban đầu của x0 và x1).

Đoạn mã trên có thể sử dụng công cụ tìm gốc đơn giản nhất, nhưng kỹ thuật tương tự có thể dễ dàng áp dụng cho Newton-Raphson, Ridder, v.v. Có ít điều kiện hơn trong phương pháp tìm gốc, phù hợp hơn này. Tuy nhiên, bạn sẽ phải thực hiện lại bất kỳ thuật toán nào bạn muốn, không có cách nào để sử dụng trực tiếp chức năng tìm gốc thư viện hiện có.

Đoạn mã trên được ghi rõ ràng, không phải tốc độ. Tránh sự lặp lại của một số tính toán, đặc biệt là đánh giá chức năng chỉ một lần mỗi lần lặp thay vì 3 lần, tốc độ này lên đến 9 giây, như sau:

... 
F0 = F(x0, a, b) 
F1 = F(x1, a, b) 

max_step = 100 
for step in range(max_step): 
    x_mid = (x0 + x1)/2.0 
    F_mid = F(x_mid, a, b) 
    mask0 = numpy.sign(F_mid) == numpy.sign(F0) 
    mask1 = numpy.sign(F_mid) == numpy.sign(F1) 
    x0 = numpy.where(mask0, x_mid, x0) 
    x1 = numpy.where(mask1, x_mid, x1) 
    F0 = numpy.where(mask0, F_mid, F0) 
    F1 = numpy.where(mask1, F_mid, F1) 
... 

Để so sánh, sử dụng scipy.bisect() để tìm một gốc tại một thời điểm mất ~ 94 giây: