ในทางคณิตศาสตร์วิธีการไล่ระดับเชิงสังยุค (conjugate gradient method)เป็นอัลกอริทึมสำหรับการแก้ระบบสมการเชิงเส้นบาง ระบบด้วยวิธีเชิงตัวเลข โดยเฉพาะอย่างยิ่งระบบสมการที่มีเมทริกซ์เป็น เมทริกซ์บวกกึ่ง กำหนด (positive-semidefinite matrix ) วิธีการไล่ระดับเชิงสังยุคมักถูกนำไปใช้ในรูปแบบอัลกอริทึมแบบวนซ้ำ ซึ่ง สามารถนำไปใช้กับ ระบบ เมทริกซ์เบาบาง (sparse systems) ที่มีขนาดใหญ่เกินกว่าจะจัดการได้ด้วยวิธีโดยตรงหรือวิธีการโดยตรงอื่นๆ เช่น การแยกตัวประกอบโคลสกี้ (Cholesky decomposition ) ระบบเมทริกซ์เบาบางขนาดใหญ่มักเกิดขึ้นเมื่อแก้สมการเชิงอนุพันธ์ย่อยหรือปัญหาการหาค่าเหมาะสมที่สุด ด้วยวิธีเชิงตัวเลข

วิธีการไล่ระดับคอนจูเกตยังสามารถใช้ในการแก้ ปัญหา การหาค่าเหมาะสมที่สุด แบบไม่มีข้อจำกัด เช่นการลดพลังงานให้เหลือน้อย ที่สุด โดยทั่วไปแล้วเชื่อกันว่าเป็นผลงานของ^Magnus HestenesและEduard Stiefel [ ^{1 ] [ 2 ] ซึ่ง}ได้เขียนโปรแกรมลงบนZ4 [ ^{3 ]}และทำการวิจัยอย่างกว้างขวาง^{[ 4 ] [ 5 ]}

วิธีการไล่ระดับแบบไบคอนจูเกต (Biconjugate Gradient Method)เป็นวิธีการทั่วไปที่ใช้กับเมทริกซ์ที่ไม่สมมาตรวิธีการไล่ระดับแบบคอนจูเกตที่ไม่เป็นเชิงเส้น ต่างๆ มุ่งหาค่าต่ำสุดของปัญหาการหาค่าเหมาะสมที่สุดที่ไม่เป็นเชิงเส้น

สมมติว่าเราต้องการแก้ระบบสมการเชิงเส้น

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

สำหรับเวกเตอร์ โดยที่ เมทริกซ์ที่ทราบนั้นเป็น เมทริกซ์ สมมาตร (เช่น) เป็นเมทริกซ์บวกแน่นอน (เช่นสำหรับเวกเตอร์ที่ไม่เป็นศูนย์ทั้งหมดใน) และ เป็นเมท ริก ซ์ จริงและ ก็เป็นที่ทราบเช่นกัน เราใช้สัญลักษณ์ แทนคำตอบเฉพาะของระบบนี้${\displaystyle \mathbf {x} }$${\displaystyle n\times n}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {A} ^{\mathsf {T}}=\mathbf {A} }$${\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {Ax} >0}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {x} _{*}}$

วิธีการไล่ระดับเชิงสังยุค (Conjugate Gradient Method) สามารถพัฒนาได้จากหลายมุมมอง รวมถึงการประยุกต์ใช้เฉพาะทางของวิธีการทิศทางเชิงสังยุค (Conjugate Direction Method) สำหรับการหาค่าเหมาะสมที่สุด และการเปลี่ยนแปลงของ การวนซ้ำแบบ Arnoldi / Lanczosสำหรับ ปัญหา ค่าลักษณะเฉพาะแม้ว่าจะมีวิธีการที่แตกต่างกัน แต่การพัฒนาเหล่านี้มีหัวข้อร่วมกันคือ การพิสูจน์ความเป็นตั้งฉากของค่าตกค้างและความเป็นสังยุคของทิศทางการค้นหา คุณสมบัติทั้งสองนี้มีความสำคัญอย่างยิ่งต่อการพัฒนาสูตรที่กระชับและเป็นที่รู้จักกันดีของวิธีการนี้

เรากล่าวว่าเวกเตอร์ที่ไม่เป็นศูนย์สองตัว คือและเป็นคู่สังยุคกัน (โดยสัมพันธ์กับ) ถ้า ${\displaystyle \mathbf {u} }$${\displaystyle \mathbf {v} }$${\displaystyle \mathbf {A} }$

${\displaystyle \mathbf {u} ^{\mathsf {T}}\mathbf {A} \mathbf {v} =0.}$

เนื่องจากเมทริกซ์สมมาตรและเป็นเมทริกซ์บวกแน่นอน ด้านซ้ายมือจึงกำหนดผลคูณภายใน${\displaystyle \mathbf {A} }$

${\displaystyle \mathbf {u} ^{\mathsf {T}}\mathbf {A} \mathbf {v} =\langle \mathbf {u} ,\mathbf {v} \rangle _{\mathbf {A} }:=\langle \mathbf {A} \mathbf {u} ,\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} ^{\mathsf {T}}\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} \mathbf {v} \rangle .}$

เวกเตอร์สองตัวเป็นคู่สังยุคกันก็ต่อเมื่อเวกเตอร์ทั้งสองตั้งฉากกันโดยพิจารณาจากผลคูณภายใน การเป็นคู่สังยุคเป็นความสัมพันธ์แบบสมมาตร: ถ้าเป็นคู่สังยุคกับแล้วเป็นคู่สังยุคกับสมมติว่า ${\displaystyle \mathbf {u} }$${\displaystyle \mathbf {v} }$${\displaystyle \mathbf {v} }$${\displaystyle \mathbf {u} }$

${\displaystyle P=\{\mathbf {p} _{1},\dots ,\mathbf {p} _{n}\}}$

คือเซตของเวกเตอร์ที่สัมพันธ์กันโดยสัมพันธ์กับ นั่นคือสำหรับทุกแล้วจะเป็นฐานสำหรับและเราสามารถแสดงคำตอบของในฐานนี้ได้: ${\displaystyle n}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{j}=0}$${\displaystyle i\neq j}$${\displaystyle P}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbf {x} _{*}}$${\displaystyle \mathbf {Ax} =\mathbf {b} }$

${\displaystyle \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{i}\ลูกศรขวา \mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {A} \mathbf {p} _{i}.}$

การคูณปัญหาทางซ้ายด้วยเวกเตอร์จะได้ผลลัพธ์ดังนี้ ${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {p} _{k}^{\mathsf {T}}}$

${\displaystyle \mathbf {p} _{k}^{\mathsf {T}}\mathbf {b} =\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{i}=\sum _{i=1}^{n}\alpha _{i}\left\langle \mathbf {p} _{k},\mathbf {p} _{i}\right\rangle _{\mathbf {A} }=\alpha _{k}\ซ้าย\langle \mathbf {p} _{k},\mathbf {p} _{k}\right\rangle _{\mathbf {A} }}$

และดังนั้น

${\displaystyle \alpha _{k}={\frac {\langle \mathbf {p} _{k},\mathbf {b} \rangle }{\langle \mathbf {p} _{k},\mathbf {p} _{k}\rangle _{\mathbf {A} }}}.}$

วิธีนี้ให้^{[ 4 ]}สำหรับการแก้สมการ: หาลำดับของทิศทางคู่ควบ จากนั้นคำนวณสัมประสิทธิ์ ${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle n}$${\displaystyle \alpha _{k}}$

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

