อัลกอริทึม Krylov แบบวนซ้ำเชิงตรรกะ (IRKA)เป็นอัลกอริทึมแบบวนซ้ำที่มีประโยชน์สำหรับการลดลำดับแบบจำลอง (MOR) ของระบบไดนามิกเชิงเส้นแบบคงที่เวลาอินพุตเดียวเอาต์พุตเดียว (SISO) ^{[ 1 ]}ในแต่ละรอบการวนซ้ำ IRKA จะทำการแทรกสอดแบบ Hermite ของฟังก์ชันถ่ายโอนระบบดั้งเดิม การแทรกสอดแต่ละครั้งต้องแก้คู่ของระบบเชิงเส้น ที่เลื่อนไป โดยแต่ละระบบมีขนาด; โดยที่คือลำดับของระบบดั้งเดิม และคือลำดับแบบจำลองที่ลดลงที่ต้องการ (โดยปกติคือ) ${\displaystyle r}$${\displaystyle n\times n}$${\displaystyle n}$${\displaystyle r}$${\displaystyle r\ll n}$

อัลกอริทึมนี้ได้รับการแนะนำครั้งแรกโดย Gugercin, Antoulas และ Beattie ในปี 2551 ^{[ 2 ]}โดยอิงจากเงื่อนไขความเหมาะสมที่จำเป็นอันดับแรก ซึ่งได้รับการศึกษาครั้งแรกโดย Meier และ Luenberger ในปี 2510 ^{[ 3 ]}การพิสูจน์การลู่เข้าครั้งแรกของ IRKA ได้รับการนำเสนอโดย Flagg, Beattie และ Gugercin ในปี 2555 ^{[ 4 ]}สำหรับระบบประเภทหนึ่งโดยเฉพาะ

พิจารณาระบบไดนามิกเชิงเส้นแบบ SISO ที่ไม่เปลี่ยนแปลงตามเวลา โดยมีอินพุตและเอาต์พุต ดังนี้: ${\displaystyle v(t)}$${\displaystyle y(t)}$

${\displaystyle {\begin{cases}{\dot {x}}(t)=Ax(t)+bv(t)\\y(t)=c^{T}x(t)\end{cases}}\qquad A\in \mathbb {R} ^{n\times n},\,b,c\in \mathbb {R} ^{n},\,v(t),y(t)\in \mathbb {R} ,\,x(t)\in \mathbb {R} ^{n}.}$

เมื่อใช้การแปลงลาปลาสโดยมีเงื่อนไขเริ่มต้นเป็นศูนย์ เราจะได้ฟังก์ชันถ่ายโอน ซึ่งเป็นเศษส่วนของพหุนาม: ${\displaystyle G}$

${\displaystyle G(s)=c^{T}(sI-A)^{-1}b,\quad A\in \mathbb {R} ^{n\times n},\,b,c\in \mathbb {R} ^{n}.}$

สมมติว่ามีเสถียรภาพ กำหนดให้MOR พยายามประมาณฟังก์ชันถ่ายโอนโดยใช้ฟังก์ชันถ่ายโอนเชิงตรรกะที่มีเสถียรภาพซึ่งมีอันดับ: ${\displaystyle G}$${\displaystyle r<n}$${\displaystyle G}$${\displaystyle G_{r}}$${\displaystyle r}$

${\displaystyle G_{r}(s)=c_{r}^{T}(sI_{r}-A_{r})^{-1}b_{r},\quad A_{r}\in \mathbb {R} ^{r\times r},\,b_{r},c_{r}\in \mathbb {R} ^{r}.}$

เกณฑ์การประมาณค่าที่เป็นไปได้คือการลดข้อผิดพลาดสัมบูรณ์ในค่ามาตรฐานให้เหลือน้อยที่สุด: ${\displaystyle H_{2}}$

${\displaystyle G_{r}\in {\underset {\dim({\hat {G}})=r,\,{\hat {G}}{\text{ stable}}}{\operatorname {arg\min } }}\|G-{\hat {G}}\|_{H_{2}},\quad \|G\|_{H_{2}}^{2}:={\frac {1}{2\pi }}\int \limits _{-\infty }^{\infty }|G(ja)|^{2}\,da.}$

