การหาคำตอบของพหุนามเป็นปัญหาที่มีมายาวนานและได้รับการศึกษาอย่างกว้างขวางตลอดประวัติศาสตร์ ซึ่งมีอิทธิพลอย่างมากต่อการพัฒนาของคณิตศาสตร์ ปัญหานี้เกี่ยวข้องกับการหาค่าประมาณเชิงตัวเลขหรือสูตรสำเร็จรูปของคำตอบของพหุนามตัวแปรเดียว กล่าวคือ การหาคำตอบโดยประมาณหรือสูตรสำเร็จรูปของสมการ ${\displaystyle x}$

${\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}$

โดยที่ จำนวน เหล่านั้นเป็นจำนวน จริงหรือจำนวนเชิงซ้อน${\displaystyle a_{i}}$

ความพยายามในการ ทำความ เข้าใจและแก้สมการพหุนามนำไปสู่การพัฒนาแนวคิดทางคณิตศาสตร์ที่สำคัญหลายประการ รวมถึงจำนวนอตรรกยะและจำนวนเชิงซ้อน ตลอดจนโครงสร้างพื้นฐานในพีชคณิตสมัยใหม่ เช่นฟิลด์วงแหวนและกลุ่ม

แม้ว่าการค้นหารากของพหุนามดีกรีสูงจะมีความสำคัญทางประวัติศาสตร์ แต่ก็ไม่ได้มีบทบาทสำคัญอีกต่อไปในคณิตศาสตร์และคณิตศาสตร์เชิงคำนวณ ยกเว้นเพียงกรณีเดียวในพีชคณิตคอมพิวเตอร์^{[ 1 ]}

สูตรสำเร็จรูปสำหรับรากของพหุนามมีอยู่เฉพาะเมื่อดีกรีของพหุนามน้อยกว่า 5 เท่านั้น สูตรกำลังสองเป็นที่รู้จักกันมาตั้งแต่สมัยโบราณ และ สูตร กำลังสามและกำลังสี่ถูกค้นพบอย่างสมบูรณ์ในศตวรรษที่ 16

เมื่อดีกรีของพหุนามอย่างน้อย 5 โดยทั่วไปแล้วจะไม่มีสูตรสำเร็จรูปสำหรับหาค่ารากโดยใช้สัมประสิทธิ์ของพหุนาม หากเราใช้เพียงการบวก การลบ การคูณ การหาร และการหารากที่ n ในสูตรเท่านั้น นี่เป็นผลมาจากทฤษฎีบทอาเบล-รัฟฟินี อันโด่งดัง ในทางกลับกันทฤษฎีบทพื้นฐานของพีชคณิตแสดงให้เห็นว่าพหุนามที่ไม่คงที่ทั้งหมดมีรากอย่างน้อยหนึ่งราก ดังนั้นในกรณีส่วนใหญ่ อัลกอริทึมการหาค่ารากจึงประกอบด้วยการหาคำตอบเชิงตัวเลข

อัลกอริทึมการหาค่ารากสามารถแบ่งออกได้เป็นหมวดหมู่ใหญ่ๆ ตามเป้าหมายของการคำนวณ บางวิธีมีเป้าหมายเพื่อหาค่ารากเพียงค่าเดียว ในขณะที่บางวิธีออกแบบมาเพื่อหาค่ารากเชิงซ้อนทั้งหมดพร้อมกัน ในบางกรณี เป้าหมายอาจเป็นการหาค่ารากภายในบริเวณเฉพาะของระนาบเชิงซ้อน บ่อยครั้งเป็นที่พึงปรารถนาและจำเป็นที่จะต้องเลือกอัลกอริทึมที่เฉพาะเจาะจงกับงานคำนวณนั้นๆ เนื่องจากเหตุผลด้านประสิทธิภาพและความแม่นยำ ดูหัวข้อ วิธีการค้นหาค่าราก สำหรับสรุปวิธีการที่มีอยู่สำหรับแต่ละกรณี

ปัญหาการหาคำตอบของสมการพหุนามได้รับการค้นพบครั้งแรกโดยชาวสุเมเรียนและชาวบาบิโลน นับจากนั้นมา การค้นหาสูตรสำเร็จรูปสำหรับสมการพหุนามก็ดำเนินมาเป็นเวลาหลายพันปี

ชาวบาบิโลนและชาวอียิปต์สามารถแก้สมการกำลังสองเฉพาะได้ในช่วงสหัสวรรษที่สองก่อนคริสต์ศักราช และคำตอบของพวกเขาโดยพื้นฐานแล้วสอดคล้องกับสูตรกำลังสอง^{[ 2 ]}

อย่างไรก็ตาม ต้องใช้ความพยายามถึง 2 พันปีในการกำหนดสูตรกำลังสองในรูปแบบที่ชัดเจนคล้ายกับสูตรสมัยใหม่ ซึ่งนักคณิตศาสตร์ชาวอินเดียพราหมณคุปตะ ได้นำเสนอไว้ ในหนังสือ Brāhmasphuṭasiddhāntaในปี ค.ศ. 625 การยอมรับสูตรกำลังสองอย่างสมบูรณ์นั้นจำเป็นต้องมีการนำจำนวนเชิงซ้อนมาใช้ ซึ่งต้องใช้เวลาอีกพันปี