เราใช้สัญลักษณ์ แทนค่าเริ่มต้นของ(เราสามารถสมมติได้โดยไม่เสียความเป็นทั่วไปว่ามิฉะนั้นให้พิจารณาระบบแทน) เริ่มต้นด้วยเราค้นหาคำตอบ และในแต่ละรอบการทำซ้ำ เราจำเป็นต้องมีตัวชี้วัดเพื่อบอกเราว่าเราเข้าใกล้คำตอบ(ซึ่งเราไม่ทราบ) มากขึ้นหรือไม่ ตัวชี้วัดนี้มาจากข้อเท็จจริงที่ว่าคำตอบนั้นเป็นตัวลดค่าต่ำสุดเพียงตัวเดียวของฟังก์ชันกำลังสอง ต่อไปนี้${\displaystyle \mathbf {x} _{*}}$${\displaystyle \mathbf {x} _{0}}$${\displaystyle \mathbf {x} _{0}=\mathbf {0} }$${\displaystyle \mathbf {Az} =\mathbf {b} -\mathbf {Ax} _{0}}$${\displaystyle \mathbf {x} _{0}}$${\displaystyle \mathbf {x} _{*}}$${\displaystyle \mathbf {x} _{*}}$

${\displaystyle f(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {A} \mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {b} ,\qquad \mathbf {x} \in \mathbb {R} ^{n}\,.}$

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

${\displaystyle \mathbf {H} (f(\mathbf {x} ))=\mathbf {A} \,,}$

และการที่ตัวลดค่าต่ำสุด (ใช้) แก้ปัญหาเริ่มต้นได้นั้น เป็นผลมาจากอนุพันธ์อันดับแรกของมัน ${\displaystyle Df(\mathbf {x} )=0}$

${\displaystyle \nabla f(\mathbf {x} )=\mathbf {A} \mathbf {x} -\mathbf {b} \,.}$

วิธีนี้แนะนำให้เลือกเวกเตอร์ฐานตัวแรกเป็นค่าลบของเกรเดียนต์ของที่ เกร เดียนต์ของ เท่ากับเริ่มต้นด้วยการคาดเดาเบื้องต้นซึ่งหมายความว่าเราเลือกเวกเตอร์อื่นๆ ในฐานจะเป็นคอนจูเกตกับเกรเดียนต์ ดังนั้นจึงเรียกว่าวิธีเกรเดียนต์คอนจูเกตโปรดทราบว่า ก็คือ ค่าตกค้างที่ได้จากขั้นตอนเริ่มต้นของอัลกอริธึมนี้ ด้วย${\displaystyle \mathbf {p} _{0}}$${\displaystyle f}$${\displaystyle \mathbf {x} =\mathbf {x} _{0}}$${\displaystyle f}$${\displaystyle \mathbf {Ax} -\mathbf {b} }$${\displaystyle \mathbf {x} _{0}}$${\displaystyle \mathbf {p} _{0}=\mathbf {b} -\mathbf {Ax} _{0}}$${\displaystyle \mathbf {p} _{0}}$

ให้เป็นค่าตกค้างที่ขั้นตอนที่ th: ${\displaystyle \mathbf {r} _{k}}$${\displaystyle k}$

${\displaystyle \mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}.}$

ดังที่สังเกตได้ข้างต้นคือค่าลบของความชันที่ดังนั้น วิธี การลดความชันจะต้องเคลื่อนที่ไปในทิศทางr _kอย่างไรก็ตาม ในที่นี้เรายืนยันว่าทิศทางจะต้องเป็นคู่กัน วิธีการที่ใช้ได้ผลในการบังคับใช้สิ่งนี้คือการกำหนดให้ทิศทางการค้นหาถัดไปสร้างขึ้นจากค่าตกค้างปัจจุบันและทิศทางการค้นหาก่อนหน้าทั้งหมด ข้อจำกัดเรื่องคู่กันนี้เป็นข้อจำกัดประเภทออร์โทนอร์มอล ดังนั้นอัลกอริทึมจึงสามารถมองได้ว่าเป็นตัวอย่างของการทำให้เป็นออร์โทนอร์มอลแบบแกรม-ชมิดท์ซึ่งจะได้นิพจน์ต่อไปนี้: ${\displaystyle \mathbf {r} _{k}}$${\displaystyle f}$${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {p} _{k}}$

${\displaystyle \mathbf {p} _{k}=\mathbf {r} _{k}-\sum _{i<k}{\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{i}}{\mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{i}}}\mathbf {p} _{i}}$

(ดูภาพด้านบนของบทความเพื่อดูผลกระทบของข้อจำกัดการสมมูลต่อการล convergence) เมื่อพิจารณาตามทิศทางนี้ ตำแหน่งที่เหมาะสมที่สุดถัดไปจะได้รับจาก

${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}$

กับ

${\displaystyle \alpha _{k}={\frac {\mathbf {p} _{k}^{\mathsf {T}}(\mathbf {b} -\mathbf {Ax} _{k})}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}={\frac {\mathbf {p} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}},}$

โดยความเท่าเทียมกันสุดท้ายเป็นผลมาจากนิยามของนิพจน์สำหรับสามารถหาได้หากแทนที่นิพจน์สำหรับx _{k +1}ลงในfและทำให้มีค่าน้อยที่สุดเมื่อเทียบกับ${\displaystyle \mathbf {r} _{k}}$${\displaystyle \alpha _{k}}$${\displaystyle \alpha _{k}}$

${\displaystyle {\begin{aligned}f(\mathbf {x} _{k+1})&=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})=:g(\alpha _{k})\\g'(\alpha _{k})&{\overset {!}{=}}0\quad \Rightarrow \quad \alpha _{k}={\frac {\mathbf {p} _{k}^{\mathsf {T}}(\mathbf {b} -\mathbf {Ax} _{k})}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}\,.\end{aligned}}}$

อัลกอริทึมข้างต้นให้คำอธิบายที่ตรงไปตรงมาที่สุดของวิธีการไล่ระดับคอนจูเกต ดูเหมือนว่าอัลกอริทึมตามที่ระบุไว้จะต้องการการจัดเก็บทิศทางการค้นหาก่อนหน้าทั้งหมดและเวกเตอร์ตกค้าง รวมถึงการคูณเมทริกซ์-เวกเตอร์จำนวนมาก ซึ่งอาจทำให้การคำนวณมีค่าใช้จ่ายสูง อย่างไรก็ตาม การวิเคราะห์อย่างละเอียด^{[ 6 ] : หน้า 558} ของอัลกอริทึมแสดงให้เห็นว่าตั้งฉาก กับ นั่น คือสำหรับและตั้งฉากกับนั่นคือสำหรับสิ่งนี้สามารถพิจารณาได้ว่าเมื่ออัลกอริทึมดำเนินไปและ ครอบคลุม พื้นที่ย่อย Krylovเดียวกันโดยที่สร้างฐานตั้งฉากกับผลคูณภายในมาตรฐาน และสร้างฐานตั้งฉากกับผลคูณภายในที่เกิดจากดังนั้น จึงสามารถพิจารณาได้ว่าเป็นภาพฉายของบนพื้นที่ย่อย Krylov ${\displaystyle \mathbf {r} _{i}}$${\displaystyle \mathbf {r} _{j}}$${\displaystyle \mathbf {r} _{i}^{\mathsf {T}}\mathbf {r} _{j}=0}$${\displaystyle i\neq j}$${\displaystyle \mathbf {p} _{i}}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {p} _{j}}$${\displaystyle \mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{j}=0}$${\displaystyle i\neq j}$${\displaystyle \mathbf {p} _{i}}$${\displaystyle \mathbf {r} _{i}}$${\displaystyle \mathbf {r} _{i}}$${\displaystyle \mathbf {p} _{i}}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {x} }$

นั่นคือ ถ้าวิธี CG เริ่มต้นด้วยแล้ว^{[ 7 ]}โดยที่คือคำตอบของ ${\displaystyle \mathbf {x} _{0}=0}$$${\displaystyle x_{k}=\mathrm {argmin} _{y\in \mathbb {R} ^{n}}{\left\{(x_{*}-y)^{\top }A(x_{*}-y):y\in \operatorname {span} \left\{b,Ab,\ldots ,A^{k-1}b\right\}\right\}}}$$${\displaystyle x_{*}}$${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

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

${\displaystyle {\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&{\hbox{if }}\mathbf {r} _{0}{\text{ is sufficiently small, then return }}\mathbf {x} _{0}{\text{ as the result}}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&k:=0\\&{\text{repeat}}\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad {\hbox{if }}\mathbf {r} _{k+1}{\text{ is sufficiently small, then exit loop}}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad k:=k+1\\&{\text{end repeat}}\\&{\text{return }}\mathbf {x} _{k+1}{\text{ as the result}}\end{aligned}}}$

นี่คืออัลกอริทึมที่ใช้กันบ่อยที่สุด สูตรเดียวกันนี้ยังใช้ในวิธีการไล่ระดับเชิงสังยุคแบบไม่เชิงเส้น ของเฟลตเชอร์-รีฟส์ ด้วย ${\displaystyle \beta _{k}}$

เราสังเกตว่าคำนวณโดย วิธี ไล่ระดับความชันที่ใช้กับการตั้งค่าจะทำให้คำนวณโดยวิธีไล่ระดับความชัน จาก ในทำนองเดียวกัน กล่าวคือ สามารถใช้เป็นการใช้งานแบบง่ายของการเริ่มต้นใหม่ของการวนซ้ำไล่ระดับความชันแบบสังยุค^{[ 4 ]}การเริ่มต้นใหม่อาจทำให้การบรรจบกันช้าลง แต่อาจปรับปรุงเสถียรภาพได้หากวิธีไล่ระดับความชันแบบสังยุคทำงานผิดปกติ เช่น เนื่องจาก ข้อผิดพลาดใน การ ปัดเศษ${\displaystyle \mathbf {x} _{1}}$${\displaystyle \mathbf {x} _{0}}$${\displaystyle \beta _{k}=0}$${\displaystyle \mathbf {x} _{k+1}}$${\displaystyle \mathbf {x} _{k}}$

สูตรและซึ่งทั้งคู่เป็นไปตามเลขคณิตที่แม่นยำ ทำให้สูตรและเทียบเท่ากันทางคณิตศาสตร์ สูตรแรกใช้ในอัลกอริทึมเพื่อหลีกเลี่ยงการคูณเพิ่มเติมด้วยเนื่องจากเวกเตอร์ได้รับการคำนวณแล้วเพื่อประเมินสูตรหลังอาจมีความแม่นยำมากกว่า โดยแทนที่การคำนวณที่ชัดเจนด้วยการคำนวณโดยปริยายด้วยการเรียกซ้ำซึ่งขึ้นอยู่กับ การสะสม ข้อผิดพลาดจากการปัดเศษดังนั้นจึงแนะนำให้ใช้สำหรับการประเมินเป็นครั้งคราว^{[ 8 ]}${\displaystyle \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}$${\displaystyle \mathbf {r} _{k}:=\mathbf {b} -\mathbf {Ax} _{k}}$${\displaystyle \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}}$${\displaystyle \mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {Ap} _{k}}$${\displaystyle \alpha _{k}}$${\displaystyle \mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}}$

โดยทั่วไปแล้วค่ามาตรฐานของค่าตกค้างจะถูกใช้เป็นเกณฑ์ในการหยุดการคำนวณ ค่ามาตรฐานของค่าตกค้างที่แสดงอย่างชัดเจนจะให้ระดับความแม่นยำที่รับประกันได้ทั้งในการคำนวณที่แม่นยำและในกรณีที่มีข้อผิดพลาดจากการปัดเศษ ซึ่งการลู่เข้าจะหยุดชะงักลงตามธรรมชาติ ในทางตรงกันข้าม ค่าตกค้างโดยปริยาย นั้นทราบกันดีว่าจะมีแอมพลิจูดลดลงเรื่อยๆ แม้จะต่ำกว่าระดับของข้อผิดพลาดจากการปัดเศษดังนั้นจึงไม่สามารถนำมาใช้ในการกำหนดการหยุดชะงักของการลู่เข้าได้ ${\displaystyle \mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}}$${\displaystyle \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}}$

ในอัลกอริทึมนี้จะเลือกให้ตั้งฉากกับตัวส่วนจะถูกทำให้ง่ายขึ้นจาก ${\displaystyle \alpha _{k}}$${\displaystyle \mathbf {r} _{k+1}}$${\displaystyle \mathbf {r} _{k}}$

${\displaystyle \alpha _{k}={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}}$

เนื่องจาก. ถูกเลือกให้มีค่าเป็นคู่ควบกับ. ในตอนเริ่มต้นคือ ${\displaystyle \mathbf {r} _{k+1}=\mathbf {p} _{k+1}-\mathbf {\beta } _{k}\mathbf {p} _{k}}$${\displaystyle \beta _{k}}$${\displaystyle \mathbf {p} _{k+1}}$${\displaystyle \mathbf {p} _{k}}$${\displaystyle \beta _{k}}$

${\displaystyle \beta _{k}=-{\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}}$

โดยใช้

${\displaystyle \mathbf {r} _{k+1}=\mathbf {r} _{k}-\alpha _{k}\mathbf {A} \mathbf {p} _{k}}$

และในทำนองเดียวกัน

${\displaystyle \mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}(\mathbf {r} _{k}-\mathbf {r} _{k+1}),}$

ตัวเศษของถูกเขียนใหม่เป็น ${\displaystyle \beta _{k}}$

${\displaystyle \mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}\mathbf {r} _{k+1}^{\mathsf {T}}(\mathbf {r} _{k}-\mathbf {r} _{k+1})=-{\frac {1}{\alpha _{k}}}\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}}$

เนื่องจากและตั้งฉากกันโดยธรรมชาติ ตัวส่วนจึงถูกเขียนใหม่เป็น ${\displaystyle \mathbf {r} _{k+1}}$${\displaystyle \mathbf {r} _{k}}$

${\displaystyle \mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}=(\mathbf {r} _{k}+\beta _{k-1}\mathbf {p} _{k-1})^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}\mathbf {r} _{k}^{\mathsf {T}}(\mathbf {r} _{k}-\mathbf {r} _{k+1})={\frac {1}{\alpha _{k}}}\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}$

โดยใช้ข้อเท็จจริงที่ว่าทิศทางการค้นหาเป็นคู่กัน และอีกครั้งที่ว่าค่าตกค้างเป็นตั้งฉากกัน ซึ่งจะทำให้ได้ผลลัพธ์ในอัลกอริทึมหลังจากตัดทิ้งแล้ว ${\displaystyle \mathbf {p} _{k}}$${\displaystyle \beta }$${\displaystyle \alpha _{k}}$

โดยใช้พีชคณิตเชิงเส้น""" x = conjugate_gradient(A, b, x0 = zero(b); atol=length(b)*eps(norm(b))ส่งคืนคำตอบของสมการ `A * x = b` โดยใช้วิธีการไล่ระดับเชิงสังยุค`A` ต้องเป็นเมทริกซ์บวกกำหนด หรือตัวดำเนินการเชิงเส้นอื่นๆ`x0` คือค่าประมาณเริ่มต้นสำหรับคำตอบ (ค่าเริ่มต้นคือเวกเตอร์ศูนย์)`atol` คือค่าความคลาดเคลื่อนสัมบูรณ์ของขนาดค่าตกค้าง `b - A * x`เพื่อการบรรจบกัน (ค่าเริ่มต้นคือค่าเอปซิลอนของเครื่อง)ส่งคืนเวกเตอร์คำตอบโดยประมาณ `x`"""ฟังก์ชันconjugate_gradient (A , b :: AbstractVector , x0 :: AbstractVector = zero ( b ); atol = length ( b ) * eps ( norm ( b )))x = copy ( x0 ) # เริ่มต้นโซลูชันr = b - A * x0 # ค่าตกค้างเริ่มต้นp = copy ( r ) # ทิศทางการค้นหาเริ่มต้นr²old = r ' * r # ค่ากำลังสองของค่าตกค้างk = 0ในขณะที่r²old > atol ^ 2 # ทำซ้ำจนกว่าจะบรรจบกันAp = A * p # ทิศทางการค้นหาα = r²old / ( p ' * Ap ) # ขนาดขั้นตอน@. x += α * p # อัปเดตโซลูชัน# อัปเดตค่าคงเหลือ:ถ้า( k + 1 ) % 16 == 0 # ทุกๆ 16 รอบการทำซ้ำ ให้คำนวณค่าตกค้างใหม่ตั้งแต่เริ่มต้นr .= b .- A * x # เพื่อหลีกเลี่ยงการสะสมของข้อผิดพลาดเชิงตัวเลขอื่น@. r -= α * Ap # ใช้สูตรการอัปเดตที่ช่วยประหยัดผลคูณเมทริกซ์-เวกเตอร์หนึ่งครั้งจบr²ใหม่= r ' * r@. p = r + ( r²new / r²old ) * p # อัปเดตทิศทางการค้นหาr²old = r²new # อัปเดตค่าความคลาดเคลื่อนกำลังสองk += 1จบส่งคืนxจบ

ฟังก์ชัน x = conjugate_gradient ( A, b, x0, tol )% ส่งคืนคำตอบของสมการ `A * x = b` โดยใช้วิธีการไล่ระดับเชิงสังยุคหมายเหตุ: เมทริกซ์ A ควรมีสมมาตรและเป็นเมทริกซ์บวกแน่นอนถ้าnargin < 4tol = eps ;จบr = b - A * x0 ;p = r ;rsold = r ' * r ;x = x0 ;ในขณะที่sqrt ( rsold ) > tolAp = A * p ;อัลฟา= rsold / ( p ' * Ap );x = x + alpha * p ;r = r - alpha * Ap ;rsnew = r ' * r ;p = r + ( rsnew / rsold ) * p ;rsold = rsnew ;จบจบ

พิจารณาระบบเชิงเส้นAx = bที่กำหนดโดย

${\displaystyle \mathbf {A} \mathbf {x} ={\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}1\\2\end{bmatrix}},}$

เราจะดำเนินการสองขั้นตอนของวิธีการไล่ระดับเชิงสังยุค โดยเริ่มจากการคาดเดาเบื้องต้น

${\displaystyle \mathbf {x} _{0}={\begin{bmatrix}2\\1\end{bmatrix}}}$

เพื่อหาคำตอบโดยประมาณของระบบสมการ

เพื่อเป็นข้อมูลอ้างอิง คำตอบที่ถูกต้องคือ

${\displaystyle \mathbf {x} ={\begin{bmatrix}{\frac {1}{11}}\\\\{\frac {7}{11}}\end{bmatrix}}\approx {\begin{bmatrix}0.0909\\\\0.6364\end{bmatrix}}}$

ขั้นตอนแรกของเราคือการคำนวณเวกเตอร์ส่วนเหลือr ₀ที่เกี่ยวข้องกับx ₀ส่วนเหลือนี้คำนวณจากสูตรr ₀ = b - Ax ₀และในกรณีของเรามีค่าเท่ากับ

${\displaystyle \mathbf {r} _{0}={\begin{bmatrix}1\\2\end{bmatrix}}-{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}2\\1\end{bmatrix}}={\begin{bmatrix}-8\\-3\end{bmatrix}}=\mathbf {p} _{0}.}$

เนื่องจากนี่เป็นการวนซ้ำครั้งแรก เราจะใช้เวกเตอร์ส่วนเหลือr ₀เป็นทิศทางการค้นหาเริ่มต้นp ₀วิธีการเลือกp _kจะเปลี่ยนไปในการวนซ้ำครั้งต่อไป

ตอนนี้เราจะคำนวณค่าสเกลาร์α ₀โดยใช้ความสัมพันธ์ต่อไปนี้

${\displaystyle \alpha _{0}={\frac {\mathbf {r} _{0}^{\mathsf {T}}\mathbf {r} _{0}}{\mathbf {p} _{0}^{\mathsf {T}}\mathbf {Ap} _{0}}}={\frac {{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}{{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}}={\frac {73}{331}}\approx 0.2205}$

ตอนนี้เราสามารถคำนวณx ₁โดยใช้สูตรได้ แล้ว

${\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}+\alpha _{0}\mathbf {p} _{0}={\begin{bmatrix}2\\1\end{bmatrix}}+{\frac {73}{331}}{\begin{bmatrix}-8\\-3\end{bmatrix}}\approx {\begin{bmatrix}0.2356\\0.3384\end{bmatrix}}.}$

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

${\displaystyle \mathbf {r} _{1}=\mathbf {r} _{0}-\alpha _{0}\mathbf {A} \mathbf {p} _{0}={\begin{bmatrix}-8\\-3\end{bmatrix}}-{\frac {73}{331}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}\approx {\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}.}$

ขั้นตอนต่อไปในกระบวนการของเราคือการคำนวณค่าสเกลาร์β ₀ ซึ่งในที่สุดจะถูก นำ มาใช้เพื่อกำหนดทิศทางการค้นหาถัดไปp ₁

${\displaystyle \beta _{0}={\frac {\mathbf {r} _{1}^{\mathsf {T}}\mathbf {r} _{1}}{\mathbf {r} _{0}^{\mathsf {T}}\mathbf {r} _{0}}}\approx {\frac {{\begin{bmatrix}-0.2810&0.7492\end{bmatrix}}{\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}}{{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}}=0.0088.}$

ทีนี้ เมื่อใช้ค่าสเกลาร์β ₀ นี้ เราสามารถคำนวณทิศทางการค้นหาถัดไปp ₁โดยใช้ความสัมพันธ์ต่อไปนี้

${\displaystyle \mathbf {p} _{1}=\mathbf {r} _{1}+\beta _{0}\mathbf {p} _{0}\approx {\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}+0.0088{\begin{bmatrix}-8\\-3\end{bmatrix}}={\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}.}$

ต่อไปนี้เราจะคำนวณค่าสเกลาร์α 1 _โดย ใช้ p ₁ที่เราเพิ่งได้รับมาโดยใช้วิธีเดียวกับที่ใช้สำหรับα ₀

${\displaystyle \alpha _{1}={\frac {\mathbf {r} _{1}^{\mathsf {T}}\mathbf {r} _{1}}{\mathbf {p} _{1}^{\mathsf {T}}\mathbf {Ap} _{1}}}\approx {\frac {{\begin{bmatrix}-0.2810&0.7492\end{bmatrix}}{\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}}{{\begin{bmatrix}-0.3511&0.7229\end{bmatrix}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}}}=0.4122.}$

สุดท้าย เราหาค่าx ₂โดยใช้วิธีเดียวกับที่ใช้หาค่า x ₁

${\displaystyle \mathbf {x} _{2}=\mathbf {x} _{1}+\alpha _{1}\mathbf {p} _{1}\approx {\begin{bmatrix}0.2356\\0.3384\end{bmatrix}}+0.4122{\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}={\begin{bmatrix}0.0909\\0.6364\end{bmatrix}}.}$

ผลลัพธ์x ₂เป็นค่าประมาณที่ดีกว่าสำหรับคำตอบของระบบเมื่อเทียบกับx ₁และx ₀หากใช้การคำนวณที่แม่นยำในตัวอย่างนี้แทนการคำนวณแบบจำกัดความแม่นยำ คำตอบที่แม่นยำจะได้รับตามทฤษฎีหลังจากวนซ้ำn = 2 ครั้ง ( โดยที่ nคือลำดับของระบบ)

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

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

เพื่อแสดงให้เห็นถึงเรื่องนี้ ลองพิจารณาระบบต่อไปนี้:

${\displaystyle A={\begin{bmatrix}3&-2\\-2&4\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}1\\1\end{bmatrix}}}$

เราเริ่มต้นจากการคาดเดาเบื้องต้นเนื่องจากเมทริกซ์ เป็นเมทริกซ์สมมาตรบวกแน่นอน และระบบเป็นแบบ 2 มิติ วิธีการไล่ระดับเชิงสังยุคจึงควรหาคำตอบที่ถูกต้องได้ภายในไม่เกิน 2 ขั้นตอน โค้ด MATLAB ต่อไปนี้แสดงให้เห็นถึงพฤติกรรมนี้: ${\displaystyle \mathbf {x} _{0}={\begin{bmatrix}1\\2\end{bmatrix}}}$${\displaystyle A}$

A = [ 3 , - 2 ; - 2 , 4 ]; x_true = [ 1 ; 1 ]; b = A * x_true ;x = [ 1 ; 2 ]; % การคาดเดาเบื้องต้นr = b - A * x ; p = r ;สำหรับk = 1 : 2 Ap = A * p ; alpha = ( r ' * r ) / ( p ' * Ap ); x = x + alpha * p ; r_new = r - alpha * Ap ; beta = ( r_new ' * r_new ) / ( r ' * r ); p = r_new + beta * p ; r = r_new ; endแสดงผลลัพธ์( 'คำตอบที่ถูกต้อง:' ); แสดงผลลัพธ์( x );

ผลลัพธ์ยืนยันว่าวิธีการนี้บรรลุผลหลังจากสองรอบการทำซ้ำ ซึ่งสอดคล้องกับการคาดการณ์ทางทฤษฎี ตัวอย่างนี้แสดงให้เห็นว่าวิธีการไล่ระดับแบบสังยุค (conjugate gradient method) ทำงานเหมือนวิธีการโดยตรง (direct method) ภายใต้เงื่อนไขในอุดมคติ ${\displaystyle {\begin{bmatrix}1\\1\end{bmatrix}}}$

คุณสมบัติการสิ้นสุดที่จำกัดยังมีนัยสำคัญในทางปฏิบัติในการแก้ระบบเมทริกซ์แบบเบาบางขนาดใหญ่ ซึ่งมักเกิดขึ้นในงานวิทยาศาสตร์และวิศวกรรม ตัวอย่างเช่น การทำให้สมการลาปลาสสองมิติเป็นแบบไม่ต่อเนื่องโดยใช้ผลต่างจำกัดบนตารางสม่ำเสมอจะนำไปสู่ระบบเชิงเส้นแบบเบาบางโดยที่เป็นเมทริกซ์สมมาตรและเป็นบวกแน่นอน ${\displaystyle \nabla ^{2}u=0}$${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle A}$

การใช้ตารางภายในทำให้ได้ระบบ และเมทริกซ์สัมประสิทธิ์มีรูปแบบแม่แบบห้าจุด แต่ละแถวประกอบด้วยค่าที่ไม่เป็นศูนย์อย่างมากที่สุดห้าค่า ซึ่งสอดคล้องกับจุดศูนย์กลางและจุดข้างเคียงโดยตรง ตัวอย่างเช่น เมทริกซ์ที่สร้างจากตารางดังกล่าวอาจมีลักษณะดังนี้: ${\displaystyle 5\times 5}$${\displaystyle 25\times 25}$${\displaystyle A}$${\displaystyle A}$

${\displaystyle A={\begin{bmatrix}4&-1&0&\cdots &-1&0&\cdots \\-1&4&-1&\cdots &0&0&\cdots \\0&-1&4&-1&0&0&\cdots \\\vdots &\vdots &\ddots &\ddots &\ddots &\vdots \\-1&0&\cdots &-1&4&-1&\cdots \\0&0&\cdots &0&-1&4&\cdots \\\vdots &\vdots &\cdots &\cdots &\cdots &\ddots \end{bmatrix}}}$

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

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

วิธีการ ไล่ระดับคอนจูเกต เป็นวิธีการวนซ้ำที่ปรับปรุงการประมาณค่าของคำตอบที่ถูกต้องอย่างต่อเนื่อง (ในบรรทัดฐานพลังงาน) และอาจบรรลุค่าความคลาดเคลื่อนที่ต้องการได้หลังจากจำนวนการวนซ้ำที่ค่อนข้างน้อย (เมื่อเทียบกับขนาดของปัญหา) การปรับปรุงโดยทั่วไปจะเป็นเชิงเส้น และความเร็วจะถูกกำหนดโดยค่าสภาพของเมทริกซ์ระบบยิ่งค่าสภาพมากการปรับปรุงก็จะยิ่งช้าลง^{[ 9 ]}${\displaystyle \mathbf {x} _{k}}$${\displaystyle \kappa (A)}$${\displaystyle A}$${\displaystyle \kappa (A)}$

อย่างไรก็ตาม กรณีที่น่าสนใจเกิดขึ้นเมื่อค่าไอเกนมีการเรียงตัวแบบลอการิทึมสำหรับเมทริกซ์สมมาตรขนาดใหญ่ ตัวอย่างเช่น ให้เป็นเมทริกซ์ตั้งฉากแบบสุ่ม และเป็นเมทริกซ์แนวทแยงที่มีค่าไอเกนตั้งแต่ ถึง โดยมีการเรียงตัวแบบลอการิทึม แม้ว่า CGM จะมีคุณสมบัติการสิ้นสุดที่จำกัด ซึ่งในทางทฤษฎีแล้วควรจะได้คำตอบที่ถูกต้องภายในขั้นตอนอย่างมากที่สุด แต่ก็อาจเกิดการชะงักงันในการลู่เข้าได้ ในสถานการณ์เช่นนี้ แม้หลังจากทำซ้ำหลายครั้งมากขึ้น เช่น สิบเท่าของขนาดเมทริกซ์ ข้อผิดพลาดอาจลดลงเพียงเล็กน้อย (เช่น ถึง) ยิ่งไปกว่านั้น ข้อผิดพลาดในการทำซ้ำอาจแกว่งไปมาอย่างมาก ทำให้ไม่น่าเชื่อถือในฐานะเงื่อนไขการหยุด การลู่เข้าที่ไม่ดีนี้ไม่ได้อธิบายด้วยค่าสภาพเพียงอย่างเดียว (เช่น) แต่เกิดจากลักษณะการกระจายของค่าไอเกนเอง เมื่อค่าไอเกนกระจายตัวอย่างสม่ำเสมอมากขึ้นหรือกระจายตัวแบบสุ่ม ปัญหาการบรรจบกันดังกล่าวมักจะไม่มีอยู่ ซึ่งแสดงให้เห็นว่าประสิทธิภาพของ CGM ไม่ได้ขึ้นอยู่กับการกระจายตัวของค่าไอเกน เพียงอย่างเดียว ^{[ 10 ]}${\displaystyle A=QDQ^{T}}$${\displaystyle Q}$${\displaystyle D}$${\displaystyle \lambda _{n}=1}$${\displaystyle \lambda _{1}=10^{6}}$${\displaystyle n}$${\displaystyle 10^{-5}}$${\displaystyle \kappa _{2}(A)=10^{6}}$${\displaystyle \kappa (A)}$

ถ้ามีขนาดใหญ่ มักใช้ การปรับสภาพเบื้องต้นเพื่อแทนที่ระบบเดิมด้วยระบบที่มีขนาดเล็กกว่า ดังรายละเอียดด้านล่าง ${\displaystyle \kappa (A)}$${\displaystyle \mathbf {Ax} -\mathbf {b} =0}$${\displaystyle \mathbf {M} ^{-1}(\mathbf {Ax} -\mathbf {b} )=0}$${\displaystyle \kappa (\mathbf {M} ^{-1}\mathbf {A} )}$${\displaystyle \kappa (\mathbf {A} )}$

กำหนดให้เซตย่อยของพหุนามเป็นดังนี้

${\displaystyle \Pi _{k}^{*}:=\left\lbrace \ p\in \Pi _{k}\ :\ p(0)=1\ \right\rbrace \,,}$

โดยที่คือเซตของพหุนามที่มีดีกรีสูงสุด ${\displaystyle \Pi _{k}}$${\displaystyle k}$

ให้เป็นการประมาณค่าแบบวนซ้ำของคำตอบที่แน่นอนและกำหนดข้อผิดพลาดเป็นตอนนี้ อัตราการล convergence สามารถประมาณได้เป็น^{[ 4 ] [ 11 ]}${\displaystyle \left(\mathbf {x} _{k}\right)_{k}}$${\displaystyle \mathbf {x} _{*}}$${\displaystyle \mathbf {e} _{k}:=\mathbf {x} _{k}-\mathbf {x} _{*}}$

${\displaystyle {\begin{aligned}\left\|\mathbf {e} _{k}\right\|_{\mathbf {A} }&=\min _{p\in \Pi _{k}^{*}}\left\|p(\mathbf {A} )\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq \min _{p\in \Pi _{k}^{*}}\,\max _{\lambda \in \sigma (\mathbf {A} )}|p(\lambda )|\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq 2\left({\frac {{\sqrt {\kappa (\mathbf {A} )}}-1}{{\sqrt {\kappa (\mathbf {A} )}}+1}}\right)^{k}\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq 2\exp \left({\frac {-2k}{\sqrt {\kappa (\mathbf {A} )}}}\right)\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\,,\end{aligned}}}$

โดยที่แทนสเปกตรัมและแทนค่า สภาพ${\displaystyle \sigma (\mathbf {A} )}$${\displaystyle \kappa (\mathbf {A} )}$

สิ่งนี้แสดงให้เห็นว่าการวนซ้ำเพียงพอที่จะลดข้อผิดพลาดลงเหลือสำหรับทุกค่า ${\displaystyle k={\tfrac {1}{2}}{\sqrt {\kappa (\mathbf {A} )}}\log \left(\left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\varepsilon ^{-1}\right)}$${\displaystyle 2\varepsilon }$${\displaystyle \varepsilon >0}$

โปรดทราบว่า ขีดจำกัดที่สำคัญเมื่อมีแนวโน้มไปทาง${\displaystyle \kappa (\mathbf {A} )}$${\displaystyle \infty }$

${\displaystyle {\frac {{\sqrt {\kappa (\mathbf {A} )}}-1}{{\sqrt {\kappa (\mathbf {A} )}}+1}}\approx 1-{\frac {2}{\sqrt {\kappa (\mathbf {A} )}}}\quad {\text{for}}\quad \kappa (\mathbf {A} )\gg 1\,.}$

ขีดจำกัดนี้แสดงให้เห็นอัตราการล convergence ที่เร็วกว่าเมื่อเปรียบเทียบกับวิธีการวนซ้ำของJacobiหรือGauss–Seidelซึ่งมีขนาดตาม ${\displaystyle \approx 1-{\frac {2}{\kappa (\mathbf {A} )}}}$

ไม่มีการสันนิษฐานข้อผิดพลาดจากการปัดเศษในทฤษฎีบทการลู่เข้า แต่ขอบเขตการลู่เข้ามักจะใช้ได้ในทางปฏิบัติ ดังที่ Anne Greenbaumได้ อธิบาย ไว้ในเชิงทฤษฎี ^{[ 5 ]}

หากเริ่มต้นแบบสุ่ม ขั้นตอนการวนซ้ำครั้งแรกมักจะเร็วที่สุด เนื่องจากข้อผิดพลาดจะถูกกำจัดภายในพื้นที่ย่อย Krylov ซึ่งในตอนแรกสะท้อนถึงหมายเลขเงื่อนไขที่มีประสิทธิภาพที่เล็กกว่า ขั้นตอนการบรรจบกันครั้งที่สองมักจะถูกกำหนดไว้อย่างดีโดยขอบเขตการบรรจบกันทางทฤษฎีด้วยแต่อาจเป็นแบบเกินเชิงเส้น ขึ้นอยู่กับการกระจายของสเปกตรัมของเมทริกซ์และการกระจายสเปกตรัมของข้อผิดพลาด^{[ 5 ]}ในขั้นตอนสุดท้าย ความแม่นยำที่น้อยที่สุดที่สามารถทำได้จะถึง และการบรรจบกันจะหยุดชะงักหรือวิธีการอาจเริ่มเบี่ยงเบน ในแอปพลิเคชันการคำนวณทางวิทยาศาสตร์ทั่วไปในรูปแบบจุดลอยตัวความแม่นยำสองเท่าสำหรับเมทริกซ์ขนาดใหญ่ วิธีการไล่ระดับแบบสังยุคจะใช้เกณฑ์การหยุดที่มีค่าความคลาดเคลื่อนที่ยุติการวนซ้ำในระหว่างขั้นตอนแรกหรือขั้นตอนที่สอง ${\textstyle {\sqrt {\kappa (\mathbf {A} )}}}$${\displaystyle A}$

ในกรณีส่วนใหญ่การปรับสภาพเบื้องต้นเป็นสิ่งจำเป็นเพื่อให้แน่ใจว่าการบรรจบกันอย่างรวดเร็วของวิธีการไล่ระดับคอนจูเกต หากเป็นเมทริกซ์สมมาตรบวกแน่นอนและมีค่าสภาพที่ดีกว่าสามารถใช้วิธีการไล่ระดับคอนจูเกตแบบปรับสภาพเบื้องต้นได้ โดยมีรูปแบบดังต่อไปนี้: ^{[ 12 ]}${\displaystyle \mathbf {M} ^{-1}}$${\displaystyle \mathbf {M} ^{-1}\mathbf {A} }$${\displaystyle \mathbf {A} ,}$

${\displaystyle \mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}}$

${\displaystyle {\textrm {Solve:}}\mathbf {M} \mathbf {z} _{0}:=\mathbf {r} _{0}}$

${\displaystyle \mathbf {p} _{0}:=\mathbf {z} _{0}}$

${\displaystyle k:=0\,}$

ทำซ้ำ

${\displaystyle \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}}$

${\displaystyle \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}$

${\displaystyle \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}}$

ถ้าr _{k +1}มีค่าเล็กพอให้ออกจากลูปจบเงื่อนไข

${\displaystyle \mathrm {Solve} \ \mathbf {M} \mathbf {z} _{k+1}:=\mathbf {r} _{k+1}}$

${\displaystyle \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}}$

${\displaystyle \mathbf {p} _{k+1}:=\mathbf {z} _{k+1}+\beta _{k}\mathbf {p} _{k}}$

${\displaystyle k:=k+1\,}$

จบการทำซ้ำ

ผลลัพธ์คือx _{k +1}

สูตรข้างต้นเทียบเท่ากับการใช้วิธีการไล่ระดับคอนจูเกตปกติกับระบบที่ปรับสภาพไว้ล่วงหน้า^{[ 13 ]}

${\displaystyle \mathbf {E} ^{-1}\mathbf {A} (\mathbf {E} ^{-1})^{\mathsf {T}}\mathbf {\hat {x}} =\mathbf {E} ^{-1}\mathbf {b} }$

