ในทางคณิตศาสตร์ โดยเฉพาะอย่างยิ่งในพีชคณิตเชิงเส้นเชิง ตัวเลขวิธีการไล่ระดับแบบไบคอนจูเกต (Biconjugate Gradient Method) เป็นอัลกอริทึม สำหรับแก้ระบบสมการเชิงเส้น
เอ x = ข . {\displaystyle Ax=b.\,} แตกต่างจากวิธีการไล่ระดับเชิงสังยุค อัลก อริทึมนี้ไม่จำเป็นต้องใช้เมทริกซ์สมมาตร ในตัวเอง แต่ต้องทำการคูณด้วยเมทริกซ์สลับตำแหน่งเชิงสังยุค A * เอ {\displaystyle A}
อัลกอริทึม เลือกค่าเดาเริ่มต้นเวกเตอร์อีกสองตัวและตัวปรับสภาพเบื้องต้น x 0 {\displaystyle x_{0}\,} x 0 * {\displaystyle x_{0}^{*}} ข * {\displaystyle b^{*}\,} M {\displaystyle M\,} r 0 ← b − A x 0 {\displaystyle r_{0}\leftarrow b-A\,x_{0}\,} r 0 ∗ ← b ∗ − x 0 ∗ A ∗ {\displaystyle r_{0}^{*}\leftarrow b^{*}-x_{0}^{*}\,A^{*}} p 0 ← M − 1 r 0 {\displaystyle p_{0}\leftarrow M^{-1}r_{0}\,} p 0 ∗ ← r 0 ∗ M − 1 {\displaystyle p_{0}^{*}\leftarrow r_{0}^{*}M^{-1}\,} เพื่อทำ k = 0 , 1 , … {\displaystyle k=0,1,\ldots } α k ← r k ∗ M − 1 r k p k ∗ A p k {\displaystyle \alpha _{k}\leftarrow {r_{k}^{*}M^{-1}r_{k} \over p_{k}^{*}Ap_{k}}\,} x k + 1 ← x k + α k ⋅ p k {\displaystyle x_{k+1}\leftarrow x_{k}+\alpha _{k}\cdot p_{k}\,} x k + 1 ∗ ← x k ∗ + α k ¯ ⋅ p k ∗ {\displaystyle x_{k+1}^{*}\leftarrow x_{k}^{*}+{\overline {\alpha _{k}}}\cdot p_{k}^{*}\,} r k + 1 ← r k − α k ⋅ A p k {\displaystyle r_{k+1}\leftarrow r_{k}-\alpha _{k}\cdot Ap_{k}\,} r k + 1 ∗ ← r k ∗ − α k ¯ ⋅ p k ∗ A ∗ {\displaystyle r_{k+1}^{*}\leftarrow r_{k}^{*}-{\overline {\alpha _{k}}}\cdot p_{k}^{*}\,A^{*}} β k ← r k + 1 ∗ M − 1 r k + 1 r k ∗ M − 1 r k {\displaystyle \beta _{k}\leftarrow {r_{k+1}^{*}M^{-1}r_{k+1} \over r_{k}^{*}M^{-1}r_{k}}\,} p k + 1 ← M − 1 r k + 1 + β k ⋅ p k {\displaystyle p_{k+1}\leftarrow M^{-1}r_{k+1}+\beta _{k}\cdot p_{k}\,} p k + 1 ∗ ← r k + 1 ∗ M − 1 + β k ¯ ⋅ p k ∗ {\displaystyle p_{k+1}^{*}\leftarrow r_{k+1}^{*}M^{-1}+{\overline {\beta _{k}}}\cdot p_{k}^{*}\,} ในสูตรข้างต้น ค่าที่คำนวณได้และตรงตามเงื่อนไข r k {\displaystyle r_{k}\,} r k ∗ {\displaystyle r_{k}^{*}}
r k = b − A x k , {\displaystyle r_{k}=b-Ax_{k},\,} r k ∗ = b ∗ − x k ∗ A ∗ {\displaystyle r_{k}^{*}=b^{*}-x_{k}^{*}\,A^{*}} และด้วยเหตุนี้ค่าตกค้าง ที่สอดคล้องกับและจึงเป็นคำตอบโดยประมาณของระบบสมการ x k {\displaystyle x_{k}\,} x k ∗ {\displaystyle x_{k}^{*}}
A x = b , {\displaystyle Ax=b,\,} x ∗ A ∗ = b ∗ ; {\displaystyle x^{*}\,A^{*}=b^{*}\,;} x ∗ {\displaystyle x^{*}} ผกผันร่วม และคือตัวผกผัน เชิงซ้อน α ¯ {\displaystyle {\overline {\alpha }}}
เวอร์ชันของอัลกอริธึมที่ไม่ได้รับการปรับสภาพล่วงหน้า เลือกค่าประมาณเริ่มต้นx 0 {\displaystyle x_{0}\,} r 0 ← b − A x 0 {\displaystyle r_{0}\leftarrow b-A\,x_{0}\,} r ^ 0 ← b ^ − x ^ 0 A ∗ {\displaystyle {\hat {r}}_{0}\leftarrow {\hat {b}}-{\hat {x}}_{0}A^{*}} p 0 ← r 0 {\displaystyle p_{0}\leftarrow r_{0}\,} p ^ 0 ← r ^ 0 {\displaystyle {\hat {p}}_{0}\leftarrow {\hat {r}}_{0}\,} เพื่อทำ k = 0 , 1 , … {\displaystyle k=0,1,\ldots } α k ← r ^ k r k p ^ k A p k {\displaystyle \alpha _{k}\leftarrow {{\hat {r}}_{k}r_{k} \over {\hat {p}}_{k}Ap_{k}}\,} x k + 1 ← x k + α k ⋅ p k {\displaystyle x_{k+1}\leftarrow x_{k}+\alpha _{k}\cdot p_{k}\,} x ^ k + 1 ← x ^ k + α k ⋅ p ^ k {\displaystyle {\hat {x}}_{k+1}\leftarrow {\hat {x}}_{k}+\alpha _{k}\cdot {\hat {p}}_{k}\,} r k + 1 ← r k − α k ⋅ A p k {\displaystyle r_{k+1}\leftarrow r_{k}-\alpha _{k}\cdot Ap_{k}\,} r ^ k + 1 ← r ^ k − α k ⋅ p ^ k A ∗ {\displaystyle {\hat {r}}_{k+1}\leftarrow {\hat {r}}_{k}-\alpha _{k}\cdot {\hat {p}}_{k}A^{*}} β k ← r ^ k + 1 r k + 1 r ^ k r k {\displaystyle \beta _{k}\leftarrow {{\hat {r}}_{k+1}r_{k+1} \over {\hat {r}}_{k}r_{k}}\,} p k + 1 ← r k + 1 + β k ⋅ p k {\displaystyle p_{k+1}\leftarrow r_{k+1}+\beta _{k}\cdot p_{k}\,} p ^ k + 1 ← r ^ k + 1 + β k ⋅ p ^ k {\displaystyle {\hat {p}}_{k+1}\leftarrow {\hat {r}}_{k+1}+\beta _{k}\cdot {\hat {p}}_{k}\,}
การอภิปราย วิธีการไล่ระดับแบบไบคอนจูเกตนั้นไม่เสถียรในเชิงตัวเลข (เมื่อเทียบกับวิธีการไล่ระดับแบบไบคอนจูเกตที่เสถียรแล้ว ) แต่มีความสำคัญมากในเชิงทฤษฎี กำหนดขั้นตอนการวนซ้ำโดย
x k := x j + P k A − 1 ( b − A x j ) , {\displaystyle x_{k}:=x_{j}+P_{k}A^{-1}\left(b-Ax_{j}\right),} x k ∗ := x j ∗ + ( b ∗ − x j ∗ A ) P k A − 1 , {\displaystyle x_{k}^{*}:=x_{j}^{*}+\left(b^{*}-x_{j}^{*}A\right)P_{k}A^{-1},} โดยใช้การฉายภาพ ที่เกี่ยวข้อง j < k {\displaystyle j<k}
P k := u k ( v k ∗ A u k ) − 1 v k ∗ A , {\displaystyle P_{k}:=\mathbf {u} _{k}\left(\mathbf {v} _{k}^{*}A\mathbf {u} _{k}\right)^{-1}\mathbf {v} _{k}^{*}A,} กับ
u k = [ u 0 , u 1 , … , u k − 1 ] , {\displaystyle \mathbf {u} _{k}=\left[u_{0},u_{1},\dots ,u_{k-1}\right],} v k = [ v 0 , v 1 , … , v k − 1 ] . {\displaystyle \mathbf {v} _{k}=\left[v_{0},v_{1},\dots ,v_{k-1}\right].} การคาดการณ์ที่เกี่ยวข้องเหล่านี้สามารถทำซ้ำได้ดังนี้
P k + 1 = P k + ( 1 − P k ) u k ⊗ v k ∗ A ( 1 − P k ) v k ∗ A ( 1 − P k ) u k . {\displaystyle P_{k+1}=P_{k}+\left(1-P_{k}\right)u_{k}\otimes {v_{k}^{*}A\left(1-P_{k}\right) \over v_{k}^{*}A\left(1-P_{k}\right)u_{k}}.} ความสัมพันธ์กับวิธีการควาซี-นิวตัน แสดงโดยและโดยที่ P k = A k − 1 A {\displaystyle P_{k}=A_{k}^{-1}A} x k + 1 = x k − A k + 1 − 1 ( A x k − b ) {\displaystyle x_{k+1}=x_{k}-A_{k+1}^{-1}\left(Ax_{k}-b\right)}
A k + 1 − 1 = A k − 1 + ( 1 − A k − 1 A ) u k ⊗ v k ∗ ( 1 − A A k − 1 ) v k ∗ A ( 1 − A k − 1 A ) u k . {\displaystyle A_{k+1}^{-1}=A_{k}^{-1}+\left(1-A_{k}^{-1}A\right)u_{k}\otimes {v_{k}^{*}\left(1-AA_{k}^{-1}\right) \over v_{k}^{*}A\left(1-A_{k}^{-1}A\right)u_{k}}.} ทิศทางใหม่
p k = ( 1 − P k ) u k , {\displaystyle p_{k}=\left(1-P_{k}\right)u_{k},} p k ∗ = v k ∗ A ( 1 − P k ) A − 1 {\displaystyle p_{k}^{*}=v_{k}^{*}A\left(1-P_{k}\right)A^{-1}} จากนั้นจะตั้งฉากกับส่วนที่เหลือ:
v i ∗ r k = p i ∗ r k = 0 , {\displaystyle v_{i}^{*}r_{k}=p_{i}^{*}r_{k}=0,} r k ∗ u j = r k ∗ p j = 0 , {\displaystyle r_{k}^{*}u_{j}=r_{k}^{*}p_{j}=0,} ซึ่งตัวมันเองก็เป็นที่น่าพอใจ
r k = A ( 1 − P k ) A − 1 r j , {\displaystyle r_{k}=A\left(1-P_{k}\right)A^{-1}r_{j},} r k ∗ = r j ∗ ( 1 − P k ) {\displaystyle r_{k}^{*}=r_{j}^{*}\left(1-P_{k}\right)} ที่ไหน. i , j < k {\displaystyle i,j<k}
วิธีการไล่ระดับแบบไบคอนจูเกตในปัจจุบันได้ทำการเลือกพิเศษและใช้การตั้งค่านี้
u k = M − 1 r k , {\displaystyle u_{k}=M^{-1}r_{k},\,} v k ∗ = r k ∗ M − 1 . {\displaystyle v_{k}^{*}=r_{k}^{*}\,M^{-1}.\,} ด้วยตัวเลือกนี้ การประเมินค่า A −1 อย่างชัดเจนจะถูก หลีก P k {\displaystyle P_{k}}
คุณสมบัติ ถ้าเมท ริกซ์ สมมาตรในตัวเอง และแล้วและวิธีการไล่ระดับเชิงสังยุค จะสร้างลำดับเดียวกัน โดย ใช้ต้นทุนการคำนวณน้อยลงครึ่งหนึ่งA = A ∗ {\displaystyle A=A^{*}\,} x 0 ∗ = x 0 {\displaystyle x_{0}^{*}=x_{0}} b ∗ = b {\displaystyle b^{*}=b} r k = r k ∗ {\displaystyle r_{k}=r_{k}^{*}} p k = p k ∗ {\displaystyle p_{k}=p_{k}^{*}} x k = x k ∗ {\displaystyle x_{k}=x_{k}^{*}} ลำดับที่ได้จากอัลกอริทึมเป็นลำดับแบบไบออร์โทกอนอล กล่าวคือสำหรับp i ∗ A p j = r i ∗ M − 1 r j = 0 {\displaystyle p_{i}^{*}Ap_{j}=r_{i}^{*}M^{-1}r_{j}=0} i ≠ j {\displaystyle i\neq j} ถ้าเป็นพหุนามที่มีแล้ว. ดังนั้นอัลกอริทึมจึงสร้างการฉายภาพลงบนปริภูมิย่อยครีลอ ฟP j ′ {\displaystyle P_{j'}\,} deg ( P j ′ ) + j < k {\displaystyle \deg \left(P_{j'}\right)+j<k} r k ∗ P j ′ ( M − 1 A ) u j = 0 {\displaystyle r_{k}^{*}P_{j'}\left(M^{-1}A\right)u_{j}=0} ถ้าเป็นพหุนามที่มีแล้วP i ′ {\displaystyle P_{i'}\,} i + deg ( P i ′ ) < k {\displaystyle i+\deg \left(P_{i'}\right)<k} v i ∗ P i ′ ( A M − 1 ) r k = 0 {\displaystyle v_{i}^{*}P_{i'}\left(AM^{-1}\right)r_{k}=0}
ดูเพิ่มเติม 
![{\displaystyle \mathbf {u} _{k}=\left[u_{0},u_{1},\dots ,u_{k-1}\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/356e9dd32012d4b25f4a3c78179554570098e78e)
![{\displaystyle \mathbf {v} _{k}=\left[v_{0},v_{1},\dots ,v_{k-1}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f9338d3797abffd4007c6c2ab27aaed7e04e893)