ความก้าวหน้าครั้งแรกในสูตรสำเร็จรูปสำหรับพหุนามที่มีดีกรีสูงกว่าสองเกิดขึ้นในอิตาลี ในช่วงต้นศตวรรษที่ 16 นักคณิตศาสตร์ชาวอิตาลีScipione del Ferroค้นพบสูตรสำเร็จรูปสำหรับสมการกำลังสามในรูปแบบโดยที่เป็นจำนวนที่ไม่เป็นลบ ต่อมา Niccolò Tartagliaก็ค้นพบวิธีการแก้สมการกำลังสามดังกล่าวเช่นกัน และGerolamo Cardanoได้สรุปและตีพิมพ์ผลงานของพวกเขาในหนังสือArs Magnaในปี 1545 ${\displaystyle x^{3}+mx=n}$${\displaystyle m,n}$

ในขณะเดียวกัน โลโดวิโก เฟอร์รารีศิษย์ของคาร์ดาโนค้นพบสูตรสำเร็จรูปของสมการกำลังสี่ในปี 1540 วิธีแก้ปัญหาของเขาอิงตามสูตรสำเร็จรูปของสมการกำลังสาม ดังนั้นจึงต้องรอจนกว่าสูตรกำลังสามจะได้รับการตีพิมพ์

ในหนังสือ Ars Magnaคาร์ดาโนสังเกตเห็นว่าวิธีการของทาร์ตาเกลียบางครั้งเกี่ยวข้องกับการหาค่ารากที่สองของจำนวนลบ อันที่จริง สิ่งนี้อาจเกิดขึ้นได้แม้ว่ารากนั้นจะเป็นจำนวนจริงก็ตามต่อ มา ราฟาเอล บอมเบลลีนักคณิตศาสตร์ชาวอิตาลีได้ศึกษาวัตถุทางคณิตศาสตร์เหล่านี้เพิ่มเติมโดยให้กฎทางคณิตศาสตร์ที่ชัดเจนในหนังสือพีชคณิต ของเขา ที่ตีพิมพ์ในปี 1569 วัตถุทางคณิตศาสตร์เหล่านี้ในปัจจุบันรู้จักกันในชื่อจำนวนเชิงซ้อนซึ่งเป็นพื้นฐานในคณิตศาสตร์ ฟิสิกส์ และวิศวกรรม

นับตั้งแต่การค้นพบสูตรกำลังสามและกำลังสี่ การแก้สมการกำลังห้าในรูปแบบปิดถือเป็นปัญหาสำคัญในพีชคณิต นักกฎหมายชาวฝรั่งเศสชื่อ Vieteซึ่งเป็นคนแรกที่กำหนดสูตรรากสำหรับกำลังสามในภาษาสมัยใหม่และนำวิธีการตรีโกณมิติมาใช้ในการแก้ราก เชื่อว่าวิธีการของเขาสามารถขยายไปสู่สูตรในรูปแบบปิดในรากสำหรับพหุนามที่มีดีกรีใดๆ ก็ได้ Descartesก็มีความคิดเห็นเช่นเดียวกัน^{[ 3 ]}

อย่างไรก็ตามลากรองจ์สังเกตเห็นข้อบกพร่องในข้อโต้แย้งเหล่านี้ในบทความ เรื่อง "การไตร่ตรองเกี่ยว กับทฤษฎีพีชคณิตของสมการ" ใน ปี 1771 ซึ่งเขาได้วิเคราะห์ว่าทำไมวิธีการที่ใช้แก้สมการกำลังสามและกำลังสี่จึงใช้ไม่ได้ผลกับสมการกำลังห้า ข้อโต้แย้งของเขาเกี่ยวข้องกับการศึกษาการเรียงสับเปลี่ยนของรากของสมการพหุนาม ถึงกระนั้น ลากรองจ์ก็ยังเชื่อว่าสูตรสำเร็จรูปสำหรับรากของสมการกำลังห้ามีอยู่จริง ดูเหมือนว่าเกาส์จะเป็นนักคณิตศาสตร์ที่มีชื่อเสียงคนแรกที่สงสัยว่าสมการกำลังห้านั้นแก้ไม่ได้ โดยระบุไว้ในวิทยานิพนธ์ปริญญาเอกของเขาในปี 1799

ความพยายามครั้งแรกอย่างจริงจังในการพิสูจน์ว่าสมการกำลังห้าไม่สามารถหาคำตอบได้นั้น มาจากนักคณิตศาสตร์ชาวอิตาลีชื่อ เปาโล รัฟฟินี เขาตีพิมพ์บทพิสูจน์ถึงหกฉบับระหว่างปี 1799 ถึง 1813 แต่บทพิสูจน์ของเขาไม่ได้รับการยอมรับอย่างกว้างขวาง เนื่องจากเนื้อหาเขียนยาวและเข้าใจยาก อีกทั้งยังพบว่ามีช่องว่างอยู่

การพิสูจน์อย่างเข้มงวดและเป็นที่ยอมรับครั้งแรกเกี่ยวกับความไม่สามารถหาคำตอบได้ของพหุนามกำลังห้า ได้รับการเสนอโดยนีลส์ เฮนริก อาเบลในปี ค.ศ. 1824 ซึ่งใช้ทฤษฎีการขยายฟิลด์ของกาลัวส์อย่างสำคัญ ในบทความนั้น อาเบลพิสูจน์ว่าพหุนามที่มีดีกรีมากกว่า 4 โดยทั่วไปไม่มีสูตรรากแบบปิดโดยใช้รากที่สอง สิ่งนี้ยุติการค้นหาสูตรรากแบบปิดของพหุนามโดยใช้รากที่สองของสัมประสิทธิ์พหุนาม

ในปี 2025 นอร์แมน ไวลด์เบอร์เกอร์และดีน รูไบน์ได้นำเสนอวิธีแก้ปัญหาทั่วไปสำหรับดีกรีใดๆ โดยใช้ชุดอนุกรมกำลังเชิงรูปธรรม สมการดังกล่าวมีคำตอบ ${\displaystyle 1-x+a_{2}x^{2}+a_{3}x^{3}+a_{4}x^{4}+...}$

${\displaystyle x=\sum _{m_{2},m_{3},...\geq 0}{{\frac {(2m_{2}+3m_{3}+4m_{4}+...)!}{(1+m_{2}+2m_{3}+...)!m_{2}!m_{3}!...}}a_{2}^{m_{2}}a_{3}^{m_{3}}...}}$

นี่เป็นการสรุปทั่วไปของวิธีแก้ปัญหาสำหรับสมการกำลังสองโดยใช้จำนวนคาตาลัน ซึ่งจะลดลงเหลือสำหรับสมการกำลังห้า สิ่งนี้มีความเกี่ยวข้องอย่างใกล้ชิดกับอนุกรมไอเซนสไตน์^{[ 4 ]}${\displaystyle C_{n}}$${\displaystyle x=\sum _{n\geq 0}C_{n}t^{n}}$

เนื่องจากการหาคำตอบในรูปแบบปิดของพหุนามดีกรีสูงนั้นยากกว่าการหาคำตอบของสมการกำลังสองมาก ความพยายามแรกเริ่มในการแก้สมการกำลังสามจึงมักใช้วิธีทางเรขาคณิตหรือวิธีเชิงตัวเลข นอกจากนี้ ในทางปฏิบัติแล้ว วิธีแก้ปัญหาเชิงตัวเลขก็มีความจำเป็นเช่นกัน

วิธีการประมาณค่าแบบวนซ้ำที่เก่าแก่ที่สุดในการหาค่ารากถูกพัฒนาขึ้นเพื่อคำนวณรากที่สอง ในหนังสือMetrica ของ Heron แห่ง Alexandria (คริสต์ศตวรรษที่ 1-2) ค่าประมาณของรากที่สองถูกคำนวณโดยการปรับปรุงค่าประมาณเริ่มต้นแบบวนซ้ำ^{[ 5 ]} Jamshīd al-Kāshīได้นำเสนอวิธีการแบบทั่วไปเพื่อคำนวณรากที่ th วิธีการที่คล้ายกันนี้ยังพบได้ใน สิ่งพิมพ์ Trigonometria BritannicaของHenry Briggsในปี 1633 Franciscus Vietaยังได้พัฒนาวิธีการประมาณค่าที่เกือบจะเหมือนกับวิธีการของ Newton อีกด้วย ${\displaystyle n}$

นิวตันได้ขยายวิธีการคำนวณรากของพหุนามใดๆ ในDe analysi per aequationes numero terminorum infinitas (เขียนในปี 1669 ตีพิมพ์ในปี 1711) ซึ่งปัจจุบันรู้จักกันในชื่อวิธีการของนิวตันในปี 1690 โจเซฟ ราฟสัน ได้ตีพิมพ์การปรับปรุงวิธีการของนิวตัน โดยนำเสนอในรูปแบบที่สอดคล้องกับเวอร์ชันสมัยใหม่ที่ใช้ในปัจจุบันมากขึ้น^{[ 6 ]}

ในปี ค.ศ. 1879 นักคณิตศาสตร์ชาวอังกฤษอาร์เธอร์ เคย์ลีย์สังเกตเห็นถึงความยากลำบากในการขยายวิธีการของนิวตันไปสู่รากเชิงซ้อนของพหุนามที่มีดีกรีมากกว่า 2 และค่าเริ่มต้นเชิงซ้อน ในบทความของเขาเรื่อง " ปัญหาจินตนาการของนิวตัน-ฟูริเยร์"ซึ่งเปิดทางไปสู่การศึกษาทฤษฎีการวนซ้ำของฟังก์ชันตรรกยะ

วิธีการหาค่าตัวเลขของรากจริงวิธีหนึ่งนั้นอาศัยการแยกรากจริงตัวอย่างแรกของวิธีนี้เสนอโดยเรเน่ เดส์การ์ตส์ในปี ค.ศ. 1637 โดยนับรากของพหุนามโดยการตรวจสอบการเปลี่ยนแปลงเครื่องหมายของสัมประสิทธิ์ ในปี ค.ศ. 1807 นักคณิตศาสตร์ชาวฝรั่งเศสฟรองซัวส์ บูดอง เดอ บัวส์ลอรองต์ ได้ขยายผลลัพธ์ของเดส์การ์ตส์ไปเป็นทฤษฎีบทของบูดองซึ่งนับรากจริงในช่วงครึ่งเปิด ( a , b ) อย่างไรก็ตาม ทั้งสองวิธีนี้ไม่เหมาะสมที่จะใช้เป็นอัลกอริทึมที่มีประสิทธิภาพ

อัลกอริทึมการแยกรากจริงแบบสมบูรณ์ครั้งแรกถูกเสนอโดย Jacques Charles François Sturm ในปี 1829 ซึ่งรู้จักกันในชื่อทฤษฎีบทของ Sturm

ในปี ค.ศ. 1836 Alexandre Joseph Hidulphe Vincent ได้เสนอวิธีการแยกรากจริงของพหุนามโดยใช้เศษส่วนต่อเนื่อง ซึ่งเป็นผลลัพธ์ที่รู้จักกันในชื่อทฤษฎีบทของ Vincentงานนี้ถูกลืมเลือนไปเป็นส่วนใหญ่ จนกระทั่งถูกค้นพบอีกครั้งในอีกกว่าศตวรรษต่อมาโดยJV Uspenskyซึ่งได้รวมไว้ในตำราTheory of Equations ในปี ค.ศ. 1948 ทฤษฎีบทนี้ได้รับการนำมาสู่ความสนใจทางวิชาการในวงกว้างมากขึ้นโดยนักคณิตศาสตร์ชาวอเมริกันAlkiviadis G. Akritasซึ่งตระหนักถึงความสำคัญของทฤษฎีบทนี้ในขณะที่ศึกษาผลงานของ Uspensky ^{[ 7 ] [ 8 ]}การนำวิธีการแยกรากจริงไปใช้ครั้งแรกด้วยคอมพิวเตอร์สมัยใหม่นั้นเกิดขึ้นโดยGE Collinsและ Alkiviadis G. Akritas ในปี ค.ศ. 1976 ซึ่งพวกเขาได้พิสูจน์ทฤษฎีบทของ Vincent เวอร์ชันที่มีประสิทธิภาพ ต่อมาได้มีการศึกษาอัลกอริธึมรูปแบบต่างๆ เพิ่มเติม^{[ 9 ]}

ก่อนที่จะมีการประดิษฐ์คอมพิวเตอร์อิเล็กทรอนิกส์ ผู้คนใช้คอมพิวเตอร์เชิงกลเพื่อทำให้การแก้ปัญหาการหาค่ารากของพหุนามเป็นไปโดยอัตโนมัติ ในปี ค.ศ. 1758 นักวิทยาศาสตร์ชาวฮังการีJA De Segnerได้เสนอการออกแบบเครื่องหาค่ารากในบทความของเขา ซึ่งทำงานโดยการวาดกราฟของพหุนามบนระนาบและหาค่ารากโดยเป็นจุดตัดของกราฟกับแกน x ในปี ค.ศ. 1770 นักคณิตศาสตร์ชาวอังกฤษJack Rowningได้ตรวจสอบความเป็นไปได้ในการวาดกราฟของพหุนามผ่านการเคลื่อนที่เฉพาะที่^{[ 10 ]}

ในปี ค.ศ. 1845 ฟรานซิส บาชฟอร์ธนักคณิตศาสตร์ชาวอังกฤษเสนอให้ใช้วิธีการทางตรีโกณมิติเพื่อลดความซับซ้อนของปัญหาการหาค่าราก กำหนดให้พหุนาม ให้แทนค่าเนื่องจากสามารถเขียนได้ในรูปผลรวมเชิงเส้นของ(ดูพหุนามเชบิเชฟ ) พหุนาม จึงสามารถเขียนใหม่ได้ในรูปแบบต่อไปนี้ ${\displaystyle a_{0}+a_{1}x+...+a_{n}x^{n}=0}$${\displaystyle x=\cos t}$${\displaystyle \cos ^{n}t}$${\displaystyle \cos kt,k\in \mathbb {Z} }$

${\displaystyle b_{0}+b_{1}\cos t+b_{2}\cos(2t)+...+b_{n}\cos(nt)}$

เส้นโค้งดังกล่าวสามารถวาดได้ด้วยเครื่องวิเคราะห์ฮาร์มอนิก (หรือที่รู้จักกันในชื่อเครื่องทำนายน้ำขึ้นน้ำลง) ^{[ 11 ]}เครื่องวิเคราะห์ฮาร์มอนิกเครื่องแรกสร้างขึ้นโดยลอร์ดเคลวินในปี พ.ศ. 2415 ในขณะที่แบชฟอร์ธได้จินตนาการถึงเครื่องจักรดังกล่าวในบทความของเขาเมื่อ 27 ปีก่อนหน้านั้น^{[ 12 ]}