ที่ไหน

${\displaystyle \mathbf {EE} ^{\mathsf {T}}=\mathbf {M} ,\qquad \mathbf {\hat {x}} =\mathbf {E} ^{\mathsf {T}}\mathbf {x} .}$

การแยกส่วนแบบ Cholesky ของตัวปรับสภาพเบื้องต้นจะต้องใช้เพื่อรักษาความสมมาตร (และความเป็นบวกแน่นอน) ของระบบ อย่างไรก็ตาม ไม่จำเป็นต้องคำนวณการแยกส่วนนี้ และเพียงพอที่จะทราบค่าก็สามารถแสดงได้ว่ามีสเปกตรัมเดียวกันกับ ${\displaystyle \mathbf {M} ^{-1}}$${\displaystyle \mathbf {E} ^{-1}\mathbf {A} (\mathbf {E} ^{-1})^{\mathsf {T}}}$${\displaystyle \mathbf {M} ^{-1}\mathbf {A} }$

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

ตัวอย่างของพรีคอนดิชันเนอร์ ที่ใช้กันทั่วไป คือการแยกตัวประกอบ Cholesky ที่ไม่สมบูรณ์^{[ 14 ]}

สิ่งสำคัญที่ควรจำไว้คือ เราไม่ต้องการหาเมทริกซ์ผกผันโดยตรงเพื่อนำมาใช้ในกระบวนการ เนื่องจากกระบวนการหา เมทริกซ์ผกผัน จะใช้เวลา/ทรัพยากรการคำนวณมากกว่าการแก้ปัญหาด้วยอัลกอริธึมการไล่ระดับแบบสังยุคเสียอีก ยกตัวอย่างเช่น สมมติว่าเราใช้ตัวปรับสภาพที่ได้จากการแยกตัวประกอบ Cholesky ที่ไม่สมบูรณ์ เมทริกซ์ที่ได้จะเป็นเมทริกซ์สามเหลี่ยมล่างและเมทริกซ์ตัวปรับสภาพคือ: ${\displaystyle \mathbf {M} }$${\displaystyle \mathbf {M} ^{-1}}$${\displaystyle \mathbf {M} }$${\displaystyle \mathbf {L} }$

${\displaystyle \mathbf {M} =\mathbf {LL} ^{\mathsf {T}}}$

จากนั้นเราต้องหาคำตอบว่า:

${\displaystyle \mathbf {Mz} =\mathbf {r} }$

${\displaystyle \mathbf {z} =\mathbf {M} ^{-1}\mathbf {r} }$

แต่:

${\displaystyle \mathbf {M} ^{-1}=(\mathbf {L} ^{-1})^{\mathsf {T}}\mathbf {L} ^{-1}}$

แล้ว:

${\displaystyle \mathbf {z} =(\mathbf {L} ^{-1})^{\mathsf {T}}\mathbf {L} ^{-1}\mathbf {r} }$

ลองใช้เวกเตอร์ตัวกลางดู: ${\displaystyle \mathbf {a} }$

${\displaystyle \mathbf {a} =\mathbf {L} ^{-1}\mathbf {r} }$

${\displaystyle \mathbf {r} =\mathbf {L} \mathbf {a} }$

เนื่องจากและเป็นที่ทราบแล้ว และเป็นเมทริกซ์สามเหลี่ยมล่าง การหาค่า จึงทำได้ง่ายและประหยัดการคำนวณโดยใช้การแทนค่าไปข้างหน้าจากนั้น เราแทนค่าลงในสมการเดิม: ${\displaystyle \mathbf {r} }$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {a} }$

${\displaystyle \mathbf {z} =(\mathbf {L} ^{-1})^{\mathsf {T}}\mathbf {a} }$

${\displaystyle \mathbf {a} =\mathbf {L} ^{\mathsf {T}}\mathbf {z} }$

เนื่องจากทราบค่าและ แล้ว และ เป็นเมทริกซ์สามเหลี่ยมบน การแก้หา จึงทำได้ง่ายและประหยัดต้นทุนในการคำนวณโดยใช้การแทนค่าแบบย้อนกลับ ${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {L} ^{\mathsf {T}}}$${\displaystyle \mathbf {L} ^{\mathsf {T}}}$${\displaystyle \mathbf {z} }$

เมื่อใช้วิธีนี้ ไม่จำเป็นต้องกลับด้านหรือระบุอย่างชัดเจนเลย และเราก็ยังคงได้ผลลัพธ์เช่นเดิม ${\displaystyle \mathbf {M} }$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {z} }$

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

${\displaystyle \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\left(\mathbf {z} _{k+1}-\mathbf {z} _{k}\right)}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}}$

แทนที่จะใช้สูตร Fletcher–Reeves

${\displaystyle \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}}$

อาจปรับปรุงการบรรจบกันอย่างมากในกรณีนี้^{[ 15 ]}เวอร์ชันของวิธีการไล่ระดับคอนจูเกตแบบปรับสภาพล่วงหน้านี้สามารถเรียกว่า^{[ 16 ]}ยืดหยุ่นได้เนื่องจากอนุญาตให้มีการปรับสภาพล่วงหน้าแบบแปรผันได้ เวอร์ชันที่ยืดหยุ่นยังแสดงให้เห็น^{[ 17 ]}ว่ามีความแข็งแกร่งแม้ว่าตัวปรับสภาพล่วงหน้าจะไม่สมมาตรบวกแน่นอน (SPD)

