Higher computing with large degree

Việc tính toán giá trị của đa thức tưởng chừng khá đơn giản nhưng nó thật sự rất phức tạp torng tính toán số.

Trong bài viết này, tôi sẽ trình bày các vấn đề sau:

1) Tính nhanh giá trị đa thức bằng thuật toán Horner.

2) Xác định giá trị đa thức bằng hệ thức truy hồi (sinh ra từ hệ thức đệ qui của phương pháp Horner hoặc  sinh ra giá trị đa thức đặc trưng của đa thức đặc trưng của ma trận ba đường chéo).

Vấn đề 1: Cho đa thức p_n(x)=\sum_{i=0}^{n}a_{n-i}x^{i}.

Với mỗi x, tính giá trị p_n(x).

Input:  bậc đa thức n,  giá trị x, các hệ số của đa thức a=[a_0, a_1, …, a_n].

Output: p_n(x).

Thuật toán 1:

p=a[0];

for i=1:n

p=p+a[i]*x^i;

end

Tại mỗi bước lặp của thuật toán 1, ta cần i phép toán nhân  (x^i được tính bằng cách thực hiện i-1 phép toán nhân liên tiếp) và 1 phép toán cộng. Do đó, trãi qua n bước lặp, thuật toán cần:

  • \displaystyle \sum_{i=1}^n i=\frac{n(n+1)}{2} phép toán nhân và
  • n phép toán cộng.

Như vậy, thuật toán 1 có  độ phức tạp  O(n^2) phép toán nhân. % Bài toán nhân ma trận, ta có thể ước tính số lần thực phép toán nhân hoặc số lần thực hiện phép toán nhân ma trận-vector. Tuy nhiên, phép toán nhân hai số thực sẽ tốt hơn và chỉ xét đến những phép toán nhân thực sự cần thiết, nghĩa là nhân giữa 2 số đều khác 0. Do vậy, ta phân tích thông qua số lượng phận tử khác 0 của ma trận.

Trong thuật toán trên, ta chưa thực sự tiết kiệm khi tính x^i như đã bàn.

Ta có nhiều kiểu để tính nhanh x^i thông qua hệ thức “đệ qui”  sau

Với i\ge 2, ta có x^i=

  • Nếu i chẳn $latex (x^{\frac{i}{2}})^2 $,
  • ngược lại, $latex  x(x^{\frac{i-1}{2}})^2$.

Công thức trên trình bày kiểu đệ qui và thuật toán đệ qui thường dẫn đến việc tính toán lặp lại nhiểu lần, do đó chi phí cao. Tuy nhiên trong cài đặt,  ta có thể cài đặt dưới dạng khử đệ qui và lưu trữ những kết quả cần thiết.

Thuật toán cần khoảng \log_2{i} phép toán  nhân.

Tuy nhiên, trong thuật toán trên, ta tính $x^{i}, i=1, …, n$  nên chi phí có thể tăng cao.

Mặc dù \log_{2}{i}<< i-1 nhưng, tính x^i, i=1, 2, .., n  bằng thuật toán trên, ta cần khoảng

 \sum\limits_{i = 1}^n {{{\log }_2}} \left( i \right) =\log_2{n!} xấp xỉ  $latex n\log_2{n} $  (Điều này được chứng minh thông qua công thức http://en.wikipedia.org/wiki/Factorial hoặc http://www.stat.ualberta.ca/people/schmu/preprints/factorial.pdf).

Ta thấy việc tính giá trị của x^i có thể kế thừa từ x^{i-1}. Điều này sẽ dẫn đến một thuật toán tiết kiệm hơn.

Thuật toán 2:

p=a[0];

xpower=1;

for i=1:n

xpower=x*xpower;

p=p+a[i]*xpower;

end

Thuật toán trên cho phép ta tính giá trị đa thức khoảng O(2n) phép toán nhân.

Nhận xét đa thức p_n có thể viết lại như sau

p_n(x)=x(p_{n-1}(x))+a_{0}.

Thật ra, ta có hệ thức đệ qui p_{i}(x)=x(p_{n-1}(x))+a_{n-i}, \forall i=0, ..., n (1).

Và ta có thể phân tích p_n(x)= x(... x((a_nx+a_{n-1})+a_{n-2})...) (2). Đẳng thức này thực sự cho thấy gia trị của đa thức được tính bởi thuật toán Horner.

Cả (1) và (2) đều dẫn đến một thuật toán xác định giá trị đa thức rất đơn giản để xác định giá trị đa thức chỉ bằng phép toán cộng và nhận. nhân. Và thực sự, nó rất tiết kiệm so với thuật toán 1 và thuật toán 2.

Như phân tích ở trên, ta có thể thầy thuật toán khá nhanh nhưng xpower  có thể dẫn nguy cơ underflow hoặc overflow.

Thuật toán 3:

p=array[0:n];

p[0]=a[0];

for i=1:n

xpower=x*xpower;

p[i]=x*p[i-1]+a[n-i];

end

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: