Lược đồ Horner

Lược đồ Horner hay phương pháp Horner là 1 trong 2 cách:

1) Một thuật toán để biến đổi đa thức

2) Một phương pháp để tính xấp xỉ nghiệm đa thức

Loại 2 còn gọi là phương pháp Ruffini-Horner.

Phương pháp đặt tên theo nhà toán học người Anh William George Horner, mặc dù các phương pháp này đã được biết đến trước đó bởi Paolo Ruffini và sáu trăm năm trước bởi nhà toán học Trung Quốc Tần Cửu Thiều.

Phương pháp biến đổi đa thức

Giả sử ta có đa thức P(x) nào đó, ví dụ là $P(x)=x^{5}+2x^{4}-3x^{3}+4x^{2}-5x-46$. Hãy phân tích đa thức trên bằng đa thức Q(x-2). Điều này có nghĩa là ta sẽ có tên gọi khác là cho đa thức $Q(x-2)=a(x-2)^{4}+b(x-2)^{3}+c(x-2)^{2}+d(x-2)+e$, hãy tìm các hệ số a,b,c,d,e sao cho đa thức Q(x-2) tương đương với đa thức P(x) đã cho. Đầu tiên với lược đồ Horner dạng bảng, ta sẽ lấy 6 giá trị đầu tiên của các hệ số đa thức P(x) làm thành 6 cột, riêng cột đầu tiên ta mặc định cho là x=2. Ở đây ta hạ 1 xuống tất cả các hàng đầu của cột thứ 2 giá trị là 1 của hệ số a đa thức P(x):

	1	2	-3	4	-5	-46
2	1
2	1
2	1
2	1
2	1
2	1

Ta hạ như vậy để áp dụng được quy tắc "nhân ngang, cộng chéo". Bây giờ ta sẽ dùng cách này để điền nốt các số trong bảng:

Ở ô thứ 3 hàng thứ 2 ta lấy 2 ở cột đầu nhân với 1 (vì là nhân ngang) rồi cộng với 2 là hệ số của b (vì là cộng chéo).

Ở ô thứ 4 hàng thứ 3 ta lấy 2 ở cột đầu nhân với kết quả ở ô vừa rồi là 6 và cộng với 5 thì ta thu được kết quả là 17.

Lặp lại các bước này ta thu được bảng sau:

Bậc của đa thức		1	2	-3	4	-5	-46
0	2	1	4	5	14	23	0
1	2	1	6	17	48	119
2	2	1	8	33	114
3	2	1	10	53
4	2	1	12
5	2	1

chú ý là do số bậc của một đa thức n bậc đầy đủ thì sẽ có tối đa n+1 hệ số và do đó có một số vị trí ta không điền vì ta chỉ quan tâm đến giá trị cuối cùng mà thôi.

Như vậy dựa vào bảng trên, ta có thể thu được đa thức $Q(x)=(x-2)^{5}+12(x-2)^{4}+53(x-2)^{3}+114(x-2)^{2}+119(x-2)+0$

Ta có thể kiểm tra lại kết quả này bằng định lý về nghiệm của đa thức:" $a$ được gọi là nghiệm của đa thức $f(x)\Leftrightarrow f(a)=0$".

Dễ thấy vì đa thức Q(x) được phân tích từ đa thức P(x) trong đó có một nhân tử chung là (x-2) do đó một nghiệm của đa thức sẽ là 2, thay 2 vào đa thức Q(x) ta sẽ có kết quả là 0, nếu ta thay 2 vào P(x) mà thu được cùng kết quả thì chứng tỏ Q(x) đã được phân tích từ P(x).

Hoặc ta có thể dùng cách khai triển nhị thức Newton để kiểm tra lại:

$Q(x)=(x-2)^{5}+12(x-2)^{4}+53(x-2)^{3}+114(x-2)^{2}+119(x-2)+0$

$\Leftrightarrow Q(x)=(x^{5}-5x^{4}.2+10x^{3}.2^{2}-10x^{2}.2^{3}+5x.2^{4}-2^{5})+12(x^{4}-4x^{3}.2+6x^{2}.2^{2}-4x.2^{3}+2^{4})+53(x^{3}-3x^{2}.2+3x.2^{2}-2^{3})+114(x^{2}-4x+4)+119(x-2)$

$\Leftrightarrow Q(x)=x^{5}-10x^{4}+40x^{3}-80x^{2}+80x-32+12x^{4}-96x^{3}+288x^{2}-384x+192+53x^{3}-318x^{2}+636x-424+114x^{2}-456x+456+119x-238$

$\Leftrightarrow x^{5}+2x^{4}-3x^{3}+4x^{2}-5x-46$

Chính vì điều này mà phương pháp Horner dùng nhiều tại các bậc học cấp II và cấp III.Những người mới đầu tính sẽ thấy khó nhưng sau đó sẽ rất đơn giản.

Nghiệm của đa thức

Sử dụng phương pháp Luật Newton kết hợp của Horner ta có thể tính xấp xỉ nghiệm của 1 đa thức $p_{n}(x)$ có $z_{n}<z_{n-1}<..<z_{1}$ bằng cách dùng liên tiếp 2 bước sau:

Dùng luật Newton tìm số 0 lớn nhất của $z_{1}$ của $p_{n}(x)$ để đoán nghiệm.

Dùng phương pháp Horner chia ra $(x-z_{1})$ để có $p_{n-1}$ và quay lại bước 1, dùng đa thức ta có ở bước 2 để đoán $z_{1}$.Sau khi lặp như vậy cho đến khi tất cả các số không thực tìm thấy trong đa thức.

Nếu các số không xấp xỉ không đủ chính xác, các giá trị thu được có thể được sử dụng như những dự đoán ban đầu cho phương pháp của Newton nhưng sử dụng đa thức đầy đủ hơn là đa thức đã giảm.

Ta có ví dụ sau:

$p_{6}(x)=(x-3)(x+3)(x+5)(x+8)(x-2)(x-7)$

$\Leftrightarrow p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040$

Từ trên chúng ta biết rằng gốc rễ lớn nhất của đa thức này là 7 vì vậy chúng ta có thể đoán ra được 8. Sử dụng phương pháp của Newton, số không đầu tiên của 7 được tìm thấy như thể hiện màu đen ở hình bên phải.

Sau đó chia cho (x-7) thi đa thức xuống bậc 5 và đường vẽ bằng đồ thị màu đỏ phía dưới, tương tự như vậy ta chia cho (x-3) thì có đồ thị là đường màu vàng và lặp lại được đồ thị màu xanh lá và phương trình giảm xuống còn $p_{2}(x)=x^{2}+13x+40$ và có một đường màu xanh lam và có một số 0 tại -5 và có thể tính ra các nghiệm trong qa trình chia vừa rồi là -8, -5, -3, 2, 3 và 7 [1]

Lịch sử

Dùng phương pháp Horner để tìm gốc rễ thay thế của đa thức cho trước.

Bài báo của Horner có tựa đề "Một phương pháp mới để giải các phương trình số của tất cả các đơn đặt hàng, bằng cách xấp xỉ liên tục"  được đọc trước Hội Hoàng gia London, tại cuộc họp vào ngày 1 tháng 7 năm 1819 với Davies Gilbert, Phó Chủ tịch và Thủ quỹ, trong cái ghế; Đây là cuộc họp cuối cùng của phiên họp trước khi Hiệp hội hoãn lại cho kỳ nghỉ hè của mình. Khi một phần tiếp theo được đọc trước Hiệp hội năm 1823, nó đã được một lần nữa tại cuộc họp cuối cùng của phiên họp. Trong cả hai lần, các bài báo của James Ivory, FRS cũng được đọc. Năm 1819, đó là bài báo của Horner đã thông qua để xuất bản trong "Giao dịch triết học".  vào cuối năm, giấy Ivory rơi xuống, dù Ivory là một Fellow; Năm 1823, khi tổng cộng 10 bài báo được đọc, vận may về xuất bản, đã bị đảo ngược. Nhưng Gilbert, người có quan hệ mật thiết với miền tây nước Anh và có thể đã có mối quan hệ xã hội với Horner, cư dân khi Horner ở Bristol và Bath, đã xuất bản bản khảo sát về các phương pháp kiểu Horner của ông hồi đầu năm 1823.