วิศวกรและนักคณิตศาสตร์ชาวสเปนLeonardo Torres Quevedoสร้างเครื่องจักรหลายเครื่องเพื่อแก้ปัญหารากจริงและรากเชิงซ้อนของพหุนามระหว่างปี 1893-1900 เครื่องจักรของเขาใช้อัลกอริทึมลอการิทึม และมีส่วนประกอบเชิงกลที่เรียกว่าหลักการไม่มีที่สิ้นสุดซึ่งมีค่าตั้งแต่ด้วยความแม่นยำสูง สิ่งนี้ทำให้เขาสามารถบรรลุความแม่นยำสูงในการค้นหารากของพหุนาม: เครื่องจักรคำนวณรากของพหุนามดีกรี 8 ด้วยความแม่นยำ^{[ 13 ]}${\displaystyle \log(a+b)}$${\displaystyle \log a,\log b}$${\displaystyle 10^{-3}}$

วิธีที่ใช้กันอย่างแพร่หลายที่สุดในการคำนวณรากของฟังก์ชันที่หาอนุพันธ์ได้ คือวิธีของนิวตันซึ่งเป็นการปรับปรุงค่าเริ่มต้นแบบวนซ้ำ ในแต่ละรอบการวน ซ้ำ เส้นสัมผัส ที่จุด at จะถูกใช้เป็นค่าประมาณเชิงเส้นของและรากของเส้นสัมผัสนี้จะถูกใช้เป็นค่าคาดเดาในรอบถัดไป ${\displaystyle f}$${\displaystyle x_{0}}$${\displaystyle f}$${\displaystyle x_{n}}$${\displaystyle f}$${\displaystyle x_{n+1}}$

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},}$

โดยทั่วไป ค่าของจะลู่เข้าสู่รากของ ${\displaystyle x_{n}}$${\displaystyle f}$

โดยเฉพาะอย่างยิ่ง วิธีนี้สามารถนำไปใช้ในการคำนวณรากของฟังก์ชันพหุนามได้ ในกรณีนี้ การคำนวณในวิธีของนิวตันสามารถเร่งความเร็วได้โดยใช้วิธีของฮอร์เนอร์หรือการประเมินผลด้วยการประมวลผลล่วงหน้าเพื่อคำนวณพหุนามและอนุพันธ์ของพหุนามในแต่ละรอบการทำซ้ำ

แม้ว่าอัตราการลู่เข้าของวิธีของนิวตันโดยทั่วไปจะเป็นแบบกำลังสองแต่ก็อาจลู่เข้าช้าลงมากหรืออาจไม่ลู่เข้าเลยก็ได้ โดยเฉพาะอย่างยิ่ง หากพหุนามไม่มีรากจริง และเลือกให้เป็นจำนวนจริง วิธีของนิวตันจะไม่สามารถลู่เข้าได้ อย่างไรก็ตาม หากพหุนามมีรากจริง ซึ่งมีค่ามากกว่ารากจริงที่ใหญ่กว่าของอนุพันธ์ วิธีของนิวตันจะลู่เข้าแบบกำลังสองไปยังรากที่ใหญ่กว่านี้ หากมีค่ามากกว่ารากที่ใหญ่กว่านี้ (มีวิธีง่ายๆ ในการคำนวณขอบเขตบนของราก ดูคุณสมบัติของรากพหุนาม ) นี่คือจุดเริ่มต้นของวิธีของฮอร์เนอร์ในการคำนวณราก ${\displaystyle x_{0}}$${\displaystyle x_{0}}$

วิธีของฮัลลีย์และวิธีของลากูร์มีความเกี่ยวข้องอย่างใกล้ชิดกับวิธีของนิวตันทั้งสองวิธีใช้พหุนามและอนุพันธ์สองลำดับแรกของพหุนามนั้นในกระบวนการวนซ้ำที่มีการลู่เข้าแบบลูกบาศก์ การ รวมสองขั้นตอนต่อเนื่องกันของวิธีเหล่านี้ในการทดสอบเดียวจะได้อัตราการลู่เข้า 9 โดยมีค่าใช้จ่ายคือการประเมินพหุนาม 6 ครั้ง (ด้วยกฎของฮอร์เนอร์) ในทางกลับกัน การรวมสามขั้นตอนของวิธีนิวตันจะให้อัตราการลู่เข้า 8 โดยมีค่าใช้จ่ายคือการประเมินพหุนามจำนวนเท่ากัน ซึ่งทำให้วิธีเหล่านี้ได้เปรียบเล็กน้อย (ไม่ชัดเจนนักสำหรับวิธีของลากูร์ เนื่องจากต้องคำนวณรากที่สองในแต่ละขั้นตอน)

