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

${\displaystyle x=a_{1}+{\frac {1}{x'}},\quad x'=a_{2}+{\frac {1}{x''}},\quad x''=a_{3}+{\frac {1}{x'''}},\ldots }$

ที่ไหน${\displaystyle a_{1},a_{2},a_{3},\ldots }$หากจำนวนบวกใดๆ มากกว่าหรือเท่ากับหนึ่ง หลังจากการแปลงดังกล่าวจำนวนหนึ่ง สมการที่แปลงแล้วจะมีเครื่องหมายเปลี่ยนแปลง เป็นศูนย์ หรือมีการเปลี่ยนแปลงเครื่องหมาย เพียงครั้งเดียว ในกรณีแรกจะไม่มีราก ในขณะที่ในกรณีที่สองจะมีรากจริงบวกเพียงรากเดียว ยิ่งไปกว่านั้น รากที่สอดคล้องกันของสมการที่เสนอจะถูกประมาณโดยเศษส่วนต่อเนื่องจำกัด: ^{[ 1 ] [ 2 ] [ 3 ]}

${\displaystyle a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}}$

ยิ่งไปกว่านั้น หากมีจำนวนอนันต์จำนวน${\displaystyle a_{1},a_{2},a_{3},\ldots }$หากพบคุณสมบัติดังกล่าว รากจะถูกแทนด้วยเศษส่วนต่อเนื่องที่สอดคล้องกัน (อนันต์)

ข้อความข้างต้นเป็นการแปลทฤษฎีบทที่พบในเอกสารต้นฉบับของวินเซนต์อย่างตรงตัว^{[ 1 ] [ 2 ] [ 3 ]}อย่างไรก็ตาม จำเป็นต้องมีข้อสังเกตต่อไปนี้เพื่อให้เข้าใจได้ชัดเจนยิ่งขึ้น:

• ถ้า${\displaystyle f_{n}(x)}$ถ้า หมายถึงพหุนามที่ได้หลังจาก การแทนที่ nครั้ง (และหลังจากการกำจัดตัวส่วน) แล้ว จะมีNอยู่จริงที่ทำให้สำหรับทุก ๆ${\displaystyle n\geq N}$ทั้ง${\displaystyle f_{n}(x)}$ไม่มีการเปลี่ยนแปลงเครื่องหมาย หรือมีการเปลี่ยนแปลงเครื่องหมายหนึ่งแบบ ในกรณีหลัง${\displaystyle f_{n}(x)}$มีรากจริงบวกเพียงรากเดียวสำหรับทุก${\displaystyle n\geq N}$.
• เศษส่วนต่อเนื่องแสดงถึงรากบวกของสมการดั้งเดิม และสมการดั้งเดิมอาจมีรากบวกมากกว่าหนึ่งราก นอกจากนี้ สมมติว่า${\displaystyle a_{1}\geq 1}$เราจะได้รากของสมการดั้งเดิมที่มีค่ามากกว่า 1 เท่านั้น เพื่อให้ได้รากบวกใดๆ เราต้องสมมติว่า${\displaystyle a_{1}\geq 0}$.
• รากที่เป็นลบได้มาจากการแทนที่xด้วย−xซึ่งในกรณีนี้รากที่เป็นลบจะกลายเป็นบวก

ให้p ( x ) เป็นพหุนามจริงดีกรี deg( p ) ที่มีรากเดี่ยวเท่านั้น เป็นไปได้ที่จะกำหนดปริมาณบวก δ เพื่อให้สำหรับทุกคู่ของจำนวนจริงบวกa , bที่ มี${\displaystyle |ba|<\delta }$พหุนามที่แปลงแล้วทุกตัวที่มีรูปแบบ

${\displaystyle f(x)=(1+x)^{\deg(p)}p\left({\frac {a+bx}{1+x}}\right)}$

1

มี การเปลี่ยนแปลงเครื่องหมาย 0 หรือ 1 ครั้งเท่านั้นกรณีที่สองเป็นไปได้ก็ต่อเมื่อ p ( x ) มีรากเดียวภายใน ( a , b )

การอภิปรายโดยละเอียดเกี่ยวกับทฤษฎีบทของวินเซนต์ การขยาย การตีความทางเรขาคณิตของการแปลงที่เกี่ยวข้อง และการพิสูจน์ที่แตกต่างกันสามแบบสามารถพบได้ในงานของ Alesina และ Galuzzi ^{[ 4 ] [ 5 ]}การพิสูจน์แบบที่สี่เป็นผลงานของOstrowski ^{[ 6 ]}ซึ่งค้นพบกรณีพิเศษของทฤษฎีบทที่Obreschkoff [ ^{7 ]}หน้า 81 กล่าวไว้ในช่วง ^ปี  1920–1923

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

บทสรุป ( ทฤษฎีบทกรวยหรือภาคส่วนของObreschkoff , 1920–1923 ^{[ 7 ]}หน้า 81): ถ้าพหุนามจริงมีรากเดี่ยวหนึ่งรากx และรากอื่นๆ ทั้งหมด (อาจเป็นรากหลายราก) อยู่ในภาคส่วน

${\displaystyle S_{\sqrt {3}}=\left\{x=-\alpha +i\beta \$ :\ |\beta |\leq {\sqrt {3}}|\alpha |,\alpha >0\right\}}

ดังนั้นลำดับของสัมประสิทธิ์จึงมีการเปลี่ยนแปลงเครื่องหมายเพียงหนึ่งเดียวเท่านั้น

ลองพิจารณาการแปลงโมเบียส ดูบ้าง

${\displaystyle M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in \mathbb {Z} _{>0}}$

และวงกลม ทั้งสามวงที่แสดงในรูปที่เกี่ยวข้อง สมมติว่า⁠ a / c ⁠ < ⁠ b / d ⁠

• วงกลม (สีเหลือง)

${\displaystyle \left|x-{\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\right|={\tfrac {1}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

วงกลม ที่มีเส้นผ่านศูนย์กลางอยู่บนแกนจริง โดยมีจุดปลายอยู่ที่⁠a / c⁠ และ⁠b / d⁠ จะถูกแปลงโดยการแปลงโมเบียสผกผัน

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

บนแกนสมมุติ ตัวอย่างเช่น จุด

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)+{\tfrac {i}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

จะถูกแมปไปยังจุด− i ⁠ d / c ⁠ จุดภายนอกจะถูกแม ปไปยังระนาบครึ่งที่มีRe( x ) < 0

• วงกลมสองวง (มองเห็นเฉพาะส่วนโค้งสีน้ำเงิน) ที่มีจุดศูนย์กลาง

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\pm {\tfrac {i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

และรัศมี

${\displaystyle {\tfrac {1}{\sqrt {3}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

ถูกกำหนดโดยการแปลงโมเบียสผกผัน

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

บนเส้นตรงIm( x ) = ± √ 3 Re( x )ตัวอย่างเช่น จุด

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)-{\tfrac {3i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

ได้รับการแมปไปยังจุดนั้น

${\displaystyle {\tfrac {-d}{2c}}\left(1-i{\sqrt {3}}\right).}$

จุดภายนอก (จุดที่อยู่นอกรูปทรงเลขแปด) จะถูกแมปไปยัง${\displaystyle S_{\sqrt {3}}}$ภาคส่วน

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

ในเอกสารพื้นฐานของเขา^{[ 1 ] [ 2 ] [ 3 ]}วินเซนต์ได้นำเสนอตัวอย่างที่แสดงให้เห็นอย่างชัดเจนถึงวิธีการใช้ทฤษฎีบทของเขาเพื่อแยกรากจริงของพหุนามที่มีเศษส่วนต่อเนื่องอย่างไรก็ตาม วิธีการดังกล่าวมี เวลาในการคำนวณ แบบเลขชี้กำลังซึ่งเป็นข้อเท็จจริงที่นักคณิตศาสตร์ต้องตระหนักในขณะนั้น เช่นเดียวกับที่อุสเปนสกี^{[ 8 ]}หน้า 136 ตระหนักในอีกหนึ่งศตวรรษต่อมา

ลักษณะที่เป็นเลขชี้กำลังของอัลกอริทึมของวินเซนต์เกิดจากวิธีการคำนวณผลหาร ย่อย a (ในทฤษฎีบทของวินเซนต์ ) กล่าวคือ ในการคำนวณ ผลหารย่อยa แต่ละตัว (นั่นคือ การระบุตำแหน่งของรากบนแกนx ) วินเซนต์ใช้ทฤษฎีบทของบูดานเป็น"การทดสอบว่าไม่มีราก"กล่าวอีกนัยหนึ่ง ในการหาค่าส่วนจำนวนเต็มของราก วินเซนต์จะทำการแทนที่แบบต่อเนื่องในรูปแบบx ← x +1 และจะหยุดก็ต่อเมื่อพหุนามp ( x ) และp ( x +1 ) แตกต่างกันในจำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับของสัมประสิทธิ์ (นั่นคือ เมื่อจำนวนการเปลี่ยนแปลงเครื่องหมายของp ( x +1) ลดลง)

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

วินเซนต์เป็นนักเขียนคนสุดท้ายในศตวรรษที่ 19 ที่ใช้ทฤษฎีบทของเขาในการแยกรากจริงของพหุนาม

เหตุผลดังกล่าวมาจากการปรากฏตัวของทฤษฎีบทของ Sturmในปี 1827 ซึ่งแก้ปัญหาการแยกรากจริงในเวลาพหุนาม โดยกำหนดจำนวนรากจริงที่แน่นอนของพหุนามในช่วงเปิดจริง ( a , b ) วิธีการ (ของ Sturm) ที่ได้ผลลัพธ์นี้สำหรับการคำนวณรากจริงของพหุนามเป็นวิธีเดียวที่เป็นที่รู้จักและใช้กันอย่างแพร่หลายนับตั้งแต่นั้นเป็นต้นมา จนกระทั่งประมาณปี 1980 เมื่อวิธีการดังกล่าวถูกแทนที่ (ในระบบพีชคณิตคอมพิวเตอร์ เกือบทั้งหมด ) ด้วยวิธีการที่ได้มาจากทฤษฎีบทของ Vincentซึ่งวิธีที่เร็วที่สุดคือ วิธี Vincent–Akritas–Strzeboński (VAS) ^{[ 9 ]}

Serret ได้รวม ทฤษฎีบทของ Vincent พร้อมทั้งการพิสูจน์ ไว้ในพีชคณิตของเขา^{[ 10 ]}หน้า 363–368 และแนะนำผู้อ่านที่สนใจทุกคนให้ไปดูเอกสารของ Vincent เพื่อดูตัวอย่างการใช้งาน Serret เป็นผู้เขียนคนสุดท้ายที่กล่าวถึงทฤษฎีบทของ Vincentในศตวรรษที่ 19

ในศตวรรษที่ 20 ไม่พบ ทฤษฎีบทของวินเซนต์ในหนังสือทฤษฎีสมการเล่มใดเลย ยกเว้นหนังสือของ^{Uspensky [ 8 ] และ Obreschkoff [} 7 ^{]ซึ่งใน}เล่มที่สอง^{มีเพียง}การกล่าวถึงทฤษฎีบทเท่านั้น

Akritas พบทฤษฎีบทของ VincentในหนังสือของUspensky ^{[ 8 ]}และนำมาใช้เป็นหัวข้อวิทยานิพนธ์ปริญญาเอกของเขาเรื่อง "ทฤษฎีบทของ Vincent ในการจัดการพีชคณิต" มหาวิทยาลัยแห่งรัฐนอร์ทแคโรไลนา สหรัฐอเมริกาปี 1978 ความสำเร็จที่สำคัญในขณะนั้นคือการได้รับเอกสารต้นฉบับของ Vincent ในปี 1836 ซึ่งเป็นสิ่งที่Uspensky ไม่สามารถหาได้ ส่งผลให้เกิดความเข้าใจผิดอย่างมากเอกสารต้นฉบับของ Vincent ในปี 1836 ได้ถูกส่งมอบให้กับ Akritas ผ่านความพยายามที่น่ายกย่อง (การยืมระหว่างห้องสมุด) ของบรรณารักษ์ในห้องสมุดของมหาวิทยาลัยวิสคอนซิน–แมดิสันสหรัฐอเมริกา

นี่เป็นวิธีการที่สอง (ต่อจากVCA ) ที่พัฒนาขึ้นเพื่อจัดการกับ พฤติกรรม แบบเลขชี้กำลังของวิธีการของวินเซนต์

วิธีเศษส่วนต่อเนื่อง VAS เป็น การนำทฤษฎีบทของวินเซนต์มาใช้ โดยตรงเดิมทีวินเซนต์นำเสนอทฤษฎีบทนี้ตั้งแต่ปี พ.ศ. 2377 ถึง พ.ศ. 2481 ในเอกสาร^{[ 1 ] [ 2 ] [ 3 ]}ในรูปแบบเลขชี้กำลัง กล่าวคือ วินเซนต์คำนวณผลหารย่อยa แต่ละตัว โดยใช้ชุดหน่วยเพิ่มขึ้นa ← a + 1 ซึ่งเทียบเท่ากับการแทนที่ในรูปแบบx ← x + 1

วิธีการของวินเซนต์ถูกแปลงให้อยู่ใน รูปแบบความซับซ้อนของ พหุนามโดยอักริตัส ซึ่งในวิทยานิพนธ์ปริญญาเอกปี 1978 ของเขา ( ทฤษฎีบทของวินเซนต์ในการจัดการพีชคณิตมหาวิทยาลัยนอร์ทแคโรไลนาสเตท สหรัฐอเมริกา) ได้คำนวณผลหาร ย่อย a แต่ละตัว เป็นขอบล่างlbของค่ารากบวกของพหุนาม นี่เรียกว่า ขอบล่างรากบวก ในอุดมคติที่คำนวณส่วนจำนวนเต็มของรากบวกที่เล็กที่สุด (ดูรูปที่เกี่ยวข้อง) กล่าวคือ ตอนนี้กำหนดให้a ← lbหรือเทียบเท่ากับการแทนที่x ← x + lbซึ่งใช้เวลาประมาณเท่ากับการแทนที่x ← x + 1

สุดท้าย เนื่องจากขอบเขตรากล่างบวกในอุดมคติไม่มีอยู่จริง Strzeboński ^{[ 15 ]}จึงได้แนะนำการแทนที่ในปี 2548${\displaystyle x\leftarrow lb_{computed}*x}$เมื่อใดก็ตามที่${\displaystyle lb_{computed}>16}$โดยทั่วไป${\displaystyle lb>lb_{computed}}$และค่า 16 ถูกกำหนดโดยการทดลอง ยิ่งไปกว่านั้น มีการแสดงให้เห็น^{[ 15 ]}ว่าวิธี VAS ( เศษส่วนต่อเนื่อง ) เร็วกว่าการใช้งานที่เร็วที่สุดของวิธี VCA (การแบ่งครึ่ง) ^{[ 16 ]}ซึ่งเป็นข้อเท็จจริงที่ได้รับการยืนยัน^{[ 17 ]}อย่างอิสระ กล่าวคือ สำหรับพหุนาม Mignotte ที่มีดีกรีสูง VAS เร็วกว่าการใช้งานที่เร็วที่สุดของ VCA ประมาณ 50,000 เท่า

ในปี พ.ศ. 2550 Sharma ^{[ 18 ]}ได้ลบสมมติฐานของขอบเขตล่างบวกในอุดมคติและพิสูจน์ว่า VAS ยังคงเป็นพหุนามในเวลา

VAS เป็นอัลกอริธึมเริ่มต้นสำหรับการแยกรากในMathematica , SageMath , SymPyและXcas

สำหรับการเปรียบเทียบระหว่างวิธีของ Sturm และ VAS ให้ใช้ฟังก์ชัน realroot(poly) และ time(realroot(poly)) ของXcasโดยค่าเริ่มต้น realroot จะใช้วิธีของ VAS ในการแยกรากจริงของ poly หากต้องการใช้วิธีของ Sturm ให้เขียน realroot(sturm, poly) ดูลิงก์ภายนอก เพิ่มเติม สำหรับแอปพลิเคชันโดย A. Berkakis สำหรับอุปกรณ์ Android ที่ทำสิ่งเดียวกัน

ต่อไปนี้คือวิธีการทำงานของ VAS( p , M ) โดยเพื่อความง่ายจึงไม่ได้รวมผลงานของ Strzeboński ไว้ด้วย:

• ให้p ( x ) เป็นพหุนามดีกรี deg( p ) โดยที่p (0) ≠ 0 เพื่อแยกรากบวกของพหุนามนี้ ให้เชื่อมโยงp ( x ) กับ การแปลงโมเบียสM ( x ) = xแล้วทำซ้ำขั้นตอนต่อไปนี้ในขณะที่มีคู่ { p ( x ), M ( x )} ที่ต้องประมวลผล
• ใช้กฎเครื่องหมายของเดส์การ์ตบนp ( x ) เพื่อคำนวณ ถ้าเป็นไปได้ (โดยใช้จำนวนvarของการเปลี่ยนแปลงเครื่องหมายในลำดับของสัมประสิทธิ์) จำนวนรากภายในช่วง (0, ∞) หากไม่มีราก ให้ส่งคืนเซตว่าง ∅ ในขณะที่หากมีรากหนึ่งราก ให้ส่งคืนช่วง ( a , b ) โดยที่a = min( M (0), M (∞)) และb = max( M (0), M (∞)); ถ้าb = ∞ ให้กำหนดb = ubโดยที่ubเป็นขอบเขตบนของค่ารากบวกของp ( x ) ^{[ 12 ] [ 13 ]}
• ถ้ามีการเปลี่ยนแปลงเครื่องหมายสองแบบขึ้นไปกฎของเดส์การ์ตเกี่ยวกับเครื่องหมายบ่งชี้ว่าอาจมีรากจริงศูนย์ หนึ่ง หรือมากกว่านั้นภายในช่วง (0, ∞) ในกรณีนี้ ให้พิจารณารากของp ( x ) ที่อยู่ภายในช่วง (0, 1) แยกต่างหากจากรากที่อยู่ภายในช่วง (1, ∞) ต้องทำการทดสอบพิเศษสำหรับ 1
  • เพื่อรับประกันว่ามีรากภายในช่วง (0, 1) จะใช้ขอบเขตล่างในอุดมคติlbนั่นคือส่วนจำนวนเต็มของรากบวกที่เล็กที่สุดจะถูกคำนวณโดยใช้ขอบเขตล่าง^{[ 12 ] [ 13 ]}${\displaystyle lb_{computed}}$โดยพิจารณาจากค่าของรากบวกของp ( x ) ถ้า${\displaystyle lb_{computed}>1}$การทดแทน${\displaystyle x\leftarrow x+lb_{computed}}$ดำเนินการกับp ( x ) และM ( x ) ในขณะที่ถ้า${\displaystyle lb_{computed}\leq 1}$ใช้การแทนที่x ← x +1 เพื่อหาค่าส่วนจำนวนเต็มของราก
  • ในการคำนวณหาค่ารากภายในช่วง (0, 1) ให้ทำการแทนที่${\displaystyle x\leftarrow {\frac {1}{1+x}}}$ไปยังp ( x ) และM ( x ) และประมวลผลคู่ดังกล่าว

${\displaystyle \left\{(1+x)^{\deg(p)}p\left({\tfrac {1}{1+x}}\right),M({\tfrac {1}{1+x}})\right\},}$

ในขณะที่การคำนวณรากในช่วง (1, ∞) ทำการแทนที่x ← x + 1 ลงในp ( x ) และM ( x ) แล้วประมวลผลคู่ { p (1 + x ), M (1 + x )} อาจเป็นไปได้ว่า 1 เป็นรากของp ( x ) ซึ่งในกรณีนี้M (1) จะเป็นรากของพหุนามดั้งเดิม และช่วงการแยกจะลดลงเหลือเพียงจุดเดียว

ด้านล่างนี้คือ การนำเสนอแบบ เรียกซ้ำของ VAS( p , M )

VAS ( p , M ):

อินพุต : พหุนาม ตัวแปรเดียว ที่ไม่มีตัวประกอบกำลังสอง${\displaystyle p(x)\in \mathbb {Z} [x],p(0)\neq 0}$ของระดับ deg( p ) และการแปลงโมเบียส

${\displaystyle M(x)={\frac {ax+b}{cx+d}}=x,\qquad a,b,c,d\in \mathbb {N} .}$

ผลลัพธ์ : รายการช่วงแยกของรากบวกของp ( x )

1 var ← จำนวนการเปลี่ยนแปลงเครื่องหมายของp ( x ) // กฎเครื่องหมายของเดส์การ์ต ; 2 ถ้าvar = 0 แล้ว ให้ส่ง ค่า ∅ กลับมา 3 ถ้าvar = 1 แล้วให้ส่งคืน {( a , b )} // a = min( M (0), M (∞)), b = max( M (0), M (∞)) แต่ถ้าb = ∞ ให้กำหนดb = ubโดยที่ubเป็นขอบเขตบนของค่ารากบวกของp ( x ); 4 ปอนด์ ← ขอบล่างใน อุดมคติของรากบวกของp ( x ); 5 ถ้าlb ≥ 1 แล้วp ← p ( x + lb ), M ← M ( x + lb ); 6 p  ← ( x + 1) deg( p ) p ( ⁠ 1 / x + 1 ⁠ ), M  ← M ( ⁠ 1 / x + 1 ⁠ ) // ค้นหารากจริงในช่วง (0, 1); 7 m ← M (1) // 1 เป็นรากหรือไม่? 8 p  ← p ( x + 1), M  ← M ( x + 1) // ค้นหารากจริงในช่วง (1, ∞); 9 ถ้าp (1) ≠ 0 แล้ว 10 ส่งคืน VAS( p  , M  ) ∪ VAS( p  , M  ) 11 มิฉะนั้น 12 ส่งคืน VAS( p  , M  ) ∪ {[ m , m ]} ∪ VAS( p  , M  ) 13 สิ้นสุด

หมายเหตุ

• เพื่อความง่าย จึงไม่ได้รวมผลงานของ Strzeboński ไว้ด้วย
• ในอัลกอริทึมข้างต้น พหุนามแต่ละตัวจะมีการแปลงโมเบียสM ( x ) ที่เกี่ยวข้อง
• ในบรรทัดที่ 1 มี การนำกฎของเครื่องหมายของเดส์การ์ตมาใช้
• หากลบบรรทัดที่ 4 และ 5 ออกจาก VAS( p , M ) อัลกอริทึมที่ได้จะเป็นอัลกอริทึมเลขชี้กำลังของวินเซนต์
• การแทนที่ใดๆ ที่กระทำกับพหุนามp ( x ) จะกระทำกับการแปลงโมเบียสM ( x ) ที่เกี่ยวข้องด้วย (บรรทัดที่ 5, 6 และ 8)
• ช่วงการแยกตัวจะคำนวณจากการแปลงโมเบียสในบรรทัดที่ 3 ยกเว้นรากจำนวนเต็มที่คำนวณในบรรทัดที่ 7 (และ 12)

เราใช้วิธี VAS กับp ( x ) = x ³ − 7 x + 7 (โปรดทราบว่า: M ( x ) = x )

VAS( x 3 − 7 x + 7, x ) 1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของp ( x ) = x 3 − 7 x + 7 4 ปอนด์ ← 1 // ขอบล่างในอุดมคติ—หาได้จากน้ำหนักเป็นปอนด์และการแทนที่x ← x + 1 5 p ← x 3 + 3 x 2 − 4 x + 1, M ← x + 1 6 p  ← x 3 − x 2 − 2 x + 1, M  ← ⁠ x + 2 / x + 1 ⁠ 7 m ← 1 8 p  ← x 3 + 6 x 2 + 5 x + 1, M  ← x + 2 10 RETURN VAS( x 3 − x 2 − 2 x + 1, ⁠ x + 2 / x + 1 ⁠ ) ∪ VAS( x 3 + 6 x 2 + 5 x + 1, x + 2)

VAS( x 3 − x 2 − 2 x + 1, ⁠ x + 2 / x + 1 ⁠ ) 1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของp ( x ) = x 3 − x 2 − 2 x + 1 4 ปอนด์ ← 0 // ขอบล่างในอุดมคติ—หาได้จากปอนด์และการแทนที่x ← x + 1 6 p  ← x 3 + x 2 − 2 x − 1, M  ← ⁠ 2 x + 3 / x + 1 ⁠ 7 m ← ⁠ 3 / 2 ⁠ 8 p  ← x 3 + 2 x 2 − x − 1, M  ← ⁠ x + 3 / x + 2 ⁠ 10 RETURN VAS( x 3 + x 2 − 2 x − 1, ⁠ 2 x + 3 / x + 2 ⁠ ) ∪ VAS( x 3 + 2 x 2 − x − 1, ⁠ x + 3 / x + 2 ⁠ )

VAS( x 3 + x 2 − 2 x − 1, ⁠ 2 x + 3 / x + 2 ⁠ ) 1 var ← 1 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของp ( x ) = x 3 + x 2 − 2 x − 1 3 RETURN {( ⁠ 3 / 2 ⁠ , 2)}

VAS( x 3 + 2 x 2 − x − 1, ⁠ x + 3 / x + 2 ⁠ ) 1 var ← 1 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของp ( x ) = x 3 + 2 x 2 − x − 1 3 RETURN {(1, ⁠ 3 / 2 ⁠ )}

VAS( x 3 + 6 x 2 + 5 x + 1, x + 2) 1 var ← 0 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของp ( x ) = x 3 + 6 x 2 + 5 x + 1 2 คืน ∅

นี่เป็นวิธีแรกที่พัฒนาขึ้นเพื่อเอาชนะ ลักษณะ เลขชี้กำลังของวิธีการดั้งเดิม ของวินเซนต์ และมีประวัติที่น่าสนใจมากในแง่ของชื่อ วิธีนี้ซึ่งแยกรากจริงโดยใช้กฎของเครื่องหมายของเดส์การ์ตและทฤษฎีบทของวินเซนต์เดิมทีเรียกว่าอัลกอริทึมของอุสเปนสกีที่ดัดแปลงโดยผู้คิดค้นคือคอลลินส์และอักริตัส^{[ 11 ]}หลังจากผ่านชื่อต่างๆ เช่น "วิธีคอลลินส์-อักริตัส" และ "วิธีของเดส์การ์ต" (ซึ่งสับสนเกินไปหากพิจารณาบทความของฟูริเยร์^{[ 20 ]} ) ในที่สุดฟรองซัวส์ บูลิเยร์ จากมหาวิทยาลัยลีลล์ เป็นผู้ตั้งชื่อให้ว่า วิธี วินเซนต์-คอลลินส์-อักริตัส (VCA) ^{[ 14 ]}หน้า 24 โดยอิงจากข้อเท็จจริงที่ว่า "วิธีของอุสเปนสกี" ไม่มีอยู่จริง^{[ 21 ]}และ "วิธีของเดส์การ์ต" ก็ไม่มีอยู่จริงเช่นกัน^{[ 22 ]}การนำวิธีนี้ไปใช้ที่ดีที่สุดมาจาก Rouillier และ Zimmerman ^{[ 16 ]}และจนถึงปัจจุบันนี้ วิธีนี้เป็นวิธีแบ่งครึ่งที่เร็วที่สุด มีความซับซ้อน ในกรณีที่เลวร้ายที่สุด เท่ากับอัลกอริทึมของ Sturm แต่โดยส่วนใหญ่แล้วจะเร็วกว่ามาก วิธีนี้ได้รับการนำไปใช้ในแพ็คเกจ RootFinding ของMaple แล้ว

นี่คือวิธีการทำงานของ VCA( p , ( a , b )):

• กำหนดให้พหุนามp ( x ) ที่มีดีกรี deg( p ) โดยที่p (0) ≠ 0 ซึ่งรากบวกจะต้องแยกออกมา ก่อนอื่นให้คำนวณขอบเขตบน^{[ 12 ] [ 13 ]} ubบนค่าของรากบวกเหล่านี้ และกำหนดp ( x ) = p ( ub * x ) และ ( a , b ) = (0, ub ) รากบวกของp ( x ) ทั้งหมดอยู่ในช่วง (0, 1) และมีการจับคู่แบบหนึ่งต่อหนึ่งระหว่างรากบวกเหล่านี้กับรากของp ( x ) ซึ่งทั้งหมดอยู่ในช่วง ( a , b ) = (0, ub ) (ดูรูปที่เกี่ยวข้อง) การจับคู่แบบหนึ่งต่อหนึ่ง นี้ แสดงโดยα = a + α ( b − a ) ในทำนองเดียวกัน มีการจับคู่แบบหนึ่ง ต่อหนึ่ง ระหว่างช่วง (0, 1) และ (0, ub )

• ทำซ้ำขั้นตอนต่อไปนี้ในขณะที่มีคู่ { p ( x ), ( a , b )} ที่ต้องประมวลผล
• ใช้ การทดสอบราก " 0_1 " ของ Budan กับp ( x ) เพื่อคำนวณ (โดยใช้จำนวนvarของการเปลี่ยนแปลงเครื่องหมายในลำดับของสัมประสิทธิ์) จำนวนรากที่อยู่ในช่วง (0, 1) หากไม่มีราก ให้ส่งคืนเซตว่าง ∅ และหากมีรากหนึ่งราก ให้ส่งคืนช่วง ( a , b )
• ถ้ามีการเปลี่ยนแปลงเครื่องหมายสองแบบขึ้นไป การทดสอบราก " 0_1 " ของ Budan บ่งชี้ว่าอาจมีรากจริงศูนย์ หนึ่ง สอง หรือมากกว่านั้นภายในช่วง (0, 1) ในกรณีนี้ ให้แบ่งครึ่งและพิจารณารากของp(x) ภายในช่วง (0, 1/2 )แยกกันซึ่งสอดคล้องกับรากของp ( x )ภายในช่วง ( a , 1/2 ( a + b )) และ รากภายในช่วง ( 1/2 , 1 )ซึ่งสอดคล้องกับรากของp orig x ) ภายในช่วง (1/2 ( a + b ) , b ) กล่าวคือประมวลผลคู่ต่างๆตามลำดับ

${\displaystyle \left\{2^{\deg(p)}p({\tfrac {x}{2}}),(a,{\tfrac {1}{2}}(a+b))\right\},\quad \left\{2^{\deg(p)}p({\tfrac {1}{2}}(x+1)),({\tfrac {1}{2}}(a+b),b)\right\}}$

( ดูรูปที่เกี่ยวข้อง) อาจเป็นไปได้ว่า1/2 เป็นรากของp ( x ) ซึ่งในกรณีนี้1/2 ( a + b )จะเป็นรากของp ( x )และช่วงการแยกจะลดลงเหลือเพียงจุดเดียว

ด้านล่างนี้คือ การนำเสนอ แบบเรียกซ้ำของอัลกอริทึมดั้งเดิม VCA( p , ( a , b ))

VCA ( p , ( a , b ))

อินพุต : พหุนามเอกตัวแปรp ( ub * x ) ∈ Z [ x ], p (0) ≠ 0 ที่มีดีกรี deg( p ) และช่วงเปิด ( a , b ) = (0, ub ) โดยที่ubเป็นขอบเขตบนของค่ารากบวกของp ( x ) (รากบวกของp ( ub * x ) ทั้งหมดอยู่ในช่วงเปิด (0, 1)) เอาต์พุต : รายการช่วงแยกของรากบวกของp ( x )

1 var ← จำนวนการเปลี่ยนแปลงเครื่องหมายของ ( x + 1) deg( p ) p ( ⁠ 1 / x + 1 ⁠ ) // การทดสอบราก 0_1ของ Budan ; 2 ถ้าvar = 0 แล้วให้ส่งค่า ∅ กลับมา 3 ถ้าvar = 1 แล้วให้ส่งคืน {( a , b )}; 4 p  ← 2 deg( p ) p ( ⁠ x / 2 ⁠ ) // ค้นหารากจริงในช่วง (0, ⁠ 1 / 2 ⁠ ); 5 ม. ← ⁠ 1 / 2 ⁠ ( a + b ) // 1 / 2เป็นรากหรือไม่? 6 p  ← 2 deg( p ) p ( ⁠ x + 1 / 2 ⁠ ) // ค้นหารากจริงใน ( ⁠ 1 / 2 ⁠ , 1); 7 ถ้าp ( ⁠ 1 / 2 ⁠ ) ≠ 0 แล้ว 8 ส่งคืน VCA ( p  , ( a , m )) ∪ VCA ( p  , ( m , b )) 9 มิฉะนั้น 10 ส่งคืน VCA ( p  , ( a , m )) ∪ {[ m , m ]} ∪ VCA ( p  , ( m , b )) 11 สิ้นสุด

หมายเหตุ

• ในอัลกอริทึมข้างต้น พหุนามแต่ละตัวจะมีช่วง ( a , b ) ที่เกี่ยวข้อง ดังที่แสดงไว้ในที่อื่น^{[ 22 ]}หน้า 11 การแปลงโมเบียสยังสามารถเชื่อมโยงกับพหุนามแต่ละตัวได้ ซึ่งในกรณีนี้ VCA จะดูคล้ายกับVAS มากกว่า
• ในบรรทัดที่ 1 มีการใช้" การทดสอบราก 0_1 "ของ Budan

เมื่อกำหนดพหุนามp ( x ) = x ³ − 7 x + 7และพิจารณาขอบเขตบน^{[ 12 ] [ 13 ]}บนค่าของรากบวกub = 4อาร์กิวเมนต์ของวิธี VCA คือ: p ( x ) = 64 x ³ − 28 x + 7และ( a , b ) = (0, 4)

1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 1 / x + 1 ⁠ ) = 7 x 3 − 7 x 2 − 35 x + 43 4 p  ← 64 x 3 − 112 x + 56 5 ม. ← 2 6 เพนนี 64 x  192 x 2 + 80 x +  7 p ( ⁠ 1 / 2 ⁠ ) = 1 8 RETURN VCA(64 x 3 − 112 x + 56, (0, 2)) ∪ VCA(64 x 3 + 192 x 2 + 80 x + 8, (2, 4))

VCA(64 x 3 − 112 x + 56, (0, 2)) 1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 1 / x + 1 ⁠ ) = 56 x 3 + 56 x 2 − 56 x + 8 4 p  ← 64 x 3 − 448 x + 448 5 ม. ← 1 6 p  ← 64 x 3 + 192 x 2 − 256 x + 64 7 p ( ⁠ 1 / 2 ⁠ ) = 8 8 RETURN VCA(64 x 3 − 448 x + 448, (0, 1)) ∪ VCA(64 x 3 + 192 x 2 − 256 x + 64, (1, 2))

VCA(64 x 3 − 448 x + 448, (0, 1)) 1 var ← 0 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 1 / x + 1 ⁠ ) = 448 x 3 + 896 x 2 + 448 x + 64 2 คืน ∅

VCA(64 x 3 + 192 x 2 − 256 x + 64, (1, 2)) 1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 1 / x + 1 ⁠ ) = 64 x 3 − 64 x 2 − 128 x + 64 4 p  ← 64 x 3 + 384 x 2 − 1024 x + 512 5 ม . ← ⁠ 3 / 2 ⁠ 6 เพนนี ← 64 x 3 + 576 x 2 − 64 x + 64 7 p ( ⁠ 1 / 2 ⁠ ) = −8 8 RETURN VCA(64 x 3 + 384 x 2 − 1024 x + 512, (1, ⁠ 3 / 2 ⁠ )) ∪ VCA(64 x 3 + 576 x 2 − 64 x − 64, ( ⁠ 3 / 2 ⁠ , 2))

VCA(64 x 3 + 384 x 2 − 1024 x + 512, (1, ⁠ 3 / 2 ⁠ )) 1 var ← 1 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 1 / x + 1 ⁠ ) = 512 x 3 + 512 x 2 − 128 x − 64 3 RETURN {(1, ⁠ 3 / 2 ⁠ )}

1 var ← 1 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 1 / x + 1 ⁠ ) = −64 x 3 − 256 x 2 + 256 x + 512 3 RETURN {( ⁠ 3 / 2 ⁠ , 2)}

VCA(64 x 3 + 192 x 2 + 80 x + 8, (2, 4)) 1 var ← 0 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 1 / x + 1 ⁠ ) = 8 x 3 + 104 x 2 + 376 x + 344 2 คืน ∅

วิธีนี้ได้รับการพัฒนาขึ้นเป็นลำดับสุดท้าย และเป็นวิธีการแยกรากจริง ที่ง่ายที่สุด ซึ่งได้มาจากทฤษฎีบทของวินเซนต์

นี่คือวิธีการทำงานของ VAG( p , ( a , b )):

• กำหนดให้พหุนามp ( x ) ที่มีดีกรี deg( p ) โดยที่p (0) ≠ 0 ซึ่งรากบวกจะต้องแยกออกจากกัน ก่อนอื่นให้คำนวณขอบเขตบน^{[ 12 ] [ 13 ]} ubบนค่าของรากบวกเหล่านี้และกำหนด ( a , b ) = (0, ub ) รากบวกของp ( x ) ทั้งหมดอยู่ในช่วง ( a , b )
• ทำซ้ำขั้นตอนต่อไปนี้ในขณะที่มีช่วงเวลา ( a , b ) ที่ต้องประมวลผล ในกรณีนี้พหุนามp ( x ) จะยังคงเหมือนเดิม
• ใช้ การทดสอบราก " a_b " ของ Alesina–Galuzzi กับp ( x ) เพื่อคำนวณ (โดยใช้จำนวนvarของการเปลี่ยนแปลงเครื่องหมายในลำดับของสัมประสิทธิ์) จำนวนรากที่อยู่ในช่วง ( a , b ) หากไม่มีราก ให้ส่งคืนเซตว่าง ∅ และหากมีรากหนึ่งราก ให้ส่งคืนช่วง ( a , b )
• ถ้ามีการเปลี่ยนแปลงเครื่องหมายสองครั้งขึ้นไปการทดสอบราก " a_b " ของ Alesina–Galuzzi บ่งชี้ว่าอาจมีรากจริงศูนย์ หนึ่ง สอง หรือมากกว่านั้นภายในช่วง ( a , b ) ใน กรณีนี้ ให้แบ่งช่วงออกเป็นครึ่งและพิจารณารากของ p(x) ภายในช่วง (a, 1/2 ( a + b)) แยกจากรากภายในช่วง (1/2 ( a + b ) , b ) กล่าวคือประมวลผลช่วง( a , 1/2 ( a + b ) )และ( 1/2 ( a + b ) , b )ตามลำดับอาจเป็นไปได้ว่า1/2 ( a + b ) เป็นรากของp ( x ) ซึ่ง ในกรณี นี้ ช่วง การ แยก จะลด ลง เหลือเพียงจุดเดียว

ด้านล่างนี้คือ การนำเสนอ แบบเรียกซ้ำของ VAG( p , ( a , b ))

VAG ( p , ( a , b )) อินพุต : พหุนามเอกตัวแปรp ( x ) ∈ Z [ x ], p (0) ≠ 0 ที่มีดีกรี deg( p ) และช่วงเปิด ( a , b ) = (0, ub ) โดยที่ubเป็นขอบเขตบนของค่ารากบวกของp ( x ) เอาต์พุต : รายการช่วงแยกของรากบวกของp ( x )

1 var ← จำนวนการเปลี่ยนแปลงเครื่องหมายของ ( x + 1) deg( p ) p ( ⁠ a + bx / 1 + x ⁠ ) // การทดสอบราก " a_b "ของ Alesina–Galuzzi ; 2 ถ้าvar = 0 แล้วให้ส่งค่า ∅ กลับมา 3 ถ้าvar = 1 แล้วให้ส่งคืน {( a , b )}; 4 ม. ← ⁠ 1 / 2 ⁠ ( a + b ) // แบ่งช่วง ( a , b ) ออกเป็นสองส่วนเท่าๆ กัน 5 ถ้าp ( m ) ≠ 0 แล้ว 6 ส่งคืน VAG( p , ( a , m )) ∪ VAG( p , ( m , b )) 7 มิฉะนั้น 8 ส่งคืน VAG( p , ( a , m )) ∪ {[ m , m ]} ∪ VAG( p , ( m , b )) 9 สิ้นสุด

หมายเหตุ

• เมื่อเปรียบเทียบกับVCAอัลกอริทึมข้างต้นนั้นง่ายมาก ในทางตรงกันข้าม VAG ใช้ "การทดสอบราก a_b" ที่ใช้เวลานานและทำให้ช้ากว่าVCA มาก ^{[ 19 ]}
• ตามที่ Alesina และ Galuzzi ชี้ให้เห็น^{[ 5 ]}หน้า 189 มีอัลกอริธึมรูปแบบหนึ่งที่พัฒนาโดย Donato Saeli Saeli แนะนำให้ ใช้ ค่ามัธยฐานของจุดปลายแทนค่ากึ่งกลาง⁠ 1 / 2 ⁠ ( a + b )อย่างไรก็ตาม ได้มีการแสดงให้เห็นแล้ว^{[ 19 ]}ว่าการใช้ค่ามัธยฐานของจุดปลายโดยทั่วไปจะช้ากว่าเวอร์ชัน "ค่ากึ่งกลาง" มาก

เมื่อกำหนดพหุนามp ( x ) = x ³ − 7 x + 7 และพิจารณาขอบเขตบน^{[ 12 ] [ 13 ]}บนค่าของรากบวกub = 4 อาร์กิวเมนต์ของ VAG คือ: p ( x ) = x ³ − 7 x + 7 และ ( a , b ) = (0, 4)

1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 4 x / x + 1 ⁠ ) = 43 x 3 − 35 x 2 − 7 x + 7 4 ม. ← ⁠ 1 / 2 ⁠ (0 + 4) = 2 5 p ( m ) = 1 8 RETURN VAG( x 3 − 7 x + 7, (0, 2)) ∪ VAG( x 3 − 7 x + 7, (2, 4)

VAG( x 3 − 7 x + 7, (0, 2)) 1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 2 x / x + 1 ⁠ ) = x 3 − 7 x 2 + 7 x + 7 4 ม. ← ⁠ 1 / 2 ⁠ (0 + 2) = 1 5 p ( m ) = 1 8 RETURN VAG( x 3 − 7 x + 7, (0, 1)) ∪ VAG( x 3 − 7 x + 7, (1, 2)

VAG( x 3 − 7 x + 7, (0, 1)) 1 var ← 0 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ x / x + 1 ⁠ ) = x 3 + 7 x 2 + 14 x + 7 2 คืน ∅

VAG( x 3 − 7 x + 7, (1, 2)) 1 var ← 2 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 2 x + 1 / x + 1 ⁠ ) = x 3 − 2 x 2 − x + 1 4 m ← ⁠ 1 / 2 ⁠ (1 + 2) = ⁠ 3 / 2 ⁠ 5 p ( m ) = − ⁠ 1 / 8 ⁠ 8 RETURN VAG( x 3 − 7 x + 7, (1, ⁠ 3 / 2 ⁠ )) ∪ VAG( x 3 − 7 x + 7, ( ⁠ 3 / 2 ⁠ , 2))

VAG( x 3 − 7 x + 7, (1, ⁠ 3 / 2 ⁠ )) 1 var ← 1 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ 2 3 ( x + 1) 3 p ( ⁠ ⁠ 3 / 2 ⁠ x + 1 / x + 1 ⁠ ) = x 3 + 2 x 2 − 8 x − 8 3 RETURN (1, ⁠ 3 / 2 ⁠ )

VAG( x 3 − 7 x + 7, ( ⁠ 3 / 2 ⁠ , 2)) 1 var ← 1 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ 2 3 ( x + 1) 3 p ( ⁠ 2 x + ⁠ 3 / 2 ⁠ / x + 1 ⁠ ) = 8 x 3 + 4 x 2 − 4 x − 1 3 RETURN ( ⁠ 3 / 2 ⁠ , 2)

VAG( x 3 − 7 x + 7, (2, 4)) 1 var ← 0 // จำนวนการเปลี่ยนแปลงเครื่องหมายในลำดับสัมประสิทธิ์ของ ( x + 1) 3 p ( ⁠ 4 x + 2 / x + 1 ⁠ ) = 344 x 3 + 376 x 2 + 104 x + 8 2 คืน ∅