Bài báo của Horner trong Phần II của Các Giao dịch triết học của Hiệp hội Hoàng gia London cho năm 1819 đã được một nhà bình luận hoan nghênh nhiệt liệt và rộng rãi trong số báo The Monthly Review: hay, Journal Literary Journal for April, 1820; So sánh, một bài báo kỹ thuật của Charles Babbage đã bị loại bỏ trong bài tổng quan này. Tuy nhiên, người đánh giá lưu ý rằng một, phương pháp tương tự gần đây cũng đã được xuất bản bởi kiến ​​trúc sư và toán học expositor, Peter Nicholson. Chủ đề này được phát triển trong một bài đánh giá thêm về một số cuốn sách của Nicholson trong ấn phẩm Đánh giá hàng tháng cho Tháng Mười Hai năm 1820, và kết thúc bằng thông báo về sự xuất hiện của một cuốn sách nhỏ của Theophilus Holdred, Từ đó Nicholson thừa nhận ông đã thu được ý nghĩa quan trọng của phương pháp tiếp cận của mình ở nơi đầu tiên, mặc dù tuyên bố đã cải thiện nó. Trình tự đánh giá được kết luận trong số tháng Tạp chí Đánh giá Hàng tháng tháng 9 năm 1821, với người đánh giá kết luận rằng trong khi Holdred là người đầu tiên khám phá ra một giải pháp thực tiễn trực tiếp và tổng quát về các phương trình số, ông ta đã không giảm nó xuống dạng đơn giản nhất Bởi thời điểm xuất bản của Horner, và nói rằng đã Holdred xuất bản bốn mươi năm trước khi lần đầu tiên ông phát hiện ra phương pháp của mình, sự đóng góp của ông có thể được dễ dàng nhận ra. Người đánh giá được thông báo một cách đặc biệt, thậm chí đã nhìn thấy mối quan hệ chuẩn bị của Horner với Peter Barlow năm 1818, tìm kiếm công việc của Budan. Thư viện Bodlean, Oxford có bản sao chú giải hàng tháng của Biên tập viên, từ đó rõ ràng rằng người đánh giá tích cực nhất trong toán học năm 1814 và 1815 (những năm cuối cùng mà thông tin này đã được xuất bản) không ai khác hơn Peter Barlow, một Của các chuyên gia đầu tiên về lý thuyết xấp xỉ của thời kỳ, cho thấy đó là Barlow, người đã viết chuỗi bài này. Cũng như nó đã xảy ra, Henry Atkinson, của Newcastle, đã đưa ra một kế hoạch xấp xỉ tương tự vào năm 1809; Ông đã hỏi ý kiến ​​đồng nghiệp Geordie của ông, Charles Hutton, một chuyên gia khác và là một đồng nghiệp cao cấp của Barlow tại Học viện Quân sự Hoàng gia, Woolwich, chỉ để được khuyên rằng, trong khi tác phẩm của ông có thể được xuất bản, nó không có nhiều ảnh hưởng. JR Young, viết vào giữa những năm 1830,

Đặc điểm của bài viết của Horner mà hầu hết nó phân biệt nó với những người đương thời tiếng Anh là cách mà ông vẽ trên văn học lục địa, nhất là tác phẩm của Arbogast. Việc vận động, cũng như sự rút gọn, của Phương pháp của Horner đã cho thấy điều này như là một ẩn ý không nói ra. Khá rõ ràng anh ấy đã đạt được sự quen thuộc như thế nào chưa được xác định. Horner được biết là đã đọc cuốn sách của John Bonneycastle về đại số học. Bonneycastle thừa nhận rằng Arbogast có một biểu hiện tổng quát, kết hợp cho việc quay lại series, một dự án ít nhất cũng đến với Newton. Nhưng mục đích chính của Bonneycastle khi đề cập tới Arbogast không phải là khen ngợi ông, nhưng phải quan sát rằng ký pháp của Arbogast không tương thích với phương pháp mà ông chấp nhận. Khoảng cách trong bài đọc của Horner là công việc của Paolo Ruffini, Trừ khi, theo như nhận thức của Ruffini, trích dẫn về tác phẩm của Ruffini bởi các tác giả, bao gồm các tác giả y khoa, trong các Giao dịch Triết học nói về các tác phẩm: không có gì - tên của Ruffini chỉ xuất hiện vào năm 1814, thu âm một tác phẩm mà ông tặng cho Hội Hoàng gia. Ruffini có thể đã làm tốt hơn nếu công việc của ông đã xuất hiện bằng tiếng Pháp, cũng như vấn đề của Malfatti trong việc định hình lại Joseph Diaz Gergonne, hoặc ông đã viết bằng tiếng Pháp, cũng như Antonio Cagnoli, một nguồn trích dẫn của Bonneycastle về sự đảo ngược loạt (hôm nay, Cagnoli Trong Wikipedia tiếng Ý, như được hiển thị, nhưng vẫn chưa làm nó thành tiếng Pháp hoặc tiếng Anh).

Fuller  cho thấy rằng phương pháp trong bài báo 1819 Horner khác với những gì sau đó được gọi là 'Horner phương pháp' và hậu quả là ưu tiên cho phương pháp này nên đến Holdred (1920). Quan điểm này có thể được so sánh với các nhận xét liên quan đến các tác phẩm của Horner và Holdred trong đoạn văn trước. Fuller cũng nhắm vào Augustus De Morgan. Mặc dù Augustus de Morgan là người tiên phong, ông không phải là người đánh giá cho tạp chí Monthly Review , trong khi một số khác - Thomas Stephens Davies, JR Young, Stephen Fenwick, TT Wilkinson - đã viết Horner vững chắc vào hồ sơ của họ, không kém Horner khi ông xuất bản rộng rãi Cho đến năm ông qua đời vào năm 1837. Giấy của ông năm 1819 là một trong những điều khó có thể bỏ qua.