เมื่อนำวิธีการเหล่านี้ไปใช้กับพหุนามที่มีสัมประสิทธิ์เป็นจำนวนจริงและจุดเริ่มต้นเป็นจำนวนจริง วิธีของนิวตันและฮัลลีย์จะยังคงอยู่บนเส้นจำนวนจริง หากต้องการหาค่ารากที่เป็นจำนวนเชิงซ้อน จะต้องเลือกจุดเริ่มต้นเป็นจำนวนเชิงซ้อน ในทางตรงกันข้าม วิธีของลากูร์ที่มีรากที่สองในการคำนวณจะทำให้ค่ารากออกจากแกนจำนวนจริงโดยอัตโนมัติ

ทั้งวิธี Aberthและ วิธี Durand–Kerner ที่คล้ายกันแต่เรียบง่ายกว่า สามารถหาคำตอบของสมการทั้งหมดได้พร้อมกันโดยใช้เพียง การคำนวณ เลขเชิงซ้อนอย่าง ง่าย วิธี Aberth ในปัจจุบันเป็นวิธีที่มีประสิทธิภาพที่สุด อัลกอริทึมเร่งความเร็วสำหรับการประเมินค่าหลายจุดและการประมาณค่าแบบคล้ายกับการแปลงฟูริเยร์แบบเร็วสามารถช่วยเพิ่มความเร็วในการคำนวณสำหรับพหุนามที่มีดีกรีสูงได้

มี โปรแกรมฟรีที่ใช้หลักการของ Aberth ในชื่อMPSolveซึ่งเป็นโปรแกรมอ้างอิงที่สามารถหาคำตอบของพหุนามที่มีดีกรีมากกว่า 1,000 และมีทศนิยมที่มีนัยสำคัญมากกว่า 1,000 หลักได้อย่างเป็นประจำ

อีกวิธีหนึ่งในลักษณะเดียวกันนี้คือวิธีของ Dandelin–Gräffe (บางครั้งก็กล่าวกันว่าเป็นของLobachevsky ) ซึ่งใช้การแปลงพหุนามเพื่อยกกำลังสองรากซ้ำๆ โดยปริยาย วิธีนี้ทำให้ความแปรปรวนของรากเพิ่มขึ้นอย่างมาก การใช้สูตรของ Vièteทำให้ได้ค่าประมาณที่ง่ายสำหรับขนาดของราก และด้วยความพยายามเพิ่มเติมอีกเล็กน้อย ก็จะได้ค่าประมาณของรากเองด้วย

อาจกล่าวได้ว่า วิธีที่น่าเชื่อถือที่สุดในการหาคำตอบทั้งหมดของพหุนามคือการหาค่าลักษณะเฉพาะของเมทริกซ์คู่ของพหุนามเอกพจน์ ซึ่งตรงกับคำตอบของพหุนาม มีอัลกอริทึมมากมายสำหรับการคำนวณค่าลักษณะเฉพาะของเมทริกซ์ วิธีมาตรฐานในการหาคำตอบทั้งหมดของพหุนามใน MATLAB ใช้อัลกอริทึม Francis QRเพื่อคำนวณค่าลักษณะเฉพาะของเมทริกซ์คู่ที่สอดคล้องกับพหุนาม^{[ 14 ]}

ด้วยการใช้โครงสร้างแบบเบาบางของเมทริกซ์คู่ขนาน วิธีการวนซ้ำ QR พิเศษบางวิธีจะให้รากเชิงซ้อนทั้งหมดในการคำนวณ O(n^2) และพื้นที่จัดเก็บ O(n) ^{[ 15 ] [ 16 ]}

โดยหลักการแล้ว เราสามารถใช้อัลกอริธึมค่าลักษณะเฉพาะ ใดๆ ก็ได้ ในการหาค่ารากของพหุนาม อย่างไรก็ตาม เพื่อประสิทธิภาพที่ดีขึ้น เราจึงนิยมใช้วิธีการที่ใช้โครงสร้างของเมทริกซ์ กล่าวคือ สามารถนำไปใช้ในรูปแบบที่ไม่ขึ้นกับเมทริกซ์ได้ ในบรรดาวิธีการเหล่านี้ ได้แก่วิธีการกำลัง (power method ) ซึ่งการประยุกต์ใช้กับเมทริกซ์ทรานสโพสของเมทริกซ์คู่ขนานคือวิธีการของเบอร์นูลลี แบบคลาสสิก ในการหาค่ารากที่มีค่าสัมบูรณ์มากที่สุดวิธีการกำลังผกผันที่มีการเลื่อน (inverse power method with shifts) ซึ่งจะหาค่ารากที่เล็กที่สุดก่อน เป็นสิ่งที่ขับเคลื่อนอัลกอริธึม Jenkins–Traub เวอร์ชัน เชิงซ้อน ( cpoly ) และทำให้มีเสถียรภาพเชิงตัวเลข นอกจากนี้ ยังมีการลู่เข้าอย่างรวดเร็วด้วยอันดับ(โดยที่คืออัตราส่วนทองคำ ) แม้จะมีรากที่กระจุกตัวอยู่ การลู่เข้าอย่างรวดเร็วนี้มาพร้อมกับต้นทุนของการประเมินพหุนามสามครั้งต่อขั้นตอน ส่งผลให้ค่าตกค้างเป็นO (| f ( x )| ^{2+3 φ} )ซึ่งเป็นการลู่เข้าที่ช้ากว่าสามขั้นตอนของวิธีการของนิวตัน ${\displaystyle 1+\varphi \approx 2.6}$${\displaystyle \varphi }$