ปัญหานี้เรียกว่า ปัญหา การหาค่าเหมาะสมที่สุดปัญหานี้ได้รับการศึกษาอย่างกว้างขวาง และเป็นที่ทราบกันว่าไม่ใช่ปัญหานูน^{[ 4 ]}ซึ่งหมายความว่าโดยปกติแล้วจะเป็นเรื่องยากที่จะหาค่าต่ำสุดทั่วโลก ${\displaystyle H_{2}}$

เงื่อนไขความเหมาะสมที่จำเป็นอันดับแรกต่อไปนี้สำหรับปัญหานี้มีความสำคัญอย่างยิ่งสำหรับอัลกอริทึม IRKA ${\displaystyle H_{2}}$

โปรดทราบว่าขั้วคือค่าลักษณะเฉพาะของเมทริกซ์ ลด รูป ${\displaystyle \lambda _{i}(A_{r})}$${\displaystyle r\times r}$${\displaystyle A_{r}}$

ตัวประมาณค่าแบบเฮอร์ไมต์ของฟังก์ชันตรรกยะที่ผ่านจุดต่างกันมีส่วนประกอบดังนี้: ${\displaystyle G_{r}}$${\displaystyle G}$${\displaystyle r}$${\displaystyle \sigma _{1},\ldots ,\sigma _{r}\in \mathbb {C} }$

${\displaystyle A_{r}=W_{r}^{*}AV_{r},\quad b_{r}=W_{r}^{*}b,\quad c_{r}=V_{r}^{*}c,\quad A_{r}\in \mathbb {R} ^{r\times r},\,b_{r}\in \mathbb {R} ^{r},\,c_{r}\in \mathbb {R} ^{r};}$

โดยที่เมทริกซ์และสามารถพบได้โดยการแก้ระบบเชิงเส้นคู่หนึ่งสำหรับแต่ละการเลื่อน^{[ 4 ]} [ทฤษฎีบท 1.1]: ${\displaystyle V_{r}=(v_{1}\mid \ldots \mid v_{r})\in \mathbb {C} ^{n\times r}}$${\displaystyle W_{r}=(w_{1}\mid \ldots \mid w_{r})\in \mathbb {C} ^{n\times r}}$${\displaystyle r}$

${\displaystyle (\sigma _{i}IA)v_{i}=b,\quad (\sigma _{i}IA)^{*}w_{i}=c,\quad \forall \,i=1,\ldots ,r.}$

ดังที่เห็นได้จากส่วนก่อนหน้า การหาตัวประมาณค่าแบบ Hermite ที่ผ่านจุดที่กำหนดนั้นค่อนข้างง่าย ส่วนที่ยากคือการหาจุดประมาณค่าที่ถูกต้อง IRKA พยายามประมาณค่าจุดประมาณค่า "ที่เหมาะสมที่สุด" เหล่านี้แบบวนซ้ำ ${\displaystyle G_{r}}$${\displaystyle G}$${\displaystyle r}$

ด้วยเหตุนี้ จึงเริ่มต้นด้วยจุดการแทรกสอดแบบสุ่ม (ซึ่งปิดภายใต้การแปลงแบบคอนจูเกชัน) จากนั้น ในแต่ละรอบการทำซ้ำจะกำหนดเงื่อนไขความเหมาะสมที่จำเป็นอันดับแรกของปัญหา: ${\displaystyle r}$${\displaystyle m}$${\displaystyle H_{2}}$

1. หาค่าประมาณแบบ Hermite ของ ที่ ผ่าน จุดเลื่อนจริง : . ${\displaystyle G_{r}}$${\displaystyle G}$${\displaystyle r}$${\displaystyle \sigma _{1}^{m},\ldots ,\sigma _{r}^{m}}$

2. อัปเดตค่าการเลื่อนโดยใช้ขั้วของค่าใหม่:${\displaystyle G_{r}}$${\displaystyle \sigma _{i}^{m+1}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r.}$

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

${\displaystyle {\frac {|\sigma _{i}^{m+1}-\sigma _{i}^{m}|}{|\sigma _{i}^{m}|}}<{\text{tol}},\,\forall \,i=1,\ldots ,r.}$