Vấn đề đặt ra là sự ủng hộ của De Morgan đối với sự ưu tiên của Horner trong phát hiện  dẫn tới "phương pháp của Horner" được gọi là sách giáo khoa, nhưng đúng là những gợi ý cho điều này có xu hướng biết về Horner phần lớn Thông qua những người trung gian, trong đó De Morgan đã làm mình trở thành một ví dụ điển hình. Tuy nhiên, phương pháp phương pháp này qua được biết đến từ lâu trước khi Horner. Theo thứ tự thời gian đảo ngược, phương pháp của Horner đã được biết đến:

• Paolo Ruffini năm 1809 (xem quy tắc Ruffini) 
• Isaac Newton năm 1669 (nhưng cần có tham khảo chính xác)
• Nhà toán học Trung Hoa Zhu Shijie vào thế kỷ 14 
• Nhà toán học người Trung Quốc Qin Jiushao trong tác phẩm toán học của mình trong chín phần trong thế kỷ 13
• Nhà toán học người Ả Rập Sharaf al-Dīn al-Tūsī trong thế kỷ 12 (người đầu tiên sử dụng phương pháp đó trong một trường hợp chung của phương trình khối) 
• Nhà toán học Trung Quốc Jia Xian trong thế kỷ 11 (triều đại Song)
• Cửu chương toán thuật , một tác phẩm của triều đại nhà Hán (202 TCN - 220 AD) do Liu Hui biên soạn(thế kỷ thứ 3). 

Tuy nhiên, quan sát trên mặt nạ của chính nó có sự khác biệt đáng kể trong việc thụ thai và cũng như công việc của Ruffini đã đề cập đến vấn đề tiếp cận.

Tần Jiushao, trong ông Shu Shu Jiu Zhang ( Toán Luận trong Chín mục ; 1247), trình bày một danh mục đầu tư của phương pháp Horner-type để giải phương trình đa thức, được dựa trên các tác phẩm trước đó của thế kỷ 11 Sông triều đại nhà toán học Jia Xian; Ví dụ, một phương pháp đặc biệt phù hợp với bi-quintics, trong đó Tần cho một ví dụ, phù hợp với thói quen của Trung Quốc trong các nghiên cứu trường hợp. Người đầu tiên viết bằng tiếng Anh để ghi nhận sự kết nối với phương pháp của Horner là Alexander Wylie, viết trong The North China Herald năm 1852; Có thể xen kẽ và hiểu nhầm các cụm từ khác nhau của Trung Quốc, Wylie gọi phương pháp Harmoniously Alternating Evolution (điều này không đồng nghĩa với việc Trung Hoa, linglong kaifang , không phải vào thời điểm đó ông ta sử dụng bính âm), làm việc trong trường hợp của một trong những tứ phân của Tần và đưa ra, để so sánh, làm việc với phương pháp của Horner. Yoshio Mikami trong Phát triển Toán học ở Trung Quốc và Nhật Bản được xuất bản ở Leipzig năm 1913, đã đưa ra một mô tả chi tiết về phương pháp của Tần, sử dụng quartic minh họa ở bên trên bên phải trong một ví dụ làm việc; Ông đã viết: "người có thể phủ nhận thực tế quá trình nổi tiếng của Horner đang được sử dụng ở Trung Quốc ít nhất là gần sáu thế kỷ dài trước đó hơn ở châu Âu... Tất nhiên chúng tôi không có ý định bằng cách nào để gán cho Horner phát minh ra nguồn gốc Trung Quốc, Nhưng sau đó là một giáo sư về triết học so sánh) đã đưa ra một mô tả chi tiết trong luận án tiến sĩ về phương pháp Tần, ông kết luận: Rõ ràng là thủ tục này là một phát minh của Trung Quốc.... phương pháp này không được biết đến ở Ấn Độ . Ông nói, Fibonacci có lẽ đã học được nó từ người Ả Rập, có lẽ người vay mượn từ Trung Quốc.  Ở đây, vấn đề là không có bằng chứng nào cho sự suy đoán này hơn là phương pháp được biết đến ở Ấn Độ. Tất nhiên, việc khai thác các hình vuông và hình lập phương dọc theo các đường tương tự đã được thảo luận bởi Liu Hui kết nối với các vấn đề IV.16 và 22 trong Jiu Zhang Suan Shu , [2] [3][4]

Liên kết ngoài

• http://dl.acm.org/citation.cfm?doid=364063.364089

• https://www.encyclopediaofmath.org/index.php/Horner_scheme

• https://www.ece.cmu.edu/~ece447/s15/lib/exe/fetch.php?media=horner-1819.pdf

• http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183421253