วิธีที่เก่าแก่ที่สุดในการหาคำตอบทั้งหมดคือการเริ่มต้นด้วยการหาคำตอบเพียงคำตอบเดียว เมื่อพบ คำตอบ r แล้ว สามารถนำคำตอบนั้นออกจากพหุนามได้โดยการหารด้วยทวินาม x – rพหุนามที่ได้จะมีคำตอบที่เหลืออยู่ ซึ่งสามารถหาได้โดยการทำซ้ำกระบวนการนี้ แนวคิดนี้แม้จะพบได้ทั่วไปในการพิสูจน์ทางทฤษฎี แต่ก็ใช้ไม่ได้ผลดีในการคำนวณเชิงตัวเลขเนื่องจากปรากฏการณ์ความไม่เสถียรเชิงตัวเลขพหุนามของวิลกินสันแสดงให้เห็นว่าการเปลี่ยนแปลงสัมประสิทธิ์เพียงเล็กน้อยอาจเปลี่ยนแปลงค่าของคำตอบอย่างมาก ไม่เพียงแต่ค่าของคำตอบเท่านั้น แต่ยังรวมถึงลักษณะของคำตอบ (จำนวนจริงหรือจำนวนเชิงซ้อน) ด้วย นอกจากนี้ แม้จะมีการประมาณที่ดี เมื่อประเมินพหุนามที่คำตอบโดยประมาณ ผลลัพธ์ที่ได้อาจใกล้เคียงกับศูนย์มากเกินไป ตัวอย่างเช่น ถ้าพหุนามดีกรี 20 (ดีกรีของพหุนามวิลกินสัน) มีรากที่ใกล้เคียงกับ 10 อนุพันธ์ของพหุนามที่รากนั้นอาจมีขนาดประมาณนี้ ซึ่งหมายความว่าข้อผิดพลาดขนาดหนึ่งในค่าของรากอาจทำให้ค่าของพหุนามที่รากโดยประมาณมีขนาดประมาณนี้${\displaystyle 10^{20};}$${\displaystyle 10^{-10}}$${\displaystyle 10^{10}.}$

การหาค่ารากจริงของพหุนามที่มีสัมประสิทธิ์เป็นจำนวนจริงเป็นปัญหาที่ได้รับความสนใจอย่างมากตั้งแต่ต้นศตวรรษที่ 19 และยังคงเป็นหัวข้อการวิจัยที่คึกคักจนถึงปัจจุบัน

วิธีการค้นหารากที่ซับซ้อนทั้งหมดสามารถให้รากจริงได้ อย่างไรก็ตาม เนื่องจากความไม่เสถียรเชิงตัวเลขของพหุนาม อาจต้องใช้การคำนวณเลขคณิตที่มีความแม่นยำสูงเพื่อตัดสินว่ารากที่มีส่วนจินตนาการเล็ก ๆ เป็นรากจริงหรือไม่ ยิ่งไปกว่านั้น เนื่องจากจำนวนรากจริงโดยเฉลี่ยเป็นสัดส่วนกับลอการิทึมของดีกรี^{[ 17 ]}จึงเป็นการสิ้นเปลืองทรัพยากรคอมพิวเตอร์ในการคำนวณรากที่ไม่ใช่รากจริงเมื่อเราสนใจรากจริง

วิธีมาตรฐานในการคำนวณรากจริงคือการคำนวณช่วงที่ไม่ทับซ้อนกันก่อน เรียกว่าช่วงแยก (isolation intervals ) โดยแต่ละช่วงจะมีรากจริงเพียงหนึ่งราก และเมื่อรวมกันแล้วช่วงเหล่านี้จะครอบคลุมรากทั้งหมด การคำนวณนี้เรียกว่าการแยกรากจริง (real-root isolation ) เมื่อได้ช่วงแยกแล้ว เราสามารถใช้วิธีการเชิงตัวเลขที่รวดเร็ว เช่นวิธีของนิวตันเพื่อปรับปรุงความแม่นยำของผลลัพธ์ได้

อัลกอริทึมที่สมบูรณ์ที่สุดที่เก่าแก่ที่สุดสำหรับการแยกรากจริงนั้นได้มาจากทฤษฎีบทของสเติร์มอย่างไรก็ตาม ดูเหมือนว่ามันจะมีประสิทธิภาพน้อยกว่าวิธีการที่อิงตาม กฎเครื่องหมายของเดส์การ์ตและส่วนขยายของมัน —ทฤษฎีบทของ บูดานและวินเซนต์วิธีการเหล่านี้แบ่งออกเป็นสองประเภทหลัก ประเภทหนึ่งใช้เศษส่วนต่อเนื่องและอีกประเภทหนึ่งใช้การแบ่งครึ่ง วิธีการทั้งสองได้รับการปรับปรุงอย่างมากตั้งแต่ต้นศตวรรษที่ 21 ด้วยการปรับปรุงเหล่านี้ พวกมันจึงมีประสิทธิภาพในการคำนวณที่ใกล้เคียงกับอัลกอริทึมที่ดีที่สุดสำหรับการคำนวณรากทั้งหมด (แม้ว่ารากทั้งหมดจะเป็นจำนวนจริงก็ตาม)

