การปรับปรุงแบบวนซ้ำเป็นวิธีการวนซ้ำที่เสนอโดยJames H. Wilkinsonเพื่อปรับปรุงความแม่นยำของคำตอบเชิงตัวเลขสำหรับระบบสมการเชิงเส้น^{[ 1 ] [ 2 ]}

เมื่อแก้ระบบสมการเชิงเส้นเนื่องจากการสะสมของข้อผิดพลาดจากการปัดเศษผลลัพธ์ที่คำนวณได้อาจเบี่ยงเบนจากคำตอบที่ถูกต้องการเริ่มต้นด้วยการปรับปรุงแบบวนซ้ำจะคำนวณลำดับที่ลู่เข้าสู่ ค่าที่ ถูกต้องเมื่อตรงตามข้อสมมติบางประการ ${\displaystyle A\mathbf {x} =\mathbf {b} \,,}$${\displaystyle {\hat {\mathbf {x} }}}$${\displaystyle \mathbf {x} _{\star }\,.}$${\displaystyle \mathbf {x} _{1}={\hat {\mathbf {x} }}\,,}$${\displaystyle \{\mathbf {x} _{1},\,\mathbf {x} _{2},\,\mathbf {x} _{3},\dots \}}$${\displaystyle \mathbf {x} _{\star }\,,}$

การปรับปรุงแบบวนซ้ำ ใน รอบ ที่mประกอบด้วยสามขั้นตอน: ${\displaystyle m=1,2,3,\dots \,,}$

เหตุผลสำคัญสำหรับอัลกอริธึมการปรับปรุงคือ แม้ว่าคำตอบสำหรับc _mในขั้นตอน (ii) อาจมีข้อผิดพลาดคล้ายกับคำตอบแรก แต่การคำนวณค่าตกค้างr _mในขั้นตอน (i) นั้นมีความแม่นยำทางตัวเลขเกือบสมบูรณ์แบบ: คุณอาจไม่ทราบคำตอบที่ถูกต้องดีนัก แต่คุณรู้ได้อย่างแม่นยำว่าคำตอบที่คุณมีอยู่นั้นอยู่ห่างจากผลลัพธ์ที่ถูกต้องมากน้อยเพียงใด ( b ) หากค่าตกค้างมีขนาดเล็กในบางแง่ การแก้ไขก็ต้องมีขนาดเล็กเช่นกัน และอย่างน้อยที่สุดควรจะนำค่าประมาณปัจจุบันของคำตอบx _mเข้าใกล้ค่าที่ต้องการมากขึ้น${\displaystyle {\hat {\mathbf {x} }}}$${\displaystyle \mathbf {x} _{\star }\,.}$

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

โปรดทราบว่าสมการเมทริกซ์ที่แก้ในขั้นตอน (ii) ใช้เมทริกซ์เดียวกันสำหรับการวนซ้ำแต่ละครั้ง หากสมการเมทริกซ์ถูกแก้โดยใช้วิธีโดยตรง เช่น การแยกตัวประกอบCholeskyหรือLUการแยกตัวประกอบที่มีค่าใช้จ่ายเชิงตัวเลขจะทำเพียงครั้งเดียวและนำกลับมาใช้ใหม่สำหรับ การแทนที่ ไปข้างหน้าและย้อนกลับที่ ค่อนข้างประหยัด เพื่อแก้หาc _mในแต่ละการวนซ้ำ^{[ 2 ]}${\displaystyle A}$${\displaystyle A}$

โดยทั่วไป การปรับปรุงแบบวนซ้ำสำหรับการกำจัดแบบเกาส์เซียนจะสร้างโซลูชันที่ถูกต้องตามความแม่นยำในการทำงาน หากใช้ความแม่นยำในการทำงานเป็นสองเท่าในการคำนวณrเช่น โดยการใช้จุดลอยตัวIEEE 754 ที่ มีความแม่นยำ แบบขยาย สี่เท่าหรือสองเท่าและหากAไม่ได้มีสภาพไม่ดีเกินไป (และการวนซ้ำและอัตราการล convergence ถูกกำหนดโดยหมายเลขสภาพของA ) ^{[ 3 ]}

กล่าวอย่างเป็นทางการมากขึ้น สมมติว่าแต่ละขั้นตอน (ii) สามารถแก้ไขได้อย่างแม่นยำพอสมควร กล่าวคือ ในทางคณิตศาสตร์ สำหรับทุกmเราจะได้ว่า $${\displaystyle A\left(I+F_{m}\right)\mathbf {c} _{m}=\mathbf {r} _{m}}$$

โดยที่‖F _m ‖ _∞ < 1ข้อผิดพลาดสัมพัทธ์ในการปรับปรุงซ้ำครั้งที่ m จะเป็นไปตามเงื่อนไข$${\displaystyle {\frac {\lVert \mathbf {x} _{m}-\mathbf {x} _{\star }\rVert _{\infty }}{\lVert \mathbf {x} _{\star }\rVert _{\infty }}}\leq {\bigl (}\sigma \,\kappa (A)\,\varepsilon _{1}{\bigr )}^{m}+\mu _{1}\,\varepsilon _{1}+n\,\kappa (A)\,\mu _{2}\,\varepsilon _{2}}$$

ที่ไหน

• ‖·‖ _∞หมายถึงนอร์ม∞ของเวกเตอร์
• κ ( A )คือค่าสภาพอนันต์ของ A
• nคือลำดับของA
• ε ₁และε ₂คือค่าปัดเศษหน่วยของการดำเนินการทางคณิตศาสตร์แบบจุดลอยตัว
• σ , μ ₁และμ ₂เป็นค่าคงที่ที่ขึ้นอยู่กับA , ε ₁และε ₂

ถ้าA "มีสภาพไม่เลวร้ายเกินไป" ซึ่งในบริบทนี้หมายความว่า

และหมายความว่าμ ₁และμ ₂มีค่าประมาณหนึ่ง

ความแตกต่างระหว่างε ₁และε _{2 มีจุดประสงค์เพื่อให้สามารถประเมินค่า} r _mด้วยความแม่นยำแบบผสมโดยที่ผลลัพธ์ระหว่างกลางจะถูกคำนวณด้วยการปัดเศษε ₂ก่อนที่ผลลัพธ์สุดท้ายจะถูกปัดเศษ (หรือตัดทิ้ง) ด้วยการปัดเศษε ₁ส่วน การคำนวณอื่นๆ ทั้งหมดจะถือว่าดำเนินการด้วยการปัดเศษε ₁