การใช้งานเวอร์ชันที่ยืดหยุ่นจำเป็นต้องจัดเก็บเวกเตอร์เพิ่มเติม สำหรับตัวปรับสภาพ SPD ที่กำหนดไว้ดังนั้นสูตรทั้งสองสำหรับβ _kจึงเทียบเท่ากันในทางคณิตศาสตร์ที่แม่นยำ กล่าวคือ โดยไม่มี ข้อผิดพลาดจาก การ ปัดเศษ${\displaystyle \mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k}=0,}$

คำอธิบายทางคณิตศาสตร์ของพฤติกรรมการบรรจบกันที่ดีกว่าของวิธีการด้วย สูตร Polak–Ribièreคือวิธีการนี้เหมาะสมที่สุดในระดับท้องถิ่นในกรณีนี้ โดยเฉพาะอย่างยิ่ง มันไม่ได้บรรจบกันช้ากว่าวิธีการลดความชันที่เหมาะสมที่สุดในระดับท้องถิ่น^{[ 18 ]}

ทั้งวิธีการไล่ระดับคอนจูเกตแบบดั้งเดิมและแบบปรับสภาพล่วงหน้า จำเป็นต้องกำหนดค่า เพื่อให้ได้ค่าที่เหมาะสมที่สุดในระดับท้องถิ่น โดยใช้การค้นหาเส้นตรงและ วิธี การลดระดับความชันสูงสุดด้วยการแทนที่นี้ เวกเตอร์pจะเหมือนกับเวกเตอร์z เสมอ ดังนั้นจึงไม่จำเป็นต้องจัดเก็บเวกเตอร์pด้วยเหตุนี้ การวนซ้ำแต่ละครั้งของ วิธีการ ลดระดับความชันสูงสุด เหล่านี้จึงประหยัดกว่าเล็กน้อยเมื่อเทียบกับวิธีการไล่ระดับคอนจูเกต อย่างไรก็ตาม วิธีการหลังจะลู่เข้าได้เร็วกว่า เว้นแต่จะใช้ ตัวปรับสภาพล่วงหน้าที่แปรผันได้ (สูง) และ/หรือไม่ใช่ SPD ดังที่กล่าวไว้ข้างต้น ${\displaystyle \beta _{k}:=0}$

วิธีการไล่ระดับคอนจูเกตยังสามารถหาได้โดยใช้ทฤษฎีการควบคุมที่เหมาะสม [ ^{19 ] ใน}แนวทางนี้ วิธีการไล่ระดับคอนจูเกตจะกลายเป็นตัวควบคุมป้อนกลับที่เหมาะสมที่สุดสำหรับระบบอินทิเกรเตอร์คู่โดยที่ปริมาณและเป็นค่าเกนป้อนกลับที่แปรผันได้^{[ 19 ]}$${\displaystyle u=k(x,v):=-\gamma _{a}\nabla f(x)-\gamma _{b}v}$$$${\displaystyle {\dot {x}}=v,\quad {\dot {v}}=u}$$${\displaystyle \gamma _{a}}$${\displaystyle \gamma _{b}}$

วิธีการไล่ระดับเชิงสังยุค (Conjugate Gradient) สามารถนำไปใช้กับ เมทริกซ์ n x m ใดๆ ได้ โดยการนำไปใช้กับสมการปกติA ^T Aและเวกเตอร์ด้านขวาA ^T bเนื่องจาก A ^T Aเป็นเมทริกซ์สมมาตรบวกกึ่งกำหนด (Symmetric Positive Semidefinite Matrix) สำหรับA ใดๆ ผลลัพธ์ที่ได้คือการไล่ระดับเชิงสังยุคบนสมการปกติ ( CGNหรือCGNR )

A ^T Ax = A ^T b

เนื่องจากเป็นวิธีการวนซ้ำ จึงไม่จำเป็นต้องสร้าง A ^T Aอย่างชัดเจนในหน่วยความจำ แต่เพียงแค่ทำการคูณเมทริกซ์กับเวกเตอร์และการคูณเมทริกซ์สลับแถวกับเวกเตอร์เท่านั้น ดังนั้น CGNR จึงมีประโยชน์อย่างยิ่งเมื่อAเป็นเมทริกซ์แบบสปาร์สเนื่องจากโดยปกติแล้วการดำเนินการเหล่านี้มีประสิทธิภาพสูงมาก อย่างไรก็ตาม ข้อเสียของการสร้างสมการปกติคือค่าสภาพ κ( A ^T A ) เท่ากับ κ ² ( A ) ดังนั้นอัตราการล convergence ของ CGNR อาจช้า และคุณภาพของคำตอบโดยประมาณอาจไวต่อข้อผิดพลาดจากการปัดเศษ การหาตัวปรับสภาพ ที่ดี มักเป็นส่วนสำคัญของการใช้วิธี CGNR

มีการเสนออัลกอริทึมหลายแบบ (เช่น CGLS, LSQR) โดยกล่าวกันว่าอัลกอริทึม LSQRมีเสถียรภาพเชิงตัวเลขที่ดีที่สุดเมื่อA มีสภาพไม่ดี กล่าว คือA มี ค่าสภาพสูง

วิธีการไล่ระดับเชิงสังยุค (conjugate gradient method) ที่มีการดัดแปลงเล็กน้อย สามารถขยายไปใช้ในการแก้ระบบสมการเชิงเส้นสำหรับเวกเตอร์เชิงซ้อน x ได้ โดยที่ A เป็น เมทริกซ์เฮอร์ มิเชียน (กล่าวคือ A' = A) และ เป็นเมทริกซ์บวกกำหนด (positive-definite matrix ) และสัญลักษณ์ ' แทนการสลับตำแหน่งเชิงสังยุค (conjugate transpose ) การดัดแปลงเล็กน้อยนี้ทำได้ง่ายๆ โดยการแทนที่การสลับตำแหน่งจริง (real transpose) ด้วยค่าการสลับตำแหน่ง เชิงสัง ยุคทุกที่ ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

ข้อดีและข้อเสียของวิธีการไล่ระดับคอนจูเกตได้รับการสรุปไว้ในบันทึกการบรรยายโดย Nemirovsky และ BenTal ^{[ 20 ] : Sec.7.3}

ตัวอย่างนี้มาจาก^{[ 21 ]} ให้และกำหนดเนื่องจากสามารถผกผันได้ จึงมีคำตอบเฉพาะสำหรับการแก้ปัญหาโดยใช้การไล่ระดับแบบคอนจูเกตทำให้การลู่เข้าค่อนข้างแย่กล่าวคือ ในระหว่างกระบวนการ CG ข้อผิดพลาดจะเพิ่มขึ้นแบบเลขชี้กำลัง จนกระทั่งกลายเป็นศูนย์อย่างกะทันหันเมื่อพบคำตอบเฉพาะ ${\textstyle t\in (0,1)}$$${\displaystyle W={\begin{bmatrix}t&{\sqrt {t}}&&&&\\{\sqrt {t}}&1+t&{\sqrt {t}}&&&\\&{\sqrt {t}}&1+t&{\sqrt {t}}&&\\&&{\sqrt {t}}&\ddots &\ddots &\\&&&\ddots &&\\&&&&&{\sqrt {t}}\\&&&&{\sqrt {t}}&1+t\end{bmatrix}},\quad b={\begin{bmatrix}1\\0\\\vdots \\0\end{bmatrix}}}$$${\displaystyle W}$${\textstyle Wx=b}$$${\displaystyle \|b-Wx_{k}\|^{2}=(1/t)^{k},\quad \|b-Wx_{n}\|^{2}=0}$$