อัลกอริทึมเหล่านี้ได้รับการพัฒนาและพร้อมใช้งานในMathematica (วิธีเศษส่วนต่อเนื่อง) และMaple (วิธีแบ่งครึ่ง) รวมถึงระบบพีชคณิตคอมพิวเตอร์ หลักอื่นๆ ( SageMath , PARI/GP ) การใช้งานทั้งสองแบบสามารถหาค่ารากจริงของพหุนามที่มีดีกรีสูงกว่า 1,000 ได้อย่างสม่ำเสมอ

มีวิธีการทดสอบอย่างรวดเร็วหลายวิธีที่บอกได้ว่าส่วนของเส้นจำนวนจริงหรือบริเวณของระนาบเชิงซ้อนไม่มีรากหรือไม่ โดยการกำหนดขอบเขตของค่าสัมบูรณ์ของรากและแบ่งบริเวณเริ่มต้นที่ระบุโดยขอบเขตเหล่านี้ออกเป็นส่วนย่อยๆ อย่างต่อเนื่อง เราสามารถแยกบริเวณเล็กๆ ที่อาจมีรากออกมาได้ จากนั้นจึงใช้วิธีการอื่นๆ เพื่อระบุตำแหน่งของรากเหล่านั้นอย่างแม่นยำ

วิธีการทั้งหมดนี้เกี่ยวข้องกับการหาค่าสัมประสิทธิ์ของพหุนามที่ถูกเลื่อนและปรับขนาด สำหรับดีกรีสูงวิธีการเร่งความเร็วโดยใช้ FFT จะเป็นไปได้

อัลกอริทึม Lehmer–Schurใช้การทดสอบ Schur–Cohnสำหรับวงกลม ในขณะที่อัลกอริทึมการแบ่งครึ่งทั่วโลกของ Wilf ซึ่ง เป็นรูปแบบที่แตกต่างออกไป ใช้การคำนวณเลขการวนซ้ำสำหรับบริเวณสี่เหลี่ยมผืนผ้าในระนาบเชิงซ้อน

วิธีการวงกลมแยกส่วนใช้การแปลงพหุนามแบบ FFT เพื่อค้นหาตัวประกอบดีกรีสูงที่สอดคล้องกับกลุ่มราก ความแม่นยำของการแยกตัวประกอบจะถูกทำให้สูงสุดโดยใช้การวนซ้ำแบบนิวตัน วิธีนี้มีประโยชน์สำหรับการค้นหารากของพหุนามดีกรีสูงด้วยความแม่นยำตามต้องการ และมีประสิทธิภาพเกือบเหมาะสมที่สุดในบริบทนี้

หากพหุนามที่กำหนดมีสัมประสิทธิ์เป็นจำนวนจริงเท่านั้น เราอาจต้องการหลีกเลี่ยงการคำนวณด้วยจำนวนเชิงซ้อน ดังนั้น จึงจำเป็นต้องหาตัวประกอบกำลังสองสำหรับคู่ของรากเชิงซ้อนสังยุค การประยุกต์ใช้วิธีของนิวตันแบบหลายมิติกับงานนี้ ส่งผลให้ได้วิธีของแบร์สโตว์

รูปแบบที่แท้จริงของอัลกอริทึม Jenkins–Traubคือการปรับปรุงวิธีการนี้

สำหรับพหุนามที่มีสัมประสิทธิ์ระบุเป็นจำนวนเต็มหรือจำนวนตรรกยะอย่าง แม่นยำ มีวิธีที่มีประสิทธิภาพในการแยกตัวประกอบของพหุนามเหล่านั้นออกเป็นตัวประกอบที่มีรากอย่างง่ายเท่านั้น และมีสัมประสิทธิ์ระบุเป็นค่าที่แน่นอนเช่นกัน วิธีนี้เรียกว่า การแยก ตัวประกอบแบบไร้ตัวประกอบกำลัง สอง (square-free factorization ) ซึ่งอาศัยหลักการที่ว่า รากซ้ำของพหุนามคือรากของตัวหารร่วมมากของพหุนามและอนุพันธ์ของพหุนามนั้น

การแยกตัวประกอบแบบไม่มีรากที่สองของพหุนามpคือการแยกตัวประกอบที่แต่ละตัวเป็น 1 หรือพหุนามที่ไม่มีรากซ้ำ และพหุนามสองตัวที่แตกต่างกันจะไม่มีรากร่วมกัน ${\displaystyle p=p_{1}p_{2}^{2}\cdots p_{k}^{k}}$${\displaystyle p_{i}}$${\displaystyle p_{i}}$

วิธีที่มีประสิทธิภาพในการคำนวณการแยกตัวประกอบนี้คืออัลกอริทึมของหยุน

• ทฤษฎีบทรากตรรกยะ