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

วิธีการรับรองสามารถแบ่งออกได้เป็นสองประเภท คือ การรับรอง แบบก่อนประสบการณ์ (a priori certification) และการรับรอง แบบหลังประสบการณ์ (a posteriori certification) การรับรอง แบบหลังประสบการณ์เป็นการยืนยันความถูกต้องของคำตอบสุดท้าย (โดยไม่คำนึงถึงวิธีการสร้างคำตอบ) ในขณะที่ การรับรอง แบบก่อนประสบการณ์เป็นการยืนยันความถูกต้องของแต่ละขั้นตอนของการคำนวณเฉพาะ ตัวอย่างทั่วไปของ การรับรอง แบบหลังประสบการณ์คือ ทฤษฎีอัลฟาของ สเมล (Smale 's alpha theory) ในขณะที่ตัวอย่างทั่วไปของ การรับรอง แบบก่อนประสบการณ์คือเลขคณิตช่วง (interval arithmetic )

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

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

มีวิธีการรับรอง ภายหลังหลายวิธีรวมถึง

หลักการสำคัญของทฤษฎีอัลฟาของ Smaleคือการจำกัดขอบเขตของข้อผิดพลาดสำหรับวิธีของ Newtonงานของ Smale ในปี 1986 ^{[ 1 ]}ได้แนะนำปริมาณซึ่งวัดการลู่เข้าของวิธีของ Newton กล่าวคือ ให้เป็นระบบของฟังก์ชันวิเคราะห์ในตัวแปร ตัวดำเนินการอนุพันธ์และตัวดำเนินการ Newton ปริมาณ และ ใช้เพื่อรับรองคำตอบที่เป็นไปได้ โดยเฉพาะอย่างยิ่ง ถ้า แล้วเป็นคำตอบโดยประมาณสำหรับ นั่นคือ คำตอบ ที่เป็นไปได้อยู่ในโดเมนของการลู่เข้าแบบกำลังสองสำหรับวิธีของ Newton กล่าวอีกนัยหนึ่ง ถ้าความไม่เท่าเทียมกันนี้เป็นจริง จะมีรากของที่ทำให้การทำซ้ำของตัวดำเนินการ Newton ลู่เข้าเป็น ${\displaystyle \alpha }$${\displaystyle F}$${\displaystyle x}$${\displaystyle D}$${\displaystyle N}$$${\displaystyle \beta (f,x)=\|xN(x)\|=\|Df(x)^{-1}f(x)\|}$$$${\displaystyle \gamma (f,x)=\sup _{k\geq 2}\left\|{\frac {Df(x)^{-1}D^{k}f(x)}{k!}}\right\|^{\frac {1}{k-1}}}$$$${\displaystyle \alpha (f,x)=\beta (f,x)\gamma (f,x)}$$$${\displaystyle \alpha (f,x)<{\frac {13-3{\sqrt {17}}}{4}},}$$${\displaystyle x}$${\displaystyle f}$${\displaystyle x^{\ast }}$${\displaystyle F}$$${\displaystyle \left\|N^{k}(x)-x^{\ast }\right\|\leq {\frac {1}{2^{2^{k}-1}}}\|xx^{\ast }\|.}$$

แพ็คเกจซอฟต์แวร์alphaCertified มีการ ^ใช้งานการทดสอบอัลฟาสำหรับพหุนามโดยการประมาณค่าและ[ ^{2 ]}${\displaystyle \beta }$${\displaystyle \gamma }$

สมมติว่าเป็นฟังก์ชันที่มีจุดตรึงสอดคล้องกับรากของตัวอย่างเช่น ตัวดำเนินการนิวตันมีคุณสมบัตินี้ สมมติว่าเป็นบริเวณ ดังนั้น ${\displaystyle G:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}$${\displaystyle F}$${\displaystyle I}$

1. ถ้าแปลงเป็น เอง กล่าวคือแล้วโดยทฤษฎีบทจุดตรึงของ Brouwerจะมีจุดตรึงอย่างน้อยหนึ่งจุดในและด้วยเหตุนี้จึงมีรากอย่างน้อยหนึ่งรากใน${\displaystyle G}$${\displaystyle I}$${\displaystyle G(I)\subseteq I}$${\displaystyle G}$${\displaystyle I}$${\displaystyle F}$${\displaystyle I}$
2. ถ้าเป็นฟังก์ชันหดตัวในบริเวณที่ประกอบด้วยแล้วจะมีรากอย่างมากที่สุดหนึ่งรากใน${\displaystyle G}$${\displaystyle I}$${\displaystyle I}$

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

ในกรณีตัวแปรเดียว วิธีของนิวตันสามารถขยายความโดยตรงเพื่อรับรองรากในช่วงได้ สำหรับช่วงให้เป็นจุดกึ่งกลางของแล้วตัวดำเนินการนิวตันแบบช่วงที่ใช้กับคือ ${\displaystyle J}$${\displaystyle m(J)}$${\displaystyle J}$${\displaystyle J}$

${\displaystyle IN(J)=m(J)-F(m(J))/F'(J).}$

ในทางปฏิบัติ ช่วงใดๆ ที่มี อยู่สามารถนำมาใช้ในการคำนวณนี้ได้ ถ้าเป็นรากของแล้วโดยทฤษฎีบทค่าเฉลี่ยจะมี บางค่าที่ทำให้ กล่าวอีกนัยหนึ่งคือเนื่องจากประกอบด้วยค่าผกผันของที่ทุกจุดของจึงสรุปได้ว่า ดังนั้น${\displaystyle F'(J)}$${\displaystyle x}$${\displaystyle F}$${\displaystyle c\in J}$${\displaystyle F(m(J))-F'(c)(m(J)-x)=F(x)=0}$${\displaystyle F(m(J))=F'(c)(m(J)-x)}$${\displaystyle F'(J)}$${\displaystyle F}$${\displaystyle J}$${\displaystyle m(J)-x\in F(m(J))/F'(J)}$${\displaystyle x=m(J)-(m(J)-x)\in IN(J)}$

นอกจากนี้ ถ้าแล้วจะเป็นรากของและหรือดังนั้นจะมีขนาดไม่เกินครึ่งหนึ่งของความกว้างของดังนั้น ถ้ามีรากของอยู่ในกระบวนการวนซ้ำของการแทนที่ด้วยจะลู่เข้าสู่รากนั้น ในทางกลับกัน ถ้าไม่มีรากของอยู่ในกระบวนการวนซ้ำนี้จะสร้างช่วงว่างในที่สุด ซึ่งเป็นหลักฐานยืนยันว่าไม่มีรากอยู่ ${\displaystyle 0\not \in F'(J)}$${\displaystyle m(J)}$${\displaystyle F}$${\displaystyle IN(J)=\{m(J)\}}$${\displaystyle m(J)\not \in IN(J)}$${\displaystyle J\cap N(J)}$${\displaystyle J}$${\displaystyle F}$${\displaystyle J}$${\displaystyle J}$${\displaystyle J\cap IN(J)}$${\displaystyle F}$${\displaystyle J}$

ดูวิธีนิวตันแบบช่วงเวลาสำหรับวิธีการที่คล้ายคลึงกันในมิติที่สูงกว่า

ให้เป็นเมทริกซ์ผกผัน ใดๆ ในโดยทั่วไปแล้ว เรามักจะใช้ เป็นค่าประมาณของจากนั้น กำหนดฟังก์ชัน เราสังเกตว่าเป็นค่าคงที่ของก็ต่อเมื่อเป็นรากของดังนั้น วิธีการข้างต้นสามารถใช้เพื่อระบุรากของวิธีการนี้คล้ายกับวิธีของนิวตันแบบหลายตัวแปร โดยแทนที่อนุพันธ์ด้วยเมทริกซ์คงที่ ${\displaystyle Y}$${\displaystyle n\times n}$${\displaystyle GL(n,\mathbb {R} )}$${\displaystyle Y}$${\displaystyle F'(y)^{-1}}$${\displaystyle G(x)=x-YF(x).}$${\displaystyle x}$${\displaystyle G}$${\displaystyle x}$${\displaystyle F}$${\displaystyle F}$${\displaystyle Y}$

เราสังเกตว่า ถ้าเป็นบริเวณที่กระชับและนูน และแล้ว สำหรับใดๆจะมีอยู่เช่นนั้น ${\displaystyle J}$${\displaystyle y\in J}$${\displaystyle x\in J}$${\displaystyle c_{1},\dots ,c_{n}\in J}$

${\displaystyle G(y)-G(x)={\begin{bmatrix}\nabla g_{1}(c_{1})^{T}\\\vdots \\\nabla g_{n}(c_{n})^{T}\end{bmatrix}}(yx).}$

ให้เป็นเมทริกซ์จาโคเบียนของที่ประเมินค่าบนกล่าวอีกนัยหนึ่งคือ ค่าใน ประกอบด้วยภาพของบนดังนั้นจึงได้ว่า โดยที่ผลคูณเมทริกซ์-เวกเตอร์คำนวณโดยใช้เลขคณิตช่วง จากนั้น เมื่ออนุญาตให้ เปลี่ยนแปลงไปตาม จะได้ว่าภาพของบนสอดคล้องกับการบรรจุต่อไปนี้: โดยที่การคำนวณนั้นคำนวณโดยใช้เลขคณิตช่วงอีกครั้ง เมื่อรวมสิ่งนี้กับสูตรสำหรับผลลัพธ์ที่ได้คือตัวดำเนินการ Krawczyck ${\displaystyle G'(J)}$${\displaystyle G}$${\displaystyle J}$${\displaystyle (G'(J))_{ij}}$${\displaystyle {\frac {\partial g_{i}}{\partial x_{j}}}}$${\displaystyle J}$${\displaystyle G(x)\in G(y)+\nabla G(J)(xy),}$${\displaystyle x}$${\displaystyle J}$${\displaystyle G}$${\displaystyle J}$${\displaystyle G(J)\subset G(y)+G'(J)(Jy),}$${\displaystyle G}$

${\displaystyle K_{y,Y}(J)=y-YF(y)+(IF'(J))(Jy),}$

เมท ริกซ์เอกลักษณ์อยู่ที่ไหน${\displaystyle I}$

ถ้าแล้วจะมีจุดตรึงใน นั่นคือมีรากในในทางกลับกัน ถ้าค่าบรรทัดฐานเมทริกซ์ สูงสุด โดยใช้ค่าบรรทัดฐานสูงสุดสำหรับเวกเตอร์ของเมทริกซ์ทั้งหมดใน น้อยกว่าแล้วจะหดตัวภายในดังนั้น จึงมีจุดตรึงที่ไม่ซ้ำกัน ${\displaystyle K_{y,Y}(J)\subset J}$${\displaystyle G}$${\displaystyle J}$${\displaystyle F}$${\displaystyle J}$${\displaystyle IF'(J)}$${\displaystyle 1}$${\displaystyle G}$${\displaystyle J}$${\displaystyle G}$

การทดสอบที่ง่ายกว่า เมื่อใดที่ทรงสี่เหลี่ยมด้านขนานวางตัวตามแนวแกน จะใช้นั่นคือ จุดกึ่งกลางของในกรณีนี้ จะมีรากเพียงหนึ่งเดียวของถ้า ${\displaystyle J}$${\displaystyle y=m(J)}$${\displaystyle J}$${\displaystyle F}$

${\displaystyle \|K(X)-m(X)\|<{\frac {w(X)}{2}},}$

ด้าน ที่ยาวที่สุดของ คือ. ${\displaystyle w(X)}$${\displaystyle J}$

• การทดสอบมิรันดา (Yap, Vegter, Sharma)

• เลขคณิตช่วง (Moore, Arb, Mezzarobba)
• ค่าดัชนีสภาพ (เบลทราน-เลย์กิน)

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

เรขาคณิตพีชคณิตเชิงตัวเลขแก้ระบบพหุนามโดยใช้การต่อเนื่องโฮโมโทปีและวิธีการติดตามเส้นทาง โดยการตรวจสอบหมายเลขเงื่อนไขสำหรับโฮโมโทปีที่ติดตามในทุกขั้นตอน และรับรองว่าไม่มีเส้นทางแก้ปัญหาสองเส้นทางใดตัดกัน เราสามารถคำนวณใบรับรองเชิงตัวเลขพร้อมกับคำตอบได้ แผนการนี้เรียกว่าการติดตามเส้นทางล่วงหน้า^{[ 3 ]}

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