ดังที่ได้กล่าวไปแล้วการแทรกสอดแบบ Hermite แต่ละครั้ง จำเป็นต้องแก้ระบบสมการเชิงเส้นแบบคู่ที่มีการเลื่อน ซึ่งแต่ละระบบมีขนาดดังนี้: ${\displaystyle r}$${\displaystyle n\times n}$

${\displaystyle (\sigma _{i}^{m}IA)v_{i}=b,\quad (\sigma _{i}^{m}IA)^{*}w_{i}=c,\quad \forall \,i=1,\ldots ,r.}$

นอกจากนี้ การปรับปรุงค่าการเลื่อนยังต้องอาศัยการหาขั้วของค่าประมาณใหม่นั่นคือ การหาค่าลักษณะเฉพาะของเมทริกซ์ ลด รูป ${\displaystyle r}$${\displaystyle G_{r}}$${\displaystyle r}$${\displaystyle r\times r}$${\displaystyle A_{r}}$

ต่อไปนี้เป็นรหัสเทียมสำหรับอัลกอริทึม IRKA ^{[ 2 ]} [อัลกอริทึม 4.1]

อัลกอริ ทึม IRKA อินพุต: , , ปิดภายใต้การผัน  % แก้ระบบสมการเชิงซ้อนดั้งเดิม  % แก้ระบบสมการเชิงซ้อนคู่${\displaystyle A,b,c}$${\displaystyle {\text{tol}}>0}$${\displaystyle \sigma _{1},\ldots ,\sigma _{r}}$${\displaystyle (\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r}$${\displaystyle (\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r}$ในขณะที่การเปลี่ยนแปลงสัมพัทธ์ใน { } > tol  % เมทริกซ์ลำดับลด  % อัปเดตการเลื่อนโดยใช้ขั้วของ % แก้ระบบหลัก  % แก้ระบบคู่ สิ้นสุดในขณะที่${\displaystyle \sigma _{i}}$${\displaystyle A_{r}=W_{r}^{*}AV_{r}}$${\displaystyle \sigma _{i}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r}$${\displaystyle G_{r}}$${\displaystyle (\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r}$${\displaystyle (\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r}$ผลตอบแทน  % รูปแบบการสั่งซื้อที่ลดลง ${\displaystyle A_{r}=W_{r}^{*}AV_{r},\,b_{r}=W_{r}^{*}b,\,c_{r}^{T}=c^{T}V_{r}}$

กล่าวกันว่าระบบเชิงเส้น SISO มีปริภูมิสถานะสมมาตร (SSS) เมื่อใดก็ตามที่ระบบประเภทนี้ปรากฏในแอปพลิเคชันที่สำคัญหลายอย่าง เช่น ในการวิเคราะห์วงจร RC และในปัญหาผกผันที่เกี่ยวข้องกับสมการของแม็กซ์เวลล์ 3 มิติ ^{[ 4 ]}สำหรับระบบ SSS ที่มีขั้วที่แตกต่างกัน ผลลัพธ์การลู่เข้าต่อไปนี้ได้รับการพิสูจน์แล้ว: ^{[ 4 ]} "IRKA คือการวนซ้ำจุดคงที่ที่ลู่เข้าในระดับท้องถิ่นไปยังตัวลดค่าต่ำสุดในระดับท้องถิ่นของปัญหาการเพิ่มประสิทธิภาพ" ${\displaystyle A=A^{T},\,b=c.}$${\displaystyle H_{2}}$

แม้ว่าจะไม่มีการพิสูจน์การลู่เข้าสำหรับกรณีทั่วไป แต่การทดลองจำนวนมากแสดงให้เห็นว่า IRKA มักจะลู่เข้าอย่างรวดเร็วสำหรับระบบไดนามิกเชิงเส้นประเภทต่างๆ^{[ 1 ] [ 4 ]}

อัลกอริทึม IRKA ได้รับการขยายโดยผู้เขียนดั้งเดิมไปยัง ระบบ หลายอินพุตหลายเอาต์พุต (MIMO) และยังรวมถึงระบบเวลาไม่ต่อเนื่องและระบบพีชคณิตเชิงอนุพันธ์ด้วย^{[ 1 ] [ 2 ]} [หมายเหตุ 4.1]

การลดลำดับแบบจำลอง

• วิกิการลดลำดับโมเดล